Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints
Source abstract
Abstract
This study investigates a two-stage assembly-type flow shop with limited waiting time constraints for minimizing the makespan. The first stage consists of m machines fabricating m types of components, whereas the second stage has a single machine to assemble the components into the final product. In the flow shop, the assembly operations in the second stage should start within the limited waiting times after those components complete in the first stage. For this problem, a mixed-integer programming formulation is provided, and this formulation is used to find an optimal solution using a commercial optimization solver CPLEX. As this problem is proved to be NP-hard, various heuristic algorithms (priority rule-based list scheduling, constructive heuristic, and metaheuristic) are proposed to solve a large-scale problem within a short computation time. To evaluate the proposed algorithms, a series of computational experiments, including the calibration of the metaheuristics, were performed on randomly generated problem instances, and the results showed outperformance of the proposed iterated greedy algorithm and simulated annealing algorithm in small- and large-sized problems, respectively.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scheduling and Optimization Algorithms · Advanced Manufacturing and Logistics Optimization · Assembly Line Balancing Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Industrial & Management Engineering, Dong-A University, Busan 49315, Korea
Division of Business Administration & Accounting, Kangwon National University, Chuncheon-si 24341, Korea
Funding
National Research Foundation of Korea
References (54)
Show source-provided references
1. Research trends of scheduling techniques for domestic major industries10.11627/jkise.2018.41.1.059 ↗
2. Flow shop scheduling problems with assembly operations: A review and new trends10.1080/00207543.2018.1550269 ↗
3. Minimizing the makespan in the 3-machine assembly scheduling problem10.1287/mnsc.39.5.616 ↗
4. The two-stage assembly scheduling problem: Complexity and approximation10.1287/opre.43.2.346 ↗
5. Scheduling a multi-stage fabrication shop for efficient subsequent assembly operations10.1016/j.ijpe.2003.08.006 ↗
6. Scheduling for two-stage production system with setup and assembly operations10.1016/S0305-0548(03)00165-5 ↗
7. Minimizing Customer Order Lead-Time in a Two-Stage Assembly Supply Chain10.1007/s10479-007-0289-7 ↗
8. Integrating optimisation and simulation approaches for daily scheduling of assembly and test operations10.1080/00207543.2014.970713 ↗
9. Robust and fuzzy optimisation models for a flow shop scheduling problem with sequence dependent setup times: A real case study on a PCB assembly company10.1080/0951192X.2016.1187293 ↗
10. Scheduling algorithms for computer-aided line balancing in printed circuit board assembly10.1080/09537280050051997 ↗
11. Scheduling hybrid flowshops in printed circuit board assembly lines10.1111/j.1937-5956.2002.tb00492.x ↗
12. Transient Analysis of Serial Production Lines With Perishable Products: Bernoulli Reliability Model10.1109/TAC.2016.2572119 ↗
13. Transient analysis to design buffer capacity in dairy filling and packing production lines10.1016/j.jfoodeng.2009.11.009 ↗
14. Zhou, N., Wu, M., and Zhou, J. (2018, January 6–9). Research on Power Battery Formation Production Scheduling Problem with Limited Waiting Time Constraints. Proceedings of the 2018 10th International Conference on Communication Software and Networks, Chengdu, China.10.1109/ICCSN.2018.8488247 ↗
15. Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures10.1016/j.ejor.2018.04.033 ↗
16. Optimal two- and three-stage production schedules with setup times included10.1002/nav.3800010110 ↗
17. A branch and bound algorithm for the two-stage assembly scheduling problem10.1016/S0377-2217(96)00312-8 ↗
18. Optimal scheduling of the 3-machine assembly-type flow shop10.1051/ro:1999120 ↗
19. Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling10.1016/S0377-2217(02)00245-X ↗
20. The three stage assembly flowshop scheduling problem10.1016/S0305-0548(00)00004-6 ↗
21. Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint10.1016/j.ijpe.2009.03.012 ↗
22. Robust scheduling for a two-stage assembly shop with scenario-dependent processing times10.1080/00207543.2020.1778208 ↗
23. Metaheuristics for two-stage flow-shop assembly problem with a truncation learning function10.1080/0305215X.2020.1757089 ↗
24. Lee, J.Y., and Bang, J.Y. (2016). A two-stage assembly-type flowshop scheduling problem for minimizing total tardiness. Math. Probl. Eng., 2016.10.1155/2016/6409321 ↗
25. Minimizing total completion time in the assembly scheduling problem10.1016/j.cie.2018.06.001 ↗
26. Lee, I.S. (2020). A scheduling problem to minimize total weighted tardiness in the two-stage assembly flowshop. Math. Probl. Eng., 2020.10.1155/2020/9723439 ↗
27. A two-stage three-machine assembly scheduling problem with a truncation position-based learning effect10.1007/s00500-019-04561-8 ↗
28. A two-stage three-machine assembly scheduling problem with a position-based learning effect10.1080/00207543.2017.1401243 ↗
29. A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flow-shop scheduling problem with learning consideration10.1080/0305215X.2019.1632303 ↗
30. New efficient constructive heuristics for the two-stage multi-machine assembly scheduling problem10.1016/j.cie.2019.106223 ↗
31. A two-stage three-machine assembly scheduling problem with deterioration effect10.1080/00207543.2019.1570378 ↗
32. Hybrid branch and bound algorithms for the two-stage assembly scheduling problem with separated setup times10.1080/00207543.2018.1489156 ↗
33. Three meta-heuristics to solve the no-wait two-stage assembly flow-shop scheduling problem
34. Ji, M., Yang, Y., Duan, W., Wang, S., and Liu, B. (2016, January 24–29). Scheduling of No-Wait Stochastic Distributed Assembly Flowshop by Hybrid PSO. Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada.10.1109/CEC.2016.7744120 ↗
35. Li, P., Yang, Y., Du, X., Qu, X., Wang, K., and Liu, B. (2017, January 5–8). Iterated Local Search for Distributed Multiple Assembly No-Wait Flowshop Scheduling. Proceedings of the 2017 IEEE Congress on Evolutionary Computation, Donostia, Spain.
36. Local search methods for a distributed assembly no-idle flow shop scheduling problem10.1109/JSYST.2018.2825337 ↗
37. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem10.1016/j.eswa.2017.09.028 ↗
38. A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem10.1016/j.eswa.2019.02.023 ↗
39. Zhao, F.Q., Zhang, L.X., Cao, J., and Tang, J.X. (2021). A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem. Comput. Ind. Eng., 153.10.1016/j.cie.2020.107082 ↗
40. An improved water wave optimization algorithm with the single wave mechanism for the no-wait flow-shop scheduling problem10.1080/0305215X.2018.1542693 ↗
41. Optimization and approximation in deterministic sequencing and scheduling: A survey10.1016/S0167-5060(08)70356-X ↗
42. A two-machine flowshop sequencing problem with limited waiting time constraints10.1016/0360-8352(94)00026-J ↗
43. A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem10.1016/S0305-0548(01)00098-3 ↗
44. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem10.1016/0305-0483(83)90088-9 ↗
45. Sadeghi, A., Doumari, S.A., Dehghani, M., Montazeri, Z., Trojovsky, P., and Ashtiani, H.J. (2021). A new “Good and Bad Groups-Based Optimizer” for solving various optimization problems. Appl. Sci., 11.10.3390/app11104382 ↗
46. A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility10.1016/j.ejor.2004.06.038 ↗
47. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem10.1016/j.ejor.2005.12.009 ↗
48. Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness10.1016/j.eswa.2017.10.050 ↗
49. A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops10.1016/j.cie.2016.06.012 ↗
50. Mao, J.Y., Pan, Q.K., Miao, Z.H., and Gao, L. (2021). An effective multi-start iterated greedy algorithm to minimize makespan for the distributed permutation flowshop scheduling problem with preventive maintenance. Expert Syst. Appl., 169.10.1016/j.eswa.2020.114495 ↗
51. An iterated greedy algorithm for the parallel blocking flow shop scheduling problem and sequence-dependent setup times10.1016/j.eswa.2021.115535 ↗
52. Simulated annealing for permutation flow-shop scheduling10.1016/0305-0483(89)90059-5 ↗
53. Abuajwa, O., Bin Roslee, M., and Yusoff, Z.B. (2021). Simulated annealing for resource allocation in downlink NOMA systems in 5G networks. Appl. Sci., 11.10.3390/app11104592 ↗
54. Thao, P.B., Truyen, D.C., and Phu, N.M. (2021). CFD analysis and taguchi-based optimization of the thermohydraulic performance of a solar air heater duct baffled on a back plate. Appl. Sci., 11.10.3390/app11104645 ↗