×

New exact and heuristic algorithms for general production and delivery integration. (English) Zbl 07874457

Summary: This study considers a general production and delivery integration problem, commonly faced by a manufacturer that adopts make-to-order and commit-to-delivery business strategies. In the problem, the manufacturer determines acceptance or rejection of customers, produces products for accepted customers, and cooperates with third-party logistics providers who offer multiple shipping modes chosen by the manufacturer to deliver the finished products to customers. To better reflect the practical needs, this problem takes into account nonlinear production cost functions, nonlinear earliness and tardiness penalty functions, and nonlinear shipping cost functions of both shipping time and shipping quantity. The problem is to determine an integrated customer acceptance, production, and delivery plan by minimizing the total cost of production, shipping and inventory holding, and the total penalty of rejection, earliness, and tardiness. We investigate two variants of the problem where splittable delivery for the orders from customers is allowed and where splittable delivery is not allowed. For both the variants, we develop exact algorithms which achieve pseudo-polynomial running time in some practical situations, and design column generation-based heuristic algorithms to find near-optimal solutions efficiently. The computational results demonstrate that the heuristic algorithms are capable of generating near-optimal solutions for the instances generated randomly, with average optimality gap less than 4% in a reasonable running time.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Bachtenkirch, D.; Bock, S., Finding efficient make-to-order production and batch delivery schedules, European Journal of Operational Research, 297, 1, 133-152, 2022 · Zbl 1487.90267
[2] Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38, 1, 22-36, 1990 · Zbl 0699.90052
[3] Chan, L. M.A.; Muriel, A.; Shen, Z.-J.; Simchi-Levi, D., On the effectiveness of zero-inventory-ordering policies for the economic lot-sizing model with a class of piecewise linear cost structures, Operations Research, 50, 6, 1058-1067, 2002 · Zbl 1163.90320
[4] Chan, L. M.A.; Muriel, A.; Shen, Z.-J. M.; Simchi-Levi, D.; Teo, C.-P., Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structures, Management Science, 48, 11, 1446-1460, 2002 · Zbl 1232.90031
[5] Chen, Z.-L., Integrated production and outbound distribution scheduling: review and extensions, Operations Research, 58, 1, 130-148, 2010 · Zbl 1233.90151
[6] Chen, Z.-L.; Hall, N. G., Supply chain scheduling, 2022, Springer · Zbl 1498.90002
[7] Chen, Z.-L.; Pundoor, G., Integrated order scheduling and packing, Production and Operations Management, 18, 6, 672-692, 2009
[8] Falq, A.-E.; Fouilhoux, P.; Kedad-Sidhoum, S., Dominance inequalities for scheduling around an unrestrictive common due date, European Journal of Operational Research, 296, 2, 453-464, 2022 · Zbl 1490.90124
[9] Gordon, V.; Proth, J.-M.; Chu, C., A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research, 139, 1, 1-25, 2002 · Zbl 1009.90054
[10] Gordon, V.; Strusevich, V.; Dolgui, A., Scheduling with due date assignment under special conditions on job processing, Journal of Scheduling, 15, 4, 447-456, 2012 · Zbl 1280.90049
[11] Hall, N. G.; Potts, C. N., Supply chain scheduling: Batching and delivery, Operations Research, 51, 4, 566-584, 2003 · Zbl 1165.90455
[12] Mirzapour Al-e hashem, S. M.J.; Baboli, A.; Sazvar, Z., A stochastic aggregate production planning model in a green supply chain: Considering flexible lead times, nonlinear purchase and shortage cost functions, European Journal of Operational Research, 230, 1, 26-41, 2013 · Zbl 1317.90051
[13] Janiak, A.; Janiak, W. A.; Krysiak, T.; Kwiatkowski, T., A survey on scheduling problems with due windows, European Journal of Operational Research, 242, 2, 347-357, 2015 · Zbl 1341.90002
[14] Koca, E., Lot sizing with nonlinear production cost functions, 2015, Bilkent Universitesi (Turkey), (Ph.D. thesis)
[15] Kramer, A.; Subramanian, A., A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, Journal of Scheduling, 22, 1, 21-57, 2019 · Zbl 1425.90047
[16] Lewis, M.; Singh, V.; Fay, S., An empirical study of the impact of nonlinear shipping and handling fees on purchase incidence and expenditure decisions, Marketing Science, 25, 1, 51-64, 2006
[17] Li, F.; Chen, Z.-L.; Tang, L., Integrated production, inventory and delivery problems: Complexity and algorithms, INFORMS Journal on Computing, 29, 2, 232-250, 2017 · Zbl 1371.90057
[18] Li, K.; Sivakumar, A. I.; Ganesan, V. K., Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain, European Journal of Operational Research, 187, 2, 442-455, 2008 · Zbl 1149.90022
[19] Li, F.; Xu, Z.; Chen, Z.-L., Production and transportation integration for commit-to-delivery mode with general shipping costs, INFORMS Journal on Computing, 32, 1012-1029, 2020 · Zbl 1456.90032
[20] Li, F.; Xu, S.; Xu, Z., New exact and approximation algorithms for integrated production and transportation scheduling with committed delivery due dates and order acceptance, European Journal of Operational Research, 306, 1, 127-140, 2022 · Zbl 1541.90162
[21] Liu, H.; Wang, Y.; Lee, L. H.; Chew, E. P., An approximate dynamic programming approach for production-delivery scheduling under non-stationary demand, Naval Research Logistics, 69, 4, 511-528, 2022 · Zbl 1523.90176
[22] Low, C.; Chang, C.-M.; Li, R.-K.; Huang, C.-L., Coordination of production scheduling and delivery problems with heterogeneous fleet, International Journal of Production Economics, 153, 139-148, 2014
[23] Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023, 2005 · Zbl 1165.90578
[24] Melo, R. A.; Wolsey, L. A., Optimizing production and transportation in a commit-to-delivery business mode, European Journal of Operational Research, 203, 3, 614-618, 2010 · Zbl 1177.90041
[25] Noroozi, A.; Mazdeh, M. M.; Heydari, M.; Rasti-Barzoki, M., Coordinating order acceptance and integrated production-distribution scheduling with batch delivery considering third party logistics distribution, Journal of Manufacturing Systems, 46, 29-45, 2018
[26] Rizk, N.; Martel, A.; Ramudhin, A., A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs, International Journal of Production Economics, 102, 2, 344-357, 2006
[27] Shaw, D. X.; Wagelmans, A. P., An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs, Management Science, 44, 6, 831-838, 1998 · Zbl 0989.90051
[28] Shen, Z.-J. M.; Shu, J.; Simchi-Levi, D.; Teo, C.-P.; Zhang, J., Approximation algorithms for general one-warehouse multi-retailer systems, Naval Research Logistics, 56, 7, 642-658, 2009 · Zbl 1183.90063
[29] Sourd, F., New exact algorithms for one-machine earliness-tardiness scheduling, INFORMS Journal on Computing, 21, 1, 167-175, 2009 · Zbl 1243.90071
[30] Stecke, K. E.; Zhao, X., 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, 2007
[31] Tang, L.; Che, P.; Liu, J., A stochastic production planning problem with nonlinear cost, Computers & Operations Research, 39, 9, 1977-1987, 2012 · Zbl 1251.90111
[32] Ullrich, C. A., Integrated machine scheduling and vehicle routing with time windows, European Journal of Operational Research, 227, 1, 152-165, 2013 · Zbl 1292.90125
[33] Wang, J.; Liu, Z.; Li, F., Integrated production and transportation scheduling problem under nonlinear cost structures, European Journal of Operational Research, 313, 3, 883-904, 2024 · Zbl 07865013
[34] Wilhelm, W. E., A technical review of column generation in integer programming, Optimization and Engineering, 2, 2, 159-200, 2001 · Zbl 1035.90047
[35] Xu, S., New algorithms for integrated production and transportation scheduling problems with committed delivery due dates, 2022, Ph.D. thesis, The Hong Kong Polytechnic University, (Ph.D. thesis)
[36] Yang, X.; Liu, Z.; Li, F.; Xu, Z., Integrated production and transportation scheduling with order-dependent inventory holding costs, Computers & Operations Research, 136, Article 105477 pp., 2021 · Zbl 1511.90228
[37] Yüksel, M.; Karakaya, Y.; Özgü, O.; Kahyaoğlu, A.; Dicleli, D.; Onaran, E.; Akkent, Z.; Gökçe, M. A.; Özkan, S., Applying available-to-promise (ATP) concept in multi-model assembly line planning problems in a make-to-order (MTO) environment, (Digitizing production systems, 2022, Springer), 639-652
[38] Zhao, D.; Li, Z., The impact of manufacturer’s encroachment and nonlinear production cost on retailer’s information sharing decisions, Annals of Operations Research, 264, 1, 499-539, 2018 · Zbl 1391.90037
[39] Zhong, W., An improved algorithm for integrated production and distribution scheduling problem with committed delivery dates, Optimization Letters, 9, 3, 537-567, 2015 · Zbl 1339.90344
[40] Zhong, W.; Chen, Z.-L.; Chen, M., Integrated production and distribution scheduling with committed delivery dates, Operations Research Letters, 38, 2, 133-138, 2010 · Zbl 1185.90107
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.