Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
复制标题
DOI：
10.1016/j.cor.2006.11.004
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Jorge M. S. Valente;Rui Alves
中科院分区：
文献类型：
--
作者：
Jorge M. S. Valente;Rui Alves
本文研究具有序列依赖设置的单机加权延迟调度问题。提出了基于波束搜索技术的启发式算法。这些算法包括经典的波束搜索程序，以及过滤和恢复变体。以前的波束搜索实现使用固定波束和滤波器宽度。我们考虑了通常的固定宽度算法，并开发了使用可变波束和滤波器宽度的新版本。计算结果表明，即使使用较低的平均波束和滤波节点数，变宽度波束搜索版本也略优于固定值波束搜索版本。恢复波束搜索算法给出了最好的结果。然而，对于大型问题，这些过程需要大量的计算时间。优先波束搜索算法要快得多，因此可以用于最大的实例。范围与目的：研究具有序列依赖设置的单机加权延迟调度问题。在当前的竞争环境中，公司按时交货是很重要的，因为如果不这样做，可能会导致商誉的重大损失。加权延迟准则是衡量是否遵守截止日期的标准方法。此外，在一些研究中已经确定了序列依赖设置在实际应用中的重要性。本文提出了几种基于波束搜索技术的启发式算法。在以前的波束搜索实现中，使用固定波束和滤波器宽度。我们考虑了通常的固定宽度算法，并开发了具有可变波束和滤波器宽度的新版本。计算试验表明，变宽度波束搜索版本略优于固定宽度波束搜索版本。对于中小型实例，恢复束搜索方法是一种启发式的选择，但对于大型问题，则需要过多的计算时间。优先级波束搜索算法是波束搜索启发式算法中速度最快的，可以用于最大的实例。
In 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. 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 recovering 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. SCOPE AND PURPOSE: We consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. In the current competitive environment, it is important that companies meet the shipping dates, as failure to do so can result in a significant loss of goodwill. The weighted tardiness criterion is a standard way of measuring compliance with the due dates. Also, the importance of sequence-dependent setups in practical applications has been established in several studies. In this paper, we present several heuristics based on the beam search technique. In previous beam search implementations, fixed beam and filter widths have been used. We consider the usual fixed width algorithms, and also develop new versions with variable beam and filter widths. The computational tests show that the beam search versions with a variable width are marginally superior to their fixed value counterparts. The recovering beam search procedures are the heuristic of choice for small and medium size instances, but require excessive computation times for large problems. The priority beam search algorithm is the fastest of the beam search heuristics, and can be used for the largest instances.