A Genetic Algorithm for the Open Shop Problem with Uncertain Durations | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Genetic Algorithm for the Open Shop Problem with Uncertain Durations

  • Conference paper
Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira’s Scientific Legacy (IWINAC 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5601))

  • 936 Accesses

Abstract

We consider a variation of the open shop problem where task durations are allowed to be uncertain and where uncertainty is modelled using fuzzy numbers. We propose a genetic approach to minimise the expected makespan: we consider different possibilities for the genetic operators and analyse their performance, in order to obtain a competitive configuration. Finally, the performance of the proposed genetic algorithm is tested on several benchmark problems, modified so as to have fuzzy durations, compared with a greedy heuristic from the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Guéret, C., Prins, C.: Classical and new heuristics for the open-shop problem: A computational evaluation. European Journal of Operational Research 107, 306–314 (1998)

    Article  MATH  Google Scholar 

  2. Liaw, C.F.: A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research 124, 28–42 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Sha, D.Y., Cheng-Yu, H.: A new particle swarm optimization for the open shop scheduling problem. Computers & Operations Research 35, 3243–3261 (2008)

    Article  MATH  Google Scholar 

  4. Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research 165, 289–306 (2005)

    Article  MATH  Google Scholar 

  5. Dubois, D., Fargier, H., Fortemps, P.: Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge. European Journal of Operational Research 147, 231–252 (2003)

    Article  MATH  Google Scholar 

  6. Celano, G., Costa, A., Fichera, S.: An evolutionary algorithm for pure fuzzy flowshop scheduling problems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 11, 655–669 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. 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 67(3), 392–403 (1998)

    Article  Google Scholar 

  8. Fortemps, P.: Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Transactions of Fuzzy Systems 7, 557–569 (1997)

    Article  Google Scholar 

  9. González Rodríguez, I., Vela, C.R., Puente, J.: A memetic approach to fuzzy job shop based on expectation model. In: Proc. of IEEE International Conference on Fuzzy Systems, London, pp. 692–697. IEEE, Los Alamitos (2007)

    Google Scholar 

  10. González Rodríguez, I., Puente, J., Vela, C.R., Varela, R.: Semantics of schedules for the fuzzy job shop problem. IEEE Transactions on Systems, Man and Cybernetics, Part A 38(3), 655–666 (2008)

    Article  Google Scholar 

  11. Tavakkoli-Moghaddam, R., Safei, N., Kah, M.: Accessing feasible space in a generalized job shop scheduling problem with the fuzzy processing times: a fuzzy-neural approach. Journal of the Operational Research Society 59, 431–442 (2008)

    Article  MATH  Google Scholar 

  12. Pinedo, M.L.: Scheduling, 3rd edn. Theory, Algorithms, and System. Springer, Heidelberg (2008)

    MATH  Google Scholar 

  13. Liu, B., Liu, Y.K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10, 445–450 (2002)

    Article  Google Scholar 

  14. Liaw, C.F.: An iterative improvement approach for the nonpreemptive open shop scheduling problem. European Journal of Operational Research 111, 509–517 (1998)

    Article  MATH  Google Scholar 

  15. Liaw, C.F.: A tabu search algorithm for the open shop scheduling problem. Computers and Operations Research 26, 109–126 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  16. Puente, J., Diez, H., Varela, R., Vela, C., Hidalgo, L.: Heuristic Rules and Genetic Algorithms for Open Shop Scheduling Problem. In: Conejo, R., Urretavizcaya, M., Pérez-de-la-Cruz, J.-L. (eds.) CAEPIA/TTIA 2003. LNCS(LNAI), vol. 3040, pp. 394–403. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  17. Jussien, N., Lhomme, O.: Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence 139, 21–45 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  18. Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd revised and extended edn. Springer, Heidelberg (1996)

    Book  MATH  Google Scholar 

  19. Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278–285 (1993)

    Article  MATH  Google Scholar 

  20. González Rodríguez, I., Vela, C.R., Puente, J., Varela, R.: A new local search for the job shop problem with uncertain durations. In: Proc. of the Eighteenth International Conference on Automated Planning and Scheduling, pp. 124–131. AAAI Press, Menlo Park (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. A.I. Centre and Department of Computer Science, University of Oviedo, Spain

    Juan José Palacios, Jorge Puente & Camino R. Vela

  2. Department of Mathematics, Statistics and Computing, University of Cantabria, Spain

    Inés González-Rodríguez

Authors
  1. Juan José Palacios
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jorge Puente
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Camino R. Vela
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Inés González-Rodríguez
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dapartamento de Inteligencia Artificial, Universidad Nacional de Educación a Distancia, E.T.S. de Ingeniería Informática, Juan del Rosal, 16, 28040, Madrid, Spain

    José Mira  & Félix de la Paz  & 

  2. Departamento de Electrónica, Tecnología de Computadores y Proyectos, Universidad Politécnica de Cartagena, Pl. Hospital, 1, 30201, Cartagena, Spain

    José Manuel Ferrández

  3. Departamento de Inteligencia Artificial, Universidad Nacional de Educación a Distancia, E.T.S. de Ingeniería Informática, Juan del Rosal, 16, 28040, Madrid, Spain

    José R. Álvarez

  4. Departamento de Electrónica, Tecnología de Computadoras y Proyectos, Universidad Politécnica de Cartagena, Pl. Hospital, 1, 30201, Cartagena

    F. Javier Toledo

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Palacios, J.J., Puente, J., Vela, C.R., González-Rodríguez, I. (2009). A Genetic Algorithm for the Open Shop Problem with Uncertain Durations. In: Mira, J., Ferrández, J.M., Álvarez, J.R., de la Paz, F., Toledo, F.J. (eds) Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira’s Scientific Legacy. IWINAC 2009. Lecture Notes in Computer Science, vol 5601. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02264-7_27

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02264-7_27

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02263-0

  • Online ISBN: 978-3-642-02264-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics