﻿ 考虑能耗与工时恶化作用下的并行机调度优化
 计算机系统应用  2001, Vol. 29 Issue (9): 66-74 PDF

1. 西南交通大学 机械工程学院, 成都 610031;
2. 轨道交通运维技术与装备四川省重点实验室, 成都 610031

Parallel Machine Scheduling with Step-Deteriorating Jobs and Energy Consumption
XUE Cong1,2, GUO Peng1,2, CHEN Mi1,2, WANG Li-Min1,2
1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China;
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China
Foundation item: National Natural Science Foundation of China (51405403); the Fundamental Research Funds for the Central Universities of China (2682018CX09)
Abstract: Jobs’ temperature will decrease as their starting times delay in heat treating flow shop. In order to process the jobs normally, the worker has to reheat them or keep them in holding furnace. In response to this situation, this study considers a parallel machine scheduling problem with step-deteriorating jobs for minimizing the total tardiness and energy consumption. Firstly, a mixed integer programming model is proposed for the problem under study. Due to the intractability of the problem, a genetic -variable neighborhood search hybrid algorithm is designed to solve it. The algorithm use genetic operations to generate the solution, and then use the variable neighborhood search to improve the solution. The numerical tests show the proposed algorithm can efficiently reduce the total tardiness and energy consumption compared with standard genetic algorithm and mathematical model with standard solver Gurobi.
Key words: energy consumption     parallel machine scheduling     deteriorating job     genetic algorithm     variable neighborhood search

1 问题描述与数学建模

 ${e_j} = {e_0} \times \max \{ 0,{s_j} - {h_j}\}$ (1)

 $F(X,Y,Z,U) = \alpha \sum\limits_{j \in N} {{T_j}} + \beta \sum\limits_{j \in N} {{E_j}}$ (2)

 $\sum\limits_{k \in M} {{y_{jk}} = 1} \;\;\;\;\;\;\;\;\forall j \in N$ (3)
 ${y_{ik}} + {y_{jk}} \le 1 + {x_{ij}} + {x_{ji}}\;\;\;\;\;\;\;\;\forall i,j \in N,i \ne j,k \in M$ (4)
 ${c_i} - {s_j} \le M(1 - {x_{ij}})\;\;\;\;\;\;\;\;\forall i,j \in N$ (5)
 ${s_j} + {p_j} \le {c_j}\;\;\;\;\;\;\;\;\forall j \in N$ (6)
 ${c_j} - {d_j} \le {T_j}\;\;\;\;\;\;\;\;\forall j \in N$ (7)
 ${a_j} \le {p_j} \le {a_j} + {b_j}\;\;\;\;\;\;\;\;\forall j \in N$ (8)
 ${s_j} \le {h_j} + M(1 - {{\textit{z}}_j})\;\;\;\;\;\;\;\;\forall j \in N$ (9)
 ${u_j} \le 1 - {{\textit{z}}_j}\;\;\;\;\;\;\;\;\forall j \in N$ (10)
 ${a_j} + {b_j}(1 - {u_j}-{{\textit{z}}_j}) \le {p_j}\;\;\;\;\;\;\;\;\forall j \in N$ (11)
 ${e_0} \times ({s_j} - {h_j}) - M(1 - {u_j}) \le {e_j}\;\;\;\;\;\;\;\;\forall j \in N$ (12)
 ${e_j} + {p_j} \times {q_j} \le {E_j}\;\;\;\;\;\;\;\;\forall j \in N$ (13)
 ${x_{ij}},{y_{ik}},{x_{ik}} \in \{ 0,1\} \;\;\;\;\;\;\;\;\forall i,j \in \Omega ,k \in \Omega$ (14)
 ${e_j},{T_j},{E_j},{s_j} \ge 0\;\;\;\;\;\;\;\;\forall j \in \Omega$ (15)

2 遗传变邻域混合搜索算法

2.1 编码和解码方式

2.2 遗传算法 2.2.1 遗传算法种群初始化

 图 1 染色解码方式甘特图表示

2.2.2 适应度函数

 $f({\pi _i}) = 1/(\alpha T({\pi _i}) + \beta E({\pi _i}))$ (16)

2.2.3 选择策略以及精英保留

 $L({\pi _i}) = \frac{{\alpha T({\pi _i}) + \beta E({\pi _i})}}{{\displaystyle\sum\limits_{i = 1}^{{p_{\rm num}}} {\alpha T({\pi _i}) + \beta E({\pi _i})} }}$ (17)

2.2.4 交叉操作

 图 2 类OX交叉示意图

2.2.5 变异操作

 图 3 随机选择变异示意图

2.3 变邻域搜索

2.4 GA-VNS算法框架

 图 4 GA-VNS程序框图

3 算例验证

 $R = \frac{{obj(Alg ) - obj(Best)}}{{obj(Best)}} \times 100\%$ (18)

3.1 算例设计

3.2 参数调试

${P_c}$ : 0.6、0.7、0.8、0.9、0.99.

${P_m}$ : 0.01、0.05、0.10、0.15、0.20.

