The single machine CON problem with unavailability period

Enrique Gerstl and Gur Mosheiov

International Journal of Production Research, 2021, vol. 59, issue 3, 824-838

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.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2019.1709672 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:59:y:2021:i:3:p:824-838

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2019.1709672

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().