A new approach in graph- based integrated production and distribution scheduling for perishable products

Document Type : Research Paper


amirkabir university


This study is concerned with how the quality of perishable products can be improved by shortening the time interval between production and distribution. As special types of food such as dairy products decay fast, the integration of production and distribution scheduling (IPDS) is investigated. An integrated scheduling of both processes improves the performance and costs because the separated scheduling of these processes without considering mutual requirements leads to non-optimal solutions. An optimal solution to IPDS requires simultaneously solving of the production scheduling and vehicle routing problems. This article deals with a variation of IPDS that contains a short shelf-life product; hence, there is no inventory of the product in the process. Once an amount of products is produced, they must be transported with non-negligible transportation time directly to various customer locations. The objective is to determine the minimum cost of the makespan and number of vehicles required to complete the distribution of the products to satisfy the demand of a given set of customers over a wide geographic region. The overall problem consists of permutation flow shop scheduling with machines,  jobs and vehicles with different speeds and transportation capacities which transport  jobs from the manufacturing company to  customers distributed in various zones by determining the vehicle routes and number of vehicles. After developing an Integer Linear Programming (ILP) model of the problem, because it is NP-hard, a new graph-based heuristic method is proposed to efficiently solve the problem.


Schmid, V., Doerner, K. F. & Laporte, G. (2013). “Rich routing problems arising in supply chain management”.European Journal of Operational Research , 228, 435-448.
Madronero, M. D., Peidro, D. & Mula, J. (2015). “A review of tactical optimization models for integrated production and transport routing planning decisions”. Computers & Industrial Engineering.
Farahani, P. Grunow, M. & Gunther, H.O. (2012). “Integrated production and distribution planning for perishable food products”.Flexible Service Manufacturing Journal , 24(1), 28-51.
Ullrich,C. A. (2013). “Integrated machine scheduling and vehicle routing with time windows”. European Journal of Operational
Research , 227 (1), 152–165.
Chang, Y. C. & Lee, C. Y. (2004). “Machine scheduling with job delivery coordination”. European Journal of Operational Research
., 158(2), 470–487.
Chen, Z. L. (2010). “Integrated production and outbound distribution scheduling: Review and extensions”.Operations Research, 58(1), 130–148.
Chen, H. K. Hsueh, C. F. & Chang, M. S. (2009). “Production scheduling and vehicle routing with time windows for perishable food products”. Computers & Operation Research, 36(7), 2311-2319.
Buer, M. G. V. Woodruff, D. L & Olson, R. T. (1999). “Solving the medium newspaper production/distribution problem”.
 European Journal of Operational Research , 115(2), 237–253.
Wang, Q., Batta, R. & Szczerba, R. J. (2005). “Sequencing the processing of incoming mail to match an outbound truck delivery schedule”. Computers and Operations Research, 32(7), 1777-1791.
Devapriya, P. Ferrell. W. & Geismar. N. “Optimal fleet size of an integrated production and distribution scheduling problem for a perishable product”. Working Paper., Clemson University (2006).
Chandra, P., & Fisher, M. L. (1994). “Coordination of production and distribution planning”. European Journal of Operational
Research ., 72(3), 503–517.
Chen, Z. L. & Vairaktarakis, G. L. (2005). “Integrated scheduling of production and distribution operations”. Management Science, 51(4), 614–628.
Pundoor, G. & Chen, Z. L. (2005). “Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and total distribution cost”. Naval Research Logistics, 52(6), 571–589.
Chen, Z. L. Handbook of Quantitative Supply Chain Analysis: Modeling in the EBusiness Era. Kluwer Academic Publishers:
Norwell, MA, USA (2004).
Lee, C. Y. & Chen, Z. L. (2001). “Machine scheduling with transportation considerations”. Journal of Scheduling, 4(1), 3–24.
Zhong, W. Y. Dosa, G. & Tan, Z. Y. (2007). “On the machine scheduling problem with job delivery coordination”. European
Journal of Operational Research , 182(3), 1057–1072.
HajiaghaeiKeshteli, M. & Aminnayeri, M. (2014). “ Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm”, 25, 184-203.
SaidiMehrabad, M., DehnaviArani, S. Evazabadian, F. & Mahmoodian, V. (2015). “An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs”, 86, 2-13.
Chen, H. k., Hsue, C. F. & Chang, M. S. (2009). “Production scheduling and vehicle routing with time windows for perishable food products”. Computers & Operation Research, 36(7) 2311-2319.
Liu, Z. Zhang. Y. & Li. M. (2014). “Integrated scheduling of ready-mixed concrete production and delivery”. Automation in
Construction, 48, 31-43.
Averbakh, I., & Xue, Z. (2010). ” On-line supply chain scheduling problems with Preemption”. European Journal of Operational
Research , 181(1), 500–504.
Zegordi, S. H., Abadi, I. N. K., & BeheshtiNia, M. A. (2007). ” A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain”. Computers & Industrial Engineering, 58(3), 373–381.
Cheng, B.Y., Joseph, Y. T., & Li, K.. (2015). “Integrated scheduling of production and distribution to minimize total cost using an improved ant colony optimization method”. Computers & Industrial Engineering, 83, 217-225.
Miller, C. E., Tucker, A. W. & Zemlin, R. A. (1960). “Integer programming formulations and traveling salesman problems”.
Journal of the ACM , 7, 326–329.
Kyparisis, G. J. & Koulamas, C. (2006). “Flexible flow shop scheduling with uniform parallel machines”. European Journal of
Operational Research, 168(3), 985–997.
Pinedo, M. L. “Scheduling: theory, algorithms, and systems”. Springer Science & Business Media (2012).
Garey, M.R. & Johnson, D.S. “Computer and Intractability”. W.H. Freeman and ‘Company, New York (1979).
Geismar,H.N., Laporte,G.L.L. & Sriskandarajah,C. (2008). The integrated production and transportation scheduling problem for a product with a short life span .Informs Journal on Computing, 20, 21-33.