Single machine scheduling with non-availability interval and optional job rejection

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

5 ציטוטים ‏(Scopus)

תקציר

This paper studies the single machine scheduling problem with availability constraints and optional job rejection. We consider the non-resumable and resumable variants, and show that the problems remain ordinary NP-hard, even with the rejection possibility extension, by presenting pseudo-polynomial dynamic-programming (DP) solutions. We also present an enhanced running time implementation of the algorithm of Kellerer and Strusevich (Algorithmica 57(4):769–795, 2010) for the resumable scenario without job rejection. This solution is adapted to efficiently solve the machine non-availability problem with a floating interval and the problem of two competing agents on a single machine, with and without optional job rejection. Numerical experiments support the efficiency of our DP implementation.

שפה מקוריתאנגלית
עמודים (מ-עד)480-497
מספר עמודים18
כתב עתJournal of Combinatorial Optimization
כרך44
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוג׳ 2022

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Single machine scheduling with non-availability interval and optional job rejection'. יחד הם יוצרים טביעת אצבע ייחודית.

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