Partially concurrent open shop scheduling with integral preemptions

Hagai Ilani (), Elad Shufan () and Tal Grinshpoun ()
Additional contact information
Hagai Ilani: SCE – Shamoon College of Engineering
Elad Shufan: SCE – Shamoon College of Engineering
Tal Grinshpoun: Ariel University

Annals of Operations Research, 2017, vol. 259, issue 1, No 7, 157-171

Abstract: Abstract Partially-concurrent open shop scheduling (PCOSS) was recently introduced as a common generalization of the well-known open shop scheduling model and the concurrent open shop scheduling model. PCOSS was shown to be NP-hard even when there is only one machine and all operations have unit processing time. In the present paper we study PCOSS problems with integral processing times that allow preemptions at integral time points. A special and simple subclass of the problems at focus is that of unit processing times, which is considered separately. For these two cases a schedule is related to the colouring of a graph called the conflict graph, which represents the operations that cannot be performed concurrently. This enables us to extract insights and solutions from the well-studied field of graph colouring and apply them to the recently introduced PCOSS model. We then focus on two special cases of the problem—the case where the conflict graph is perfect, and the case of uniform PCOSS, in which all the jobs, including their conflicts, are identical. The development of the PCOSS model was motivated from a real-life timetabling project of assigning technicians to a fleet of airplanes. The latter case of uniform PCOSS correlates to instances in which the fleet of airplanes is homogeneous.

Keywords: Open shop scheduling; PCOSS; Integral processing times; Integral preemption; Graph colouring; Technician timetabling (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2503-6 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:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2503-6

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

DOI: 10.1007/s10479-017-2503-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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