Distributed Production Assembly Scheduling with Hybrid Flowshop in Assembly Stage

Document Type : Original Article

Authors

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

Abstract

A new three stage production-assembly problem is considered in this paper. To the best of our knowledge, considering parallel machines in the third stage, identical parallel factories including the three stage production-assembly system and identical parallel factories with parallel machines in the third stage of the production-assembly system, has been specifically investigated in this paper. To minimize the maximum completion time (Makespan) of all jobs in the all factories, jobs assignment to factories and their processing sequence should be done properly. A Mixed Integer Linear Programming (MILP) model is presented to solve small size problem by using cplex solver. According to the problem computational complexity, large size of problem is not possible to solve using the cplex, so to solve it and to control the computational complexity, a new improved genetic algorithm (GA) is proposed by combining GA and Longest Proseccing Time (LPT) method that is called Hybrid Genetic Algorithm Longest Proseccing Time (HGALPT). The problem parameters values are determined using one-way analysis of variance (ANOVA). Finally, in order to evaluate the efficiency and effectiveness of the proposed algorithm, and to specify each parameter impact on the objective function, sensitivity analysis is performed on the problem parameters.

Keywords

Main Subjects


  1. Babaeimorad. S, Fatthi. P,  Fazlollahtabar. H, “A Joint Optimization Model for Production Scheduling and Preventive Maintenance Interval.” International Journal of Engineering, Transactions B: Applications, Vol. 34, No. 11 (2021), 2508-2516, DOI: 10.5829/IJE.2021.34.11B.13.
  2. Shoaardebili, N., Fattahi, P. “Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints.” International Journal of Production Research, Vol. 53, No. 3, (2015), 944-968. DOI: https://doi.org/10.1080/00207543.2014.948575.
  3. Ahmadi, R., Bagchi, U., Roemer, T. A. “Coordinated scheduling of customer orders for quick response.” Naval Research Logistics (NRL),Vol. 52, No. 6 (2005), 493-512. DOI: https://doi.org/10.1002/nav.20092.
  4. Lee, C. Y., Cheng, T. C. E., Lin, B. M. T. “Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem.” Management Science, Vol. 39, No. 5, (1993), 616-625. DOI: https://doi.org/10.1287/mnsc.39.5.616.
  5. Garey, M. R., Johnson, D. S., Sethi, R. “The complexity of flowshop and jobshop scheduling.” Mathematics of Operations Research, Vol. 1, No. 2 (1976), 117-129. DOI: https://doi.org/10.1287/moor.1.2.117
  6. Deng, J., Wang, L., Wang, S. Y., Zheng, X. L. “A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem.” International Journal of Production Research, Vol. 54, No. 12 (2016), 3561-3577. DOI: https://doi.org/10.1080/00207543.2015.1084063.
  7. Hatami, S., García, R. R., Romano, C. A. “The Distributed Assembly Parallel Machine Scheduling Problem with eligibility constraints.” International Journal of Production Management and Engineering, Vol. 3, No. 1, (2015), 13-23. DOI: https://doi.org/10.4995/ijpme.2015.3345
  8. Framinan, J. M., Perez-Gonzalez, P. “Order scheduling with tardiness objective: Improved approximate solutions.” European Journal of Operational Research,Vol. 66, No. 3 (2018). 840-850, DOI: https://doi.org/10.1016/j.ejor.2017.10.064.
  9. Xiong, F., Xing, K., Wang, F., Lei, H., Han, L. “Minimizing the total completion time in a distributed two stage assembly system with setup times.” Computers & Operations Research, Vol. 47, (2014), 92-105. DOI: https://doi.org/10.1016/j.cor.2014.02.005.
  10. Allahverdi, A., Al-Anzi, F. S. “Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times.” International Journal of Production Research, Vol. 44, No. 22, (2006), 4713-4735. DOI: https://doi.org/10.1080/00207540600621029.
  11. Zhang, Y., Zhou, Z., Liu, J. “The production scheduling problem in a multi-page invoice printing system.” Computers & Operations Research, Vol, 37, No. 10, (2010), 1814-1821. DOI: https://doi.org/10.1016/j.cor.2010.01.014.
  12. Xiong, F., Xing, K., Wang, F. “Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time”. European Journal of Operational Research, Vol, 240, No. 2, (2015), 338-354. DOI: https://doi.org/10.1016/j.ejor.2014.07.004.
  13. Liu, B., Wang, K., Zhang, R. (2016, July). “Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop.” In Congress on Evolutionary Computation, (2016), 1682-1686. DOI: 10.1109/CEC.2016.7743990.
  14. Sung, C. S., Kim, H. A. “A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times.” International Journal of Production Economics, Vol, 113, No. 2, (2008), 1038-1048. DOI: https://doi.org/10.1016/j.ijpe.2007.12.007.
  15. Maboudian, Y., Shafaei, R. “Modeling a bi-criteria two stage assembly flow shop scheduling problem with sequence dependent setup times.” In International Conference on Industrial Engineering and Engineering Management, (2009), 1748-1752, DOI: 10.1109/IEEM.2009.5373156.
  16. Fattahi, P., Hosseini, S., Jolai, F. “Some heuristics for the hybrid flow shop scheduling problem with setup and assembly operations.” International Journal of Industrial Engineering Computations, Vol. 4, No. 3 (2013), 393-416. DOI: 10.5267/j.ijiec.2013.03.004.
  17. Xiong, F., Xing, K. “Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time.” International Journal of Production Research, Vol. 52, No. 9 (2014), 2743-2766. DOI: https://doi.org/10.1080/00207543.2014.884290.
  18. Mahdavi, I., Komaki, G. M., Kayvanfar, V. “Aggregate hybrid flowshop scheduling with assembly operations.” In 18th International Conference on Industrial Engineering and Engineering Management, (2011), 663-667. DOI: 10.1109/ICIEEM.2011.6035244.
  19. Pan, Q. K., Gao, L., Xin-Yu, L., Jose, F. M. “Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem.” Applied Soft Computing, Vol. 81, (2019), 105492. DOI: https://doi.org/10.1016/j.asoc.2019.105492.
  20. Huang, J., Gu, X. “Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm.” Engineering Optimization, (2021), 1-21. DOI: https://doi.org/10.1080/0305215X.2021.1886289.
  21. Lei, D., Yuan, Y., Cai, J. “An improved artificial bee colony for multi-objective distributed unrelated parallel machine scheduling.” International Journal of Production Research, Vol. 59, No. 17, (2021), 5259-5271. DOI: https://doi.org/10.1080/00207543.2020.1775911.
  22. Fathollahi-Fard, A. M., Woodward, L., Akhrif, O. Sustainable distributed permutation flow-shop scheduling model based on a triple bottom line concept. Journal of Industrial Information Integration, Vol 24, 100233. (2021). https://doi.org/10.1016/j.jii.2021.100233
  23. Wang, W., Fathollahi-Fard, A. M. “Multi-objective low-carbon hybrid flow shop scheduling via an improved teaching-learning-based optimization algorithm.” Scientia Iranica, (2022), DOI: 10.24200/SCI.2022.58317.5665
  24. Hosseini, S. M. H. “Distributed assembly permutation flow-shop scheduling problem with non-identical factories and considering budget constraints.” Kybernetes, (2022). DOI: https://doi.org/10.1108/K-11-2021-1112
  25. Jabbari, M., Tavana, M., Fattahi, P., Daneshamooz, F. “A parameter tuned hybrid algorithm for solving flow shop scheduling problems with parallel assembly stages.” Sustainable Operations and Computers, Vol. 3, (2022). 22-32. DOI: https://doi.org/10.1016/j.susoc.2021.09.002
  26. Potts, C. N., Sevast'Janov, S. V., Strusevich, V. A., Van Wassenhove, L. N., Zwaneveld, C. M. “The two-stage assembly scheduling problem: complexity and approximation.” Operations Research, Vol. 43, No. 2, (1995), 346-355. DOI: http://dx.doi.org/10.1287/opre.43.2.346.
  27. Jabbari, M., Azizi, V. “Lot streaming in no-wait multi product flowshop considering sequence dependent setup times and position based learning factors.” International Journal of Engineering, Transactions A: Basics, Vol. 28, No. 7, (2015), 1031-1039. DOI: 10.5829/idosi.ije.2015.28.07a.09
  28. Abtahi, Z., Sahraeian, R. (2021). “Robust and Stable Flow Shop Scheduling Problem Under Uncertain Processing Times and Machines Disruption.” International Journal of Engineering Transactions A: Basics, Vol. 34, No. 4, (2022). DOI: 10.5829/ije.2021.34.04a.20
  29. Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., Tavakkoli-Moghaddam, R. “The social engineering optimizer (SEO).” Engineering Applications of Artificial Intelligence, Vol. 72, (2018), 267-293. DOI: https://doi.org/10.1016/j.engappai.2018.04.009
  30. Gholizadeh, H., Fazlollahtabar, H., Fathollahi-Fard, A. M., Dulebenets, M. A. Preventive maintenance for the flexible flowshop scheduling under uncertainty: a waste-to-energy system. Environmental Science and Pollution Research,. (2021), 1-20. DOI: https://doi.org/10.1007/s11356-021-16234-x
  31. Li, X., Zhang, X., Yin, M., Wang, J. “A genetic algorithm for the distributed assembly permutation flowshop scheduling problem.” In Congress on Evolutionary Computation, (2015), 3096-3101. DOI: 10.1109/CEC.2015.7257275.
  32. Noroozi, A., Mokhtari, H. “Scheduling of printed circuit board (PCB) assembly systems with heterogeneous processors using simulation-based intelligent optimization methods.” Neural Computing and Applications, Vol. 26, No. 4, (2015), 857-873, DOI: 10.1007/s00521-014-1765-z.
  33. Jia, H. Z., Fuh, J. Y., Nee, A. Y., Zhang, Y. F. “Web-based multi-functional scheduling system for a distributed manufacturing environment.” Concurrent Engineering, Vol. 10, No. 1, (2002), 27-39. DOI: https://doi.org/10.1177/1063293X02010001054.
  34. Jia, H. Z., Nee, A. Y., Fuh, J. Y., Zhang, Y. F. “A modified genetic algorithm for distributed scheduling problems.” Journal of Intelligent Manufacturing, Vol. 14, No. 3, (2003), 351-362, DOI: https://doi.org/10.1023/A:1024653810491.
  35. Chang, P. C., Huang, W. H., Wu, J. L., Cheng, T. C. E. “A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem.” International Journal of Production Economics, Vol. 141, No. 1, (2013), 45-55. DOI: https://doi.org/10.1016/j.ijpe.2012.06.007.
  36. Tavakoli, M. R., Mahdizadeh, E. “A new ILP model for identical parallel-machine scheduling with family setup times minimizing the total weighted flow time by a genetic algorithm.” International Journal of Engineering, Transactions A: Basics, (2007), 183-194. https://www.ije.ir/article_71659_16ca2c1872353424a108cbed1308c9e3.pdf
  37. Maghzi. P, Mohammadi. M, Pasandideh. S. H. R, Naderi. B.” Operating Room Scheduling Optimization Based on a Fuzzy Uncertainty Approach and Metaheuristic Algorithms.” International Journal of Engineering, Transactions B: Applications, Vol. 35, No. 2, (2022), 258-275, DOI: 10.5829/IJE.2022.35.02B.01
  38. Abbasi, M., Rafiee, M. “Efficient Parallelization of a Genetic Algorithm Solution on the Traveling Salesman Problem with Multi-core and Many-core Systems.” International Journal of Engineering, Transactions A: Basics, Vol. 33, No. 7, (2020). 1257-1265. DOI: 10.5829/IJE.2020.33.07A.12
  39. Eiben, A. E., Smith, J. E. “Introduction to evolutionary computing,” Berlin: Springer, Vol. 53, (2003), DOI: https://link.springer.com/book/10.1007%2F978-3-662-44874-8
  40. Pillai, A. S., Singh, K., Saravanan, V., Anpalagan, A., Woungang, I., Barolli, L. “A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems.” Soft Computing, Vol. 22, No. 10, (2018), 3271-3285. DOI: https://doi.org/10.1007/s00500-017-2789-y.
  41. Bahalke, U., Yolmeh, A. M., Hajizade, A. N., Bahalke, A., “Genetic and tabu search algorithms for the single machine scheduling problem with sequence-dependent set-up times and deteriorating jobs.” International Journal of Engineering, Transactions A: Basics, Vol. 23, No. 3, (2010), 227-234. https://www.ije.ir/article_71863_722b2d35a63e36bcda4a13526b9d5525.pdf
  42. Yazdani, M., Kabirifar, K., Fathollahi-Fard, A. M., Mojtahedi, M. “Production scheduling of off-site prefabricated construction components considering sequence dependent due dates.” Environmental Science and Pollution Research, (2021), 1-17. DOI: https://doi.org/10.1007/s11356-021-16285-0
  43. Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., Tavakkoli-Moghaddam, R. Red deer algorithm (RDA): a new nature-inspired meta-heuristic. Soft Computing, Vol. 24, No. 19 (2020), 14637-14665. DOI: https://doi.org/10.1007/s00500-020-04812-z