×

Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking. (English) Zbl 1398.90159

Summary: Recently, the flow shop scheduling problem under blocking has gained broad attention in academic fields. Various papers have been devoted to investigate this issue and have been mostly restricted to the treatment of single objective at a time. Nevertheless, in practice the scheduling decisions often involve simultaneous consideration of multiple objectives (usually contradicting) to give more realistic solutions to the decision maker. In this study, we deal with a bi-objective blocking permutation flow shop scheduling problem where the makespan and total completion time are considered as objective functions. Both measures lead to an NP-hard problem. Our interest is to propose for the first time a genetic algorithm based on NSGA-II for searching locally Pareto-optimal frontier for the problem under consideration. The individuals in the algorithm are represented as discrete job permutations. Some specific versions of the NEH heuristic are used to generate the initial population. Non-dominated solutions and differences among parents are taken advantage of when designing the selection operator. The efficiency of the proposed algorithm, based on various metrics, is compared against the multiobjective evolutionary algorithm SPEA-II.

MSC:

90C29 Multi-objective and goal programming
90B35 Deterministic scheduling theory in operations research

Software:

SPEA2; Genocop
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armentano, VA; Ronconi, DP, Minimizao do tempo total de atraso no problema de flowshop com buffer zero atravs de busca tabu, Gestao & Produao, 7, 352, (2000) · doi:10.1590/S0104-530X2000000300011
[2] Asefi, H; Jolai, F; Rabiee, M; Tayebi Araghi, ME, A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem, International Journal of Advanced Manufacturing Technology, 75, 1017-1033, (2014) · doi:10.1007/s00170-014-6177-9
[3] Caraffa, V; Ianes, S; Bagchi, T; Sriskandarajah, C, Minimizing makespan in a flowshop using genetic algorithms, International Journal of Production Economics, 2, 101-15, (2001) · doi:10.1016/S0925-5273(99)00104-8
[4] Collette, Y., & Siarry, P. (2003). Multi objective optimization: Principles and case studies. Berlin: Springer.
[5] Companys, R; Mateo, M, Different behaviour of a double branch-and-bound algorithm on \(Fm|prmu|Cmax\) and \(Fm|block|Cmax\) problems, Computers and Operations Research, 34, 938-953, (2007) · Zbl 1107.90016 · doi:10.1016/j.cor.2005.05.018
[6] Dario Landa Silva, J; Burke, Edmund K; Petrovic, S, An introduction to multiobjective metaheuristics for scheduling and timetabling, Lecture Notes in Economics and Mathematical Systems, 535, 91-129, (2004) · Zbl 1139.90420 · doi:10.1007/978-3-642-17144-4_4
[7] Davendra, D., Bialic-Davendra, M., Senkerik, R., & Pluhacek, M. (2013). Scheduling the flow shop with blocking problem with the chaos-induced discrete self organising migrating algorithm. In Proceedings 27th European conference on modelling and simulation. · Zbl 1273.90005
[8] Deb, K. (2008). Introduction to evolutionary multiobjective optimization. In J. Branke, K Deb, K. Miettinen, R. Słowiński (Eds.), Multiobjective Optimization. Lecture Notes in Computer Science (vol. 5252). Berlin: Springer.
[9] Deb, K; Pratap, A; Agarwal, S; Meyarivan, T, A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Transaction on Evolutionary Computation, 6, 182-197, (2002) · doi:10.1109/4235.996017
[10] Deng, G; Xu, Z; Gu, X, A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling, Chinese Journal of Chemical Engineering, 20, 1067-1073, (2012) · doi:10.1016/S1004-9541(12)60588-6
[11] Gen, M., & Cheng, R. (2000). Genetic algorithms and engineering optimization. New York: Wiley.
[12] Gilmore, P; Gomory, R, Sequencing a one state variable machine: A solvable case of the traveling salesman problem, Operations Research, 5, 655-679, (1964) · Zbl 0126.36006 · doi:10.1287/opre.12.5.655
[13] Grabowski, J; Pempera, J, The permutation flowshop problem with blocking. a tabu search approach, Omega, 3, 302-11, (2007) · doi:10.1016/j.omega.2005.07.004
[14] Graham, R; Lawler, E; Lenstra, J; Rinnooy, K, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-362, (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[15] Han, Y-Y; Gong, D; Sun, X, A discrete artificial bee colony algorithm differential evolution for the flow-shop scheduling problem with blocking, Engineering Optimization, 47, 1-20, (2014)
[16] Han, Y-Y; Liang, J; Pan, Q-K; Li, J-Q; Sang, H-Y; Cao, N, Effective hybrid discrete artificial bee colony algorithms for the total flowtime minimization in the blocking flowshop problem, International Journal of Advanced Manufacturing Technology, 67, 397-414, (2013) · doi:10.1007/s00170-012-4493-5
[17] Holland, H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.
[18] Ishibuchi, H; Murata, T, A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Transactions on Systems, Man and Cybernetics—Part C: Applications and Reviews, 28, 392-403, (1998) · doi:10.1109/5326.704576
[19] Ishibuchi, H., Murata, T., & Tomioka, S. (1997). Effectiveness of genetic local search algorithms. Proceedings of the seventh international conference on genetic algorithms (pp. 505-512).
[20] Jolai, F; Asefi, H; Rabiee, M; Ramezanid, P, Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem, Scientia Iranica, Transactions E: Industrial Engineering, 20, 861-872, (2013)
[21] Kamrani, A; Rong, W; Gonzalez, R, A genetic algorithm methodology for data mining and intelligent knowledge acquisition, Computers & Industrial Engineering, 40, 361-377, (2001) · doi:10.1016/S0360-8352(01)00036-5
[22] Karabati, S; Kouvelis, P, Cycle scheduling in flow lines: modeling observations, effective heuristics and a cycle time minimization procedure, Naval Research Logistics, 2, 21131, (1996) · Zbl 0871.90048
[23] Khorasanian, D; Moslehi, G, An iterated greedy algorithm for solving the blocking flow shop scheduling problem with total flow time criteria, International Journal of Industrial Engineering and Production Research, 23, 301-308, (2012)
[24] Levner, EM, Optimal planning of parts machining on a number of machines, Automation and Remote Control, 12, 19728, (1969)
[25] Lin, S; Ying, K, Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm, Omega, 41, 383-389, (2013) · doi:10.1016/j.omega.2012.03.006
[26] Michalewicz, Z. (1999). Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer.
[27] Moslehi, G; Khorasanian, D, Optimizing blocking flowshop scheduling problem with total completion time criterion, Computers and Operations Research, 40, 1874-1883, (2013) · Zbl 1348.90294 · doi:10.1016/j.cor.2013.02.003
[28] Murata, T., Ishibuchi, H., & Gen, M. (2000). Cellular genetic local search for multiobjective optimization. In Proceedings of the 2000 genetic and evolutionary computation conference, (pp. 307-314).
[29] Murata, T; Ishibuchi, H; Tanaka, H, Multi-objective genetic algorithm and its applications to flow shop scheduling, Computers & Industrial Engineering, 30, 957-968, (1996) · doi:10.1016/0360-8352(96)00045-9
[30] Nawaz, M; Enscore, J; Ham, I, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 91-95, (1993) · doi:10.1016/0305-0483(83)90088-9
[31] Nouri, N., & Ladhari, T. (2015). Minimizing regular objectives for blocking permutation flow shop scheduling: Heuristic approaches. In Proceedings of the genetic and evolutionary computation conference (pp. 441-448).
[32] Pan, Q-K; Wang, L; Qian, B, A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems, Computers & Operations Research, 36, 2498-2511, (2009) · Zbl 1157.90423 · doi:10.1016/j.cor.2008.10.008
[33] Pan, Q; Wang, L; Sang, H; Li, J; Liu, M, A high performing memetic algorithm for the flowshop scheduling problem with blocking, IEEE Transactions on Automation Science and Engineering, 10, 741-756, (2013) · doi:10.1109/TASE.2012.2204874
[34] Pinedo, M. (2008). Scheduling: theory, algorithms, and systems. Englewood CliKs, NJ: Prentice-Hall.
[35] Ponnambalam, SG; Jagannathan, H; Kataria, M; Gadicherla, A, A TSP-GA multi-objective algorithm for flow shop scheduling, International Journal of Advanced Manufacturing Technology, 23, 909-915, (2004) · doi:10.1007/s00170-003-1731-x
[36] Rahimi-Vahed, A; Mirzaei, AH, Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm, Soft Computing, 12, 435-452, (2008) · Zbl 1170.90397 · doi:10.1007/s00500-007-0210-y
[37] Rahimi-Vahed, AR; Mirghorbani, SM, A multi-objective particle swarm for a flow shop scheduling problem, Journal of Combinatorial Optimization, 13, 79-102, (2007) · Zbl 1112.90037 · doi:10.1007/s10878-006-9015-7
[38] Ravindran, D; Noorul Haq, A; Selvakuar, SJ; Sivaraman, R, Flow shop scheduling with multiple objective of minimizing makespan and total flow time, International Journal of Advance Manufacturing Technology, 25, 1007-1012, (2005) · doi:10.1007/s00170-003-1926-1
[39] Reddi, S; Ramamoorthy, C, On the flow-shop sequencing problem with no wait in process, Operational Research Quarterly, 3, 323-31, (1972) · Zbl 0238.90080 · doi:10.1057/jors.1972.52
[40] Ribas, I; Companys, R, Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization, Computers & Industrial Engineering, 87, 30-39, (2015) · doi:10.1016/j.cie.2015.04.013
[41] Ribas, I; Companys, R; Tort-Martorell, X, An iterated greedy algorithm for the flowhsop scheduling problem with blocking, Omega, 3, 293-301, (2011) · doi:10.1016/j.omega.2010.07.007
[42] Ribas, I; Companys, R; Tort-Martorell, X, An efficient iterated local search algorithm for the total tardiness blocking flow shop problem, International Journal of Production Research, 51, 5238-5252, (2013) · doi:10.1080/00207543.2013.802390
[43] Ribas, I; Companys, R; Tort-Martorell, X, An efficient discrete artificial bee colony algorithm for the blocking flow shop problem with total flowtime minimization, Expert Systems with Applications, 42, 6155-6167, (2015) · doi:10.1016/j.eswa.2015.03.026
[44] Rock, H, Some new results in flow shop scheduling, Zeitschrift fur Operations Research, 28, 1-16, (1984) · Zbl 0529.90059
[45] Ronconi, DP, A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking, Annals of Operations Research, 1, 53-65, (2005) · Zbl 1091.90075 · doi:10.1007/s10479-005-2444-3
[46] Ronconi, DP; Armentano, VA, Lower bounding schemes for flowshops with blocking in-process, Journal of the Operational Research Society, 11, 12897, (2001) · Zbl 1181.90125
[47] Ronconi, DP; Henriques, LRS, Some heuristic algorithms for total tardiness minimization in a flowshop with blocking, Omega, 2, 272-81, (2009) · doi:10.1016/j.omega.2007.01.003
[48] Sadaqa, M; Moraga, RJ, Scheduling blocking flow shops using meta-raps, Procedia Computer Science, 61, 533-538, (2015) · doi:10.1016/j.procs.2015.09.211
[49] Schaffer, JD; Schaffer, JD (ed.), Multiple objective optimization with vector evaluated genetic algorithms, 93-100, (1985), Hillsdale, NJ
[50] Smutnicki, C; Pempera, J; Rudy, J; Zelazny, D, A new approach for multi-criteria scheduling, Computers & Industrial Engineering, 90, 212-220, (2015) · doi:10.1016/j.cie.2015.09.003
[51] Srinivas, N; Deb, K, Multiobjective function optimization using nondominated sorting genetic algorithms, Evolutionary Computation, 2, 221-248, (1995) · doi:10.1162/evco.1994.2.3.221
[52] Srinivas, N; Deb, K, Multiobjective function optimization using nondominated sorting genetic algorithms, Evolutionary Computation, V2, 221-248, (1995) · doi:10.1162/evco.1994.2.3.221
[53] Suhami, I; Mah, RSH, An implicit enumeration scheme for the flowshop problem with no intermediate storage, Computers and Chemical Engineering, 2, 83-91, (1981) · doi:10.1016/0098-1354(81)87003-2
[54] Taillard, E, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-85, (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M
[55] Tavakkoli-Moghaddam, R; Rahimi-Vahed, AR; Mirzaei, AH, Solving a bi-criteria permutation flow shop problem using immune algorithm, No. 1, 49-56, (2007), Hawaii
[56] Toktas, B; Azizoglu, M; Koksalan, SK, Two-machine flow shop scheduling with two criteria: maximum earliness and makespan, European Journal of Operational Research, 157, 286-295, (2004) · Zbl 1103.90343 · doi:10.1016/S0377-2217(03)00192-9
[57] Veldhuizen, DA; Lamont, GB, Multiobjective evolutionary algorithms: analyzing the state-of-the-art, Journal of Evolutionary Computation, 8, 125-147, (2000) · doi:10.1162/106365600568158
[58] Veldhuizen, D. V. (1999). Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations. Ph. D. Thesis, Dayton, OH: Air Force Institute of Technology.
[59] Wang, X; Tang, L, A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking, Applied Soft Computing, 12, 652-662, (2012) · doi:10.1016/j.asoc.2011.09.021
[60] Wang, L; Pan, Q; Suganthan, P; Wang, W; Wang, Y, A novel hybrid discrete differential evolution algorithm for blocking flowshop scheduling problems, Computers and Operational Research, 3, 509-520, (2010) · Zbl 1175.90199 · doi:10.1016/j.cor.2008.12.004
[61] Wang, L; Pan, Q; Tasgetiren, M, Minimizing the total flow time in a flowshop with blocking by using hybrid harmony search algorithms, Expert Systems with Applications, 12, 7929-7936, (2010) · doi:10.1016/j.eswa.2010.04.042
[62] Wang, L; Zhang, L; Zheng, D-Z, An effective hybrid genetic algorithm for flow shop scheduling with limited buffers, Computers and Operations Research, 33, 2960-2971, (2006) · Zbl 1086.90029 · doi:10.1016/j.cor.2005.02.028
[63] Yusoff, Y; Ngadiman, MS; Zain, AM, Overview of NSGA-II for optimizing machining process parameters, Procedia Engineering, 15, 3978-3983, (2011) · doi:10.1016/j.proeng.2011.08.745
[64] Zitzler, E. (1999). Evolutionary algorithms for multi-objective optimization: Methods and applications. Ph.D. Thesis, Dissertation ETH No. 13398, Swiss Federal Institute of Technology (ETH), Zrich, Switzerland.
[65] Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength pareto evolutionary algorithm. Computer Engineering and Networks Laboratory (TIK) -Report 103 Sept.
[66] Zitzler, E; Thiele, L, Multiobjective optimization using evolutionary algorithms—A comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 257-271, (1999) · doi:10.1109/4235.797969
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.