New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives

Christos Koulamas and George J. Kyparisis

European Journal of Operational Research, 2019, vol. 278, issue 1, 149-159

Abstract: We show that the single-machine scheduling problem with past-sequence-dependent (p-s-d) setup times and either the minimum maximum lateness or the minimum maximum tardiness objective is solvable in O(n2) time by an index priority rule followed by backward insertions of certain qualifying jobs. We also show that the problem with the minimum number of tardy jobs objective is solvable in O(n2) time by a variant of Moore's algorithm. We then show how to modify a general purpose dynamic programming algorithm to solve the problem with other due-date related objectives such as the total weighted tardiness, the weighted number of tardy jobs and, in the case of an unrestricted common due date, the total weighted earliness/ tardiness. We also present heuristic decomposition algorithms for the NP-hard scheduling problems with p-s-d setup times and the objectives of total weighted tardiness, weighted number of tardy jobs and total weighted earliness/tardiness around an unrestricted common due date. These algorithms decompose the respective problem heuristically into smaller sub-problems which are then solved optimally by dynamic programming. We show experimentally that the heuristic performs well with extended job due dates close to the makespan because, in those cases, the heuristic is capable of locating the optimal solution with either zero total weighted tardiness or with only a few tardy jobs. In the remaining cases, the quality of the DS solutions is superior with normally distributed data compared to the corresponding solutions with uniformly distributed data. This is because sampling from the normal distribution reduces the variability among processing times and weights which in turn decreases the hardness of the problem. Finally, we show that the heuristic's performance deteriorates as the problem size increases.

Keywords: Scheduling; Single-machine; Setup times (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171930342X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:278:y:2019:i:1:p:149-159

DOI: 10.1016/j.ejor.2019.04.022

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().