Approximation Algorithms for Three-Machine Open Shop Scheduling

Published Online:https://doi.org/10.1287/ijoc.5.3.321

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.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.