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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA Journal of Computing 3, 149–156 (1991)
Brucker, P., Knust, S.: Complex Scheduling. Springer, Heidelberg (2006)
Dell’ Amico, M., Trubian, M.: Applying tabu search to the job-shop scheduling problem. Annals of Operational Research 41, 231–252 (1993)
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)
Fortemps, P.: Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Transactions of Fuzzy Systems 7, 557–569 (1997)
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)
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)
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)
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)
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)
Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research 165, 289–306 (2005)
Liu, B., Liu, Y.K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10, 445–450 (2002)
Mattfeld, D.C.: Evolutionary Search and the Job Shop Investigations on Genetic Algorithms for Production Scheduling. Springer, Heidelberg (1995)
Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop scheduling problem. Management Science 42, 797–813 (1996)
Petrovic, S., Fayad, S., Petrovic, D.: Sensitivity analysis of a fuzzy multiobjective scheduling problem. International Journal of Production Research 46(12), 3327–3344 (2007)
Pinedo, M.L.: Scheduling. Theory, Algorithms, and Systems, 3rd edn. Springer, Heidelberg (2008)
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)
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)
Taillard, E.D.: Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing 6(2), 108–117 (1994)
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)
Van Laarhoven, P., Aarts, E., Lenstra, K.: Job shop scheduling by simulated annealing. Operations Research 40, 113–125 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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)