Single-machine common due date total earliness/tardiness scheduling with machine unavailability

Kerem Bülbül (), Safia Kedad-Sidhoum () and Halil Şen ()
Additional contact information
Kerem Bülbül: Sabancı University
Safia Kedad-Sidhoum: Sorbonne Universités, Université Pierre et Marie Curie
Halil Şen: Inria Bordeaux - Sud-Ouest, Institut de Mathématiques de Bordeaux UMR 5251

Journal of Scheduling, 2019, vol. 22, issue 5, No 3, 543-565

Abstract: Abstract Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and $$\mathcal {NP}$$ NP -complete cases. Pseudo-polynomial dynamic programming algorithms are devised for $$\mathcal {NP}$$ NP -complete variants in the ordinary sense.

Keywords: Single-machine; Earliness/tardiness; Common due date; Unrestrictive; Machine unavailability; Maintenance; Resumable; Semi-resumable; Non-resumable; $$\mathcal {NP}$$ NP -complete; Dynamic programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0585-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:22:y:2019:i:5:d:10.1007_s10951-018-0585-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0585-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().