A review of tactical planning models

Abstract

The aim of this paper is to give an overview on models and methods used to solve tactical planning problems. The modeling and the elaboration of the well-know tactical planning problems (master planning & scheduling, material requirement planning and multi-site planning) are discussed. These problems are modeled from two “lot sizing” models called the Capacitated Lot Sizing Problem (CLSP) and Multi Level Capacitated Lot Sizing Problem (MLCLSP). From both models, a lot of extensions has been proposed in the literature. The purpose of this paper is twofold: first, classifications of the CLSP and MLCLSP as well as their extensions are given. For each model, the major scientific contributions are mentioned. These classifications made from seventy papers give an overview of “lot sizing” models dedicated to the MPS, MRP and Multi-site and show the diversity of models. Second, from a classification, an analysis of methods used for each model is given. The instance size, best gap and reference for gap computation are given for each contribution. This work can be used to elaborate an optimization tool for tactical planning problematic such as Advanced Planning System.

Keywords

Tactical planning / lot sizing models / resolution approach

References

[1] Absi, N. & Kedad-Sidhoum, S. (2006). The multi-item capacitated lot-sizing problem with setup-times and shortage costs. Technical report

[2] Afentakis P., Gavish B.. Optimal lot-sizing algorithms for complex product structures. Operations Research, 1986, 34: 237-249.

[3] Aliev R.A., Fazlollahi B., Guirimov B.G., Aliev R.R.. Fuzzy-genetic approach to aggregate production-distribution planning in supply chain management. Information Sciences, 2007, 177(20): 4241-4255.

[4] Barany I., Van Roy T.J., Wolsey L.A.. Strong formulations for multi-items capacitated lotsizing. Management Science, 1984, 30: 1255-1261.

[5] Barbarosoglu G., Özdamar L.. Analysis of solution space-dependent performance of simulated annealing the case of the multilevel capacitated lot sizing problem. Computers and Operational Research, 2000, 27(9): 895-903.

[6] Belvaux G., Wolsey L.A.. Lot-sizing problems: modeling issues and a specialized branch-and-cut system BC-prod. Management Science, 2000, 46(5): 724-738.

[7] Berretta R., Rodrigues L.F.. A memetic algorithm for a multi stage capacitated lot-sizing problem. International Journal Production Economics, 2004, 87: 67-81.

[8] Billington P.J., McClain J.O., Thomas L.J.. Heuristics for multilevel lot-sizing with a bottleneck. Management Science, 1986, 32(8): 989-1006.

[9] Billington P.J., McClain J.O., Thomas L.J.. Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Management Science, 1983, 29: 1126-1141.

[10] Bitran G.R., Yanasse H.H.. Computational complexity of the capacitated lot size problem. Management Science, 1982, 46(5): 724-738.

[11] Blackburn J., Millen R.. An evaluation of heuristic performance in multi stage lot sizing systems. International Journal of Production Research, 1985, 23(5): 857-866.

[12] Blackburn J., Millen R.. Improved heuristics for multi stage requirements planning systems. Management Science, 1982, 28(1): 44-56.

[13] Byrne M.D., Bakir M.A.. Production planning using a hybrid simulation-analytical approach. International Journal of Production Economics, 1999, 59: 305-311.

[14] Chan F.T.S., Chung S.H., Chan S.W.. A hybrid genetic algorithm for production and distribution. Omega, 2005, 33(4): 345-355.

[15] Chen H., Chu C.. A lagrangian relaxation approach for supply chain planning with order-setup costs and capacity constraints. Journal of Systems Science and Systems Engineering, 2003, 12(1): 98-110.

[16] Chen W.H., Thizy J.M.. Analysis of relaxation for the multi-item capacities lot-sizing problem. Annal of Operations Research, 1990, 26: 29-72.

[17] Clark, A.R. (2002). Approximate combinatorial optimization models for large-scale production lot sizing and scheduling with sequence-dependent setup times. In: IV ALIO/EURO Workshop on Applied Combinatorial Optimization, Pucón, Chile

[18] Clark A.R., Armentano V.A.. The application of valid inequalities to the multistage lot-sizing problem. Computers and Operations Research, 1995, 22: 669-680.

[19] Dauzere-Peres S., Lasserre J.B.. On the importance of sequencing decisions in production planning and scheduling. International Transactions in Operational Research, 2002, 9(6): 779-793.

[20] Degraeve Z., Jans R.. A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot sizing model with set-up times. ERIM Report Series in Management ERS-2003-010-LIS, 2003, Rotterdam: Erasmus University

