Production-assembly problem with parallel machines in three steps and in distributed factories

Document Type : Research Paper

Authors

Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

10.22070/jqepo.2024.17794.1261

Abstract

 Distributed factories represent a type of manufacturing system in which production is spread out
across multiple geographically dispersed locations. This approach offers several advantages, including
reduced transportation costs, improved responsiveness to customer demand, increased flexibility and
enhanced supply chain resilience. The production-assembly flow shop problem with three stages is a
scheduling problem focused on optimizing the sequence of jobs to be processed on a set of machines. In this
problem, the first and third stages involve dedicated parallel machines, meaning that each job is assigned to
a specific machine and cannot be processed on any other. The second stage consists of identical parallel
machines, where all machines are functionally equivalent and capable of processing any job. A model is
presented for minimizing total tardiness times. Since the problem under investigation is NP-hard, solving it
exactly is either impossible or highly time-consuming (depending on the processor's capability) for large
instances. Consequently, the Hybrid Biogeography-Based Optimization Dominance Rules (HBBO) algorithm
is proposed to address the problem in larger instances. This algorithm is an enhanced version of the
Biogeography-Based Optimization (BBO) algorithm, incorporating dominance rules. The Taguchi method
has been employed to determine appropriate parameter values. The results obtained from the model and
algorithm demonstrate the algorithm’s acceptable efficiency and the inclusion of dominance rules has further
improved the outcomes. 

Keywords

References

Al-Anzi, F. S., & Allahverdi, A. (2009). Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan. Computers & Operations Research, 36(9), 2682-2689.
Allahverdi, A., Aydilek, H., & Aydilek, A. (2016). Two-stage assembly scheduling problem for minimizing total tardiness with setup times. Applied Mathematical Modelling, 40(17-18), 7796-7815.
Baker, K. R., & Trietsch, D. (2009). Principles of sequencing and scheduling. John Wiley & Sons.
Basir, S. A., Mazdeh, M. M., & Namakshenas, M. (2018). Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system. Computers & Industrial Engineering, 126, 217-231.
Campos, S. C., Arroyo, J. E. C., & Tavares, R. G. (2017). A general VNS heuristic for a three-stage assembly flow shop scheduling problem. In Intelligent Systems Design and Applications: 16th International Conference on Intelligent Systems Design and Applications (ISDA 2016) held in Porto, Portugal, December 16-18, 2016 (pp. 955-964). Springer International Publishing.
Chen, S., Pan, Q. K., Gao, L., & Sang, H. Y. (2021). A population-based iterated greedy algorithm to minimize total flowtime for the distributed blocking flowshop scheduling problem. Engineering Applications of Artificial Intelligence, 104, 104375.
Chung, T. P., & Chen, F. (2019). A complete immunoglobulin-based artificial immune system algorithm for two-stage assembly flowshop scheduling problem with part splitting and distinct due windows. International Journal of Production Research, 57(10), 3219-3237.
Cui, H., Li, X., & Gao, L. (2023). An improved multi-population genetic algorithm with a greedy job insertion inter-factory neighborhood structure for distributed heterogeneous hybrid flow shop scheduling problem. Expert Systems with Applications, 222, 119805.
Deng, C., Hu, R., Qian, B., & Jin, H. P. (2021). Hybrid estimation of distribution algorithm for solving three-stage multiobjective integrated scheduling problem. Complexity, 2021, 1-18.
Esmaeili, M., Ahmadizar, F., & Sadeghi, H. (2021). Minimizing the sum of earliness and tardiness in single-machine scheduling. Journal of Quality Engineering and Production Optimization, 6(2), 59-78.
Fattahi, P., Hosseini, S. M. H., Jolai, F., & SAFI, S. A. (2014). Multi-objective scheduling problem in a three-stage production system. Intternattiionall Journall off Industtriiall Engiineeriing & Producttiion Research, 25(1), 1-12.
Fernandez-Viagas, V., Perez-Gonzalez, P., & Framinan, J. M. (2018). The distributed permutation flow shop to minimise the total flowtime. Computers & Industrial Engineering, 118, 464-477.
Ferone, D., Hatami, S., González‐Neira, E. M., Juan, A. A., & Festa, P. (2020). A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem. International Transactions in Operational Research, 27(3), 1368-1391.
Framinan, J. M., & Perez-Gonzalez, P. (2018). Order scheduling with tardiness objective: Improved approximate solutions. European Journal of Operational Research, 266(3), 840-850.
Framinan, J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. (2019). Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research, 273(2), 401-417.
Gonzalez-Neira, E. M., Ferone, D., Hatami, S., & Juan, A. A. (2017). A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory, 79, 23-36.
Hatami, S., Ruiz, R., & Andres-Romano, C. (2013). The distributed assembly permutation flowshop scheduling problem. International Journal of Production Research, 51(17), 5292-5308.
Hosseini, S. M. H., Sana, S. S., & Rostami, M. (2022). Assembly flow shop scheduling problem considering machine eligibility restrictions and auxiliary resource constraints. International Journal of Systems Science: Operations & Logistics, 9(4), 512-528.
Huang, Y. Y., Pan, Q. K., & Gao, L. (2023). An effective memetic algorithm for the distributed flowshop scheduling problem with an assemble machine. International Journal of Production Research, 61(6), 1755-1770.
Huang, Y. Y., Pan, Q. K., Huang, J. P., Suganthan, P. N., & Gao, L. (2021). An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem. Computers & Industrial Engineering, 152, 107021.
Jia, Y., Yan, Q., & Wang, H. (2023). Q-learning driven multi-population memetic algorithm for distributed three-stage assembly hybrid flow shop scheduling with flexible preventive maintenance. Expert Systems with Applications, 120837.
Ji, M., Yang, Y., Duan, W., Wang, S., & Liu, B. (2016, July). Scheduling of no-wait stochastic distributed assembly flowshop by hybrid PSO. In 2016 IEEE congress on evolutionary computation (CEC) (pp. 2649-2654). IEEE.
Jung, S., Woo, Y. B., & Kim, B. S. (2017). Two-stage assembly scheduling problem for processing products with dynamic component-sizes and a setup time. Computers & Industrial Engineering, 104, 98-113.
Khare, A., & Agrawal, S. (2021). Effective heuristics and metaheuristics to minimise total tardiness for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 59(23), 7266-7282.
Komaki, G. M., & Kayvanfar, V. (2015). Grey Wolf Optimizer algorithm for the two-stage assembly flow shop scheduling problem with release time. Journal of Computational Science, 8, 109-120.
Lee, C. Y., Cheng, T. C. E., & Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5), 616-625.
Lee, I. S. (2013). Minimizing total tardiness for the order scheduling problem. International Journal of Production Economics, 144(1), 128-134.
Lei, D., & Liu, M. (2020). An artificial bee colony with division for distributed unrelated parallel machine scheduling with preventive maintenance. Computers & Industrial Engineering, 141, 106320.
Lei, D., & Su, B. (2023). A multi-class teaching–learning-based optimization for multi-objective distributed hybrid flow shop scheduling. Knowledge-Based Systems, 263, 110252.
Leung, J. Y. T., Li, H., & Pinedo, M. (2005). Order scheduling in an environment with dedicated resources in parallel. Journal of Scheduling, 8, 355-386.
Li, M., Su, B., & Lei, D. (2021). A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling. Journal of Intelligent & Fuzzy Systems, 40(3), 4545-4561.
Li, X., Zhang, X., Yin, M., & Wang, J. (2015, May). A genetic algorithm for the distributed assembly permutation flowshop scheduling problem. In 2015 IEEE Congress on Evolutionary Computation (CEC) (pp. 3096-3101). IEEE.
Li, X., Zhang, Z. Q., Hu, R., Qian, B., & Li, K. (2023, July). Hyper-heuristic Three-Dimensional Estimation of Distribution Algorithm for Distributed Assembly Permutation Flowshop Scheduling Problem. In International Conference on Intelligent Computing (pp. 386-396). Singapore: Springer Nature Singapore.
Liao, C. J., Lee, C. H., & Lee, H. C. (2015). An efficient heuristic for a two-stage assembly scheduling problem with batch setup times to minimize makespan. Computers & Industrial Engineering, 88, 317-325.
Lin, J., & Zhang, S. (2016). An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem. Computers & Industrial Engineering, 97, 128-136.
Lin, T. L., Horng, S. J., Kao, T. W., Chen, Y. H., Run, R. S., Chen, R. J., ... & Kuo, I. H. (2010). An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications, 37(3), 2629-2636.
Ma, H. (2010). An analysis of the equilibrium of migration models for biogeography-based optimization. Information Sciences, 180(18), 3444-3464.
Mahabadpour, M., Naderi, B., & Mohammadi, M. (2020). An effective model and algorithm for two-stage assembly flow shop problems. International Journal of Services and Operations Management, 35(1), 100-114.
Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghaddam, R., & Seyyedi, I. (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. Journal of Industrial Engineering International, 8, 1-7.
Mozdgir, A., Fatemi Ghomi, S. M. T., Jolai, F., & Navaei, J. (2013). Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times. International Journal of Production Research, 51(12), 3625-3642.
Naderi, B., & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers & operations research, 37(4), 754-768.
Ochi, H., & Driss, O. B. (2019). Scheduling the distributed assembly flowshop problem to minimize the makespan. Procedia Computer Science, 164, 471-477.
Pan, Q. K., Gao, L., Xin-Yu, L., & Jose, F. M. (2019). Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem. Applied Soft Computing, 81, 105492.
Pan, Y. R., Chen, Q. D., & Pan, Q. K. (2018, July). An Effective Fruit Fly Optimization for the Distributed Assembly Flowshop Scheduling Problem. In 2018 37th Chinese Control Conference (CCC) (pp. 8374-8378). IEEE.
Potts, C. N., Sevast'Janov, S. V., Strusevich, V. A., Van Wassenhove, L. N., & Zwaneveld, C. M. (1995). The two-stage assembly scheduling problem: complexity and approximation. Operations Research, 43(2), 346-355.
Pourhejazy, P., Cheng, C. Y., Ying, K. C., & Lin, S. Y. (2021). Supply chain-oriented two-stage assembly flowshops with sequence-dependent setup times. Journal of Manufacturing Systems, 61, 139-154.
Pourhejazy, P., Cheng, C. Y., Ying, K. C., & Nam, N. H. (2023). Meta-Lamarckian-based iterated greedy for optimizing distributed two-stage assembly flowshops with mixed setups. Annals of Operations Research, 322(1), 125-146.
Rastgar, I., Rezaean, J., Mahdavi, I., & Fattahi, P. (2021). Opportunistic maintenance management for a hybrid flow shop scheduling problem. Journal of Quality Engineering and Production Optimization, 6(2), 17-30.
Rostami, M., & Shad, S. (2020). A Hybrid Bee Algorithm for Two-Machine Flow-Shop Scheduling Problems with Batch Delivery. Journal of Quality Engineering and Production Optimization, 5(1), 137-164.
Samarghandi, H., & Firouzi Jahantigh, F. (2019). Comparing Mixed-Integer and Constraint Programming for the No-Wait Flow Shop Problem with Due Date Constraints. Journal of Quality Engineering and Production Optimization, 4(1), 17-24.
Shoaardebili, N., & Fattahi, P. (2015). Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints. International Journal of Production Research, 53(3), 944-968.
Shao, W., Pi, D., & Shao, Z. (2018). Local search methods for a distributed assembly no-idle flow shop scheduling problem. IEEE Systems Journal, 13(2), 1945-1956.
Shao, Z., Shao, W., & Pi, D. (2020). Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem. Applied Intelligence, 50, 4647-4669.
Sheikh, S., Komaki, G. M., & Kayvanfar, V. (2018). Multi objective two-stage assembly flow shop with release time. Computers & Industrial Engineering, 124, 276-292.
Simon, D. (2008). Biogeography-based optimization. IEEE transactions on evolutionary computation, 12(6), 702-713.
Song, H. B., & Lin, J. (2021). A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times. Swarm and Evolutionary Computation, 60, 100807.
Soon, G. K., Guan, T. T., On, C. K., Alfred, R., & Anthony, P. (2013, November). A comparison on the performance of crossover techniques in video game. In 2013 IEEE international conference on control system, computing and engineering (pp. 493-498). IEEE.
Tian, Y., Liu, D., Yuan, D., & Wang, K. (2013). A discrete PSO for two-stage assembly scheduling problem. The International Journal of Advanced Manufacturing Technology, 66, 481-499.
Torabzadeh, E., & Zandieh, M. (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop. Advances in Engineering Software, 41(10-11), 1238-1243.
Torkashvand, M., Ahmadizar, F., & Farughi, H. (2022). Distributed Production Assembly Scheduling with Hybrid Flowshop in Assembly Stage. International Journal of Engineering, 35(5), 1037-1055.
Torkashvand, M., & Ahmadizar, F. (2024). One-step production and two-step assembly scheduling in identical factories. Engineering Optimization, 56(8), 1255-1277.
Wagneur, E., & Sriskandarajah, C. (1993). Openshops with jobs overlap. European Journal of Operational Research, 71(3), 366–378.
Wang, J., Lei, D., & Li, M. (2022). A Q-Learning-Based Artificial Bee Colony Algorithm for Distributed Three-Stage Assembly Scheduling with Factory Eligibility and Setup Times. Machines, 10(8), 661.
Wang, K., Ma, W. Q., Luo, H., & Qin, H. (2016). Coordinated scheduling of production and transportation in a two-stage assembly flowshop. International journal of production research, 54(22), 6891-6911.
Wang, Z., Deng, Q., Zhang, L., Li, H., & Li, F. (2023). Joint optimization of integrated mixed maintenance and distributed two-stage hybrid flow-shop production for multi-site maintenance requirements. Expert Systems with Applications, 215, 119422.
Wu, C. C., Azzouz, A., Chung, I. H., Lin, W. C., & Ben Said, L. (2019). A two-stage three-machine assembly scheduling problem with deterioration effect. International Journal of Production Research, 57(21), 6634-6647.
Wu, C. C., Bai, D., Azzouz, A., Chung, I. H., Cheng, S. R., Jhwueng, D. C., ... & Said, L. B. (2020). A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flow-shop scheduling problem with learning consideration. Engineering Optimization, 52(6), 1009-1036.
Wu, C. C., Liu, S. C., Lin, T. Y., Yang, T. H., Chung, I. H., & Lin, W. C. (2018). Bicriterion total flowtime and maximum tardiness minimization for an order scheduling problem. Computers & Industrial Engineering, 117, 152-163.
Yan, H. S., Wan, X. Q., & Xiong, F. L. (2014). A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem. International Journal of Production Research, 52(19), 5626-5639.
Yang, S., & Xu, Z. (2021). The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery. International Journal of Production Research, 59(13), 4053-4071.
Yang, Y., Li, P., Wang, S., Liu, B., & Luo, Y. (2017, June). Scatter search for distributed assembly flowshop scheduling to minimize total tardiness. In 2017 IEEE Congress on evolutionary computation (CEC) (pp. 861-868). IEEE.
Yin, Y., Wu, W. H., Wu, W. H., & Wu, C. C. (2014). A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects. Information Sciences, 256, 91-108.
Ying, K. C., & Lin, S. W. (2023). Reinforcement learning iterated greedy algorithm for distributed assembly permutation flowshop scheduling problems. Journal of Ambient Intelligence and Humanized Computing, 14(8), 11123-11138.
Yu, F., Lu, C., Zhou, J., & Yin, L. (2024). Mathematical model and knowledge-based iterated greedy algorithm for distributed assembly hybrid flow shop scheduling problem with dual-resource constraints. Expert Systems with Applications, 239, 122434.
Zhang, G., & Xing, K. (2018). Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment. Computers & Industrial Engineering, 125, 423-433.
Zhang, G., Xing, K., & Cao, F. (2018). Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan. International Journal of Production Research, 56(9), 3226-3244.
Zhang, Y., Zhou, Z., & Liu, J. (2010). The production scheduling problem in a multi-page invoice printing system. Computers & Operations Research, 37(10), 1814-1821.
Zhang, Z., & Tang, Q. (2021). Integrating flexible preventive maintenance activities into two-stage assembly flow shop scheduling with multiple assembly machines. Computers & industrial engineering, 159, 107493.
Zhang, Z. Q., Qian, B., Hu, R., Jin, H. P., & Wang, L. (2021). A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem. Swarm and Evolutionary Computation, 60, 100785.
Zhao, F., Hu, X., Wang, L., Xu, T., Zhu, N., & Jonrinaldi. (2023). A reinforcement learning-driven brain storm optimisation algorithm for multi-objective energy-efficient distributed assembly no-wait flow shop scheduling problem. International Journal of Production Research, 61(9), 2854-2872.
Zhao, F., Qin, S., Zhang, Y., Ma, W., Zhang, C., & Song, H. (2019). A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem. Expert Systems with Applications, 126, 321-339.
Zhao, F., Zhao, J., Wang, L., & Tang, J. (2021). An optimal block knowledge driven backtracking search algorithm for distributed assembly No-wait flow shop scheduling problem. Applied Soft Computing, 112, 107750.
Zhao, F., Zhang, L., Cao, J., & Tang, J. (2021). A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem. Computers & Industrial Engineering, 153, 107082.
Zheng, J., & Wang, Y. (2021). A Hybrid Bat Algorithm for Solving the Three-Stage Distributed Assembly Permutation Flowshop Scheduling Problem. Applied Sciences, 11(21), 10102.
Zou, Y., Wang, D., Lin, W. C., Chen, J. Y., Yu, P. W., Wu, W. H., & Wu, C. C. (2020). Two-stage three-machine assembly scheduling problem with sum-of-processing-times-based learning effect. Soft Computing, 24, 5445-5462.
Journal of Quality Engineering and Production Optimization
Volume 9, Issue 1
May 2024
Pages 65-114

Files

Share

How to cite

Statistics