Two parameter-tuned metaheuristic algorithms for the multi-level lot sizing and scheduling problem

Abstract: This paper addresses the problem of lot sizing and scheduling problem for n-products and m-machines in flow shop environment where setups among machines are sequence-dependent and can be carried over. Many products must be produced under capacity constraints and allowing backorders. Since lot sizing and scheduling problems are well-known strongly NP-hard, much attention has been given to heuristics and metaheuristics methods. This paper presents two metaheuristics algorithms namely, Genetic Algorithm (GA) and Imperialist Competitive Algorithm (ICA). Moreover, Taguchi robust design methodology is employed to calibrate the parameters of the algorithms for different size problems. In addition, the parameter-tuned algorithms are compared against a presented lower bound on randomly generated problems. At the end, comprehensive numerical examples are presented to demonstrate the effectiveness of the proposed algorithms. The results showed that the performance of both GA and ICA are very promising and ICA outperforms GA statistically.

How to cite this paper

 Babaei, M., Mohammadi, M., Ghomi, S & Sobhanallahi, M. (2012). Two parameter-tuned metaheuristic algorithms for the multi-level lot sizing and scheduling problem.International Journal of Industrial Engineering Computations , 3(5), 751-766.

Refrences

Abdi, B., Mozafari, H., Ayob, A., & Kohandel, R. (2011). Imperialist Competitive Algorithm and its Application in Optimization of Laminated Composite Structures. European Journal of Scientific Research, 55 (2), 174-187.

Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, IEEE Congress on Evolutionary Computation, Singapore, 4661–4667.

Ara?jo, C. D., Nagano, M. S. (2010). A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem. International Journal of Industrial Engineering Computations, 2, 155–166.

Bitran, G., & Yanasse, H. (1982).Computational complexity of the capacitated. Management Science, 28(10), 1174–1186.

Buschkühl, L., Sahling, F., Helber, S., & Tempelmeier, H. (2010). Dynamic capacitated lot-sizing problems: a classi?cation and review of solution approaches. OR Spectrum, 32, 231–261.

Drexl, A., & Kimms, A. (1997). Lot sizing and scheduling - Survey and extensions. European Journal of Operational Research, 99, 221-235.

Goren, H. G., Tunali, S., & Jans, R. (2010). A review of applications of genetic algorithms in lot sizing. Journal of Intelligence Manufacturing, 21, 575–590.

Holland, J. (1975). Adaptation in Natural and Arti?cial Systems. Ann Arbor: The U. of Michigan Press
Kaveh, A., & Talatahari, S. (2010). Optimum design of skeletal structures using imperialist competitive algorithm. Computer Structure, 88(21–22), 1220–1229.

Kayvanfar, V., & Zandieh, M. (2012). The economic lot scheduling problem with deteriorating items and shortage: an imperialist competitive algorithm. The International Journal of Advanced Manufacturing Technology, doi:10.1007/s00170-011-3820-6
Khabbazi, A., Gargari, E., & Lucas, C. (2009). Imperialist competitive algorithm for minimum bit error rate beamforming. International Journal of Bio-Inspiration Computing, 1(1/2), 125–133.

Khanzadi, M., Soufipour R., & Rostami, M. (2011).A new improved genetic algorithm approach and a competitive heuristic method for large-scale multiple resource-constrained project-scheduling problems. International Journal of Industrial Engineering Computations, 2, 737–748.

Kimms, A. (1999). A genetic algorithm for multi-level, multi-machine lot sizing and scheduling. Computers & Operations Research, 26, 829-848.

Lang, J. C., & Shen, Z.-J.M. (2011).Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions. Production, Manufacturing and Logistics, 3, 214.

Lian, K., Zhang, C., Shao, X., & Gao, L. (2012). Optimization of process planning with various flexibilities using an imperialist competitive algorithm. The International Journal of Advanced Manufacturing Technology, 59, 815-828.

Logendran, R., Salmasi, N., & Sriskandarajah, C. (2006).Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. ChelliahSriskandarajah, 33, 158 – 180.

