The single machine CON problem with unavailability period

Abstract

The classical CON problem focuses on scheduling jobs on a single machine sharing a common due-date. We study the CON problem with a given unavailability period. The basic problem (assuming linear job-independent costs and no idle times prior to or after the unavailability period) is easily shown to be NP-hard, and an efficient pseudo-polynomial dynamic programming algorithm is introduced. Extensions of the algorithm to general monotonic job-independent costs, and to linear job-dependent costs are studied as well. All algorithms are tested numerically, and are shown to produce optimal schedules in reasonable time. Then we allow idle times, verify that this case is NP-hard in the ordinary sense as well, and introduce a greedy-type heuristic. Numerical tests are performed, and the results indicate that the heuristic performs extremely well.

Keywords:

• Scheduling
• single machine
• dynamic programming
• heuristics
• unavailability period

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the ISRAEL SCIENCE FOUNDATION (grant number 2505/19). The second author was also supported by the Charles I. Rosen Chair of Management, and by The Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel.