nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Fitness Landscape Analysis of the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion

verfasst von : Marco Baioletti, Valentino Santucci

Erschienen in: Computational Science and Its Applications – ICCSA 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper provides a fitness landscape analysis of the Permutation Flowshop Scheduling Problem considering the Total Flow Time criterion (PFSP-TFT). Three different landscapes, based on three neighborhood relations, are considered. The experimental investigations analyze aspects such as the smoothness and the local optima structure of the landscapes. To the best of our knowledge, this is the first landscape analysis for PFSP-TFT.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Analysis of Tweets to Find the Basis of Popularity

Nächstes Kapitel Clustering Facebook for Biased Context Extraction

Note that the results of the INS neighborhood on the 10-jobs instances, due to the very small number of local minima, are not too much significant.

Baioletti, M., Milani, A., Santucci, V.: Algebraic particle swarm optimization for the permutations search space. In: IEEE Congress on Evolutionary Computation CEC 2017 (in press)

Baioletti, M., Busanello, G., Vantaggi, B.: Acyclic directed graphs representing independence models. Int. J. Approx. Reason. 52(1), 2–18 (2011). http://dx.doi.org/10.1016/j.ijar.2010.09.005 MathSciNetCrossRefMATH

Baioletti, M., Chiancone, A., Poggioni, V., Santucci, V.: Towards a new generation ACO-based planner. In: Murgante, B., et al. (eds.) ICCSA 2014. LNCS, vol. 8584, pp. 798–807. Springer, Cham (2014). doi:10.1007/978-3-319-09153-2_59

Baioletti, M., Milani, A., Santucci, V.: Linear ordering optimization with a combinatorial differential evolution. In: 2015 IEEE International Conference on Systems, Man, and Cybernetics, Kowloon Tong, Hong Kong, 9–12 October 2015, pp. 2135–2140 (2015). http://dx.doi.org/10.1109/SMC.2015.373

Baioletti, M., Milani, A., Santucci, V.: A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling. Intell. Artif. 10(2), 81–95 (2016). http://dx.doi.org/10.3233/IA-160097

Baioletti, M., Milani, A., Santucci, V.: An extension of algebraic differential evolution for the linear ordering problem with cumulative costs. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 123–133. Springer, Cham (2016). doi:10.1007/978-3-319-45823-6_12 CrossRef

Ceberio, J., Irurozki, E., Mendiburu, A., Lozano, J.A.: A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem. IEEE Trans. Evol. Comput. 18(2), 286–300 (2014). http://dx.doi.org/10.1109/TEVC.2013.2260548 CrossRef

Chiancone, A., Franzoni, V., Niyogi, R., Milani, A.: Improving link ranking quality by quasi-common neighbourhood. In: Proceedings of 15th International Conference on Computational Science and Its Applications, ICCSA 2015, pp. 21–26, June 2015. doi:10.1109/ICCSA.2015.19

Chiancone, A., et al.: A multistrain bacterial diffusion model for link prediction. Int. J. Pattern Recogn. Artif. Intell. 31(8), 201–233 (2017). doi:10.1142/S0218001417590248

10.

Franzoni, V., Mencacci, M., Mengoni, P., Milani, A.: Heuristics for semantic path search in wikipedia. In: Murgante, B., et al. (eds.) ICCSA 2014. LNCS, vol. 8584, pp. 327–340. Springer, Cham (2014). doi:10.1007/978-3-319-09153-2_25

11.

Franzoni, V., Milani, A.: Semantic context extraction from collaborative networks. In: 2015 IEEE 19th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 131–136, May 2015. doi:10.1109/CSCWD.2015.7230946

12.

Franzoni, V., Milani, A.: A semantic comparison of clustering algorithms for the evaluation of web-based similarity measures. In: Gervasi, O., et al. (eds.) ICCSA 2016. LNCS, vol. 9790, pp. 438–452. Springer, Cham (2016). doi:10.1007/978-3-319-42092-9_34 CrossRef

13.

Gupta, J.N., Stafford Jr., E.F.: Flowshop scheduling research after five decades. Eur. J. Oper. Res. 169(3), 699–711 (2006). http://dx.doi.org/10.1016/j.ejor.2005.02.001 CrossRefMATH

14.

Hains, D.R., Whitley, L.D., Howe, A.E.: Revisiting the big valley search space structure in the TSP. J. Oper. Res. Soc. 62(2), 305–312 (2011). http://dx.doi.org/10.1057/jors.2010.116 CrossRef

15.

Hoos, H.H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Elsevier, Amsterdam (2004)MATH

16.

Milani, A., Santucci, V.: Community of scientist optimization: an autonomy oriented approach to distributed optimization. AI Commun. 25(2), 157–172 (2012). http://dx.doi.org/10.3233/AIC-2012-0526 MathSciNet

17.

Ochoa, G., Verel, S., Daolio, F., Tomassini, M.: Local optima networks: a new model of combinatorial fitness landscapes. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes. ECC, vol. 6, pp. 233–262. Springer, Heidelberg (2014). doi:10.1007/978-3-642-41888-4_9 CrossRef

18.

Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Araujo, C.P.S. (eds.) Recent Advances in Intelligent Engineering Systems. SCI, vol. 378, pp. 161–191. Springer, Heidelberg (2012). doi:10.1007/978-3-642-23229-9_8 CrossRef

19.

Santucci, V., Baioletti, M., Milani, A.: Algebraic differential evolution algorithm for the permutation flowshop scheduling problem with total flowtime criterion. IEEE Trans. Evol. Comput. 20(5), 682–694 (2016). http://dx.doi.org/10.1109/TEVC.2015.2507785 CrossRef

20.

Santucci, V., Baioletti, M., Milani, A.: A differential evolution algorithm for the permutation flowshop scheduling problem with total flow time criterion. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 161–170. Springer, Cham (2014). doi:10.1007/978-3-319-10762-2_16

21.

Santucci, V., Baioletti, M., Milani, A.: An algebraic differential evolution for the linear ordering problem. In: Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, 11–15 July 2015, Companion Material Proceedings, pp. 1479–1480 (2015). http://doi.acm.org/10.1145/2739482.2764693

22.

Santucci, V., Baioletti, M., Milani, A.: Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm. AI Commun. 29(2), 269–286 (2016). http://dx.doi.org/10.3233/AIC-2012-0526 MathSciNetCrossRef

23.

Schiavinotto, T., Stützle, T.: A review of metrics on permutations for search landscape analysis. Comput. Oper. Res. 34(10), 3143–3153 (2007). http://dx.doi.org/10.1016/j.cor.2005.11.022 CrossRefMATH

24.

Stadler, P.F.: Fitness landscapes. In: Lässig, M., Valleriani, A. (eds.) Biological Evolution and Statistical Physics. LNP, vol. 585, pp. 183–204. Springer, Heidelberg (2002). doi:10.1007/3-540-45692-9_10 CrossRef

25.

Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2), 278–285 (1993). http://dx.doi.org/10.1016/0377-2217(93)90182-M CrossRefMATH

26.

Tomassini, M., Vanneschi, L., Collard, P., Clergue, M.: A study of fitness distance correlation as a difficulty measure in genetic programming. Evol. Comput. 13(2), 213–239 (2005). http://dx.doi.org/10.1162/1063656054088549 CrossRefMATH

27.

Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63(5), 325–336 (1990). http://dx.doi.org/10.1007/BF00202749 CrossRefMATH

28.

Wu, Y., McCall, J.A.W., Corne, D.: Fitness landscape analysis of bayesian network structure learning. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2011, New Orleans, LA, USA, 5–8 June 2011, pp. 981–988 (2011). http://dx.doi.org/10.1109/CEC.2011.5949724

Titel: Fitness Landscape Analysis of the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion
verfasst von: Marco Baioletti
Valentino Santucci
Verlag: Springer International Publishing
Buch: Computational Science and Its Applications – ICCSA 2017
Print ISBN: 978-3-319-62391-7

Electronic ISBN: 978-3-319-62392-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-62392-4_51

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"