考虑区间工时的多目标柔性作业车间节能调度

doi:10.16182/j.issn1004731x.joss.21-0395

摘要/Abstract

摘要：

在综合考虑经济指标和环境因素基础上，研究了工件加工时间不确定的多目标柔性作业车间节能调度问题。将工件不确定加工时间描述为区间数，并以最小化最大区间完工时间、区间总能耗为目标构建区间柔性作业车间调度节能问题优化模型。同时，依据区间可能度的支配关系，设计了一种有效求解该问题的区间多目标进化算法。通过15组测试问题，分别对区间多目标进化算法、SPEA-II及NSGA-II进行仿真实验，并采用反转世代距离(inverse generation distance, IGD)和覆盖集测度(C测度)两种性能指标验证了所提算法的可行性和有效性。

关键词: 柔性作业车间, 多目标优化, 区间数, 可能度, 能耗

Abstract:

Based on the comprehensive consideration of economic indicators and environmental factors, the energy-efficient scheduling problem of multi-objective flexible job shop with uncertain processing time is studied. The interval number is used to describe uncertain processing time of the workpiece, and the optimization model for energy-efficient problem of interval flexible job shop scheduling is established to minimize the maximum interval completion time and total energy consumption. According to the domination relation of interval possibility degree, an effective interval multi-objective evolutionary algorithm is designed. The simulation experiments of the interval multi-objective evolutionary algorithm, SPEA-II and NSGA-II are carried out through 15 groups of test problems, and the feasibility and effectiveness of the proposed algorithm are verified by two performance indexes, the inverse generation distance (IGD) and the covering set measure (C measure).

Key words: flexible job shop scheduling, multi-objective optimization, interval number, possibility degree, energy consumption

中图分类号:

TP301
TP391

张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.

Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time[J]. Journal of System Simulation, 2022, 34(09): 1976-1987.

图/表 15

表1

表2

图1

图2

图3

图4

图5

表3

表4

表5

表6

表7

图6

图7

图8

参考文献 28

[1]	费凡. 面向节能优化的多目标柔性作业车间生产调度方法研究[D]. 合肥: 合肥工业大学, 2018.
	Fei Fan. Research on Multi-objective Flexible Job Shop Scheduling Method for Energy-saving Optimization[D].Hefei: Hefei University of Technology, 2018.
[2]	罗雄, 钱谦, 伏云发. 遗传算法解柔性作业车间调度问题应用综述[J]. 计算机工程与应用, 2019, 55(23): 15-21,34.
	Luo Xiong, Qian Qian, Fu Yunfa. Review of Application of Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems[J]. Computer Engineering and Applications, 2019, 55(23): 15-21,34.
[3]	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 (S0921-3449), 2018, 128: 267-283.
[4]	Wu X, Shen X, Li C. The Flexible Job-shop Scheduling Problem Considering Deterioration Effect and Energy Consumption Simultaneously[J]. Computers & Industrial Engineering (S0360-8352), 2019, 135: 1004-1024.
[5]	Caldeira R H, Gnanavelbabu A, Vaidyanathan T. An Effective Backtracking Search Algorithm for Multi-objective Flexible Job Shop Scheduling Considering New Job Arrivals and Energy Consumption[J]. Computers & Industrial Engineering (S0360-8352), 2020, 149: 106863.
[6]	朱光宇, 徐文婕. 考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法[J]. 控制与决策, 2019, 34(2): 252-260.
	Zhu Guangyu, Xu Wenjie. Multi-objective Flexible Job Shop Scheduling Method for Machine Tool Component Production Line Considering Energy Consumption and Quality[J]. Control and Decision, 2019, 34(2): 252-260.
[7]	刘彩洁, 徐志涛, 张钦, 等. 分时电价下基于NSGA-Ⅱ的柔性作业车间绿色调度[J]. 中国机械工程, 2020, 31(5): 576-585.
	Liu Caijie, Xu Zhitao, Zhang Qin, et al. Green Scheduling of Flexible Job Shop Based on NSGA-II under TOU Power Price[J]. China Mechanical Engineering, 2020, 31(5): 576-585.
