Approximation Algorithms for Three-Machine Open Shop Scheduling
ORSA Journal on Computing · 1993 · Volume 5 · Issue 3
Abstract
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.
Keywords
production/scheduling, approximation/heuristic
Enable JavaScript for citation tools and additional paper interactions.