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

Ö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

1. 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.
2. Bitran, G.R., Yanasse, H.H. (1982). Computational complexity of the capacitated lot size problem, Management Science 28, 1174-1186.
3. Blackstone, John H., and James F. Cox. 2005. APICS dictionary. Alexandria, VA: APICS
4. 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,
5. 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
6. 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.
7. 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)
8. 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.

9. 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.
10. Drexl A., & Kimms A. (1997). Lot sizing and scheduling – survey and extensions. European Journal of Operations Research 99, 221-235.
11. Drexl, A., Haase, K. (1995). Proportional lot sizing and scheduling, International Journal of Production Economics 40, 73-87.
12. Fleischmann, B. (1990). The discrete lot-sizing and scheduling problem, European Journal of Operational Research 44, 337-348.
13. 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
14. Florian, M., Lenstra, J.K., Rinnooy Kan, A.H.G., 1980, Deterministic Production Planning: Algorithms and Complexity, Management Science 26 (7), 669-679.
15. Günter, H.P. (2005), Supply Chain Management and Advanced Planning Systems: A Tutorial, Physica-Verlag HD.
16. 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.
17. 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
18. 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.
19. Karmarker, U.S., Scharge L. (1985). The deterministic dynamic product cycling problem, Operations Research 33, 326-345.
20. 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,
21. 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.
22. 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.
23. Meyr, H., 1999. Simultane Losgrößen- und Reihenfolgeplanung für kontinuierliche Produktionslnien. Gabler Edition Wissenschaft: Produktion und Logistik. Gabler, Wiesbaden.
24. 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
25. Ozcan E, Bilgin B, Korkmaz E.E. (2008) A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis, 12:1, 3-23
26. Ozturk C. (2007). Finite Capacity Planning in MRP systems; Problems and Issues, Msc. Thesis, Dokuz Eylul University, Graduate School of Natural and Applied Sciences.
27. Pochet Y., Woolsey L.A. (2006). Production Planning by Mixed Integer Programming, Springer, New York.
28. Quadt D, Kuhn H (2008) Capacitated lot-sizing with extensions: a review. 4OR Q J Oper Res 6: 61–83
29. Stadtler, H. (1996). Mixed integer model formulations for dynamic multi item multi level capacitated lot sizing. European Journal of Operations Research 94, 561-581.
30. 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.
31. Steger-Jensen, K. et al. (2011) Advanced Planning and Scheduling technology. Production Planning & Control, v. 22, n. 8, p. 800-808.
32. Suerie, C.,Stadtler, H., The capacitated lot-sizing problem with linked lot sizes, Management Science 49 (2003), pp. 1039–1054
33. 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.
34. 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.
35. 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
36. 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
37. 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