Approximate model and algorithms for precast supply chain scheduling problem with time-dependent transportation times

Abstract

This paper focuses on the precast supply chain scheduling problem with time-dependent transportation time to minimise the total weighted tardiness (PSCSP_TDT |TWT). In the problem, an order sequence and several job sequences are to be determined simultaneously. At first, through in-depth analysis of problem structure and real data from a precast manufacturer, we approximate the problem into a three-stage order scheduling problem by combining the seven production stages into one differentiation stage, and then explore some useful properties of the schedules for the approximate problem. Subsequently, to solve the small instances for the PSCSP_TDT |TWT, we propose an approximate model-based hybrid dynamic programming and heuristic (AMHDPH) and obtain a lower bound as a by-product of the algorithm. For dealing with medium-or large instances, with considering the complexity of the problem, we propose four approximate model-based hybrid iterated greedy (AMHIG) algorithms by integration of constructive heuristics, structural properties of solutions, an iterated greedy, and a correction heuristic. Comprehensive computational results show that the AMHDPH generates tight lower bounds for small instances and solves the most of small instances to optimality within 60 seconds. Whereas the best AMHIG generates feasible solutions with an average optimality gap below 5 percent for around 70 percent instances.

Keywords:

• Scheduling
• precast supply chain system
• approximate model
• iterated greedy algorithm
• time-dependent transportation times

Acknowledgements

The authors would like to thank the editors and the two anonymous reviewers for their insightful comments and inspirational suggestions on this study.

Data availability statement

The authors confirm that the data supporting the findings of this study are available within the article and/or its supplementary materials as indicated in the paper, further inquiries can be directed to the corresponding author. All tested instances are available at: http://dx.doi.org/10.13140/RG.2.2.25557.35040.

Disclosure statement

No potential conflict of interest was supported by the authors.

Additional information

Funding

This work is supported in part by the National Natural Science Foundation of China under Grants 61473216, the Natural Science Basic Research Program of Shaanxi Province of China (Program No. 2020JM-489 and No. 2015JM6337), Scientific Research Program Funded by Shaanxi Provincial Education Department (Key Scientific Research Project of Education Department of Shaanxi Province) (Program No. 17JK0459), Basic Research Foundation of Xi'an University of Architecture and Technology, (Program No. ZR18049) and I would like to thank the Support Program from China Scholarship Council (Program No. 201608610008).

Notes on contributors

Fuli Xiong

Fuli Xiong received the B.E. degree in Applied Geophysics from Northeast Petroleum University, Daqing, China, in 1998, M.E. degree in Control Theory and Control Engineering from Petroleum University of China, Qingdao, China, in 2003, and Ph.D. degree in Control Theory and Control Engineering from Southeast University, Nanjing, China, in 2011. Afterwards, he worked as a postdoctoral of the Institute of System Engineering, Xi'an Jiaotong University from 2011 to 2013. He is currently an associate professor with the School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an, China. Meanwhile, he was supported by the China Scholarship Council to work as a Visiting Scholar, from 2016 to 2017 with the Manufacturing Computing Lab, University of Connecticut, USA. His research interests include integrated production and distributed scheduling, production planning and scheduling, and large-scale optimisation.

Siyuan Chen

Siyuan Chen received the B.E. degree in Engineering Management from Shenyang Jianzhu University, Shenyang, China. She is currently working toward the Master degree with the School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an, China. Her research interests include production scheduling and supply chain management.

Zongfang Ma

Zongfang Ma received the B.E. degree in Communication Engineering and M.E. degrees in Computer Technology from Xi'an University of Architecture and Technology, Xi'an, China, and Ph.D. degree in Control Science and Engineering from Northwestern Polytechnical University, Xi'an, China, in 2002, 2006 and 2011, respectively. He is currently a professor with the School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an, China. His research interests include combinatorial optimisation, machine learning and pattern recognition.

Linlin Li

Linlin Li received the B.E. degree in Software Engineering from Xi'an University of Architecture and Technology, Xi'an, China. She is currently working toward the Master degree with the School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an, China. Her research interests include production planning, scheduling, and supply chain management.