Paper Info
Title
Single machine scheduling with non-availability interval and optional job rejection
Abstract
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.
Year
DOI
Venue
2022
10.1007/s10878-022-00845-2
Journal of Combinatorial Optimization
Keywords
DocType
Volume
Non-availability interval, Job rejection, NP-hard, Dynamic programming
Journal
44
Issue
ISSN
Citations 
1
1382-6905
0
PageRank 
References 
Authors
0.34
16
2
Name
Order
Citations
PageRank
Baruch Mor115416.10
Dana Shapira214432.15