Skip to main content
Springer Nature Link
Log in

Combining Neighbourhoods in Fuzzy Job Shop Problems

  • Conference paper
Advances in Artificial Intelligence (CAEPIA 2011)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 7023))

Included in the following conference series:

  • 1287 Accesses

Abstract

In the sequel, we propose a new neighbourhood structure for local search for the fuzzy job shop scheduling problem, which is a variant of the well-known job shop problem, where uncertain durations are modelled as fuzzy numbers and the objective is to minimise the expected makespan of the resulting schedule. The new neighbourhood structure is based on changing the position of a task in a critical block. We provide feasibility conditions and a makespan estimate which allows to select only feasible and promising neighbours. The experimental results illustrate the success of our proposal in reducing expected makespan within a memetic algorithm. The experiments also show that combining the new structure with an existing neighbourhood from the literature considering both neighborhoods at the same time, provides the best results.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA Journal of Computing 3, 149–156 (1991)

    Article  MATH  Google Scholar 

  2. Brucker, P., Knust, S.: Complex Scheduling. Springer, Heidelberg (2006)

    MATH  Google Scholar 

  3. Dell’ Amico, M., Trubian, M.: Applying tabu search to the job-shop scheduling problem. Annals of Operational Research 41, 231–252 (1993)

    Article  MATH  Google Scholar 

  4. 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  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  6. González Rodríguez, I., Vela, C.R., Puente, J.: Sensitivity Analysis for the Job Shop Problem with Uncertain Durations and Flexible Due Dates. In: Mira, J., Álvarez, J.R. (eds.) IWINAC 2007. LNCS, vol. 4527, pp. 538–547. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  7. 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 

  8. González Rodríguez, I., Vela, C.R., Hernández-Arauzo, A., Puente, J.: Improved local search for job shop scheduling with uncertain durations. In: Proc. of ICAPS 2009, pp. 154–161. AAAI Press (2009)

    Google Scholar 

  9. 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 ICAPS 2008, pp. 124–131. AAAI Press (2008)

    Google Scholar 

  10. Grabowski, J., Wodecki, M.: A very fast tabu search algorithm for job shop problem. In: Metaheuristic Optimization via Memory and Evolution. Tabu Search and Scatter Search. Operations Research/Computer Science Interfaces Series, pp. 117–144. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. 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 

  12. 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 

  13. Mattfeld, D.C.: Evolutionary Search and the Job Shop Investigations on Genetic Algorithms for Production Scheduling. Springer, Heidelberg (1995)

    MATH  Google Scholar 

  14. Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop scheduling problem. Management Science 42, 797–813 (1996)

    Article  MATH  Google Scholar 

  15. Petrovic, S., Fayad, S., Petrovic, D.: Sensitivity analysis of a fuzzy multiobjective scheduling problem. International Journal of Production Research 46(12), 3327–3344 (2007)

    Article  MATH  Google Scholar 

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

    MATH  Google Scholar 

  17. Puente, J., Vela, C.R., González-Rodríguez, I.: Fast local search for fuzzy job shop scheduling. In: Proc. of ECAI 2010, pp. 739–744. IOS Press (2010)

    Google Scholar 

  18. Sakawa, M., Kubota, R.: Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms. European Journal of Operational Research 120, 393–407 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  19. Taillard, E.D.: Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing 6(2), 108–117 (1994)

    Article  MATH  Google Scholar 

  20. 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 

  21. Van Laarhoven, P., Aarts, E., Lenstra, K.: Job shop scheduling by simulated annealing. Operations Research 40, 113–125 (1992)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Jorge Puente & Camino R. Vela

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

    Inés González-Rodríguez

Authors
  1. Jorge Puente
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Camino R. Vela
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. 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. Computer Science School, University of the Basque Country, Pº Manuel de Lardizabal 1, 20018, Donostia-San Sebastian, Spain

    Jose A. Lozano

  2. Computing Systems Department, University of Castilla-La Mancha, Campus Universitario s/n, 02071, Albacete, Spain

    José A. Gámez

  3. Dep. Statistics, O.R. and Computation, University of La Laguna, 38271, La Laguna, S.C. Tenerife, Spain

    José A. Moreno

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Puente, J., Vela, C.R., González-Rodríguez, I. (2011). Combining Neighbourhoods in Fuzzy Job Shop Problems. In: Lozano, J.A., Gámez, J.A., Moreno, J.A. (eds) Advances in Artificial Intelligence. CAEPIA 2011. Lecture Notes in Computer Science(), vol 7023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25274-7_35

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-25274-7_35

  • Publisher Name: Springer, Berlin, Heidelberg

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

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation