Genetic algorithm for short-term scheduling of make-and-pack batch production process

doi:10.1016/j.cjche.2015.04.021

摘要/Abstract

摘要： This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy all constraints while meeting demand requirement of packed products from various product families. This problemis NP-hard and the problemsize is exponentially large for a realistic-sized problem. Therefore, we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromosomes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to determine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for comparison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, all heuristics show the capability to solve large instances within reasonable computational time. In all problem instances, genetic algorithmaveragely outperforms ant colony optimization and Tabu search with slightly longer computational time.

关键词: Genetic algorithm, Ant colony optimization, Tabu search, Batch scheduling, Make-and-pack production, Forward assignment strategy

Abstract: This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy all constraints while meeting demand requirement of packed products from various product families. This problemis NP-hard and the problemsize is exponentially large for a realistic-sized problem. Therefore, we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromosomes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to determine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for comparison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, all heuristics show the capability to solve large instances within reasonable computational time. In all problem instances, genetic algorithmaveragely outperforms ant colony optimization and Tabu search with slightly longer computational time.

Key words: Genetic algorithm, Ant colony optimization, Tabu search, Batch scheduling, Make-and-pack production, Forward assignment strategy

Wuthichai Wongthatsanekorn, Busaba Phruksaphanrat. Genetic algorithm for short-term scheduling of make-and-pack batch production process[J]. , 2015, 23(9): 1475-1483.

参考文献

[1] S. Honkomp, S. Lombardo, O. Rosen, J.F. Pekny, The curse of reality—why process scheduling optimization problems are difficult in practice, Comput. Chem. Eng. 21 (1) (2000) 123-136.
[2] C.U. Fündeling, N. Trautmann, Scheduling of make and pack plants: a case study, 16th International European Symposium on Computer Aided Process Engineering and 9th International Symposium on Process Systems Engineering, Elsevier, Garmisch-Partenkirchen 2006, pp. 1551-1556.
[3] P. Baumann, N. Trautmann, A continuous-time MILP model for short-term scheduling of make-and-pack production processes, Int. J. Prod. Res. 51 (6) (2013) 1707-1727.
[4] R. Belaid, V. T'Kindt, C. Esswein, Decomposition algorithms for planning the production of a real shampoo industry, International Conference on Industrial and Systems Management, Metz, France, 2011.
[5] H.O. Günther, M. Grunow, U. Neuhaus, Realizing block planning concepts in makeand- pack production using MILP modeling and SAP APO, Int. J. Prod. Res. 44 (18-19) (2006) 3711-3726.
[6] S. Liu, J. Pinto, L. Papageorgiou, A TSP-based MILP model for medium-term planning of single-stage continuous multiproduct plants, Ind. Eng. Chem. Res. 47 (20) (2008) 7733-7743.
[7] G.M. Kopanos, L. Puigjaner, C. Maravelias, Production planning and scheduling of parallel continuous processes with product families, Ind. Eng. Chem. Res. 50 (3) (2011) 1369-1378.
[8] S. Velez, C.T. Maravelias, Multiple and nonuniform time grids in discrete-time MIP models for chemical production scheduling, Comput. Chem. Eng. 53 (1) (2013) 70-85.
[9] S. Velez, C.T.Maravelias, A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing, Comput. Chem. Eng. 55 (8) (2013) 28-39.
[10] M. Karimi-Nasab, S.M. Seyedhoseini, Multi-level lot sizing and job shop scheduling with compressible process times: a cutting plane approach, Eur. J. Oper. Res. 231 (3) (2013) 598-616.
[11] Y. Qian, M. Pan, Y. Huang, Modeling and optimization for scheduling of chemical batch, Chin. J. Chem. Eng. 17 (1) (2009) 1-7.
[12] G. Chen, L. Yan, B. Shi,Modeling and optimization for short-term scheduling ofmultipurpose batch plants, Chin. J. Chem. Eng. 22 (6) (2014) 682-689.
[13] A.H. Rabie, M.M. El-Halwagi, Synthesis and scheduling of optimal batch waterrecycle networks^** supported by the Texas Water Resources Institute (TWRI) and the Texas Hazardous Waste Research Center, Chin. J. Chem. Eng. 16 (3) (2008) 474-479.
[14] L. Chen, K. Wang, X. Xu, P. Yao, Hierarchical on-line scheduling of multiproduct batch plants with a combined approach of mathematical programming and genetic algorithm, Chin. J. Chem. Eng. 12 (1) (2004) 78-84.
[15] L.Wu, Y. Hu, D. Xu, B. Hua, Genetic algorithm-based approach to scheduling of batch production with maximum profit, Chin. J. Chem. Eng. 13 (1) (2005) 68-73.
[16] Y. He, C.-W. Hui, Genetic algorithmfor large-sizemulti-stage batch plant scheduling, Chem. Eng. Sci. 62 (2007) 1504-1523.
[17] Y. He, C.-W. Hui, A binary coding genetic algorithm for multi-purpose process scheduling: a case study, Chem. Eng. Sci. 65 (16) (2010) 4816-4828.
[18] Y. He, C.-W. Hui, A novel search framework for multi-stage process scheduling with tight due dates, AIChE J. 56 (8) (2010) 2103-2121.
[19] E. Capón-García, A.D. Bojarski, A. Espuña, L. Puigjaner, Multiobjective evolutionary optimization of batch process scheduling under environmental and economic concerns, AIChE J. 59 (2) (2013) 429-444.
[20] M.R. Garey, D.S. Johnson, R. Sethi, The complexity of flowshop and job-shop scheduling, Math. Oper. Res. 1 (1976) 117-129.
[21] P. Fattahi, M. Saidi Mehrabad, F. Jolai, Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, J. Intell. Manuf. 18 (3) (2007) 331-342.
[22] W. Cheung, H. Zhou, Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times, Ann. Oper. Res. 107 (1-4) (2001) 65-81.
[23] J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.
[24] M. Kreutz, D. Handke, S. Gehlen, Solving extended hybrid-flow-shop problems using active schedule generation and genetic algorithms, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 1917, Springer, Berlin 2000, p. 293-202.
[25] D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[26] O.A. Jadann, L. Rajamani, C.R. Rao, Improved Selection Operator for GA, J. Theor. Appl. Inf. Technol. 4 (4) (2008) 269-277.
[27] N.M. Razali, J. Geraghty, Genetic algorithm performance with different selection strategies in solving TSP, Proceeding of the World Congress on Engineering 2011 Vol II, WCE 2011, London, UK, 2011.
[28] P.W. Poon, J.N. Carter, Genetic algorithm crossover operators for ordering applications, Comput. Oper. Res. 22 (1) (1995) 135-147.
[29] P. Larranga, C.M.H. Kuijpers, R.H. Murga, Y. Yurramendi, Learning Bayesian network structures by searching for the best orderingwith genetic algorithm, IEEE Trans. Syst. Man Cybern. Syst. Hum. 26 (4) (1996) 487-493.
[30] M. Nourelfath, N. Nahas, Quantized hopfield networks for reliability optimization, Reliab. Eng. Syst. Saf. 81 (2003) 191-196.
[31] N. Nahas, M. Nourelfath, Ant system for reliability optimization of a series system with multiple-choice and budget constraints, Reliab. Eng. Syst. Saf. 87 (2005) 1-12.
[32] F. Glover, Tabu Search Part I, ORSA J. Comput. 1 (3) (1989) 190-206.
[33] F. Glover, Tabu Search Part II, ORSA J. Comput. 2 (1) (1990) 4-32.