Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
AbstractIn this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths. Two new improvement procedures, based on adjacent pairwise interchanges and 3-swaps, are also presented. The computational results show that the beam search versions with a variable width are marginally superior to their fixed value counterparts, even when a lower average number of beam and filter nodes is used. The best results are given by the filtered beam search algorithms. For large problems, however, these procedures require excessive computation times. The priority beam search algorithms are much faster, and can therefore be used for the largest instances. The 3-swap method is the best of the improvement procedures, giving the largest relative improvement and decreasing the total cost for a larger number of instances.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Universidade do Porto, Faculdade de Economia do Porto in its series FEP Working Papers with number 186.
Length: 28 pages
Date of creation: Aug 2005
Date of revision:
scheduling; weighted tardiness; sequence-dependent setups; beam search;
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Sabuncuoglu, I. & Bayiz, M., 1999. "Job shop scheduling with beam search," European Journal of Operational Research, Elsevier, vol. 118(2), pages 390-412, October.
- Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
- Jon K. Wilbrecht & William B. Prescott, 1969. "The Influence of Setup Time on Job Shop Performance," Management Science, INFORMS, vol. 16(4), pages B274-B280, December.
- Sen, Tapan & Sulek, Joanne M. & Dileepan, Parthasarati, 2003. "Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey," International Journal of Production Economics, Elsevier, vol. 83(1), pages 1-12, January.
- Raman, Narayan & Rachamadugu, Ram V. & Talbot, F. Brian, 1989. "Real-time scheduling of an automated manufacturing center," European Journal of Operational Research, Elsevier, vol. 40(2), pages 222-242, May.
- Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ().
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.