Approximation Algorithms for Three-Machine Open Shop Scheduling

This paper shows that a greedy algorithm for three machine open shop scheduling with the objective to minimize the makespan provides schedules with the worst-case performance ratio 5/3. A linear time heuristic is presented which improves the schedules and reduces the ratio to 3/2.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.