Improved formulations, heuristics and metaheuristics for the dynamic demand coordinated lot-sizing problem

Coordinated lot sizing problems, which assume a joint setup is shared by a product family, are commonly encountered in supply chain contexts. Total system costs include a joint set-up charge each time period any item in the product family is replenished, an item set-up cost for each item replenished in each time period, and inventory holding costs. Silver (1979) and subsequent researchers note the occurrence of coordinated replenishment problems within manufacturing, procurement, and transportation contexts. Due to their mathematical complexity and importance in industry, coordinated lot-size problems are frequently studied in the operations management literature. In this research, we address both uncapacitated and capacitated variants of the problem. For each variant we propose new problem formulations, one or more construction heuristics, and a simulated annealing metaheuristic (SAM). We first propose new tight mathematical formulations for the uncapacitated problem and document their improved computational efficiency over earlier models. We then develop two forward-pass heuristics, a two-phase heuristic, and SAM to solve the uncapacitated version of the problem. The two-phase and SAM find solutions with an average optimality gap of 0.56% and 0.2% respectively. The corresponding average computational requirements are less than 0.05 and 0.18 CPU seconds. Next, we propose tight mathematical formulations for the capacitated problem and evaluate their performance against existing approaches. We then extend the two-phase heuristic to solve this more general capacitated version. We further embed the six-phase heuristic in a SAM framework, which improves heuristic performance at minimal additional computational expense. The metaheuristic finds solutions with an average optimality gap of 0.43% and within an average time of 0.25 CPU seconds. This represents an improvement over those reported in the literature. Overall the heuristics provide a general approach to the dynamic demand lot-size problem that is capable of being applied as a stand-alone solver, an algorithm embedded with supply chain planning software, or as an upper-bounding procedure within an optimization based algorithm. Finally, this research investigates the performance of alternative coordinated lotsizing procedures when implemented in a rolling schedule environment. We find the perturbation metaheuristic to be the most suitable heuristic for implementation in rolling schedules.