.png){kind=icon}
.png){kind=icon}
Return
The single machine CON problem with unavailability period
.png){kind=icon}
PRE
AI
DOI：10.1080/00207543.2019.1709672.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The classical CON problem focuses on scheduling jobs on a single machine sharing a common due-date. We study the CON problem with a given unavailability period. The basic problem (assuming linear job-independent costs and no idle times prior to or after the unavailability period) is easily shown to be NP-hard, and an efficient pseudo-polynomial dynamic programming algorithm is introduced. Extensions of the algorithm to general monotonic job-independent costs, and to linear job-dependent costs are studied as well. All algorithms are tested numerically, and are shown to produce optimal schedules in reasonable time. Then we allow idle times, verify that this case is NP-hard in the ordinary sense as well, and introduce a greedy-type heuristic. Numerical tests are performed, and the results indicate that the heuristic performs extremely well.
Keywords:
Scheduling
single machine
dynamic programming
heuristics
unavailability period
Journal
IF:
7.3
Papers:
1.1W
Citations:
3.7W