[8]	李益兵, 黄炜星, 吴锐. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程, 2020, 31(11): 1344-1350,1385.
	Li Yibing, Huang Weixing, Wu Rui. Research on Multi-objective Green Flexible Job Shop Scheduling Based on Improved ABC Algorithm[J]. China Mechanical Engineering, 2020, 31(11): 1344-1350,1385.
[9]	Lin J, Zhu L, Wang Z-J. A Hybrid Multi-verse Optimization for the Fuzzy Flexible Job-shop Scheduling Problem[J]. Computers & Industrial Engineering (S0360-8352), 2019, 127: 1089-1100.
[10]	李俊萱, 王艳, 纪志成. 基于混合QPSO的模糊柔性作业车间调度问题研究[J]. 系统仿真学报, 2020, 32(10): 2010-2021.
	Li Junxuan, Wang Yan, Ji Zhicheng. Research on Fuzzy Flexible Job Shop Scheduling Problem Based on Hybrid QPSO[J]. Journal of System Simulation, 2020, 32(10): 2010-2021.
[11]	郑小操, 龚文引. 改进人工蜂群算法求解模糊柔性作业车间调度问题[J]. 控制理论与应用, 2020, 37(6): 1284-1292.
	Zheng Xiaocao, Gong Wenyin. An Improved Artificial Bee Colony Algorithm for Fuzzy Flexible Job-shop Scheduling Problem[J]. Control Theory & Applications, 2020, 37(6): 1284-1292.
[12]	杨子豪. 基于强化学习的批处理机随机调度问题研究[D]. 合肥: 合肥工业大学, 2020.
	Yang Zihao. Research on Stochastic Batch Machine Scheduling Problem Based on Reinforcement Learning[D]. Hefei: Hefei University of Technology, 2020.
[13]	Gu J, Gu M, Lu X, et al. Asymptotically Optimal Policy for Stochastic Job Shop Scheduling Problem to Minimize Makespan[J]. Journal of Combinatorial Optimization, 2018, 36(1): 142-161.
[14]	Xiao S, Wu Z, Yu S. A Two-stage Assignment Strategy for the Robust Scheduling of Dual-resource Constrained Stochastic Job Shop Scheduling Problems[J].IFAC-PapersOnLine, 2019, 52(13): 421-426.
[15]	Ghasemi A, Ashoori A, Heavey C. Evolutionary Learning Based Simulation Optimization for Stochastic Job Shop Scheduling Problems[J]. Applied Soft Computing (S1568-4946), 2021, 106: 107309.
[16]	李雅琼, 李强, 阳小兰. 考虑非确定加工时间的柔性作业车间调度问题研究[J]. 计算机应用研究, 2018, 35(10): 3016-3019.
	Li Yaqiong, Li Qiang, Yang Xiaolan. Research on Flexible Job-Shop Scheduling Problem Considering Uncertain Processing Time[J]. Application Research of Computers, 2018, 35(10): 3016-3019.
[17]	王凌, 郑洁, 王晶晶. 求解区间数分布式流水线调度的混合离散果蝇优化算法[J]. 控制与决策, 2020, 35(4): 930-936.
	Wang Ling, Zheng Jie, Wang Jingjing. A Hybrid Discrete Fruit Fly Optimization Algorithm for Distributed Permutation Flowshop Scheduling with Interval Data[J].Control and Decision, 2020, 35(4): 930-936.
[18]	朱艳艳, 徐震浩, 顾幸生. 工序加工时间不确定的可重入调度问题的求解[J]. 控制与决策, 2021, 36(5): 1127-1136.
	Zhu Yanyan, Xu Zhenhao, Gu Xingsheng. Solution of Reentrant Scheduling Problem with Uncertain Processing Time[J]. Control and Decision, 2021, 36(5): 1127-1136.
