Bounded colouring motivated by the limited resource partially concurrent open shop problem

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

Annals of Operations Research, 2021, vol. 302, issue 2, No 7, 476 pages

Abstract: Abstract Partially Concurrent Open Shop Scheduling (PCOSS) is a relaxation of the well-known Open Shop Scheduling (OSS), where some of the operations that refer to the same job may be processed concurrently. Here we extend the study of the PCOSS model by considering an additional resource, which is limited to several units. We deal with the case of preemption PCOSS, where a few polynomial algorithms are known for its OSS counterpart. The scheduling problem is equivalent to the problem of conflict graph colouring. The restriction on the number of resource units bounds the size of colour classes. We thus study the problem of bounded vertex colouring. A new bound for the makespan is presented, and it is shown that for a 2-bounded colouring the bound is attainable. Some insight about a special case of PCOSS, composed of identical jobs, is given. The model correlates to a real-life timetabling project of assigning technicians to vehicles in a garage, with an additional resource, such as vehicle lift.

Keywords: Graph colouring; Bounded colouring; Open shop scheduling; Concurrent machines; Limited resources; Technician timetabling (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03503-9 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:302:y:2021:i:2:d:10.1007_s10479-019-03503-9

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

DOI: 10.1007/s10479-019-03503-9

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 ().