ISSN:
1573-9724
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1007508400656
Permalink