考虑学习效应的多目标流水车间调度问题  

Multi-objective Flow-Shop Scheduling Problems with A Learning Effect

作　　者：李永林 董明[2] ZHANG Yufeng[3] 

机构地区：[1]上海工程技术大学管理学院,上海201620 [2]上海交通大学安泰经济与管理学院,上海200030 [3]伯明翰大学商学院

出　　处：《系统管理学报》2017年第6期1071-1080,共10页Journal of Systems & Management

基　　金：国家自然科学基金资助项目(71371123;71502101;71632008;1271138);上海市哲学社会科学规划课题(2017EGL009);上海工程技术大学科研启动项目(校启2017-27);Europe-China High Value Engineering Network(EC-HVEN:295130)

摘　　要：考虑了学习效应对流水车间调度问题的影响,以最大完工时间和总加权滞后时间为优化目标,建立了与加工顺序相关的对数线性调度模型,设计了LNEH(NEH heuristic with Learning effect)启发式算法和MCF(Membrane Computing for multi-objective Flow-shop scheduling)算法进行求解。LNEH算法根据对学习效应下问题性质的分析,在初始序列和工件插入两个环节进而达到对原有NEH算法的改进,同时采用随机策略以获得多个解。MCF算法是采用膜计算理论设计的一种近似调度优化算法,针对调度问题设计了字符对象的编码方式,根据前端等级大小将字符对象往复地分配为均匀的对象集,借鉴PSO算法制订膜内规则:从外部档案和所在的基本膜内中分别选择作为参考的选择规则和类似于PSO算法的移动规则。数值仿真显示,不同学习系数对调度结果具有较大影响,并对比证明了所提两种算法的有效性。Considering a multi-objective flow-shop scheduling problem with a learning effect, we propose a log-linear learning effect scheduling model to minimize the maximum completion time and total weight tardiness. Then, a LNEH （NEH heuristic with Learning effect） heuristic algorithm and a MFA （Membrane Computing for multi-objective Flow- shop scheduling） metaheuristic algorithm, the second of which is inspired by membrane computing, are put forward to solve the proposed model. According to the characteristics of the learning effect, the concept of Pareto-dominance is introduced in LNEH algorithm with two improved aspects of initial sequence and insertion search, which can yield a multiple non-dominated solutions in a probabilistic selection sense. On another hand, MCF algorithm adopts the alphabet of objects to label scheduling features, and then allocate the alphabetical objects in a repeated cycle to ensure an even distribution according to the ranking. It also introduces a selection rule of picking one object from external files and subordinate membranes separately, which is similar to the movement rule of PSO. Numerical simulation results show the significant influence of learning effects on schedule and further verify the performances of the two proposed algorithms are superior to existing classical algorithms.

关 键 词：学习效应 流水车间调度 多目标 PARETO支配 膜计算 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论] TP18[自动化与计算机技术—计算机科学与技术]