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

This paper considers the problem of sequencing n jobs in a two-machine re-entrant shop with the objective of minimizing the maximum completion time. The shop consists of two machines, M1 and M2, and each job has the processing route (M1, M2, M1). An O(n log n) time heuristic is presented which generates a schedule with length at most 4/3 times that of an optimal schedule, thereby improving the best previously available worst-case performance ratio of 3/2.