A heuristic algorithm for two-machine re-entrant shop scheduling

This paper considers the problem of sequencing n jobs in a two-machine re-e ntrant shop with the objective of minimizing the maximum completion time. T he shop consists of two machines, M-1 and M-2 , and each job has the proces sing route (M-1 , M-2 , M-1 ). An O(n log n) time heuristic is presented wh ich generates a schedule with length at most 4/3 times that of an optimal s chedule, thereby improving the best previously available worst-case perform ance ratio of 3/2.