A Hybrid Evolutionary Hyper-Heuristic Approach for Intercell Scheduling Considering Transportation Capacity
A Hybrid Evolutionary Hyper-Heuristic Approach for Intercell Scheduling Considering Transportation Capacity
复制标题
考虑运输能力的混合进化超启发式小区间调度方法
DOI：
10.1109/tase.2015.2470080
复制
发表时间：
2016-04
影响因子：
5.6
通讯作者：
Ikou Kaku
中科院分区：
文献类型：
--
作者：
Dongni Li;Rongxin Zhan;Dan Zheng;Miao Li;Ikou Kaku
研究了以总加权延误最小为目标的考虑运输能力的小区间调度问题，其实质是生产与运输的协调问题。由于这是一个实际的决策问题，具有高的复杂性和大的问题实例，混合进化超启发式（HEH）方法，结合启发式生成和启发式选择，本文提出。为了提高启发式规则的多样性和有效性，采用遗传规划方法根据零件、机器和车辆的属性自动生成新规则。新规则被添加到候选规则集，并开发了规则选择遗传算法，以选择合适的规则，机器和车辆。最后，调度解决方案得到使用所选择的规则。进行了比较评估，一些国家的最先进的超启发式方法，缺乏一些战略提出的HEH，与元启发式方法，适合于大规模的调度问题，并与一些著名的启发式规则的适应。计算结果表明，在HEH中生成的新规则具有相似的性能最好的人制定的规则，但更有效，由于在HEH的进化过程。此外，HEH方法在计算效率和解决方案质量方面都优于其他方法，特别适合于具有大实例大小的问题。从业人员注意事项-我们对中国装备制造业的调查表明，对于合成传动装置等复杂产品，超过51%的零部件的加工路线中发生了单元间转移。超过47%的延误零件是由电池间合作效率低下造成的。因此，小区间的传输是不可避免的，寻找一种有效的小区间调度方法是值得努力的。在复杂产品的工业环境中，解决单元间调度问题有两个不可忽视的特点。第一个是大的问题规模，其中涉及多达数百个部件和数千个操作;第二个是运输对小区间调度的重要性，其中涉及车辆的分配和利用。然而，足够的运输能力是作为一个共同的假设，在大多数的研究与小区间调度，这屏蔽了运输的维度，并阻碍了这些小区间调度方法的应用。因此，考虑运输能力有限的小区间调度问题，提出了一种混合进化超启发式算法。这种方法的优点在于：（i）作为一种超启发式算法，它提供了高的计算效率，这是适合于大规模的工业环境中的问题;和（ii）遗传编程是用来产生特定于问题的启发式规则，这提高了学习和搜索能力的方法。我们比较了所提出的方法与人工启发式规则，在实践中被广泛使用。实验结果表明，对于数百个零件和数千个操作，给定相同的运行时间，我们的方法优于人工规则的平均差距为60.6%，在最小化总加权拖期。因此，我们的方法是在计算效率和解决方案的质量，特别是适用于小区间调度问题的实际优势。
The problem ofintercell scheduling considering transportation capacity with the objective of minimizing total weighted tardiness is addressed in this paper, which in nature is the coordination of production and transportation. Since it is a practical decision-making problem with high complexity and large problem instances, a hybrid evolutionary hyper-heuristic (HEH) approach, which combines heuristic generation and heuristic selection, is developed in this paper. In order to increase the diversity and effectiveness of heuristic rules, genetic programming is used to automatically generate new rules based on the attributes of parts, machines, and vehicles. The new rules are added to the candidate rule set, and a rule selection genetic algorithm is developed to choose appropriate rules for machines and vehicles. Finally, scheduling solutions are obtained using the selected rules. A comparative evaluation is conducted, with some state-of-the-art hyper-heuristic approaches which lack some of the strategies proposed in HEH, with a meta-heuristic approach that is suitable for large scale scheduling problems, and with adaptations of some well-known heuristic rules. Computational results show that the new rules generated in HEH have similarities to the best-performing human-made rules, but are more effective due to the evolutionary processes in HEH. Moreover, the HEH approach has advantages over other approaches in both computational efficiency and solution quality, and is especially suitable for problems with large instance sizes. Note to Practitioners-Our survey of the equipment manufacturing industry in China indicates that, for complex products like synthetic transmission devices, intercell transfers occur in the processing routes of more than 51% of parts. More than 47% of tardy parts are caused by inefficient intercell cooperation. Therefore, intercell transfers are inevitable and it is worth an effort to find out an effective approach to intercell scheduling. To solve intercell scheduling problems, two characteristics in industrial environments of complex products cannot be neglected. The first one is the large problem sizes, which involve up to hundreds of parts and thousands of operations; and the second one is the importance of transportation to intercell scheduling, which involves allocation and utilization of vehicles. However, sufficient transportation capacity is taken as a common assumption in most of research with respect to intercell scheduling, which shields the transportation dimension and hinders the application of these intercell scheduling approaches. Therefore, intercell scheduling with limited transportation capacity is considered, and a hybrid evolutionary hyper-heuristic is proposed in this paper. The advantages of this approach lie in that, (i) as a hyper-heuristic, it provides high computational efficiency, which is suitable for industrial environments with large problem sizes; and (ii) genetic programming is employed to generate problem-specific heuristic rules, which enhances the learning and searching ability of the approach. We compare the proposed approach with the man-made heuristic rules that are widely used in practice. Experimental results indicate that, for hundreds of parts and thousands of operations, given the same running time, our approach outperforms man-made rules with an average gap of 60.6% in minimizing total weighted tardiness. Therefore, our approach is advantageous in both computational efficiency and solution quality, and is especially suitable for the intercell scheduling problems in practice.
登录
查看更多内容
影响因子：
12
作者：
Pickardt, Christoph W.;Hildebrandt, Torsten;Scholz-Reiter, Bernd
通讯作者：
Scholz-Reiter, Bernd
DOI：
10.1016/j.cie.2011.03.007
发表时间：
2011-08
期刊：
Comput. Ind. Eng.
影响因子：
--
作者：
Atabak Elmi;M. Solimanpur;Seyda Topaloglu;Afshin Elmi
通讯作者：
Atabak Elmi;M. Solimanpur;Seyda Topaloglu;Afshin Elmi
DOI：
10.1016/j.cor.2005.07.016
发表时间：
2005-06
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
J. Watson;A. Howe;L. D. Whitley
通讯作者：
J. Watson;A. Howe;L. D. Whitley
DOI：
--
发表时间：
1968
期刊：
--
影响因子：
--
作者：
V. Petrov
通讯作者：
V. Petrov
DOI：
10.1109/iccie.2009.5223947
发表时间：
2009-07
期刊：
2009 International Conference on Computers & Industrial Engineering
影响因子：
--
作者：
Amirmohsen Golmohammadi;R. Ghodsi
通讯作者：
Amirmohsen Golmohammadi;R. Ghodsi