Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer
-
摘要: 研究对象是带有限缓冲区混合流水车间中的多目标调度问题。以各机器前置后置缓冲区容积有限、工件以批量形式运输、运载设备的运载能力有限等作为资源限制因素，以最小化完工时间、最小化物料运输时间、最小化并行机前置缓冲区空间占用率均衡指数为目标，建立调度模型。分别采用NSGA-II、NSGA-III算法求解该模型，并对比两者之间的差别；设置不同的缓冲区容积，探究不同缓冲区容积对生产目标的影响，寻找最优缓冲区容积；建立不同模型，探究以最小化并行机前置缓冲区空间占用率均衡指数为目标的意义，最后以某船用管类生产企业的实际生产案例作为对象，通过对比优化结果与实际生产数据，验证了算法有效性。Abstract: Buffer zones in a production company are set before and after each processing equipment based on various factors such as workshop space in the hybrid-flow workshop, transportation capacity of the carrying equipment, ease of handling of the machine, machine productivity at various stages, and production cycle time. The objective of this paper was to optimizing the multi-objective scheduling problem in hybrid flow shop with limited buffer. As there was limited space (capacity) at front and rear buffers of each machine, transportation of workpieces in batches, limited carrying capacity of carrier equipment, differences in workability between parallel machines, and process determination, etc., were considered as resource limiting factors, and based upon these factors two-objective scheduling model was established with the goal of minimizing completion time and minimizing material transportation time. The two-objective scheduling model was added with minimization parallel machine front buffer space occupancy rate equilibrium index as a new goal, and established a three-objective scheduling model. In this article, NSGA-II and NSGA-III algorithms were used to solve the three-objective scheduling model, and the crossover and mutation parts of the algorithm were redesigned according to the model established. The actual production data of a marine pipe production enterprise was taken as an example and optimization results were compared with the actual production data. Thus the effectiveness of the algorithm was verified, and the difference between the two algorithms when processing the three-target scheduling model was compared, and it is concluded that NSGA-III has better convergence effect when processing the three-objective model. To explore the impact of different buffer volumes on production, target values under different buffer volumes were compared, and finally optimal buffer volume for each target was found out; then the two-objective model and the three-objective model were compared under different buffer volumes. The optimization results of these indicators prove the practical importance of adding the minimization of the parallel machine front buffer space occupancy rate balance index.
-
Key words:
- hybrid flow shop /
- multi-objective /
- buffer equalization /
- multi-constraint /
- NSGA-III
-
图 3 NSGA-II（a）与NSGA-III（b）优化结果图
Figure 3. NSGA-II (a) and NSGA-III (b) optimization results
图 4 NSGA-II与NSGA-III一级个体数量对比图
Figure 4. Comparison of the number of NSGA-II and NSGA-III individuals
图 5 优化3目标有限缓冲区的混合流水车间调度模型三指标统计结果
Figure 5. Three statistical results of hybrid flow shop scheduling model with optimized three-object limited buffer zone
图 6 模型1与模型2对比。（a）完工时间；（b）运输时间；（c）缓冲区均衡指数
Figure 6. Comparison of model 1 and model 2: (a) completion time; (b) transportation time; (c) buffer equilibrium index
表 1 参数及变量设计
Table 1. Design of the parameters and decision variables
Parameters Description $C_{s,k}^{\rm{F}}$ Capacity of the kth machine’s front buffer in the stage s $C_k^{\rm{B}}$ Capacity of the kth machine’s back buffer ${N_s}$ Number of machines at the s processing stage ${J_a}$ Total number of artifacts in batch a $T_{s,k,j}^{\rm{C}}$ Completion time of job $j$ on the kth machine belong to sth stage $T_{i,s \to (s + 1),j}^{}$ Transportation completion time of ith transporter for transports job $j$ $T_{s,k,j}^{\rm{s}}$ Starting time of job $j$ that processed on the kth machine belong to sth stage $t_{_{s,k,j}}^{\rm{p}}$ The processing time of job $j$ on the kth machine belong to sth stage ${t_{i,s \to (s + 1),j}}$ The transportation time of ith transporter for transports job $j$ $T_{i,s \to (s + 1),j}^{\rm{l}}$ The leaving time of job $j$ that leaves ith transporter $T_{s,k}^{\rm{i}}$ The idle time of the kth machine belong to sth stage $T_{s,k,j}^{\rm{l}}$ The leaving time of job $j$ that leaves the kth machine belong to sth stage s $T_{s,k,{\rm{B}},j}^{\rm{l}}$ The leaving time of job $j$ that leaves back buffer of the kth machine belong to sth stage $T_{a,s,k}^{\rm{l}}$ The leaving time of ath batch that leaves the kth machine belong to sth stage $T_{i,s \to (s + 1),k}^{\rm{a}}$ The arriving time of ith transporter that arrives the kth machine belong to sth stage $V_{s,k}^{\rm{B}}$ The remaining volume of the back buffer of the kth machine belong to sth stage $V_{s,k}^{\rm{F}}$ The remaining volume of the front buffer of the kth machine belong to sth stage $T_{j,s,k}^{\rm{B}}$ The last time the back buffer of the kth machine has enough room for job $j$ $T_{(s + 1),k,a}^{\rm{F}}$ The last time the front buffer of the kth machine has enough room for batch a $T_{j,s,k}^{\rm{B}}$ The moment that the back buffer of the kth machine has enough room for job $j$ $T_{a,s,k}^{\rm{F}}$ The moment that the front buffer of the kth machine has enough room for batch a $t$ Production moment ${X_{i,s \to (s + 1),j,t}}$ If job $j$ is transported by transporter ith transporter at $t$, it is equal to 1, otherwise 0 ${X_{k,j,t}}$ If job $j$ is processed on the kth machine at $t$, it is equal to 1, otherwise 0 ${X_{j,s,k,{\rm{F}},t}}$ If job $j$ is in the front buffer of the kth machine belong to sth stage at $t$, it is equal to 1, otherwise 0 ${X_{j,k,{\rm{B}},t}}$ If job $j$ is in the back buffer of the kth machine at $t$, it is equal to 1,otherwise 0 ${X_{i,s \to (s + 1),a,t}}$ If ath transported by ith transporter t, it is equal to 1, otherwise 0 
下载: 导出CSV
表 2 工件编号以及对应各阶段机器适用状况统计表
Table 2. Workpiece number and statistics of applicable conditions of the machine at each stage
Job number Cutting Bending Spot-welding Fully-welding Polishing Pumping 1 [1,2] [6,7] [16,17] [18,19] [20,21] [22] 2 [3,4,5] [8] [16,17] [18,19] [20,21] [22] 3 [3,4,5] [9] [16,17] [18,19] [20,21] [22] 4 [3,4,5] [10] [16,17] [18,19] [20,21] [22] 5 [3,4,5] [11,12] [16,17] [18,19] [20,21] [22] 6 [3,4,5] [13] [16,17] [18,19] [20,21] [22]
下载: 导出CSV
-
[1] Khosla I. The scheduling problem where multiple machines compete for a common local buffer. Eur J Oper Res, 1995, 84(2): 330 doi: 10.1016/0377-2217(93)E0352-X [2] 黄君政, 李爱平, 刘雪梅, 等. 考虑缓冲区配置的生产线布局优化设计. 同济大学学报(自然科学版), 2015, 43(7):1075 doi: 10.11908/j.issn.0253-374x.2015.07.018Huang J Z, Li A P, Liu X M, et al. Optimal design of production line layout considering buffer allocation. J Tongji Univ Nat Sci, 2015, 43(7): 1075 doi: 10.11908/j.issn.0253-374x.2015.07.018 [3] Papadopoulos H T, Vidalis M I. A heuristic algorithm for the buffer allocation in unreliable unbalanced production lines. Comput Ind Eng, 2001, 41(3): 261 doi: 10.1016/S0360-8352(01)00051-1 [4] Gupta J N D. Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc, 1988, 39(4): 359 doi: 10.1057/jors.1988.63 [5] Djellab H, Djellab K. Preemptive hybrid flowshop scheduling problem of interval orders. Eur J Oper Res, 2002, 137(1): 37 doi: 10.1016/S0377-2217(01)00094-7 [6] Bolat A, Al-Harkan I, Al-Harbi B. Flow-shop scheduling for three serial stations with the last two duplicate. Comput Oper Res, 2005, 32(3): 647 doi: 10.1016/j.cor.2003.08.010 [7] Guirchoun S, Martineau P, Billaut J C. Total completion time minimization in a computer system with a server and two parallel processors. Comput Oper Res, 2005, 32(3): 599 doi: 10.1016/j.cor.2003.08.007 [8] Brah S A. A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Prod Plan Control, 1996, 7(4): 362 doi: 10.1080/09537289608930364 [9] Brah S A, Wheeler G E. Comparison of scheduling rules in a flow shop with multiple processors: A simulation. Simulation, 1998, 71(5): 302 doi: 10.1177/003754979807100501 [10] Priya A, Sahana S K. Multiprocessor scheduling based on evolutionary technique for solving permutation flow shop problem. IEEE Access, 2020, 8: 53151 doi: 10.1109/ACCESS.2020.2973575 [11] Ruiz R, Vazquez-Rodriguez J A. The hybrid flow shop scheduling problem. Eur J Oper Res, 2010, 205(1): 1 doi: 10.1016/j.ejor.2009.09.024 [12] Khan B, Hanoun S, Johnstone M, et al. Multi-objective job shop scheduling using i-NSGA-III // 2018 Annual IEEE International Systems Conference. Vancouver, 2018: 1 [13] Li P, Yang Y X, Du X Y, et al. Iterated local search for distributed multiple assembly no-wait flowshop scheduling // 2017 IEEE Congress on Evolutionary Computation. San Sebastian, 2017 [14] Smutnicki C. A two-machine permutation flow shop scheduling problem with buffers. Oper-Res-Spektrum, 1998, 20(4): 229 doi: 10.1007/s002910050070 [15] Nowicki E. The permutation flow shop with buffers: A tabu search approach. Eur J Oper Res, 1999, 116(1): 205 doi: 10.1016/S0377-2217(98)00017-4 [16] Qian B, Wang L, Huang D X, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput Oper Res, 2009, 36(1): 209 doi: 10.1016/j.cor.2007.08.007 [17] Wang X P, Tang L X. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Comput Oper Res, 2009, 36(3): 907 doi: 10.1016/j.cor.2007.11.004 [18] Sioud A, Gravel M, Gagne C. A genetic algorithm for solving a hybrid flexible flowshop with sequence dependent setup times // 2013 IEEE Congress on Evolutionary Computation. Cancun, 2013: 2512 [19] Omar M K. Spreadsheet approach for solving complex flowshop scheduling problems // 2011 IEEE International Conference on Industrial Engineering and Engineering Management. Singapore, 2011: 176 [20] Duan J H, Zhang M, Qiao G Y, et al. A genetic algorithm for permutation flowshop scheduling with total flowtime criterion // 2011 Chinese Control and Decision Conference (CCDC). Mianyang, 2011: 1514 [21] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput, 2002, 6(2): 182 doi: 10.1109/4235.996017 [22] Wang D J, Liu F, Jin Y C. A proactive scheduling approach to steel rolling process with stochastic machine breakdown. Nat Comput, 2019, 18(4): 679 doi: 10.1007/s11047-016-9599-5 [23] Boufellouh R, Belkaid F. Multi-objective approach to optimize production and maintenance scheduling in flow shop environment under non-renewable resources constraints // 2019 International Conference on Advanced Electrical Engineering (ICAEE). Algiers, 2019 [24] Wang D J, Liu F, Wang J J, et al. Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization. Soft Comput, 2016, 20(4): 1635 doi: 10.1007/s00500-015-1615-7 [25] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints. IEEE Trans Evol Comput, 2014, 18(4): 577 doi: 10.1109/TEVC.2013.2281535 -
点击查看大图
计量
- 文章访问数: 818
- HTML全文浏览量: 210
- 被引次数: 0
