On optimizing a bi-objective flowshop scheduling problem in an uncertain environment.

*(English)*Zbl 1268.90020Summary: Existing models from scheduling often over-simplify the problems appearing in real-world industrial situations. The original application is often reduced to a single-objective one, where the presence of uncertainty is neglected. In this paper, we focus on multi-objective optimization in uncertain environments. A bi-objective flowshop scheduling problem with uncertain processing times is considered. An indicator-based evolutionary algorithm is proposed to handle these two difficulties (multiple objectives and uncertain environment) at the same time. Four different strategies, based on uncertainty-handling quality indicators, are proposed in the paper. Computational experiments are performed on a large set of instances by considering different scenarios with respect to uncertainty. We show that an uncertainty-handling strategy is a key issue to obtain good-quality solutions, and that the algorithm performance is strongly related to the level of uncertainty over the environmental parameters.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C29 | Multi-objective and goal programming |

90C27 | Combinatorial optimization |

##### Keywords:

permutation flowshop scheduling; evolutionary algorithms; multi-objective combinatorial optimization; uncertain processing times
PDF
BibTeX
XML
Cite

\textit{A. Liefooghe} et al., Comput. Math. Appl. 64, No. 12, 3747--3762 (2012; Zbl 1268.90020)

Full Text:
DOI

##### References:

[1] | T’Kindt, V.; Billaut, J.-C., Multicriteria scheduling: theory, models and algorithms, (2002), Springer-Verlag Berlin, Germany · Zbl 1014.90046 |

[2] | () |

[3] | Coello Coello, C.A.; Lamont, G.B.; Van Veldhuizen, D.A., () |

[4] | Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons Chichester, UK · Zbl 0970.90091 |

[5] | Jin, Y.; Branke, J., Evolutionary optimization in uncertain environments — a survey, IEEE transactions on evolutionary computation, 9, 303-317, (2005) |

[6] | Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (), 832-842 |

[7] | Basseur, M.; Liefooghe, A.; Le, K.; Burke, E., The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems, Journal of heuristics, 18, 2, 263-296, (2012) |

[8] | Basseur, M.; Zitzler, E., Handling uncertainty in indicator-based multiobjective optimization, International journal of computational intelligence research, 2, 3, 255-272, (2006) |

[9] | Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem, (), 457-471 |

[10] | Dudek, R.A.; Panwalkar, S.S.; Smith, M.L., The lessons of flowshop scheduling research, Operations research, 40, 1, 7-13, (1992) · Zbl 0825.90554 |

[11] | Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: a literature survey, European journal of operational research, 81, 88-104, (1995) · Zbl 0913.90178 |

[12] | Landa Silva, J.D.; Burke, E.; Petrovic, S., An introduction to multiobjective metaheuristics for scheduling and timetabling, (), 91-129 · Zbl 1139.90420 |

[13] | Lenstra, J.K.; Rinnooy Kan, A.H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of discrete mathematics, 1, 343-362, (1977) · Zbl 0301.90025 |

[14] | Du, J.; Leung, J.Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of operations research, 15, 483-495, (1990) · Zbl 0714.90052 |

[15] | Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044 |

[16] | Gourgand, M.; Grangeon, N.; Norre, S., Metaheuristics and performance evaluation models for the stochastic permutation flow-shop scheduling problem, (), 143-170, (Chapter 5) |

[17] | Kouvelis, P.; Daniels, R.L.; Vairaktarakis, G., Robust scheduling of a two-machine flow shop with uncertain processing times, IIE transactions, 32, 5, 421-432, (2000) |

[18] | Cunningham, A.A.; Dutta, S.K., Scheduling jobs with exponentially distributed processing times on two machines of a flow shop, Naval research logistics quarterly, 16, 69-81, (1973) · Zbl 0254.90021 |

[19] | Ku, P.S.; Niu, S.C., On johnson’s two-machine flow shop with random processing times, Operations research, 34, 130-136, (1986) · Zbl 0595.90044 |

[20] | Wang, L.; Zhang, L.; Zheng, D.-Z., A class of hypothesis-test based genetic algorithm for flow shop scheduling with stochastic processing time, The international journal of advanced manufacturing technology, 25, 11-12, 1157-1163, (2005) |

[21] | Maddox, M.J.; Birge, J.R., Using second moment information in stochastic scheduling, (), 99-120 · Zbl 0854.90080 |

[22] | Dauzère-Pérès, S.; Castagliola, P.; Lahlou, C., Service level in scheduling, (), 99-121, (Chapter 7) |

[23] | Zitzler, E.; Thiele, L.; Laumanns, M.; Foneseca, C.M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 2, 117-132, (2003) |

[24] | Jin, Y.; Sendhoff, B., Trade-off between optimality and robustness: an evolutionary multiobjective approach, (), 237-251 · Zbl 1036.90540 |

[25] | Goh, C.K.; Tan, K.C., Evolving the tradeoffs between Pareto-optimality and robustness in multi-objective evolutionary algorithms, (), 457-478, (Chapter 20) |

[26] | Deb, K.; Gupta, H., Introducing robustness in multi-objective optimization, Evolutionary computation, 14, 4, 463-494, (2006) |

[27] | Teich, J., Pareto-front exploration with uncertain objectives, (), 314-328 |

[28] | Hughes, E.J., Evolutionary multi-objective ranking with uncertainty and noise, (), 329-343 |

[29] | Babbar, M.; Lakshmikantha, A.; Goldberg, D.E., A modified NSGA-II to solve noisy multiobjective problems, (), 21-27 |

[30] | Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6, 2, 182-197, (2002) |

[31] | Barrico, C.; Antunes, C.H., An evolutionary approach for assessing the degree of robustness of solutions to multi-objective models, (), 565-582, (Chapter 25) |

[32] | Goh, C.K.; Tan, K.C., An investigation on noisy environments in evolutionary multiobjective optimization, IEEE transactions on evolutionary computation, 11, 3, 354-381, (2007) |

[33] | Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer Academic · Zbl 0873.90071 |

[34] | J. Knowles, L. Thiele, E. Zitzler, A tutorial on the performance assessment of stochastic multiobjective optimizers, TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland, (revised version), 2006. |

[35] | Bleuler, S.; Laumanns, M.; Thiele, L.; Zitzler, E., PISA — a platform and programming language independent interface for search algorithms, (), 494-508 · Zbl 1037.68743 |

[36] | Tan, K.C.; Cheong, C.Y.; Goh, C.K., Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation, European journal of operational research, 177, 2, 813-839, (2007) · Zbl 1110.90015 |

[37] | Eskandari, H.; Geiger, C., Evolutionary multiobjective optimization in noisy problem environments, Journal of heuristics, 15, 16, 559-595, (2009) · Zbl 1180.90287 |

[38] | Fieldsend, J.E.; Everson, R.M., Multi-objective optimisation in the presence of uncertainty, (), 243-250 |

[39] | Goh, C.K.; Tan, K.C.; Cheong, C.Y.; Ong, Y.S., Noise-induced features in robust multi-objective optimization problems, (), 568-575 |

[40] | Taillard, E.D., Benchmarks for basic scheduling problems, European journal of operational research, 64, 278-285, (1993) · Zbl 0769.90052 |

[41] | Liefooghe, A.; Jourdan, L.; Talbi, E.-G., A software framework based on a conceptual unified model for evolutionary multiobjective optimization: paradiseo-MOEO, European journal of operational research, 209, 2, 104-112, (2011) |

[42] | 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, 3, 392-403, (1998) |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.