  Capacitated lot-sizing problems (CLSPs) are important and challenging
optimization problems in production planning. Amongst the many approaches
developed for CLSPs, constructive heuristics are known to be the most intuitive
and fastest method for finding good feasible solutions for the CLSPs, and
therefore are often used as a subroutine in building more sophisticated exact
and metaheuristic approaches. Classical constructive heuristics, such as the
period-by-period heuristics and lot elimination heuristics, are first
introduced in the 1990s, and thereafter widely used in solving the CLSPs. This
paper evaluates the performance of period-by-period and lot elimination
heuristics, and improves the heuristics using perturbation techniques and
self-adaptive methods. We have also proposed a procedure for automatically
adjusting the parameters of the proposed heuristics so that the values of the
parameters can be chosen based on features of individual instances.
Experimental results show that the proposed self-adaptive randomized
period-by-period constructive heuristics are efficient and can find better
solutions with less computational time than the tabu search and lot elimination
heuristics. When the proposed constructive heuristic is used in a basic tabu
search framework, high-quality solutions with 0.88% average optimality gap can
be obtained on benchmark instances of 12 periods and 12 items, and optimality
gap within 1.2% for the instances with 24 periods and 24 items.
