Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer

YUAN Qing-xin; DONG Shao-hua

doi:10.13374/j.issn2095-9389.2020.02.26.002

Volume 43 Issue 11

Nov. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Engineering > 2021 > 43(11): 1491-1498

YUAN Qing-xin, DONG Shao-hua. Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering, 2021, 43(11): 1491-1498. doi: 10.13374/j.issn2095-9389.2020.02.26.002

Citation:

YUAN Qing-xin, DONG Shao-hua. Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering, 2021, 43(11): 1491-1498. doi: 10.13374/j.issn2095-9389.2020.02.26.002

Citation:

PDF( 1251 KB)

Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer

doi: 10.13374/j.issn2095-9389.2020.02.26.002

YUAN Qing-xin^,,
DONG Shao-hua

School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China

More Information

Corresponding author: E-mail: 15522625919@163.com
Received Date: 2020-02-26
Available Online: 2020-05-11
Publish Date: 2021-11-25

Abstract

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.
- hybrid flow shop,
- multi-objective,
- buffer equalization,
- multi-constraint,
- NSGA-III

FullText(HTML)

References(25)

References

[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.018 Huang 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