Minimizing total weighted tardiness in a generalized job shop

Minimizing total weighted tardiness in a generalized job shop

0.00 Avg rating0 Votes
Article ID: iaor2008729
Country: United Kingdom
Volume: 8
Issue: 6
Start Page Number: 479
End Page Number: 496
Publication Date: Dec 2005
Journal: Journal of Scheduling
Authors:
Keywords: heuristics: tabu search
Abstract:

We consider a generalization of the classical job shop scheduling problem with release times, positive end–start time lags, and a general precedence graph. As objective we consider the total weighted tardiness. We use a tabu search algorithm to search for the order in which the operations are processed on each machine. Given a sequence of operations on each machine, we determine optimal starting times by solving a maximum cost flow problem. This solution is used to determine the neighborhood for our tabu search algorithm. All sequences in our neighborhood are obtained by swapping certain pairs of adjacent operations. We show that only swaps that possess a certain property can improve the current solution; if no such swap is available in the neighborhood, then the current solution is globally optimal. In the computational results we compare our method with other procedures proposed in literature. Our tabu search algorithm seems to be effective both with respect to time and solution quality.

Reviews

Required fields are marked *. Your email address will not be published.