Minimizing Total Weighted Tardiness in a Generalized Job Shop |
| |
Authors: | Email author" target="_blank">K?M?J?De?BontridderEmail author |
| |
Affiliation: | (1) Siemens VDO Automotive, P.O. Box 8807, 5605 LV Eindhoven, The Netherlands |
| |
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.
The research was carried out at the Technische Universiteit Eindhoven and the Universiteit Utrecht with support of Baan and
the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT). |
| |
Keywords: | tabu search total weighted tardiness job shop scheduling |
本文献已被 SpringerLink 等数据库收录! |