Abstract
This study addresses a two-stage supply chain scheduling problem, where the jobs need to be processed on the manufacturer’s serial batching machine and then transported by vehicles to the customer for further processing. The size and processing time of the jobs are varying due to the differences of types, and setup time is needed before processing one batch. For the problem with minimizing the makespan, we formalize it as a mixed integer programming model. In addition, the structural properties and lower bound of the problem are provided. Based on the analysis above, a novel hybrid dynamic programming algorithm, combining dynamic programming and heuristics, is proposed to solve the problem. Furthermore, its time complexity is also analyzed. By comparing the experimental results of our proposed algorithm with the heuristics \(BFF\) and \(LFF\), we demonstrate that our proposed algorithm has better performance and can solve the problem in a reasonable time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Hall, N.G., Potts, C.N.: Supply chain scheduling: batching and delivery. Oper. Res. 51(4), 566–584 (2003)
Alcali, E., Geunes, J., Pardalos, P.M., Romeijn, H.E., Shen, Z.J.: Applications of Supply Chain Management and E-commerce Research in Industry. Kluwer Academic Publishers, Dordrecht (2004)
Gordon, V.S., Strusevich, V.A.: Single machine scheduling and due date assignment with positionally dependent processing times. Eur. J. Oper. Res. 198(1), 57–62 (2009)
Cheng, T.C.E., Wang, X.: Machine scheduling with job class setup and delivery considerations. Comput. Oper. Res. 37(6), 1123–1128 (2010)
Li, S., Ng, C.T., Cheng, T.C.E., Yuan, J.: Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. Eur. J. Oper. Res. 210(3), 482–488 (2011)
Yeung, W.K., Choi, T.M., Cheng, T.C.E.: Supply chain scheduling and coordination with dual delivery modes and inventory storage cost. Int. J. Prod. Econ. 132(2), 223–229 (2011)
Hwang, F.J., Kovalyov, M.Y., Lin, B.M.T.: Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence. Discret. Optim. 9(1), 29–39 (2012)
Hwang, F.J., Lin, B.M.T.: Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence. J. Oper. Res. Soc. 63(6), 839–845 (2012)
Geunes, J., Pardalos, P.M.: Supply Chain Optimization. Kluwer Academic Publishers, Dordrecht (2003)
Agrawal, V., Chao, X., Seshadri, S.: Dynamic balancing of inventory in supply chains. Eur. J. Oper. Res. 159(2), 296–317 (2004)
Pardalos, P.M., Shylo, O.V., Vazacopoulos, A.: Solving job shop scheduling problems utilizing the properties of backbone and “big valley”. Comput. Optim. Appl. 47(1), 61–76 (2010)
Gong, H., Tang, L.: Two-machine flowshop scheduling with intermediate transportation under job physical space consideration. Comput. Oper. Res. 38(9), 1267–1274 (2011)
Averbakh, I., Xue, Z.: On-line supply chain scheduling problems with preemption. Eur. J. Oper. Res. 181(1), 500–504 (2007)
Kim, H., Jeong, H., Park, J.: Integrated model for production planning and scheduling in a supply chain using benchmarked genetic algorithm. Int. J. Adv. Manuf. Technol. 39(11), 1207–1226 (2008)
You, P.S., Hsieh, Y.C.: A heuristic approach to a single stage assembly problem with transportation allocation. Appl. Math. Comput. 218(22), 11100–11111 (2012)
Mehravaran, Y., Logendran, R.: Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times. Int. J. Prod. Econ. 135(2), 953–963 (2012)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic machine scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)
Gottlieb, J., Raidl, G.R. (eds.): EvoCOP 2006. LNCS, vol. 3906. Springer, Heidelberg (2006)
Koh, S.G., Koo, P.H., Kim, D.C., Hur, W.S.: Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families. Int. J. Prod. Econ. 98(1), 81–96 (2005)
Acknowledgements
This work is supported by the National Natural Science Foundation of China (Nos. 71231004, 71171071, 71131002). Panos M. Pardalos is partially supported by LATNA laboratory, NRU HSE, RF government grant, ag. 11.G34.31.0057.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Pei, J., Liu, X., Fan, W., Pardalos, P.M., Liu, L. (2014). A Novel Hybrid Dynamic Programming Algorithm for a Two-Stage Supply Chain Scheduling Problem. In: Pardalos, P., Resende, M., Vogiatzis, C., Walteros, J. (eds) Learning and Intelligent Optimization. LION 2014. Lecture Notes in Computer Science(), vol 8426. Springer, Cham. https://doi.org/10.1007/978-3-319-09584-4_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-09584-4_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09583-7
Online ISBN: 978-3-319-09584-4
eBook Packages: Computer ScienceComputer Science (R0)