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

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. [ABSTRACT FROM AUTHOR]