Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness

Abstract

This paper addresses the NP-hard problem of scheduling N independent jobs on a single machine with release dates, due dates, sequence dependent setup times, and no preemption where the objective is to minimize the weighted sum of squared tardiness. A Lagrangian relaxation based approach is developed for single-machine scheduling with sequence dependent setup times that is based on a list scheduling concept in conjunction with Lagrangian relaxation. Sequence dependent setup times are formulated as capacity constraints, and then are relaxed using Lagrangian multipliers. The primal problem is decomposed into job-level subproblems which are solved optimally and an approximate dual problem is then solved using a sub-gradient technique. The result of the relaxation is a list of jobs sequenced by beginning times that is then improved via a three-way swap. Experimental results are compared with EDD (Earliest Due Date) and ATCS (Apparent Tardiness Cost with Setups) dispatching rules, a four-way swap local search, tabu search, and simulated annealing. The adopted approach results in superior solution quality with respect to EED, ATCS, four-way swap, and tabu search results. It has comparable solution quality to the simulated annealing results, but is substantially more computationally efficient. Overall, the approach is capable of dealing with realistically sized single machine scheduling problems with release dates, due dates, and sequence dependent setup times.