Return to search

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.

Identiferoai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-1802
Date02 June 2009
CreatorsNarayanan, Arunachalam
ContributorsRobinson, E. Powell
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeBook, Thesis, Electronic Dissertation, text
Formatelectronic, application/pdf, born digital

Page generated in 0.0019 seconds