Partially concurrent open shop scheduling with preemption and limited resources

Hagai Ilani, Tal Grinshpoun, Elad Shufan

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

1 ציטוט ‏(Scopus)

תקציר

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.

שפה מקוריתאנגלית
כותר פרסום המארחPATAT 2018 - Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling
עורכיםEdmund K. Burke, Luca Di Gaspero, Barry McCollum, Nysret Musliu, Ender Ozcan
עמודים299-311
מספר עמודים13
מסת"ב (אלקטרוני)9780992998424
סטטוס פרסוםפורסם - 2018
אירוע12th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2018 - Vienna, אוסטריה
משך הזמן: 28 אוג׳ 201831 אוג׳ 2018

סדרות פרסומים

שםPATAT 2018 - Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling

כנס

כנס12th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2018
מדינה/אזוראוסטריה
עירVienna
תקופה28/08/1831/08/18

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Partially concurrent open shop scheduling with preemption and limited resources'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי