Approximation algorithms for the three-stage flexible flow shop problem with mid group constraint
Approximation algorithms for the three-stage flexible flow shop problem with mid group constraint
复制标题
DOI：
10.1016/j.eswa.2014.12.024
复制
发表时间：
2015-05
期刊：
影响因子：
--
通讯作者：
Zhantao Li;Jianjun Liu;Qing-xin Chen;N. Mao;Xiaoming Wang
中科院分区：
文献类型：
--
作者：
Zhantao Li;Jianjun Liu;Qing-xin Chen;N. Mao;Xiaoming Wang
研究了一类三阶段柔性流水车间调度问题，其中工件在第二阶段具有成组约束，三个阶段由不相关的并行机组成。首先，基于Soewandi和Elmaghraby（2001）提出的组合算法思想，提出了10种启发式算法，并给出了它们的时间复杂度。其次，由于没有关于RDM、SP. H1和SP. H2算法在无关并行机上的最坏性能比的文献，我们给出了这三种算法的最坏性能比，并给出了本文提出的九种算法的最坏性能比。最后，为了评估这十个算法的性能，在附录A中提出了这个问题的四个下界，并设计了一个计算实验，其中生成了大量的实例，并对每个实例运行每个算法。实验结果表明，10种启发式算法的性能取决于不同的配置，SP.JH-MJ算法在求解三阶段柔性流水车间调度问题上的性能普遍优于其他算法。
This paper considers a three-stage flexible flow shop scheduling problem, where the jobs have the group constraint at the second stage and the three stages consist of unrelated parallel machines. Because of the complexity of this problem, approximation algorithms are more appropriate to solve it. Firstly, we propose ten heuristic algorithms based on the idea of combined algorithms proposed by Soewandi and Elmaghraby (2001) and give their time complexities. Secondly, since there is no reference on the worst-case performance ratios of RDM, SP.H1 and SP.H2 algorithms for the unrelated parallel machines, we provide the worst-case performance ratios of these three algorithms and then give the worst-case performance ratios of the nine algorithms proposed in this paper. Finally, to evaluate the performance of the ten algorithms, four lower bounds of this problem are proposed in Appendix A and a computational experiment is designed, where lots of instances are generated and each algorithm is run with every instance. Experimental results indicate that the performances of ten heuristic algorithms are contingent on different configurations and SP.JH-MJ algorithm generally outperforms the others with respect to the three-stage flexible flow shop scheduling problem addressed in this paper.