考虑准备时间和关键目标的柔性作业车间低碳调度研究

doi:10.3901/JME.2019.21.139

摘要/Abstract

摘要： 针对考虑依赖于顺序准备时间的柔性作业车间低碳调度问题（Flexible job shop low carbon scheduling problem，FJSP），提出了一种新型帝国竞争算法（Imperialist competitive algorithm，ICA）以充分优化关键目标最大完成时间和总延迟时间的同时持续改进非关键目标总能耗。该算法采用新的同化策略使得帝国内每个解至少存在多个学习对象并区别对待帝国内的最好解和其他殖民地，新型帝国竞争中给出了归一化总成本新定义并引入了殖民国家的全局搜索。通过试验系统地分析了总能耗的恶化程度与关键目标的改善程度之间的关系，并验证了新型ICA在求解所研究低碳FJSP方面较强的优势。

关键词: 柔性作业车间低碳调度, 帝国竞争算法, 准备时间, 关键目标

Abstract: Aiming at flexible job shop low carbon scheduling problem (FJSP) with sequence-dependent setup times, a new imperialist competitive algorithm (ICA) is proposed to optimize fully makespan and total tardiness as key objectives and continuously improve total energy consumption as non-key one. In ICA, a new assimilation is implemented by making each solution have more than one learning object and differing some best solutions from other colonies and a new imperialist competition is done by the new definition of normalized total cost and the inclusion of global search of imperialist. A number of experiments are conducted to analyze the relation between the deterioration degree of total energy consumption and improvement degree of key objectives. Experimental results also demonstrate the strong advantages on solving the considered FJSP.

Key words: flexible job shop low carbon scheduling, imperialist competitive algorithm, setup times, key objectives

中图分类号:

TP18

李明, 雷德明. 考虑准备时间和关键目标的柔性作业车间低碳调度研究[J]. 机械工程学报, 2019, 55(21): 139-149.

LI Ming, LEI Deming. Research on Flexible Job Shop Low Carbon Scheduling with Setup Times and Key Objectives[J]. Journal of Mechanical Engineering, 2019, 55(21): 139-149.

参考文献

