Scheduling step-deteriorating jobs to minimise the total weighted tardiness on a single machine. Issue 2 (3rd April 2017) - Guo, Peng
ABSTRACT: This paper addresses the scheduling problem of minimising the total weighted tardiness on a single machine with step-deteriorating jobs. With the assumption of deterioration, the job processing times are modelled by step functions of job starting times and pre-specified job deteriorating dates. The introduction of step-deteriorating jobs makes the single-machine total weighted tardiness problem more intractable. Until now, the computational complexity of this problem under consideration was not determined. In this study, it is proved to be strongly NP-hard. Then, a linear ordering mixed-integer programming model is derived for solving the problem instances optimally. In order to tackle large-sized problems, seven dispatching heuristic procedures are developed for near-optimal solutions. Meanwhile, the solutions delivered by the proposed heuristics are further improved by a pairwise swap movement. Computational results are presented to reveal the performance of all proposed approaches.