Paper Info
Title
Minsum scheduling with acceptable lead-times and optional job rejection
Abstract
In our current fast-paced era, customers are often willing to pay extra premium for shorter lead times, which motivates further research on the scheduling problem with due-date assignment and customer-specified lead times. As part of this effort, we extend the classic minsum ‘DIF’ scheduling model to allow optional job-rejection, thus adding an important component of real-life applications, namely, the possibility that the scheduler decides to process only a subset of the jobs and outsource the disjoint set. The scheduler is penalised for rejecting certain jobs by setting job-dependent rejection costs, and he is limited by a given upper bound on the total rejection cost. The most general version of the minsum DIF problem includes job-dependent cost parameters and lead-times, and it is strongly NP-hard. Therefore, we study six variants of the problem, where either only the cost parameters or the lead-times are job dependent. All alternatives are extended by optional job-rejection that possibly bounds the constraints or the underlying cost functions. We establish that all studied problems are NP-hard in the ordinary sense and present pseudo-polynomial dynamic programming algorithms and extensive numerical studies for most solutions.
Year
DOI
Venue
2022
10.1007/s11590-021-01763-8
Optimization Letters
Keywords
DocType
Volume
Single-machine scheduling, Due-date assignment, Minsum, Job-rejection, Dynamic programming
Journal
16
Issue
ISSN
Citations 
3
1862-4472
0
PageRank 
References 
Authors
0.34
17
2
Name
Order
Citations
PageRank
Baruch Mor115416.10
Dana Shapira214432.15