Philippine E-Journals

A Heuristic for minimizing total weighted Tardiness in the Two-machine Flowshop problem when jobs have processing times MIN(P1) > MAX(P2)

Eric A. Siy

Discipline: Engineering, Technology

 

Abstract:

Minimizing the NP-hard problem of total weighted tardiness for the two machine flowshop(F2//WjTj) requires a computationally less difficult approach than complete enumeration. This paper presents a heuristic for the case of the two-machine flowshop where the largest processing times for all job in the 2nd machine (P2) js smaller than the minimum processing times the first (P1). In this case of the flowshop, all jobs are initially available for processing and have to be processed in the same sequence of machines; jobs also have associated due dates and weights. The heuristic performance is compared against the currently accepted Rachamadugu and Morton (1981) heuristic on numerical examples on 4-and 5 jobs flowshop with completely enumerated permutation schedules. It is shown that the presented heuristic would be able to find a sequence of jobs that surpasses the performance of R&M heuristic in finding the minimum total weighted tardiness.