[1] RAHIMIFARD S,SEOW Y,CHILDS T. Minimising embodied product energy to support energy efficient manufacturing[J]. CIRP Annals,2010,59:25-28.
[2] DING J Y,SONG S J,WU C. Carbon-efficient scheduling of flow shops by multi-objective optimization[J]. European Journal of Operations Research,2016,248:758-771.
[3] LEE S,CHUNG B D,JEON H W,et al. A dynamic control approach for energy-efficient production scheduleing on single machine under time-varying electricity pricing[J]. Journal of Cleaner Production,2017,165:552-563.
[4] CHE A,WU X Q,PENG J,et al. Energy-efficient biobjective single-machine scheduling with power-down mechanism[J]. Computers & Operations Research,2017,85:172-183.
[5] WU X,CHE A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling[J]. Omega,2019,82:155-165.
[6] WANG S J,WANG X D,YU J B,et al. Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan[J]. Journal of Cleaner Production,2018,193:424-440.
[7] 雷德明,潘子肖,张清勇. 多目标低碳并行机调度研[J]. 华中科技大学学报,2018,46(8):104-109. LEI Deming,PAN Zixiao,ZHANG Qingyong. Researches on multi-objective low carbon parallel machines scheduling[J]. Journal of Huazhong University of Science and Technology,2018,46(8):104-109.
[8] MANSOURI S A,AKTAS E,BESIKCI U. Green schedu-ling of a two-machine flowshop:Trade-off between make-span and energy consumption[J]. European Journal of Operations Research,2016,248:772-788.
[9] LIU G S,ZHOU Y,YANG H D. Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time[J]. Journal of Cleaner Production,2017,147:470-484.
[10] LU C,GAO L,LI X Y,et al. Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm[J]. Journal of Cleaner Production,2017,144:228-238.
[11] LI J Q,SANG H Y,HAN Y Y,et al. Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions[J]. Journal of Cleaner Production,2018,181:584-598.
[12] WANG J J,WANG L. A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2018:1-15.
[13] LEI D M,GAO L,ZHENG Y L. A novel teaching-learning-based optimization algorithm for energy-effici-ent scheduling in hybrid flow shop[J]. IEEE Transactions on Engineering Management,2018,65:330-340.
[14] MAY G,STAHL B,TAISCH M,et al. Multi-objective genetic algorithm for energy-efficient job shop scheduling[J]. International Journal of Production Research,2015,53:7071-7089.
[15] LEI D M,GUO X P. An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective[J]. International Journal of Production Economics,2015,159:296-303.
[16] ZHANG R,CHIONG R. Solving the energy-efficient job shop scheduling problem:A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption[J]. Journal of Cleaner Production,2016,112:3361-3375.
[17] SALIDO M A,ESCAMILLA,GIRET A,et al. A genetic algorithm for energy-efficiency in job shop scheduling[J]. International Journal of Advanced Manufacturing Technology,2016,85:1303-1314.
[18] PIROOZFARD H,WONG K Y,TIWARI M K. Reduction of carbon emission and total late work criterion in job shop scheduling by applying a multi-objective imperialist competitive algorithm[J]. International Journal of Computational Intelligence Systems,2018,11:805-829.
[19] ZHANG L P,TANG Q H,WU Z J,et al. Mathematical modeling and evolutionary generation of rule sets for energy-efficient flexible job shops[J]. Energy,2017,138:210-227.
[20] 李聪波,沈欢,李玲玲,等. 面向能耗的多工艺路线柔性作业车间调度分批优化调度模型[J]. 机械工程学报,2017,53(5):12-23. LI Congbo,SHEN Huan,LI Lingling,et al. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans[J]. Journal of Mechanical Engineering,2017,53(5):12-23.
[21] 雷德明. 基于新型教学优化算法的低碳柔性作业车间调度[J]. 控制与决策,2017,32:1621-1627. LEI Deming. A Novel teaching-learning-based optimization algorithm for low carbon scheduling of flexible job shop[J]. Control and Decision,2017,32:1621-1627.
[22] LEI D M,ZHENG Y L,GUO X P. A shuffled frog leaping algorithm for flexible job shop scheduling with the consideration of energy consumption[J]. International Journal of Production Research,2017,55:3126-3140.
[23] HE Y,LI Y F,WU T,et al. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops[J]. Journal of Cleaner Production,2015,87:245-254.
[24] YIN L J,LI X Y,GAO L,et al. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem[J]. Sustainable Computing:Informatics and Systems,2017,13:15-30.
[25] MOKHTARI H,HASANI A. An energy-efficient multiobjective optimization for flexible job-shop scheduling problem[J]. Computers & Chemical Engineering,2017,104:339-352.
[26] LIU Q,ZHAN M M,CHEKEM F,et al. A hybrid fruit fly algorithm for solving flexible job-shop scheduling to reduce manufacturing carbon footprint[J]. Journal of Cleaner Production,2017,68:668-678.
[27] WANG H,JIANG Z G,WANG Y,et al. A two-stage optimization method for energy-saving flexible job-shop scheduling based on energy dynamic characterization[J]. Journal of Cleaner Production,2018,188:575-588.
[28] PIROOZFARD H,WONG K Y,WONG W P. Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm[J]. Resources,Conservation and Recycling,2018b,128:267-283.
[29] LEI D M,LI M,WANG L. A two-phase meta-heuristic for multi-objective flexible job shop scheduling problem with total energy consumption threshold[J]. IEEE Transactions on Cybernetics,2019,49(3):1097-1109.
[30] 魏鑫,张泽群,唐敦兵,等. 面向节能的导弹结构件混线生产作业车间多目标调度研究[J]. 机械工程学报,2018,54(9):45-54. WEI Xin,ZHANG Zequn,TANG Dunbing,et al. Energy-saving oriented multi-objective shop floor scheduling for mixed-line production of missile components[J]. Journal of Mechanical Engineering,2018,54(9):45-54.
[31] WU X L,SUN Y J. A green scheduling algorithm for flexible job shop with energy-saving measures[J]. Journal of Cleaner Production,2018,172:3249-3264.
[32] NOUIRI M,BEKRAR A,TRENTESAUX D. Towards energy efficient scheduling and rescheduling for dynamic flexible job shop problem[J]. IFAC-PapersOnLine,2018,51(11):1275-1280.
[33] DAI M,TANG D B,GIRET A,et al. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints[J]. Robotics and Computer Integrated Manufacturing,2019,59:143-157.
[34] GONG X T,PESSEMIER D,MARTENS L,et al. Energy and labor-aware flexible job shop scheduling under dynamic electricity pricing:A many-objective optimization investigation[J]. Journal of Cleaner Production,2019,209:1078-1094.
[35] ABDELMAGUID T F. A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times[J]. Applied Mathematics and Computation,2015,260:188-203.
[36] SHEN L J,PERES S D,NEUFELD J S. Solving the flexible job shop scheduling problem with sequence-dependent setup times[J]. European Journal of Operations Research,2018,265:503-516.
[37] AZZOUZ A,ENNIGROU M,SAID L B. A self-adaptive hybrid algorithm for solving flexible job-shop problem with sequence dependent setup time[J]. Procedia Computer Science,2017,112:457-466.
[38] ATASHPAZ-GAGARI E,LUCAS C. Imperialist competitive algorithm:An algorithm for optimization inspired by imperialist competition[C]//In:IEEE Congress on Evolutionary Computation,Singapore,2007:4661-4667.
[39] HOSSEINI S,KHALED A A. A survey on the imperialist competitive algorithm metaheuristic:Implementation in engineering domain and directions for future research[J]. Applied Soft Computing,2014,24:1078-1094.
[40] SHOKROLLAHPOUR E,ZANDIEH M,DORRI B. A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flow shop problem[J]. International Journal of Production Research,2011,49:3087-3103.
[41] SEIDGAR H,KIANI M,ABEDI M,et al. An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem[J]. International Journal of Production Research,2014,52:1240-1256.
[42] ZANDIEH M,KHATAMI A R,RAHMATI S H A. Flexible job shop scheduling under condition-based maintenance:improved version of imperialist competitive algorithm[J]. Applied Mathematics and Computation,2017,58:449-464.
[43] KARIMI S,ARDALAN Z,NADERI B,et al. Scheduling flexible job-shops with transportation times:Mathematical models and a hybrid imperialist competitive algorithm[J]. Applied Mathematical Modelling,2017,41:667-682.
[44] AHMADIZAR F,FARHADI S. Single-machine batch delivery scheduling with job release dates,due windows and earliness,tardiness,holding and delivery costs[J]. Computers & Operations Research,2105,53:194-205.
[45] YOUSEFI M,YUSUFF R M. Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm[J]. International Journal of Production Research,2013,51(16):4797-4804.
[46] YAZDANI M,KHALILI S M,JOLAI F. A parallel machine scheduling problem with two-agent and tool change activities:An efficient hybrid metaheuristic algorithm[J]. International Journal of Computer Integrated Manufacturing,2016,29(10):1075-1088.
[47] GOLDANSAZ S M,JOLAI F,ANARAKI A H Z. A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop[J]. Applied Mathematical Modelling,2013,37:9603-9616.
[48] LEI D M,ZHENG Y L. Hybrid flow shop scheduling with assembly operations and key objectives:A novel neighborhood[J]. Applied Soft Computing,2017,61:122-128.
[49] AFRUZI E N,NAJAFI A A. ROGHANIAN E,et al. A multi-objective imperialist competitive algorithm for solving discrete time,cost and quality trade-off problems with mode-identity and resource-constrained situations[J]. Computers & Operations Research,2014,50:80-96.
[50] BARNES J W,CHAMBERS J B. Flexible job shop scheduling by tabu search[D]. Texas:Texas University,1996.
[51] KNOWLES J D,CORNE D W. On metrics for comparing non-dominated sets[C]//Proc. of 2002 Congress on Evolutionary Computation Honolulu,May 12-17,2002:711-716.
[52] ZITZLER E,THIELE L. Multi-objective evolutionary algorithm:A comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation,1999,3:257-271.
[53] AHMADI E,ZANDIEH M,FARROKH M,et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithm[J]. Computers & Operations Research,2016,73:56-66.
[54] JIANG Z Q,ZUO L,E M C. Study on multi-objective flexible job-shop scheduling problem considering energy consumption[J]. Journal of Industrial Engineering and Management,2014,7(3):589-604.
[55] YUAN Y,XU H. Multiobjective flexible job shop scheduling using memetic algorithms[J]. IEEE Trans-actions on Automation Science and Engineering,2015,12:336-353.