[21] Dellaert N., Jeunet J.. Randomized multi-level lot-sizing heuristics for general product structures. European Journal of Operational Research, 2002, 148(1): 211-228.

[22] Dellaert N., Jeunet J.. Solving large unconstrained multilevel lot-sizing problems using a hybrid genetic algorithm. International Journal of Production Research, 2000, 38(5): 1083-1099.

[23] Diaby M., Bahl M.H., Karwan H.C., Zionts S.. A lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Management Science, 1992, 38(9): 1329-1340.

[24] Diaby M., Bahl M.H., Karwan H.C., Zionts S.. Capacitated lot-sizing and scheduling by lagrangean relaxation. European Journal of Operational Research, 1992, 59: 444-458.

[25] Dixon P.S., Silver E.A.. A heuristic solution procedure for the multi-item, single level, limited capacity, lotsizing problem. Journal of Operations Management, 1981, 2: 23-39.

[26] Dogramaci A., Panayiotopoulos J.C., Adam N.R.. The dynamic lot-sizing problem for multiple items under limited capacity. AIIE Transactions, 1981, 13(4): 294-303.

[27] Drexl A., Kimms A.. Lot sizing and scheduling — survey and extensions. European Journal of Operational Research, 1997, 99: 221-235.

[28] Du Merle O., Goffin J.L., Trouiller C., Vial J.P.. A lagrangian relaxation of the capacitated multi-item lot sizing problem solved with an interior point cutting plane algorithm. Research paper, 1997, Montréal, Canada: McGill University

[29] Eppen G.D., Martin R.K.. Solving multi-item lot-sizing problems using variable redefinition. Operations Research, 1987, 35: 832-848.

[30] Fleischmann, B. & Meyr, H. (2003). Planning hierarchy, modeling and advanced planning systems. In: de Kok, A.G., Graves, S.C. (eds.), Supply Chain Management: Design, Coordination and Operation, Handbooks in Operations Research and Management Science, 11: pp. 457–502

[31] Franca P.M., Armentano V.A., Berretta R.E., Clark A. R.. A heuristic for lot-sizing in multi-stage systems. Computers nd Operations Research, 1997, 24(9): 861-874.

[32] Garavelli A.C., Geoffrey O., Garavelli N.V.. Global manufacturing systems: a model supported by genetic algorithms to optimize production planning. Computers & Industrial Engineering, 1996, 31(1–2): 193-196.

[33] Gelders, L.F., Maes, J. & Van Wassenhove, L.N. (1986). A branch and bound algorithm for the multi-item single level capacitated dynamic lotsizing problem, multi-stage production planning and inventory control. Lectures Notes in Economics and Mathematical Systems, 92–108

[34] Génin, P. (2003). Planification tactique robuste avec usage d’un A.P.S. Proposition d’un mode de gestion par plan de référence. PhD thesis, Ecole supérieure des mines de Paris

[35] Gilbert K.C., Madan M.S.. A heuristic for a class of production planning and scheduling problems. IIE Transactions, 1991, 23: 282-289.

[36] Gnoni M.G., Iavagnilio R., Mossa G., Mummolo G., Di Leva A.. Production planning of a multi-site manufacturing system by hybrid modelling: a case study from the automotive industry. International Journal of Production Economics, 2003, 85: 251-262.

[37] Gopalakrishnan M., Ding K., Bourjolly J.M., Mohan S.. A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Management Science, 2001, 47(6): 851-863.

[38] Guinet A.. Multi-site planning: a transshipment problem. International Journal of Production Economics, 2001, 74(1–3): 21-32.

[39] Gupta A., Maranas C.D.. Managing demand uncertainty in supply chain planning. Computer and Chemical Engineering, 2003, 27: 219-1227.

[40] Gupta D., Magnusson T.. The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers & Operations Research, 2005, 32: 727-747.

[41] Haase, K. & Kohlmorgen, U. (1995). Parallel genetic algorithm for the capacitated lotsizing problem. Operations Research Proceedings, 370–375

[42] Hagdorn L., van Numen J., Ramondt A.. Forecasting-bridging the gap between sales and manufacturing. International Journal of Productions Economics, 1994, 37: 101-114.

[43] Hassini, E. (2006). Order lot sizing with multiple capacitated suppliers offering lead time-dependent capacity reservation and unit price discounts. Production Planning Control, in press

[44] Haugen, K.K., Olstad, A. & Pettersen, B.I. (2006). The profit maximizing capacitated lot-size (PCLSP) problem. European Journal of Operational Research, in press