${T_p}$ : 100、200、300、400、500.

 图 5 不同 ${P}_{c}$ 取值均值图和TukeyHSD区间

 图 6 不同 ${P}_{m}$ 取值均值图和TukeyHSD区间

 图 7 不同 ${T}_{p }$ 取值的均值图和TukeyHSD区间

3.3 算例分析

4 结论与展望

 [1] 吴国忠, 白浩然, 杨显志, 等. 尿素造粒塔内热环境仿真研究. 当代化工, 2014, 43(6): 975-977, 993. DOI:10.3969/j.issn.1671-0460.2014.06.035 [2] 付亚平, 黄敏, 王洪峰, 等. 混合并行机调度问题的多目标优化模型及算法. 控制理论与应用, 2014, 31(11): 1510-1516. DOI:10.7641/CTA.2014.31233 [3] Li K, Yang SL. Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms. Applied Mathematical Modelling, 2009, 33(4): 2145-2158. DOI:10.1016/j.apm.2008.05.019 [4] 孟磊磊, 张超勇, 詹欣隆, 等. 不相关并行机节能调度问题建模. 中国机械工程, 2018, 29(23): 2850-2858. DOI:10.3969/j.issn.1004-132X.2018.23.012 [5] 周炳海, 顾佳颖. 考虑多资源约束的非等效并行机节能调度算法. 东北大学学报(自然科学版), 2019, 40(3): 403-408. DOI:10.12068/j.issn.1005-3026.2019.03.019 [6] 雷德明, 潘子肖, 张清勇. 多目标低碳并行机调度研究. 华中科技大学学报(自然科学版), 2018, 46(8): 104-109. DOI:10.13245/j.hust.180820 [7] Li ZT, Yang HD, Zhang SQ, et al. Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology, 2016, 84(1–4): 213-226. DOI:10.1007/s00170-015-7657-2 [8] 王永琦, 吴飞, 江潇潇, 等. 求解并行机拖期与能耗成本优化调度的混合教—学算法. 计算机应用研究, 2019, 36(3): 673-676. DOI:10.19734/j.issn.1001-3695.2017.09.0929 [9] 郭鹏, 程文明, 张则强. 求解具有恶化工件单机调度问题的改进遗传算法. 西南交通大学学报, 2011, 46(3): 506-511. DOI:10.3969/j.issn.0258-2724.2011.03.025 [10] Ji M, Cheng TCE. Parallel-machine scheduling of simple linear deteriorating jobs. Theoretical Computer Science, 2009, 410(38–40): 3761-3768. DOI:10.1016/j.tcs.2009.04.018 [11] Wang XY, Zhou ZL, Ji P, et al. Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times. Computers & Industrial Engineering, 2014, 74: 88-91. DOI:10.1016/j.cie.2014.05.003 [12] Guo P, Cheng WM, Wang Y. Parallel machine scheduling with step-deteriorating jobs and setup times by a hybrid discretecuckoo search algorithm. Engineering Optimization, 2015, 47(11): 1564-1585. DOI:10.1080/0305215x.2014.982634 [13] Guo P, Cheng WM, Zeng M, et al. Scheduling step-deteriorating jobs on parallel machines by mixed integer programming. Journal of Donghua University (English Edition), 2015, 32(5): 709-714, 719. [14] Cheng WM, Guo P, Zhang ZQ, et al. Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs. Mathematical Problems in Engineering, 2012, 2012: 928312. DOI:10.1155/2012/928312 [15] Lalla-Ruiz E, VOß S. Modeling the parallel machine scheduling problem with step deteriorating jobs. European Journal of Operational Research, 2016, 255(1): 21-33. DOI:10.1016/j.ejor.2016.04.010 [16] Pei J, Wang XM, Fan WJ, et al. Scheduling step-deteriorating jobs on bounded parallel-batching machines to maximise the total net revenue. Journal of the Operational Research Society, 2019, 70(10): 1830-1847. DOI:10.1080/01605682.2018.1464428 [17] 轩华, 秦莹莹, 王薛苑, 等. 带恶化工件的不相关并行机调度优化. 系统仿真学报, 2019, 31(5): 919-924. DOI:10.16182/j.issn1004731x.joss.17-0150 [18] Yin YQ, Wang Y, Cheng TCE, et al. Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, 2017, 69: 17-28. DOI:10.1016/j.omega.2016.07.006 [19] Arık OA, Toksarı MD. Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects. International Journal of Production Research, 2018, 56(7): 2488-2505. DOI:10.1080/00207543.2017.1388932 [20] Lu SJ, Liu XB, Pei J, et al. A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Applied Soft Computing, 2018, 66: 168-182. DOI:10.1016/j.asoc.2018.02.018 [21] 郭鹏. 具有分段恶化效应生产过程的智能优化调度研究[博士学位论文]. 成都: 西南交通大学, 2014. [22] Guo P, Cheng WM, Wang Y. Scheduling step-deteriorating jobs to minimise the total weighted tardiness on a single machine. International Journal of Systems Science: Operations & Logistics, 2017, 4(2): 92-107. DOI:10.1080/23302674.2015.1084393