Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance
Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance
复制标题
可重入双目标循环提升调度的混合离散差分进化算法
DOI：
10.1016/j.cor.2016.06.011
复制
发表时间：
2016
影响因子：
4.6
通讯作者：
Yaoyiran Li
中科院分区：
文献类型：
--
作者：
Pengyu Yan;Guanhua Wang;Ada Che;Yaoyiran Li
自动电镀生产线和表面处理车间的循环提升调度问题引起了实践者和研究者的广泛关注和兴趣。在这样的系统中，零件通过材料处理提升机从一个工作站运输到另一个工作站。现有的文献主要讨论如何找到一个最优的循环计划，以尽量减少衡量生产线的生产周期时间。物料搬运成本是一个重要的因素，需要考虑在实践中，但很少在文献中提到。本文研究了同时最小化周期时间和物料搬运成本的双目标循环提升机调度问题。我们认为，可重入的工作站，通常在现实生活中遇到的线，但不可避免地使部分流更复杂。该问题被制定为一个双目标线性规划模型与给定的起重机移动序列，并转化为寻找一组Pareto最优起重机移动序列的双准则。为了获得Pareto最优或近优前沿，提出了一种混合离散差分进化（DDE）算法。该算法根据系统的最大在制品水平将种群划分为若干个子种群，并动态调整子种群的大小，以平衡搜索的探索和利用.我们提出了一个建设性的启发式生成初始子种群与不同的水平，混合变异和交叉算子，评价方法，可以处理不可行的个人和一对一的贪婪禁忌选择方法。对基准实例和随机生成实例的计算结果表明，本文提出的混合DDE算法优于基本DDE算法，并且比现有的ε-约束方法能够求解更大规模的实例.
Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported from a workstation to another by a material handling hoist. The existing literature mainly addressed how to find an optimal cyclic schedule to minimize the cycle time that measures the productivity of the lines. The material handling cost is an important factor that needs to be considered in practice but seldom addressed in the literature. This study focuses on a biobjective cyclic hoist scheduling problem to minimize the cycle time and the material handling cost simultaneously. We consider the reentrant workstations that are usually encountered in real-life lines but inevitably make the part-flow more complicated. The problem is formulated as a biobjective linear programming model with a given hoist move sequence and transformed into finding a set of Pareto optimal hoist move sequences with respect to the bicriteria. To obtain the Pareto optimal or near-optimal front, a hybrid discrete differential evolution (DDE) algorithm is proposed. In this hybrid evolutional algorithm, the population is divided into several subpopulations according to the maximal work-in-process (WIP) level of the system and the sizes of subpopulations are dynamically adjusted to balance the exploration and exploitation of the search. We propose a constructive heuristic to generate initial subpopulations with different WIP levels, hybrid mutation and crossover operators, an evaluation method that can tackle infeasible individuals and a one-to-one greedy tabu selection method. Computational results on both benchmark instances and randomly generated instances show that our proposed hybrid DDE algorithm outperforms the basic DDE algorithm and can solve larger-size instances than the existingε-constraint method.