Abstract
In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP+, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bitran GB and Yanasse HH (1982). Complexity of the capacitated lot size problem. Mngt Sci 28: 1174–1185.
Florian M, Lenstra JK and Rinnooy Kan AHG (1980). Deterministic production planning: Algorithms and complexity. Mngt Sci 26: 669–679.
Sox CR and Gao Y (1999). The capacitated lot sizing problem with setup carry-over. IIE Trans 31: 173–181.
Baker KR (1990). Lot-sizing procedures and a standard data set: a reconciliation of the literature. J Manuf Opns Mngt 2: 199–221.
Debodt M, Gelders L and Van Wassenhove LN (1984). Lot-sizing under dynamic demand conditions: a review. Eng Costs Prod Econ 8: 165–187.
Drexl A and Kimms A (1997). Lot sizing and scheduling—survey and extensions. Eur J Opl Res 99: 221–235.
Maes J and Van Wassenhove LN (1988). Multi-item single-level capacitated dynamic lot sizing heuristics: a general review. J Opl Res Soc 39: 991–1004.
Karimi B, Fatemi Ghomi SM and Wilson JM (2003). The capacitated lot sizing problem: a review of models and algorithms. OMEGA 31: 365–378.
Pochet Y and Wolsey L (1988). Lot size models with backlogging: strong reformulations and cutting planes. Math Prog 40: 317–335.
Barany I, Van Roy TJ and Wolsey LA (1984). Strong formulations for multi-item capacitated lot sizing. Mngt Sci 30: 1255–1261.
Eppen GA and Martin RK (1987). Solving multi-item capacitated lot sizing problems using variable redefinition. Opns Res 35: 832–848.
Millar HH and Yang M (1994). Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering. Int J Prod Econ 34: 1–15.
Dillenberger C, Escudero LF, Wollensak A and Zhang W (1994). On practical resource allocation for production planning and scheduling with period over-lapping setups. Eur J Opl Res 75: 275–286.
Gopalakrishnan M, Miller DM and Schmidt CP (1995). A framework for modeling setup carryover in the capacitated lot sizing problem. Int J Prod Res 33: 1973–1988.
Haase K (1996). Capacitated lot-sizing with sequence dependent setup costs. OR Spektrum 18: 51–59.
Karimi B and Fatemi Ghomi SMT (2002). A new heuristic for the CLSP problem with backlogging and set-up carryover. Int J Adv Manuf Sys 5 (2): 66–77.
Groff GK (1979). A lot sizing rule for time-phased component demand. Prod Inv Mngt 20: 47–53.
Dogramaci A, Panayiotopoulos JC and Adam NR (1981). The dynamic lot-sizing problem for multiple items under limited capacity. AIIE Trans 13: 294–303.
Ali AI, Padman R and Thiagarajan H (1989). Dual algorithms for pure network problems. Opns Res 37: 158–171.
Bertsekas D and Tseng P (1988). Relaxation methods for minimum cost ordinary and generalized network flow problems. Opns Res 36: 93–114.
Grigoriadis MD (1986). An efficient implementation of the network simplex method. Math Prog Study 26: 83–111.
Goldberg AV (1997). An efficient implementation of a scaling minimum-cost flow algorithm. J Algorithms 22: 1–29.
Glover F (1987). Tabu search methods in artificial intelligence and operations research. ORSA Artif Intell Newslett 1: 6.
Hansen P (1986). The steepest ascent mildest descent heuristic for combinatorial optimization. Presented at the Congress on Numerical Methods in Combinatorial Optimization, Italy, Capri.
Glover F (1996). Tabu search. In: Gass S and Harris C (eds). Encyclopedia of Operations Research and Management Science. Kluwer Academic Publishers: Dordrecht, pp 671–678.
Glover F (1998). Tabu search—wellsprings and challenges. Eur J Opl Res 106: 221–225.
Glover F and M Laguna M (1998). Tabu Search. Kluwer Academic Publishers: Dordrecht.
Glover F, Taillard E and De Werra D (1993). A user's guide to tabu search. Ann Opns Res 41: 3–28.
Hindi KS (1996). Solving the CLSP by a tabu search heuristic. J Opl Res Soc 47: 151–161.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Karimi, B., Ghomi, S. & Wilson, J. A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over. J Oper Res Soc 57, 140–147 (2006). https://doi.org/10.1057/palgrave.jors.2601968
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2601968