A Hybrid Genetic Algorithm for Integrated Production and Distribution Scheduling Problem with Outsourcing Allowed

Document Type : Original Article


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


In this paper, we studied a new integrated production scheduling, vehicle routing, inventory and outsourcing problem. The production phase considers parallel machine scheduling including setup times with outsourcing allowed and the distribution phase considered batch delivery by a fleet of homogenous vehicles with respect to holding cost of completed jobs. The objective of the Mixed Integer Linear Programming (MILP) formulated model is to minimize the total costs including production, outsourcing, holding, tardiness and distribution fixed and variable costs. Due to the nondeterministic polynomial time (Np)-hardness of the problem, we derive a number of dominance properties for the optimal solution and combine them with a Genetic Algorithm (GA) to solve the problem. To assess the efficiency and effectiveness of the proposed hybrid algorithm, we conduct the computational study on randomly generated instances. Sensitivity analyses showed the impacts of the parameters on the objective function were incorporated. In order to evaluate the significance of the differences among the results obtained by GA and GADP one-tailed paired t tests were performed and interval plots were depicted.


1.     Taghizadehalvandi, M., and Kamisli Ozturk, Z. “Multi-objective Solution Approaches for Employee Shift Scheduling Problems in Service Sectors (RESEARCH NOTE).” International Journal of Engineering, Transactions C: Aspects , Vol. 32, No. 9, (2019), 1312–1319. https://doi.org/10.5829/ije.2019.32.09c.12
2.     Amin-Tahmasb, H., and Hami, M. “Optimization of a Bi-objective Scheduling for Two Groups of Experienced and Inexperienced Distribution Staff Based on Capillary Marketing.” International Journal of Engineering, Transactions B: Applications, Vol. 31, No. 11, (2018), 1943–1952. https://doi.org/10.5829/ije.2018.31.11b.19
3.     Sarmiento, A. M., and Nagi, R. “A review of integrated analysis of production-distribution systems.” IIE Transactions (Institute of Industrial Engineers), Vol. 31, No. 11, (1999), 1061–1074. https://doi.org/10.1080/07408179908969907
4.     Chang, Y. C., Li, V. C., and Chiang, C. J. “An ant colony optimization heuristic for an integrated production and distribution scheduling problem.” Engineering Optimization, Vol. 46, No. 4, (2014), 503–520. https://doi.org/10.1080/0305215X.2013.786062
5.     Ahmadizar, F., and Amiri, Z. “Outsourcing and scheduling for a two-machine flow shop with release times.” Engineering Optimization, Vol. 50, No. 3, (2018), 483–498. https://doi.org/10.1080/0305215X.2017.1325483
6.     McIvor, R. “The influence of capability considerations on the outsourcing decision: The case of a manufacturing company.” International Journal of Production Research, Vol. 48, No. 17, (2010), 5031–5052. https://doi.org/10.1080/00207540903049423
7.     Qi, X. “Outsourcing and production scheduling for a two-stage flow shop.” International Journal of Production Economics, Vol. 129, No. 1, (2011), 43–50. https://doi.org/10.1016/j.ijpe.2010.08.011
8.     Amorim, P., Belo-Filho, M. A. F., Toledo, F. M. B., Almeder, C., and Almada-Lobo, B. “Lot sizing versus batching in the production and distribution planning of perishable goods.” International Journal of Production Economics, Vol. 146, No. 1, (2013), 208–218. https://doi.org/10.1016/j.ijpe.2013.07.001
9.     Van Buer, M. G., Woodruff, D. L., and Olson, R. T. “Solving the medium newspaper production/distribution problem.” European Journal of Operational Research, Vol. 115, No. 2, (1999), 237–253. https://doi.org/10.1016/S0377-2217(98)00300-2
10.   Chen, Z. L., and Vairaktarakis, G. L. “Integrated scheduling of production and distribution operations.” Management Science, Vol. 51, No. 4, (2005), 614–628. https://doi.org/10.1287/mnsc.1040.0325
11.   Li, C. L., and Vairaktarakis, G. “Coordinating production and distribution of jobs with bundling operations.” IIE Transactions (Institute of Industrial Engineers), Vol. 39, No. 2, (2007), 203–215. https://doi.org/10.1080/07408170600735561
12.   Chang, Y. C., and Lee, C. Y. “Machine scheduling with job delivery coordination.” European Journal of Operational Research, Vol. 158, No. 2, (2004), 470–487. https://doi.org/10.1016/S0377-2217(03)00364-3
13.   Li, C. L., Vairaktarakis, G., and Lee, C. Y. “Machine scheduling with deliveries to multiple customer locations.” European Journal of Operational Research, Vol. 164, No. 1, (2005), 39–51. https://doi.org/10.1016/j.ejor.2003.11.022
14.   Geismar, J. H. N., Laporte, G., Lei, L., and Sriskandarajah, C. “The integrated production and transportation scheduling problem for a product with a short lifespan.” INFORMS Journal on Computing, Vol. 20, No. 1, (2008), 21–33. https://doi.org/10.1287/ijoc.1060.0208
15.   Chen, H. K., Hsueh, C. F., and Chang, M. S. “Production scheduling and vehicle routing with time windows for perishable food products.” Computers and Operations Research, Vol. 36, No. 7, (2009), 2311–2319. https://doi.org/10.1016/j.cor.2008.09.010
16.   Ullrich, C. A. “Integrated machine scheduling and vehicle routing with time windows.” European Journal of Operational Research, Vol. 227, No. 1, (2013), 152–165. https://doi.org/10.1016/j.ejor.2012.11.049
17.   Belo-Filho, M. A. F., Amorim, P., and Almada-Lobo, B. “An adaptive large neighbourhood search for the operational integrated production and distribution problem of perishable products.” International Journal of Production Research, Vol. 53, No. 20, (2015), 6040–6058. https://doi.org/10.1080/00207543.2015.1010744
18.   Kang, H. Y., Pearn, W. L., Chung, I. P., and Lee, A. H. I. “An enhanced model for the integrated production and transportation problem in a multiple vehicles environment.” Soft Computing, Vol. 20, No. 4, (2016), 1415–1435. https://doi.org/10.1007/s00500-015-1595-7
19.   Li, K., Zhou, C., Leung, J. Y. T., and Ma, Y. “Integrated production and delivery with single machine and multiple vehicles.” Expert Systems with Applications, Vol. 57, (2016), 12–20. https://doi.org/10.1016/j.eswa.2016.02.033
20.   Karao─član, ─░., and Kesen, S. E. “The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm.” International Journal of Production Research, Vol. 55, No. 2, (2017), 536–557. https://doi.org/10.1080/00207543.2016.1213916
21.   Devapriya, P., Ferrell, W., and Geismar, N. “Integrated production and distribution scheduling with a perishable product.” European Journal of Operational Research, Vol. 259, No. 3, (2017), 906–916. https://doi.org/10.1016/j.ejor.2016.09.019
22.   Lacomme, P., Moukrim, A., Quilliot, A., and Vinot, M. “Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product.” International Journal of Production Research, Vol. 56, No. 12, (2018), 4313–4336. https://doi.org/10.1080/00207543.2018.1431416
23.   Tamannaei, M., and Rasti-Barzoki, M. “Mathematical programming and solution approaches for minimizing tardiness and transportation costs in the supply chain scheduling problem.” Computers and Industrial Engineering, Vol. 127, (2019), 643–656. https://doi.org/10.1016/j.cie.2018.11.003
24.   Tavares-Neto, R. F., and Nagano, M. S. “An Iterated Greedy approach to integrate production by multiple parallel machines and distribution by a single capacitated vehicle.” Swarm and Evolutionary Computation, Vol. 44, (2019), 612–621. https://doi.org/10.1016/j.swevo.2018.08.001
25.   Mohammadi, S., Al-e-Hashem, S. M. J. M., and Rekik, Y. “An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company.” International Journal of Production Economics, Vol. 219, (2020), 347–359. https://doi.org/10.1016/j.ijpe.2019.05.017
26.   Mousavi, M., Hajiaghaei–Keshteli, M., and Tavakkoli–Moghaddam, R. “Two calibrated meta-heuristics to solve an integrated scheduling problem of production and air transportation with the interval due date.” Soft Computing, Vol. 24, No. 21, (2020), 16383–16411. https://doi.org/10.1007/s00500-020-04948-y
27.   L., I., F., A., and J., A. “A Hybrid Imperialist Competitive Algorithm for Integrated Scheduling of Production and Distribution with Vehicle Routing.” ournal of Industrial Engineering Research in Production Systems, Vol. 6, No. 12, (2018), 63–81. Retrieved from https://www.sid.ir/en/Journal/ViewPaper.aspx?ID=711650
28.   Ahmadizar, F., and Farhadi, S. “Single-machine batch delivery scheduling with job release dates, due windows and earliness, tardiness, holding and delivery costs.” Computers and Operations Research, Vol. 53, (2015), 194–205. https://doi.org/10.1016/j.cor.2014.08.012
29.   Chang, P. C., Chen, S. H., and Mani, V. “A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties.” Applied Mathematical Modelling, Vol. 33, No. 1, (2009), 579–596. https://doi.org/10.1016/j.apm.2008.01.006
30.   Chang, P. C., and Chen, S. H. “Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times.” Applied Soft Computing Journal, Vol. 11, No. 1, (2011), 1263–1274. https://doi.org/10.1016/j.asoc.2010.03.003
31.   Ahmadizar, F., and Hosseini, L. “Bi-criteria single machine scheduling with a time-dependent learning effect and release times.” Applied Mathematical Modelling, Vol. 36, No. 12, (2012), 6203–6214. https://doi.org/10.1016/j.apm.2012.02.002
32.   Holland, J. H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. MIT press, 1975. Retrieved from https://ui.adsabs.harvard.edu/abs/1975anas.book.....H/abstract
33.   Goldenberg, D. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, 1989.
34.   Davis, L. Handbook of genetic algorithms. Van Nostrand Reynold, 1991. Retrieved from http://papers.cumincad.org/cgi-bin/works/paper/eaca
35.   Talbi, E. Metaheuristics: from design to implementation. John Wiley & Sons, 2009. Retrieved from https://books.google.com/books?hl=en&lr=&id=SIsa6zi5XV8C&oi=fnd&pg=PR7&ots=-bPJrReuCr&sig=kqHIxfQssPePngA0_zVAfx3ljQs
36.   Gendreau, M., and Potvin, J. Handbook of metaheuristics. Springer, 2010. Retrieved from https://link.springer.com/content/pdf/10.1007/978-1-4419-1665-5.pdf
37.   Suzuki, J. “A Markov Chain Analysis on Simple Genetic Algorithms.” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 25, No. 4, (1995), 655–659. https://doi.org/10.1109/21.370197
38.   Lozano, J. A., Larrañaga, P., Graña, M., and Albizuri, F. X. “Genetic algorithms: Bridging the convergence gap.” Theoretical Computer Science, Vol. 229, No. 1–2, (1999), 11–22. https://doi.org/10.1016/S0304-3975(99)00090-0
39.   Tavares Neto, R. F., Godinho Filho, M., and da Silva, F. M. “An ant colony optimization approach for the parallel machine scheduling problem with outsourcing allowed.” Journal of Intelligent Manufacturing, Vol. 26, No. 3, (2015), 527–538. https://doi.org/10.1007/s10845-013-0811-5