Lucas, C., Nasiri-Gheidari, Z., & Tootoonchian, F. (2010).Application of an imperialist competitive algorithm to the design of a linear induction motor. Energy Conversion Management, 51(7), 1407–1411.

Maes, J., McClain, J., & Van Wassenhove, L. (1991). Multilevel capacitated lotsizing complexity and LP-based heuristics. European Journal of Operational Research, 53, 131-148.

Mohammadi, M. (2010).Integrating lotsizing, loading, and scheduling decisions in flexible flow shops.The International Journal of Advanced Manufacturing Technology, 50, 1165–1174.

Mohammadi, M., FatemiGhomi, S.-M.-T., Karimi, B., & Torabi, S-A. (2010a). MIP-based heuristics for lotsizing in capacitated pure flow shop with sequence-dependent setups. International Journal of Production Research, 48 (10), 2957–2973.

Mohammadi, M., FatemiGhomi, S.-M.-T., Karimi, B., & Torabi, S-A. (2010b). Rolling-horizon and fix-and-relax heuristics for the multi-product multi-level capacitated lotsizing problem with sequence-dependent setups. Journal of Intelligent Manufacturing, 21(4), 501–510.

Mohammadi, M., Ghomi, S. F., & Jafar, N. (2011). A genetic algorithm for simultaneous lotsizing and sequencing of the permutation flow shops with sequence-dependent setups. Expert Systems with Applications, 24, 87-93.

Montgomery, D. (2000). Design and Analysis of Experiments. New York: Wiley.

Nagano, M., Ruiz, R., & Lorena, L. (2008).A constructive genetic algorithm for permutation ?owshop scheduling. Computers & Industrial Engineering, 55 (1), 195–207.

Nazari-Shirkouhi, S., Eivazy, H., Ghodsi, R., Rezaie, K., & Atashpaz- Gargari, E. (2010).Computers and Industrial Engineering, 37(12), 7615–7626.

Phadke, M. (1989).Quality Engineering using Robust Design. Engelwood Cliffs: Prentice-Hall.
Quadt, D., & Kuhn, H. (2008). Capacitated lot-sizing with extensions: a review. 4OR, 6(1), 61–83.

Rajabioun, R., Atashpaz-Gargari, E., & Lucas, C. (2008).Colonial competitive algorithm as a tool for Nash equilibrium point achievement. International Journal of Intelligent Computing and Cybernetics, 49 (11), 680–695.

Sarayloo, F., & Tavakkoli-Moghaddam, R. (2010).Imperialistic competitive algorithm for solving a dynamic cell formation problem with production planning. Advanced Intelligent Computing Theories and Applications, 6215, 266–276.

Shim, I.-S., Kim, H.-C., Doh, H.-H., & Lee, D.-H.(2011). A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs. Computers & Industrial Engineering, 61(4), 920-929.

Shokrollahpour, E., Zandieh, M., & Dorri, B. (2010).A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem. International Journal of Production Research, 49(11), 3087–3103.

Sun, H., Huang, H.-C., & Jaruphongsa, W. (2009).Genetic algorithms for the multiple-machine economic lot scheduling problem. The International Journal of Advanced Manufacturing Technology, 43, 1251-1260.

Taguchi, G. (1986). Introduction to quality engineering. White Plains: Asian Productivity.
Tsai, J.T., Ho, W.H., Liu, T.K., & Chou, J.H. (2007). Improved immune algorithm for global numerical optimization and job-shop scheduling problems. Applied Mathematics and Computation, 194, 406–424.

Wagner, H.-M., & Whithin, T.-M.(1958). Dynamic version of the economic lot size model. Management Science, 5, (89–96).

Xiao, Y., Kaku, I., Zhao, Q., & Zhang, R. (2012).Neighborhood search techniques for solving uncapacitated multilevel lot-sizing problems. Computers & Operations Research, 39, 647–658.

Yao, M. J., & Huang, J. X. (2005).Solving the economic lot scheduling problem with deteriorating items using genetic algorithms. Journal of Food Engineering, 70, 309–322.

Zhua, X., & Wilhelm, W. E. (2006). Scheduling and lot sizing with sequence-dependent setup: A literature review. IIE Transactions, 38, 987–1007.