[45] Heinrich C., Schneeweiss C.. Axsater S., Schneeweiss C., Silver E.. Multi-stage lot-sizing for general production systems. Lecture Notes in Economics and Mathematical Systems, 1986, Heidelberg, Germany: Springer Verlag

[46] Hindi K.S.. Solving the CLSP by a tabu search heuristic. Journal of Operational Research Society, 1996, 47(1): 151-161.

[47] Hindi K.S.. Computationally efficient solution of multi-item capacitated lot sizing problems. Computers and Industrial Engineering, 1995, 28(4): 709-719.

[48] Hindi K.S., Fleszar K., Charalambous C.. An effective heuristic for the CLSP with set-up times. Journal of Operational Research Society, 2003, 54: 490-498.

[49] Huisman, D., Jans, R., Peeters, M. & Wagelmans, A.P.M. (2003). Combining column generation and lagrangian relaxation. Technical Report

[50] Jeunet J., Jonard N.. Single-point stochastic search algorithms for the multi-level lot-sizing problem. Computers and Operations Research, 2005, 32(4): 985-1006.

[51] Kanayalkar A.P., Adil G.K.. An integrated aggregate and detailed planning in a multi-site production environment using linear programming. International Journal of Production Research, 2005, 43(20): 4431-4454.

[52] Karimi B., Fatemi Ghomi S.M.T., Wilson J.M.. A tabu-search heuristic for the clsp with backlogging and set-up carry-over. Journal of Operational Research Society, 2005, 47(6): 851-863.

[53] Karimi B., Fatemi Ghomi S.M.T., Wilson J.M.. The capacitated lot sizing problem: a review of models and algorithms. Omega, 2003, 31(5): 365-378.

[54] Katok E., Lewis H.S., Harrison T.P.. Lot sizing in general assembly systems with setup costs, setup times, and multiple constrained resources. Management Science, 1998, 44(6): 859-877.

[55] Kim H.J., Hosni Y.A.. Manufacturing lot-sizing under MRP II environment: an improved analytical model and a heuristic procedure. Computers and Industrial Engineering, 1998, 35(3): 423-426.

[56] Kirca, Kökten M.. A new heuristic approach for the multi-item dynamic lot sizing problem. European Journal of Operational Research, 1994, 75: 332-341.

[57] Kuik R., Salomon M.. Multi-level lot-sizing problem: evaluation of a simulated annealing heuristic. European Journal of Operational Research, 1990, 45(1): 25-37.

[58] Kuik R., Salomon M., Van Wassenhove L.N., Maes J.. Linear programming, simulated annealing and tabu search heuristics for lotsizing in bottleneck assembly system. IIE Transactions, 1993, 25(1): 62-72.

[59] Lambrecht M., Vanderveken H.. Heuristic procedures for the single operation multi item loading problem. AIIE Transactions, 1979, 11: 319-326.

[60] Leung J.M., Magnanti T.L., Vachani R.. Facets and algorithms for the capacitated lot sizing. Mathematical Programming, 1989, 45: 331-359.

[61] Lin J.T., Chen Y.Y.. A multi-site supply network planning problem considering variable time buckets— a TFL-LCD industry case. International Journal Manufacturing Technology, 2007, 33: 1031-1044.

[62] Liu M.L., Sahinidis N.V.. Optimization in process planning under uncertainty. Industrial Engineering Chemical Research, 1996, 35511: 4154-4165.

[63] Maes J., McClain J.O., Van Wassenhove L.N.. Multilevel capacitated lotsizing complexity and LP-based heuristics. European Journal of Operations Research, 1991, 53: 131-148.

[64] Maes J., Van Wassenhove L.N.. A simple heuristic for the multi-item single level capacitated lot sizing problem. Letters of the Operational Research Society, 1986, 4: 265-274.

[65] Manne A.S.. Programming of economic lot sizes. Management Science, 1958, 4: 115-135.

[66] Marty, C. (1997). Le juste à temps produire autrement. 2ème édition, Edition Hermes, 124

[67] McDonald C.M., Karimi I.A.. Planning and scheduling of parallel semicontinuous processes. 1. production planning. Industrial Engineering Chemical Research, 1997, 36: 2691-2700.

[68] Miller, A.J., Nemhauser, G.L. & Savelsbergh, M.W.P. (2000). Solving multi-item capacitated lot-sizing problems with setup-times by branch-and-cut. Technical Report

[69] Olhager J., Rudberg M., Wikner J.. Long-term capacity management: linking the perspectives from manufacturing strategy and sales and operations planning. International Journal of Production Economics, 2001, 69(2): 215-225.

[70] Orlicky J.. Material Requirements Planning, 1975, London: McGraw-Hill

