TY - GEN
T1 - Partially concurrent open shop scheduling with preemption and limited resources
AU - Ilani, Hagai
AU - Grinshpoun, Tal
AU - Shufan, Elad
N1 - Publisher Copyright:
© PATAT 2018 Organizing Committee.
PY - 2018
Y1 - 2018
N2 - Partially Concurrent Open Shop Scheduling (PCOSS) is a relaxation of the well-known Open Shop Scheduling (OSS) problem, 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 the addition of limited resources. 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 resources bounds the size of colour classes.We thus study the problem of bounded vertex colouring and focus on bounds. In particular, we introduce a new bound for this problem, propose a colouring procedure that is inspired by this new bound, and show that for perfect graphs with two resources the procedure attains the bound, and hence is optimal. The model correlates to a real-life timetabling project of assigning technicians to vehicles in a garage, with additional resources, such as vehicle lifts.
AB - Partially Concurrent Open Shop Scheduling (PCOSS) is a relaxation of the well-known Open Shop Scheduling (OSS) problem, 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 the addition of limited resources. 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 resources bounds the size of colour classes.We thus study the problem of bounded vertex colouring and focus on bounds. In particular, we introduce a new bound for this problem, propose a colouring procedure that is inspired by this new bound, and show that for perfect graphs with two resources the procedure attains the bound, and hence is optimal. The model correlates to a real-life timetabling project of assigning technicians to vehicles in a garage, with additional resources, such as vehicle lifts.
KW - Concurrent machines
KW - Graph colouring
KW - Limited resources
KW - Open shop scheduling
KW - Technician timetabling
UR - http://www.scopus.com/inward/record.url?scp=85085637175&partnerID=8YFLogxK
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:85085637175
T3 - PATAT 2018 - Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling
SP - 299
EP - 311
BT - PATAT 2018 - Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling
A2 - Burke, Edmund K.
A2 - Di Gaspero, Luca
A2 - McCollum, Barry
A2 - Musliu, Nysret
A2 - Ozcan, Ender
T2 - 12th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2018
Y2 - 28 August 2018 through 31 August 2018
ER -