×

Production scheduling with supply and delivery considerations to minimize the makespan. (English) Zbl 1162.90017

Summary: We study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O\((n)\) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.

MSC:

90B40 Search theory
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Chang, Y.-C.; Lee, C.-Y., Machine scheduling with job delivery coordination, European Journal of Operational Research, 158, 470-487 (2004) · Zbl 1067.90041
[2] Chen, Z.-L.; Vairaktarakis, G. L., Integrated scheduling of production and distribution operations, Management Science, 51, 614-628 (2005) · Zbl 1145.90380
[3] Cheng, T. C.E.; Gordon, V. S.; Kovalyov, M. Y., Single machine scheduling with batch deliveries, European Journal of Operational Research, 94, 277-283 (1996) · Zbl 0947.90579
[4] Cheng, T. C.E.; Kovalyov, M. Y.; Lin, B. M.T., Single machine scheduling to minimize batch delivery and job earliness penalties, SIAM Journal on Optimization, 7, 547-559 (1997) · Zbl 0874.68142
[5] Erengüc, S. S.; Simpson, N. C.; Vakharia, A. J., Integrated production/distribution planning in supply chains, European Journal of Operational Research, 115, 219-236 (1999) · Zbl 0949.90658
[6] Hall, N. G.; Potts, C. N., Supply chain scheduling: Batch and delivery, Operations Research, 51, 566-584 (2003) · Zbl 1165.90455
[7] Lee, C.-Y.; Chen, Z.-L., Machine scheduling with transportation considerations, Journal of Scheduling, 4, 3-24 (2001) · Zbl 0979.90055
[8] Li, C.-L.; Ou, J.-W., Machine scheduling with pickup and delivery, Naval Research Logistics, 52, 1-14 (2005)
[9] Li, C.-L.; Vairaktarakis, G. L.; Lee, C.-Y., Machine scheduling with deliveries to multiple customer locations, European Journal of Operational Research, 164, 39-51 (2005) · Zbl 1132.90329
[10] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028
[11] Potts, C. N.; Van Wassenhove, L. N., Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, Journal of the Operational Research Society, 43, 395-406 (1992) · Zbl 0756.90050
[12] Pundoor, G.; Chen, Z.-L., Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and distribution cost, Naval Research Logistics, 52, 571-589 (2005) · Zbl 1122.90358
[13] Quadt, D.; Kuhn, H., Batch scheduling of jobs with identical process times on flexible flow lines, International Journal of Production Economics, 105, 385-401 (2007)
[14] Schaller, J., Scheduling on a single machine with family setups to minimize total tardiness, International Journal of Production Economics, 105, 329-344 (2007)
[15] Thomas, D. J.; Griffin, P. M., Coordinated supply chain management, European Journal of Operational Research, 94, 1-15 (1996) · Zbl 0929.90004
[16] Wang, X-. L.; Cheng, T. C.E., Machine scheduling with an availability constraint and job delivery coordination, Naval Research Logistics, 54, 11-20 (2007) · Zbl 1124.90011
[17] Wang, H.; Lee, C.-Y., Production and transport logistics scheduling with two transport mode choices, Naval Research Logistics, 52, 796-809 (2005) · Zbl 1278.90175
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.