Two-machine scheduling made efficient despite machine downtime
An FPTAS for Two-Machine Open-Shop Scheduling with a Single Unavailability Interval
Discrete Mathematics
Summary
Scheduling jobs between two machines can get tricky when one machine is unavailable for a certain period. The problem gets harder when interrupted tasks can resume later without penalty. The authors found a new way to closely approximate the shortest total time to complete all jobs, solving a question that remained unanswered for 20 years. They improved on previous methods by simplifying the problem’s complexity, making the scheduling approach more efficient and practical.
What this means in practice
- •For manufacturing schedulers: Schedule jobs on two machines efficiently when one machine has planned downtime to minimize overall production time.
- •For maintenance planners: Plan machine maintenance intervals without losing optimal scheduling efficiency for resumable production tasks.
Authors
Hao Lu, Yuan Yuan, Xingwu Liu, Xin Han, Yong Zhou
Abstract
We consider the two-machine open-shop scheduling problem in which one machine is unavailable during a fixed interval. We study the resumable setting: an operation interrupted by the unavailability interval may resume, without penalty, when the machine becomes available. The objective is to minimize the makespan. Although the problem is NP-hard and several approximation algorithms are known, whether it admits a fully polynomial-time approximation scheme (FPTAS) has remained open for two decades. We resolve this question affirmatively by giving the first FPTAS, thereby strengthening the previously known polynomial-time approximation scheme (PTAS). As an intermediate result, we develop a new pseudo-polynomial dynamic program with seven state dimensions, improving on the ten-dimensional formulation in the literature.