Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times in Multi-Factory Production Network: Modeling and Algorithm

Document Type : Original Article


1 Msc, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.

2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.


Today, due to some challenges and competition, such as external pressures, factories are forced to reduce production time, traditional centralized production scheduling is not flexible enough to respond to rapid market changes. In such an environment, factories decide to merge and form a multi-factory production network to work more closely together.  In this research, the multi-factory scheduling problem is considered, which factories belong to a company. The problem is assigning the jobs to appropriate factory and scheduling jobs on machines in each factory. In this paper, it is assumed machines in each factory are unrelated parallel machines. For scheduling jobs on machines sequence-dependent setup times are considered. After proposing a novel mixed integer linear programming model for the problem which is a combination of two types of modeling based on sequence and assignment, we developed an evolutionary metaheuristic namely imperialist competitive algorithm (ICA) to minimize the maximum completion time or makespan among the factories. We compare the obtained solutions using the proposed ICA with those using an adopted genetic algorithm to show the efficiency of the proposed algorithm. Finally, the results are reported. Numerical results show that the proposed algorithm has good performance.


Main Subjects

  1. Bagheri Rad, N., & Samouei, P. (2021). Integrated scheduling of multi-stage production system and transportation in the supply chain by considering the sequence dependent setup time. The Journal of Industrial Management Perspective, 11(3), 181-213 (In Persian).
  2. B., Lukszo, Z. Adhitya, A., Srinivasan, R. (2010). Decentralized vs. centralized management of abnormal situations in a multi-plant enterprise using an agent-based approach. Computer Aided Chemical Engineering, 28, 1219-1224.
  3. Behnamian J. & Fatemi Ghomi, S.M.T. (20l4). A survey of multi-factory scheduling, Journal of Intelligent Manufacturing, 27(1), 231-249.
  4. Behnamian J. Fatemui Ghomi, S.M.T. (20l4). Realistic variant of just-in-time flowshop scheduling: Integration of Lp-metric method Ln PSO-like algorithm. The International Journal of Advanced Manufacturing Technology, 75(9-12), 1787-1797.
  5. Behnamian, J. (2014). Decomposition based hybrid VNS–TS algorithm for distributed parallel factories scheduling with virtual corporation. Computers & Operations Research, 52, 81-191.
  6. Behnamian, J. (2016). Multi-objective production network scheduling using sub-population genetic algorithm and elastic method. Journal of Industrial Engineering Research in Production Systems, 3(6), 133-147. (In Persian)
  7. Behnamian, J. (2017). Heterogeneous Networked cooperative scheduling with anarchic particle swarm optimization. IEEE Transactions on Engineering Management, 64(2), 166-178.
  8. Behnamian, J., & Fatemi Ghomi. S.M.T. (2012). Incorporating transportation time in multi agent production network scheduling. International Journal of Computer Integrated Manufacturing, 25(12), 1111-1128.
  9. Behnamian, J., Fatemi Ghomi. S.M.T. (2013). The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine. Information Sciences, 219, 181-196.
  10. Behnamian, J., Fatemi, Ghomi. S.M.T. (2016). A survey of multi-factory scheduling. Journal of Intelligent Manufacturing, 27(1), 231-249.
  11. Bullinger, H.J. Faehnrich, K.P. & Laubscher, H.-P. (1997). Planning of multi-site production-an object-oriented model. International Journal of Production Economics, 51(1), 19-35.
  12. Cai, S. Yang, K. Liu, K. (2018). Multi-objective optimization of the distributed permutation flowshop scheduling problem with transportation and eligibility constraints. Journal of the Operations Research Society of China, 6(3), 391–416.
  13. Chen, W-L. Huang, C-Y. & Lai, Y-C. (2009). Multi-tier and multi-site collaborative production: Illustrated by a case example of TFT-LCD manufacturing, Computers & Industrial Engineering, 57(1), 61-72.
  14. Cicirello, V.A., Smith, S.F. (2004). Wasp-like agents for distributed factory coordination. Autonomous Agents and Multi-Agent Systems, 8, 237–266.
  15. Faraji Amiri, M., & Behnamian, J. (2020). A simulation based genetic algorithm for flowshop scheduling problem considering energy cost under uncertainty. The Journal of Industrial Management Perspective, 10(2), 9-32. (In Persian).
  16. Gharaei A. Jolai, F. (2021). A Pareto approach for the multi-factory supply chain scheduling and distribution problem. Operational Research, 21, 2333–2364.
  17. Glass, C. A., Potts, C. N. Shade, P. (1994). Unrelated parallel machine scheduling using local search. Mathematical and Computer Modelling, 20(2), 41-52.
  18. Gnoni, M.G. Iavagnilio, R. Mossa, G. Mummolo, G. & Leva, A.D. (2003). Production planning of a multi-site manufacturing system by hybrid modeling: A case study from the automotive industry. International Journal of Production Economics, 85, 251–262.
  19. Kim Y. Yun, C. Park, S.B., Park, S., Fan, L.T. (2008). An integrated model of supply network and production planning for multiple fuel products of multi-site refineries. Computers & Chemical Engineering, 32, 2529-2535.
  20. Leung, S.C.H. Wu, Y. & Lai, K.K. (2003). Multi-site aggregate production planning with multiple objectives: A goal programming approach. Production Planning and Control, 14(5), 425-436.
  21. Marandi F. Fatemi Ghomi, S. M. T. (2019). Integrated multi-factory production and distribution scheduling applying vehicle routing approach, International Journal of Production Research, 57(3), 722–748.
  22. Marandi, F., Fatemi Ghomi, M.T. (2019). Network configuration multi-factory scheduling with batch delivery: A learning-oriented simulated annealing approach. Computers & Industrial Engineering, 132, 293-310.
  23. Rahimi, H., Azar, A., & Rezaei Pandari, A. (2015). Designing a multi objective job shop scheduling model and solving it by simulated annealing. The Journal of Industrial Management Perspective, 5(3), 39-63. (In Persian)
  24. Ruiz, R. Pan, Q.-K. Naderi, B. (2019). Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega, 83, 213–222.
  25. Tavakkoli-Moghaddam, R. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(12), 3224-3230.
  26. Timpe, C.H. & Kallrath, J. (2000). Optimal planning in large multi-site production networks, European Journal of Operational Research, 126, 422-435.
  27. Weng, M.X., Lu, J., Ren, H. (2001). Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International journal of production economics, 70(3), 215-226.
  28. Westfield, F.M. (1955). Marginal analysis, multi-plant firms, and business practice: An example, The Quarterly Journal of Economics, 69(2), 253-268.
  29. Ying K.-C. Lin, S.-W. (2018). Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks. Expert Systems with Applications: An International Journal, 92, 132–141.
  30. Zeidi, J.R., Hosseini. S.M. (2015). Scheduling unrelated parallel machines with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 81(9-12), 1487-1496.
  31. Zhang, H., Wu, Y., Pan, R., Xu, G. (2021) Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs. Journal of Intelligent Manufacturing. 1-22.