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

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.