Abstract
We consider the fuzzy job shop scheduling problem, which is a variant of the well-known job shop problem, with uncertainty in task durations that we model using fuzzy numbers. We propose a tabu search algorithm for minimising the expected makespan based on reversing arcs within critical blocks. We test the algorithm and then combine it with a genetic algorithm from the literature so we can observe the synergy effect, obtaining better results with the hybrid algorithm than with its components by separate. Finally we compare our hybrid algorithm with a memetic algorithm from the literature and show that even in similar times, our method is better in terms of expected makespan.
This is a preview of subscription content, log in via an institution to check access.
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
Bortolan, G., Degani, R.: A review of some methods for ranking fuzzy subsets. In: Dubois, D., Prade, H., Yager, R. (eds.) Readings in Fuzzy Sets for Intelligence Systems, pp. 149–158. Morgan Kaufmann, Amsterdam (1993)
Brucker, P., Knust, S.: Complex Scheduling. Springer (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., Hernández-Arauzo, A., Puente, J.: Improved local search for job shop scheduling with uncertain durations. In: Proceedings of ICAPS-2009, pp. 154–161. AAAI Press, Thesaloniki (2009)
González Rodríguez, I., Vela, C.R., Puente, J.: A memetic approach to fuzzy job shop based on expectation model. In: Proceedings of IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2007, pp. 692–697. IEEE, London (2007)
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: Proceedings of ICAPS-2008, pp. 124–131. AAAI Press, Sidney (2008)
Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research 165, 289–306 (2005)
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)
Liu, B., Liu, Y.K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10, 445–450 (2002)
Niu, Q., Jiao, B., Gu, X.: Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time. Applied Mathematics and Computation 205, 148–158 (2008)
José Palacios, J., González-Rodríguez, I., Vela, C.R., Puente, J.: Particle swarm optimisation for open shop problems with fuzzy durations. In: Ferrández, J.M., Álvarez Sánchez, J.R., de la Paz, F., Toledo, F.J. (eds.) IWINAC 2011, Part I. LNCS, vol. 6686, pp. 362–371. Springer, Heidelberg (2011)
Petrovic, S., Fayad, S., Petrovic, D., Burke, E., Kendall, G.: Fuzzy job shop scheduling with lot-sizing. Annals of Operations Research 159, 275–292 (2008)
Pinedo, M.L.: Scheduling, 3rd edn. Theory, Algorithms, and Systems. Springer (2008)
Puente, J., Vela, C.R., González-Rodríguez, I.: Fast local search for fuzzy job shop scheduling. In: Proceedings 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)
Słowiński, R., Hapke, M. (eds.): Scheduling Under Fuzziness, Studies in Fuzziness and Soft Computing, vol. 37. Physica-Verlag (2000)
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
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Palacios, J.J., Puente, J., González-Rodríguez, I., Vela, C.R. (2013). Hybrid Tabu Search for Fuzzy Job Shop. In: Ferrández Vicente, J.M., Álvarez Sánchez, J.R., de la Paz López, F., Toledo Moreo, F.J. (eds) Natural and Artificial Models in Computation and Biology. IWINAC 2013. Lecture Notes in Computer Science, vol 7930. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38637-4_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-38637-4_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38636-7
Online ISBN: 978-3-642-38637-4
eBook Packages: Computer ScienceComputer Science (R0)