Abstract
In this paper, we study the zero-inventory production and distribution problem with a single transporter and a fixed sequence of customers. The production facility has a limited production rate, and the delivery truck has non-negligible traveling times between locations. The order in which customers may receive deliveries is fixed. Each customer requests a delivery quantity and a time window for receiving the delivery. The lifespan of the product starts as soon as the production for a customer’s order is finished, which makes the product expire in a constant time. Since the production facility and the shipping truck are limited resources, not all the customers may receive the delivery within their specified time windows and/or within product lifespan. The problem is then to choose a subset of customers from the given sequence to receive the deliveries to maximize the total demand satisfied, without violating the product lifespan, the production/distribution capacity, and the delivery time window constraints. We analyze several fundamental properties of the problem and show that these properties can lead to a fast branch and bound search procedure for practical problems. A heuristic lower bound on the optimal solution is developed to accelerate the search. Empirical studies on the computational effort required by the proposed search procedure comparing to that required by CPLEX on randomly generated test cases are reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chen, Z. L. (2002). Integrated production and distribution operations: Taxonomy, models, and review. In Supply chain analysis in the e-business era. Dordrecht: Kluwer Academic.
Cheng, T. C. E., & Gordon, V. S. (1994). On batch delivery scheduling on a single machine. Journal of the Operational Research Society, 45, 1211–1216.
Cheng, T. C. E., Gordon, V. S., & Kovalyov, M. Y. (1996). Single machine scheduling with batch deliveries. European Journal of Operations Research, 94, 277–283.
Cheng, T. C. E., Kovalyov, M. Y., & Lin, B. M.-T. (1997). Single machine scheduling to minimize batch delivery and job earliness penalties. SIAM Journal of Optimization, 7, 547–559.
Dueck, G., & Scheuer, T. (1990). Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90, 161–175.
Geismar, N., Laporte, G., Lei, L., & Sriskandarajah, C. (2007, in press). The integrated production and transportation scheduling problem with expiring product and non-instantaneous transportation time. INFORMS Journal on Computing.
Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: Batching and delivery. Operations Research, 51(4), 566–584.
Hall, L., & Shmoys, D. (1989). Approximation schemes for constrained scheduling problems. In Proceedings of the 30th annual symposium on foundations of computer science (Vol. 30, pp. 134–140).
Hurter, A. P., & Van Buer, M. G. (1996). The newspaper production/distribution problem. Journal of Business Logistics, 17, 85–107.
Lee, C.-Y., & Chen, Z.-L. (2001). Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3–24.
Pinedo, M. (1995). Scheduling: Theory, algorithms, and systems. New York: Prentice Hall.
Potts, C. N. (1980). An analysis of a heuristic for one machine sequencing with release dates and delivery time. Operations Research, 28, 1436–1441.
Tarantilis, C. D., & Kiranoudis, C. T. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering, 50, 1–9.
Van Buer, M. G., Woodruff, D. L., & Olson, R. T. (1999). Solving the medium newspaper production/distribution problem. European Journal of Operations Research, 115, 237–253.
Wang, G., & Cheng, T. C. E. (2000). Parallel machine scheduling with batch delivery costs. International Journal of Production and Economics, 68, 177–183.
Woeginger, G. J. (1998). Polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times. Journal of Scheduling, 1, 79–87.
Yuan, J. A. (1996). A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs. European Journal of Operational Research, 94, 203–205.
Zdrzalka, S. (1995). Analysis of approximation algorithms for single-machine scheduling with delivery times and sequence independent batch setup times. European Journal of Operational Research, 80, 371–380.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Armstrong, R., Gao, S. & Lei, L. A zero-inventory production and distribution problem with a fixed customer sequence. Ann Oper Res 159, 395–414 (2008). https://doi.org/10.1007/s10479-007-0272-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0272-3