A Single Machine Job Scheduling Problem with Sequence Dependent Setup Times

Abstract

In this paper a real-life single machine job scheduling problem with sequence-dependent setup times of a hood manufacturer company is addressed to minimize total weighted tardiness of the jobs with given due dates. Initially a mixed-integer linear programming model is developed for the problem. Since the problem is NP-hard heuristic algorithms are also proposed to solve larger instances. Namely Apparent Tardiness Cost with Setups (ATCS) Earliest Due Date (EDD) Weighted Earliest Due Dates (WEDD) Shortest Processing Time (SPT) and Weighted Shortest Processing Time (WSPT) rule-based algorithms are developed for the problem. A swap move-based improvement is also employed in the proposed heuristic algorithms. To evaluate the effectiveness and efficiency of the proposed solution approaches a comprehensive computational study is conducted by developing instances for the problem using the methodology from the related literature. Initially optimal results are obtained for small instances by solving the mathematical model. Then the performance of the proposed heuristic algorithms is evaluated by comparisons with the optimal results and time-limited model results. The computational results show that proposed ATCS rule-based heuristic is very effective to solve the problem. A user-friendly decision support system (DSS) is also developed to serve users with easy and efficient job scheduling. © 2020 Elsevier B.V. All rights reserved.