Scheduling step-deteriorating jobs to minimise the total weighted tardiness on a single machine. Issue 2 (3rd April 2017)

• Record Type: Journal Article
• Authors: Guo, Peng; Cheng, Wenming; Wang, Yi
• Is Part Of: International journal of systems science. Volume 4:Issue 2(2017)
• Page Start: 92
• Page End: 107
• Publication Date: 2017-04-03
• Subjects: scheduling -- single machine -- total weighted tardiness -- step-deteriorating jobs -- heuristics -- NP-hardness; Operations research -- Periodicals; Logistics -- Periodicals; System analysis -- Periodicals; 003
• DOI: 10.1080/23302674.2015.1084393
• Languages: English
• ISSNs: 2330-2674

Abstract

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.