Approximation Algorithms for Three-Machine Open Shop Scheduling

What is it about?

This paper shows that a greedy algorithm for three-machine open-shop scheduling with the objective of minimizing the makespan provides a schedule of makespan at most 5/3 times of the optimal. A linear-time heuristic is presented that improves the schedule and reduces the ratio to 3/2.

Featured Image