Algorithms for a realistic variant of flowshop scheduling
Algorithms for a realistic variant of flowshop scheduling
复制标题
DOI：
10.1016/j.cor.2009.04.017
复制
发表时间：
2010-02-01
影响因子：
4.6
通讯作者：
Zandieh, M.
中科院分区：
文献类型：
--
作者：
Naderi, B.;Ruiz, Ruben;Zandieh, M.
本文讨论了流水作业调度的一个现实变体，即混合灵活流水作业。混合流水作业通过考虑具有并行机器的阶段而不是每个阶段只有一台机器，混合了常规流水作业和并行机器问题的特征。我们还研究了可能发生阶段跳跃的灵活版本，即并非所有作业都必须访问所有阶段。最后，我们还考虑每个阶段依赖于作业顺序的设置时间。考虑的优化标准是完工时间最小化。虽然已经提出了许多混合流水车间的方法，但混合灵活流水车间的研究却很少。如果添加依赖于序列的设置，情况会更糟。在这项研究中，我们提出了两种先进的算法，专门处理这个问题的灵活性和设置特征。第一个算法是动态调度规则启发式算法，第二个算法是迭代局部搜索元启发式算法。通过与其他七种高性能现有算法进行比较来评估所提出的算法。统计上合理的结果支持了这样的观点，即所提出的算法对于所研究的问题非常有竞争力。 (c) 2009 Elsevier Ltd. 保留所有权利。
This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem. (c) 2009 Elsevier Ltd. All rights reserved.