A Hyperheuristic Approach for Dynamic Multilevel Capacitated Lot Sizing with Linked Lot Sizes for APS implementations

Yıl 2017, Cilt: 12 Sayı: 45, 1 - 13, 22.02.2017

Mahmut Ali Gökçe , Berkay Beygo Turgut Ekmekçi

Öz

This study is concerned with solving real-life sized APS problems practically. Specifically, the problem of Multilevel Capacitated Lot Sizing Problem with linked lot sizes (MLCLSP-L) is considered. The problem is a classical, practical and notoriously hard problem. We propose a new modeling technique for MLCLSP-L based on a GA-driven hyperheuristic, which enables modeling of some issues previously not modeled. Proposed model uses an indirect representation by allowing GA search through a space of low level heuristics. Each one of the low level heuristics is simple and determines the detailed production plan of a machine in a period. The solution is constructed through combination of these low level heuristics. New model is demonstrated by solving moderate size test problem along with software developed.

Kaynakça

• Bai R., Burke E.K. and Kendall G. (2008) Heuristic, Meta-heuristic and Hyper-heuristic Approaches for Fresh Produce Inventory Control and Shelf Space Allocation. Journal of the Operational Research Society, 59(10), pages 187-1397.
• Bitran, G.R., Yanasse, H.H. (1982). Computational complexity of the capacitated lot size problem, Management Science 28, 1174-1186.
• Blackstone, John H., and James F. Cox. 2005. APICS dictionary. Alexandria, VA: APICS
• Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., and Schulenburg, S., 2003, Handbook of metaheuristics, chapter 16, Hyper-heuristics: an emerging direction in modern search technology, pp. 457--474. Kluwer Academic Publishers,
• Chaklevitch K., Cowling, P.:Hyperheuristics: Recent Developments. In: Cotta, C., Sevaux, M., and Srensen, K.(eds.), 2008, Adaptive and Multilevel Metaheuristics (Studies in Computational Intelligence), pp 3-29, Springer Publishing Company, Incorporated
• Chen, W.H., Thizy, J.M., 1990, Analysis of relaxations for the multi-item capacitated lot-sizing problem, Annals of Operations Research 26, 29–72.
• Cowling, P., Kendall, G., Soubeiga, E.: A hyperheuristic approach to scheduling a sales summit. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 176–190. Springer, Heidelberg (2001)
• De Kok, A.G and Graves, S.C. (2003). Handbook in Operations Research and Management Science Vol. 11- Supply Chain Management: Design, Coordination and Operation, Elsevier, Amsterdam.
• Denizel, M and Süral, H (2006). On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times, Journal of the Operational Research Society , 57 (4), 389-399.
• Drexl A., & Kimms A. (1997). Lot sizing and scheduling – survey and extensions. European Journal of Operations Research 99, 221-235.
• Drexl, A., Haase, K. (1995). Proportional lot sizing and scheduling, International Journal of Production Economics 40, 73-87.
• Fleischmann, B. (1990). The discrete lot-sizing and scheduling problem, European Journal of Operational Research 44, 337-348.
• Fleischmann, B.; Meyr, H.; Wagner, M. (2008) Advanced planning, in: H. Stadtler; C. Kilger (Eds.) Supply Chain Management and Advanced Planning, Springer, Berlin et al., 4th ed., 81–109
• Florian, M., Lenstra, J.K., Rinnooy Kan, A.H.G., 1980, Deterministic Production Planning: Algorithms and Complexity, Management Science 26 (7), 669-679.
• Günter, H.P. (2005), Supply Chain Management and Advanced Planning Systems: A Tutorial, Physica-Verlag HD.
• Haase, K. (1998). Capacitated lot-sizing with linked production quantities of adjacent periods. Beyond Manufacturing Resource Planning (MRP II). Advanced Models and Methods for Production Planning, Springer, Berlin, 127-146.
• Jans R., Degraeve Z., Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches, European Journal of Operational Research 177 (2007), pp. 1855–1875
• Karimi,B., Ghomi, S.M.T.F., Wilson, J.M. (2003). The capacitated lot sizing problem: a review of models and algorithms. Omega, 31, 365-378.
• Karmarker, U.S., Scharge L. (1985). The deterministic dynamic product cycling problem, Operations Research 33, 326-345.
• Kilger, C. and Schneeweiss, L. (2005), “Demand fulfillment and ATP”, In： Stadtler H., Kilger, C. (Eds.), Supply Chain Management and Advanced Planning Concepts, Models, Software and Case Studies, Springer, Berlin, , pp. 179-195. King, B. E. and Benton,
• Kreipl, S. and Dickersbach, J.D. (2008). “Scheduling coordination problems in supply chain planning”, Annals of Operations Research, Vol. 161, No. 1, pp. 103-123.
• Lin, C.H., Hwang, S-L. and Wang, M-Y. (2007). “A reappraisal on advanced planning and scheduling systems”, Industrial Management & Data Systems, Vol. 107, No. 8, pp. 1212-1226.
• Meyr, H., 1999. Simultane Losgrößen- und Reihenfolgeplanung für kontinuierliche Produktionslnien. Gabler Edition Wissenschaft: Produktion und Logistik. Gabler, Wiesbaden.
• Ochoa, G: A Bibliography of Hyper-heuristics and Related Approaches. ASAP research group. http://www.asap.cs.nott.ac.uk/projects/ngds/hhref.shtml (2009). Accessed 12 March 2009
• Ozcan E, Bilgin B, Korkmaz E.E. (2008) A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis, 12:1, 3-23
• Ozturk C. (2007). Finite Capacity Planning in MRP systems; Problems and Issues, Msc. Thesis, Dokuz Eylul University, Graduate School of Natural and Applied Sciences.
• Pochet Y., Woolsey L.A. (2006). Production Planning by Mixed Integer Programming, Springer, New York.
• Quadt D, Kuhn H (2008) Capacitated lot-sizing with extensions: a review. 4OR Q J Oper Res 6: 61–83
• Stadtler, H. (1996). Mixed integer model formulations for dynamic multi item multi level capacitated lot sizing. European Journal of Operations Research 94, 561-581.
• Staggemeier, A.T.,. Clark, A.R, A survey of lot-sizing and scheduling models, 23rd Annual Symposium of the Brazilian Operational Research Society (SOBRAPO), Campos do Jordao SP, Brazil (2001), pp. 938–947.
• Steger-Jensen, K. et al. (2011) Advanced Planning and Scheduling technology. Production Planning & Control, v. 22, n. 8, p. 800-808.
• Suerie, C.,Stadtler, H., The capacitated lot-sizing problem with linked lot sizes, Management Science 49 (2003), pp. 1039–1054
• Tay J.C and N. B. Ho, (2008) Evolving Dispatching Rules for solving Multi-Objective Flexible Job-Shop Problems, Computers & Industrial Engineering, vol. 54 (3), pp. 453-473.
• Tempelmeier, H., A simple heuristic for dynamic order sizing and supplier selection with time-varying data, Production and Operations Management 11 (2003), pp. 499–515.
• Tempelmeier, H., Buschkühl L., (2008). A heuristic for the dynamic multi-level capacitated lotsizing problem with linked lot sizes for general product structures. OR Spectrum, DOI 10.1007/s00291-008-0130-y
• Tempelmier, H., Derstroff, M., (1996) A Lagrangean based heuristic for dynamic multilevel multi item constrained lot sizing with setup times, Management Science 42, 738-757
• Zoryk-Schalla A., Fransoo J. and de Kok T.G (2004). “Modelling the planning process in advanced planning systems”, Information and Management, Vol. 42, No. 1, pp. 75-87