1、第 36 卷第 6 期 2019 年 6 月 控 制 理 论 与 应 用 Control Theory 柔性作业车间调度; 帝国竞争算法; 低碳调度 引用格式: 李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度. 控制理论与应用, 2019, 36(6): 893 901 DOI: 10.7641/CTA.2018.80105 Novel imperialist competitive algorithm for many-objective fl exible job shop scheduling LI Ming, LEI De-ming (School of Autom
2、ation, Wuhan University of Technology, Wuhan Hubei 430070, China) Abstract: In this study many-objective fl exible job shop scheduling problem (MaOFJSP) is investigated, the goal of which is to minimize makespan, maximum tardiness, maximum workload of machine and total energy consumption simul- tane
3、ously. A novel imperialist competitive algorithm (ICA) is proposed, in which initial empires are newly constructed so that most of imperialists are assigned close number of colonies. Assimilation of imperialist is introduced, and revolution and imperialist competition are implemented in a new way, r
4、espectively, to produce high quality solutions. Extensive ex- periments are conducted to test the impact of strategies of ICA on its performance and compare ICA with other algorithms fi nally. The experimental results validate that ICA has a strong advantage for MaOFJSP. Key words: many-objective op
5、timization; fl exible job shop scheduling problem; imperialist competitive algorithm; energy-effi cient scheduling Citation: LI Ming, LEI Deming. Novel imperialist competitive algorithm for many-objective fl exible job shop schedul- ing. Control Theory 录用日期: 20180702. 通信作者. E-mail: deminglei11 ; Tel
6、.: +86 15327311013. 本文责任编委: 胡跃明. 国家自然科学基金项目(61573264, 71471151)资助. Supported by the National Natural Science Foundation of China (61573264, 71471151). 894控 制 理 论 与 应 用第 36 卷 II. He 等14提出了一种节能优化算法, 它通过机床选 择减少机器加工能耗和操作序列调整减少机器闲置 时的能源浪费. Yin等15设计了一种多目标遗传算法 (multi-objective genetic algorithm, MOGA)求解以生
7、产率、 能源效率和噪音减少为目标的FJSP. Lei等1619 分别应用蛙跳算法、 教学优化算法和帝国竞争算法 (imperialist competitive algorithm, ICA)解决了具有不 同目标的低碳FJSP. Piroozfard等20提出一种MOGA 以同时最小化碳排放量和总拖期. Mokhtari等21给出 基于进化算法和模拟退火算法的混合算法以同时优 化总完成时间、 总能耗和总利用率. MOFJSP根据目标个数可以分成: 1) 常规MOFJ SP, 通常只优化2个或者3个目标, 包括最大完成时间 和总拖期等; 2) 高维多目标柔性作业车间调度问题 (many-obje
8、ctive fl exible job shop scheduling problem, MaOFJSP), 其目标个数大于等于4. 现有研究以常规 MOFJSP为主, 很少考虑MaOFJSP, 实际上, MaOFJSP 广泛存在于实际生产系统中, 例如, 随着总能耗或碳 排放目标的引入, 文献1, 7所研究的三目标FJSP将 转化为MaOFJSP. 和常规MOFJSP相比, MaOFJSP的 计算复杂度和搜索难度更大, 求解该问题的智能算法 所获得的非劣解在种群中所占比例显著上升, 因此, 有必要根据MaOFJSP的特点探讨有效的解决方法. 帝国竞争算法 (imperialist compe
9、titive algorithm, ICA22)是一种模拟社会政治行为的新型智能算法, 其 搜索始于由一组国家组成的初始种群, 其中一些成本 值最小的国家被选作殖民国家, 其他国家为殖民地. ICA主要由殖民地同化、 殖民地革命和帝国竞争等步 骤组成, 它已成功应用于设备布局23、 调度19,24和装 配线平衡25等, 只是很少用来解决MOFJSP19和Ma- OFJSP. ICA既具有较强的邻域搜索能力, 又是有效的 全局优化方法且结构灵活26, 这些特点和ICA的成功 应用表明, 应该大力探讨ICA在MaOFJSP求解方面的 优势. 本文研究MaOFJSP并提出了一种新型ICA以同时 最小
10、化最大完成时间、 最大拖期、 最大机器负荷和总 能耗, 该算法通过应用初始帝国构建的新策略、 引入 殖民国家的同化, 并结合新的革命策略和帝国竞争方 法以逼近问题的Pareto最优前端. 最后通过大量实验 测试ICA的新策略对其性能的影响并将ICA与其他算 法对比, 实验结果表明新型ICA在求解MaOFJSP方面 具有较强的优势. 2问问问题题题描描描述述述 MaOFJSP描述如下: 存在工件集J=J1,J2, , Jn和机器集M=M1,M2, ,Mm. 工件Ji具有 hi道工序, 工序oij为工件Ji的第j道工序, 该工序可由 相容机器集Sij中的任何一台机器加工,SijM; 机器Mk具有2
11、种模式: 加工模式和空闲模式;Ek, SEk分别表示机器Mk在加工模式和空闲模式时单位 时间的能耗. 存在一些与机器和工件相关的约束, 包括同一时 刻一台机器最多只能加工一道工序; 同一时刻一个工 件最多只能在一台机器上加工; 机器加工不能中断; 准备时间和清理时间包含在加工时间内等. MaOFJSP包括调度子问题和机器分配子问题, 前 者确定每台机器上各个工序的加工顺序, 后者为每道 工序选择合适的机器. 通常, 调度子问题比机器分配 子问题更复杂, 求解难度也更大. MaOFJSP的目的是在所有约束得到满足的条件下 同时最小化如下4个目标函数: f1= Cmax,(1) f2= max 1
12、6i6n Ci Di,0,(2) f3= m k=1 wCmax 0 ( n i=1 hi j=1 Ekyijk(t)+SEkzk(t)dt, (3) f4= max 16k6m Wk,(4) 其中:yijk(t)为二进制量, 如果在时刻t机器Mk Sij 处于加工模式, 则yijk(t) = 1; 否则yijk(t) = 0; 如果 机器Mk在时刻t处于空闲, 则zk(t)=1; 否则zk(t)= 0.Cmax表示最大完成时间.Ci,Di分别表示工件Ji的 完成时间和交货期.Wk表示机器Mk的负荷.f1,f2, f3和f4分别表示最大完成时间、 最大拖期、 总能耗和 最大机器负荷. 4个目标
13、中,f1反映车间的生产效率, 优化f2可以提高客户满意度, 总能耗f3为机器在加工 模式和空闲模式下能耗之和, 对其优化能够有效降低 能耗, 而减小f4有利于提高机器利用率. 现有研究表明, 最大完成时间与最大机器负荷之 间存在冲突关系1,7, 最大完成时间、 最大拖期和总能 耗之间也存在冲突关系1621, 另外, 最大机器负荷、 最大拖期和总能耗也彼此冲突2728, 由此可以得出, 本文的4个目标间不可避免地存在冲突关系. 机器分配子问题的优化将直接决定f4和所有机器 加工模式下的能耗总和, 即f3的第1部分的积分, 同时 也会改变f1和f2, 而f3的第2部分的积分, 即空闲模式 下的总能耗直接取决于调度子问题的求解质量, 由f4的定义可
