Integrated production and distribution scheduling with lifespan constraints. (English) Zbl 1302.90089

Summary: We consider an integrated production and distribution scheduling problem in a make-to-order business scenario. A product with a short lifespan (e.g., perishable or seasonal) is produced at a single production facility with a limited production rate. This means that the product expires in a constant time after its production is finished. Orders are received from a set of geographically dispersed customers, where a demand for the product and a time window for the delivery is associated with each customer for the planning period. A single vehicle with non-negligible traveling times between the locations is responsible for the deliveries. Due to the limited production and distribution resources, possibly not all customers may be supplied within their time windows or the lifespan. The problem consists in finding a selection of customers to be supplied such that the total satisfied demand is maximized. We extend the work by R. Armstrong et al. [Ann. Oper. Res. 159, 395–414 (2008; Zbl 1152.90301)] on the problem for fixed delivery sequences by pointing out an error in their branch and bound algorithm and presenting a corrected variant. Furthermore, we introduce model extensions for handling delays of the production start as well as for variable production and distribution sequences. Efficient heuristic solution algorithms and computational results for randomly generated instances are presented.


90B35 Deterministic scheduling theory in operations research


Zbl 1152.90301


Tabu search
Full Text: DOI


[1] Armstrong, R., Gao, S., & Lei, L. (2008). A zero-inventory production and distribution problem with a fixed customer sequence. Annals of Operations Research, 159(1), 395–414. · Zbl 1152.90301
[2] Azi, N., Gendreau, M., & Potvin, J. Y. (2007). An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European Journal of Operational Research, 178(3), 755–766. · Zbl 1159.90306
[3] Chen, Z. L. (2010). Integrated production and outbound distribution scheduling: review and extensions. Operations Research, 58(1), 130–148. · Zbl 1233.90151
[4] Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581.
[5] Garcia, J. M., & Lozano, S. (2005). Production and delivery scheduling problem with time windows. Computers & Industrial Engineering, 48(4), 733–742.
[6] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman. · Zbl 0411.68039
[7] 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. · Zbl 1243.90023
[8] Glover, F., & Laguna, M. (1997). Tabu search. Dordrecht: Kluwer Academic. · Zbl 0930.90083
[9] Lourenço, H., Martin, O., & Stützle, T. (2003). Iterated local search. In F. Glover & G. A. Kochenberger (Eds.), Handbook of metaheuristics (pp. 321–353). Dordrecht: Kluwer Academic. · Zbl 1116.90412
[10] Savelsbergh, M. W. P. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4(1), 285–305.
[11] Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265. · Zbl 0625.90047
[12] Stecke, K. E., & Zhao, X. (2007). Production and transportation integration for a make-to-order manufacturing company with a commit-to-delivery business mode. Manufacturing Service Operations Management, 9(2), 206–224.
[13] Tarantilis, C. D., & Kiranoudis, C. T. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering, 50(1), 1–9.
[14] Tsirimpas, P., Tatarakis, A., Minis, I., & Kyriakidis, E. G. (2008). Single vehicle routing with a predefined customer sequence and multiple depot returns. European Journal of Operational Research, 187(2), 483–495. · Zbl 1149.90024
[15] Van Buer, M. G., Woodruff, D. L., & Olson, R. T. (1999). Solving the medium newspaper production/distribution problem. European Journal of Operational Research, 115(2), 237–253. · Zbl 0938.90022
[16] Viergutz, C. (2011). Integrated production and distribution scheduling. PhD thesis, University of Osnabrück, Department of Mathematics and Computer Science. · Zbl 1302.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.