[71] Özdamar L., Barbarosoglu G.. An integrated Lagrangean relaxationsimulated annealing approach to the multi-level multi-item capacitated lot sizing problem. International Journal of Production Economics, 2000, 68: 319-331.

[72] Özdamar L., Bozyel M.A.. The capacitated lot sizing problem with overtime decisions and setup times. IIE Transactions, 2000, 32: 1043-1057.

[73] Özdamar L., Birbil S.I., Portmann M.C.. Technical note: new result for the capacitated lot sizing problem with overtime decisions and setup times. Production Planning & Control, 2002, 13(1): 2-10.

[74] Pochet Y., Wolsey L.. Solving multi-item lot-sizing problems using strong cutting planes. Management Science, 1991, 37: 53-67.

[75] Pibernik R., Sucky R.. An approach to inter-domain master planning in supply chains. International Journal Production Economics, 2007, 108: 200-212.

[76] Pirkul H., Jayaraman V.. A multi commodity, multi plant, capacitated facility location problem: formulation and efficient heuristic solution. Computers Operation Research, 1998, 25(10): 869-878.

[77] Rizk, N. & Martel, A. (2001). Supply chain flow planning methods: a review of the lot-sizing literature. Working paper, DT-2001-AM-1, Université Laval (Canada)

[78] Roll Y., Karni R.. Multi item, multi level lot sizing with an aggregate capacity constraint. European Journal of Operational Research, 1991, 51: 73-87.

[79] Rota, K. (1998). Coordination temporelle de centres gérant de façon autonome des ressources. Application aux chaínes logistiques intégrées en aéronautique. PhD Thesis, ENSAE

[80] Salomon M., Kuik R., Van Wassenhove L.N.. Statistical search methods for lot-sizing problems. Annals Operations Research, 1993, 41: 453-468.

[81] Sambasivan M., Yahya S.. A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers. Computers & Operations Research, 2005, 32(3): 537-555.

[82] Stadler H.. Mixed integer programming model formulations for dynamic multi-item multi-level capacitated lotsizing. European Journal of Operational Research, 1996, 94: 561-581.

[83] Tang O.. Simulated annealing in lot sizing problem. International Journal of Production Economics, 2004, 88(2): 173-181.

[84] Tempelmeier H., Derstro M.. A Lagrangean based heuristic for dynamic multi-item multi-level constrained lot sizing with setup times. Management Science, 1996, 42: 738-758.

[85] Tempelmeier H., Helber S.. A heuristic for dynamic multi-item multi-level capacitated lotsizing for general product structures. European Journal of Operations. Research, 1994, 75: 296-311.

[86] Thierry, C., Chapeaublanc, N., Lepage, P. & Bel, G. (1994). Multi-site planning: a centralized or a distributed approach?. In: Conference INRIA, Sophia Antipolis, France

[87] Thizy J.M., Van Wassenhove L.N.. Relaxation for the multi-item capacitated lotsizing problem: a heuristic implementation. IIE Transactions, 1985, 17: 308-313.

[88] Timpe C.H., Kallrath J.. Optimal planning in large multi-site production networks. European Journal of Operational Research, 2000, 126: 422-435.

[89] Torabi, S.A. & Hassini, E. (2007). An interactive possibilistic programming approach for multipleobjective supply chain master planning. Fuzzy Sets and System, in press

[90] Trigeiro W.W., Thomas L.J., McClain J.O.. Capacitated lot sizing with setup times. Management Science, 1989, 35: 353-366.

[91] Vob S., Woodruff D.L.. Introduction to Computational Optimization Models for Production Planning in a Supply Chain, 2003, Heidelberg: Springer-Verlag Berlin

[92] Vollmann, T.E., Berry, D.W. & Whybark, D.C. (1997). Manufacturing Planning and Control Systems, 4th ed. New York et al.

[93] Voros J.. On the relaxation of multi-level dynamic lot-sizing models. International Journal of Production Economics, 2002, 77(1): 53-61.

[94] Wagner H.M., Whitin T.M.. Dynamic version of the economic lot sizemodel. Management Science, 1958, 5: 89-96.

[95] Wight, O. (1984). Manufacturing Resource Planning: MRP II: Unlocking America’s Productivity Potential Revised Edition. Oliver Wight editor

[96] Xie J., Dong J.. Heuristic genetic algorithms for GCLSP. Computers and Mathematics with Applications, 2002, 44: 263-276.

[97] Xie, J., Lee, T.S. & Zhao, X. (2004). Impact of forecasting error on the performance of capacitated multi-item production systems. Computers & Industrial Engineering, in press