[19]	Zhou R, Lei D, Zhou X. Multi-objective Energy-efficient Interval Scheduling in Hybrid Flow Shop using Imperialist Competitive Algorithm[J]. IEEE Access (S2169-3536), 2019, 7: 85029-85041.
[20]	Sengupta A, Pal T K. On Comparing Interval Numbers[J].European Journal of Operational Research (S0377-2217), 2000, 127(1): 28-43.
[21]	肖峻, 张跃, 付川. 基于可能度的区间数排序方法比较[J]. 天津大学学报, 2011, 44(8): 705-711.
	Xiao Jun, Zhang Yue, Fu Chuan. Comparison between Methods of Interval Number Ranking Based on Possibility[J]. Journal of Tianjin University, 2011, 44(8): 705-711.
[22]	张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145-151.
	Zhang Guohui, Gao Liang, Li Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.
[23]	Gong D W, Qin N N, Sun X Y. Evolutionary Algorithms for Multi-objective Optimization Problems with Interval Parameters[C]// 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). Changsha, China: IEEE, 2010: 411-420.
[24]	张守京, 王彦亭. 基于改进NSGA2的柔性车间多目标智能调度问题研究[J]. 现代制造工程, 2020(9): 23-31.
	Zhang Shoujing, Wang Yanting. Research on Multi-objective Intelligent Scheduling of Flexible Job Shop Based on Improved NSGA2[J]. Modern Manufacturing Engineering, 2020(9): 23-31.
[25]	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(2): 182-197.
[26]	Brandimarte P. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research (S0254-5330), 1993, 41(3): 157-183.
[27]	Tian Y, Cheng R, Zhang X, et al. PlatEMO: A MATLAB Platform for Evolutionary Multi-objective Optimization [educational forum][J]. IEEE Computational Intelligence Magazine (S1556-603X), 2017, 12(4): 73-87.
[28]	Zitzler E, Thiele L. Multiobjective Evolutionary Algorithms: a Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 1999, 3(4): 257-271.

工件	工序	可选设备及加工时间t/min
工件	工序	M₁	M₂	M₃
J₁	O₁₁	[6,8]	[2,5]	[7,8]
	O₁₂	—	[4,8]	[2,4]
	O₁₃	[7,10]	[6,8]	—
J₂	O₂₁	[3,4]	[8,11]	[6,7]
J₂	O₂₂	[2,3]	—	[2,5]
J₃	O₃₁	[7,11]	[2,6]	[5,8]
	O₃₂	—	[3,7]	—
	O₃₃	[6,10]	—	[8,12]

符号	定义
n	待加工工件总数
m	机器总数
J	工件集
M	机器集
n_i	工件J_i 的工序总数
i	工件序号，i=1,2,···,n
j	工序序号，j=1,2,···,n_i
k	机器序号，k=1,2,···,m
O_ij	工件J_i 的第j道工序
	工序O_ij 在机器M_k 上区间加工时间
	工件J_i 第j道工序在机器M_k 上区间开工时间
	工件J_i 第j道工序在机器M_k 上区间完工时间
	工件J_i 的区间完工时间
L	一个足够大的正数
pe_k	机器M_k 单位时间加工能耗
ie_k	机器M_k 单位时间空闲能耗
ce	车间单位时间公共能耗
	车间区间总加工能耗
	车间区间总空闲能耗
	车间区间公共能耗
	车间区间总能耗
决策变量：


i=1,2,…,n，s=1,2,…,n，j1,2,…,n_i,
t=1,2,…,n_s，k=1,2,…,m

水平	PS	CR	MR
1	50	0.6	0.05
2	100	0.7	0.1
3	150	0.8	0.15
4	200	0.9	0.2

实验号	PS	CR	MR	IGD
1	1	1	1	279.338 9
2	1	2	2	84.262 3
3	1	3	3	160.174 2
4	1	4	4	113.116 8
5	2	1	2	49.983 0
6	2	2	1	113.116 8
7	2	3	4	102.391 0
8	2	4	3	238.586 0
9	3	1	3	74.320 0
10	3	2	4	215.115 4
11	3	3	1	314.163 7
12	3	4	2	133.028 8
13	4	1	4	286.812 3
14	4	2	3	162.841 0
15	4	3	2	477.423 0
16	4	4	1	165.190 2

水平	PS	CR	MR
1	159.2	172.6	218.0
2	126.0	143.8	186.2
3	184.2	263.5	159.0
4	273.1	162.5	179.4
极差	147.1	119.7	59
等级	1	2	3