Document Type : Original Article


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

2 Assistant professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.


In this research, an integrated scheduling problem of job shop systems with an assembly stage and transportation to minimize the total tardiness time is studied. In this problem, the parts are processed in a job shop system and then assembled in the assembly stage. Ultimately, the products are shipped in packages to customers. Setup time is assumed to depend on sequence. At first, a mixed-integer linear model is developed. Since the problem is NP-hard, a hybrid imperialist competitive and simulated annealing (ICA-SA) algorithm is proposed to solve the problems with the medium and large sizes. To validate the performance of the proposed algorithm, results are compared to an imperialist competitive algorithm and a hybrid imperialist competitive and tabu search (ICA-TS) algorithm. Analysis of variance random block design is used to compare the results of the algorithms. P-values of algorithms and blocks in this test are smaller than the significance level of 0.05. The computational results show that the proposed hybrid algorithm achieves better performance than the imperialist competitive algorithm and hybrid imperialist competitive and tabu search.


Main Subjects

  1. Al-Anzi, F.S., & Allahverdi, A. (2009). Heuristics for a two-stage assembly flow shop with bicriteria of maximum lateness and makespan. Computers & Operations Research, 36(9), 2682-2689.
  2. Armstrong, R., Su, G., & Lei, L. (2008). A Zero-inventory Production and Distribution Problem with a Fixed Customer Sequence. Annals of Operations Research, 159(1), 395–414.
  3. Atashpaz-Gargari E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, in: Proceedings of IEEE Congress on Evolutionary Computation, Singapore, 25-28 Sept, 4661–4667.
  4. Chang, Y. C., & Lee, C. Y. (2004). Machine Scheduling with Job Delivery Coordination. European Journal of Operational Research, 158(2), 470–487.
  5. Chen, Z. L., & Vairaktarakis, G. L. (2005). Integrated Scheduling of Production and Distribution Operations. Management Science, 51(4), 614–628
  6. Cheng, T.C.E. (1990). Analysis of material flow in a job shop with assembly operations, International Journal of Production Research, 28(7): 1369-1383.
  7. Chopra, S., & Meindle, P. (2004). Supply chain management- strategy, planning and operation. 2 nd Ed. Prentic Hall.
  8. Condotta, A., Knust, S., Dimitri, M., & Shakhlevich, N.V. (2013). Tabu Search and Lower Bounds for a Combined Production–Transportation Problem. Computers & Operations Research, 40(3), 886–900.
  9. Daneshamooz, F., Jabbari, M. and Fattahi, P. (2015). A model for job shop scheduling with a parallel assembly stage to minimize makespan. Journal of Industrial Engineering Research in Production Systems, 2(4), 39-53. (In Persian)
  10. Dimyati, T. (2007). Minimizing production flow time in a process and assembly job shop, Proceedings of the International Seminar on Industrial engineering and Management, Jakarta, 68- 73.
  11. Farahani, P., Martin, G., & Günther, H.O. (2012). Integrated Production and Distribution Planning for Perishable Food Products. Flexible Services and Manufacturing Journal, 24(1), 28–51.
  12. Fattahi, P., Hosseini, S.M.H., Jolai, F., & Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling, 38(1), 119-134.
  13. Fattahi, P., Mohammadi, E., & Daneshamooz, F. (2019). Providing a Harmony Search Algorithm for Solving Multi Objective Job Shop Scheduling Problem with Considering an Assembly Stage and Lot Streaming. Journal of Industrial Management Perspective, 9(1), 61-86. (In Persian)
  14. Fontes, B.M.M., & Homayouni, S.M. (2019). Joint production and transportation scheduling in flexible manufacturing systems. Journal of Global Optimization, , 74(4), 879-908.
  15. Frazzona, E.M., Albrechta, A., Piresa, M., Israela, E., Kückc, M., & Freitagc, M. (2018). Hybrid approach for the integrated scheduling of production and transport processes along supply chains. International Journal of Production Research, 56(5), 2019-2035.
  16. Garey, M.R., Johnson, D.S., & sethi, R. (1976). The Complexity of flow shop and job shop scheduling. Mathematics of Operation Research, 1(2), 117-129.
  17. Geismar, H. N., Laporte, G., Lei, L., & Sriskandarajah, C. (2008). The Integrated Production and Transportation Scheduling Problem for a Product with a Short Lifespan. Informs Journal on Computing, 20(1), 21–33.
  18. Gholami, H.R., Mehdizadeh, E., Naderi, B. (2018). Mathematical modeling and imperialist competitive algorithm for Assembly Flowshops. Journal of Industrial Management Perspective, 8(1), 93-111. (In Persian)
  19. Hall, L.A., & Shmoys, D. B. (1992). Jackson’s rule for single-machine scheduling: Making a good heuristic better, Math. Oper. Res, 17:22–35.
  20. Hajiaghaei-Keshteli, M., Aminnayeri, M., & Fatemi Ghomi, S.M.T. (2014). Integrated Scheduling of Production and Rail Transportation. Computers & Industrial Engineering, 74, 240–256.
  21. Jia, Z-H., Zhuo, X-X., Leung, Y-T., & Li, K. (2019). Integrated production and transportation on parallel batch machines to minimize total weighted delivery time. Computers & Operations Research, 102, 39-51.
  22. Kang, H.Y., Peam, W. L. Pearn, Chung, I.P., & Lee, A.H. (2015). An Enhanced Model for the İntegrated Production and Transportation Problem in a Multiple Vehicles Environment. Soft Computing, 20(4), 1415–1435.
  23. Kirkpatrick, S., Gelatt, C. D., Jr., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220: 671-680.
  24. Lee, C.Y., Cheng, T.C.E., & Lin, B.M.T. (1993). Minimizing the makespan in the 3- machine assembly-type flow shop-scheduling problem. Management Science, 39(5), 616-625.
  25. Lee, J., Kim, B.I., Johnson, A.L., & Lee, K. (2014). The Nuclear Medicine Production and Delivery Problem. European Journal of Operational Research, 236(2), 461–472.
  26. Li, C. L., & Vairaktarakis, G. (2007). Coordinating Production and Distribution of Jobs with Bundling Operations. IIE Transactions, 39(2), 203–215.
  27. Low, C., Chang, C.M., Li, R.K., & Huang, C.L. (2014). Coordination of Production Scheduling and Delivery Problems with Heterogeneous Fleet. International Journal of Production Economics, 153, 139–148.
  28. Manne, A.S. (1960). On the job shop-scheduling problem. Operation Research, 8(2), 219-223.
  29. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculation by east computing machines. The Journal of Chemical Physics, 21, 1087-1091.
  30. Potts, C. N. (1980). Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper. Res, 28, 1436–1441.
  31. Rahimi, H., Azar, A., & Rezaei-Pandari, A. (2015). Designing a Multi Objective Job Shop Scheduling Model and solving it by Simulated Annealing. Journal of Industrial Management Perspective, 5(3), 39-63. (In Persian)
  32. Shokrollahpour, E., Zandieh, M., & Dorri, B. (2011). A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flow shop problem. International Journal of Production Research, 49(11), 3087-3103.
  33. Tanimizu, Y., ITO, H., & Matsui, K. (2016). Integrated Production and Transportation Scheduling for Low-Carbon Supply Chains, Sustainability through Innovation in Product Life Cycle Design, 399-415.
  34. Torabzadeh, E., & Zandieh, M. (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flow shop. Advances in Engineering Software, 41(10-11), 1238-1243.
  35. Ullrich, C.A. (2012). Supply Chain Scheduling: Makespan Reduction Potential. International Journal of Logistics Research and Applications, 15(5), 323–336.
  36. Varadharajan, T. K., & Rajendran, C. (2005). A Multi-Objective Simulated-Annealing Algorithm for Scheduling in Flow shops to Minimize the Makespan and Total Flow time of Jobs. European Journal of Operational Research, 167(3), 772-795.
  37. Viergutz, C., & Knust. S. (2014). Integrated Production and Distribution Scheduling with Lifespan Constraints. Annals of Operations Research, 213(1), 293–318.
  38. Wagner, H. (1959). An integer linear-programming model for machine scheduling, Naval Research logistics quarterly, 6(2): 131-140.
  39. Wang, K., Ma, W.Q., Luo, H., & Qin, H. (2016). Coordinated scheduling of production and transportation in a two-stage assembly flow shop, International Journal of Production Research, 6891-6911.
  40. Woeginger, G. J. (1994). Heuristics for parallel machine scheduling with delivery times. Acta Inform, 31, 503–512.
  41. Woeginger, G. J. (1998). A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence- independent batch set-up times. J. Scheduling one, 1(2), 79–87.
  42. Zhang, R.A. (2011). Simulation-based Genetic Algorithm for Job Shop Scheduling with Assembly Operations. International Journal of Advancements in Computing Technology, 3(10).