Abstract
We consider the fuzzy job shop problem, where uncertain durations are modelled as fuzzy numbers and the objective is to minimise the expected makespan. A recent local search method from the literature has proved to be very competitive when used in combination with a genetic algorithm, but at the expense of a high computational cost. Our aim is to improve its efficiency with an alternative rescheduling algorithm and a makespan lower bound to prune non-improving neighbours. The experimental results illustrate the success of our proposals in reducing both CPU time and number of evaluated neighbours.
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
Pinedo, M.L.: Scheduling. Theory, Algorithms, and Systems, 3rd edn. Springer, Heidelberg (2008)
Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research 165, 289–306 (2005)
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)
Słowiński, R., Hapke, M. (eds.): Scheduling Under Fuzziness. Studies in Fuzziness and Soft Computing, vol. 37. Physica-Verlag, Heidelberg (2000)
Brucker, P., Knust, S.: Complex Scheduling. Springer, Heidelberg (2006)
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)
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)
Petrovic, S., Fayad, S., Petrovic, D.: Sensitivity analysis of a fuzzy multiobjective scheduling problem. International Journal of Production Research 46(12), 3327–3344 (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)
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.: A memetic approach to fuzzy job shop based on expectation model. In: Proc. of IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2007, London, pp. 692–697. IEEE, Los Alamitos (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: Proc. of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-2008), Sidney, pp. 124–131. AAAI Press, Menlo Park (2008)
Liu, B., Liu, Y.K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10, 445–450 (2002)
González Rodríguez, I., Puente, J., Varela, R., Vela, C.R.: A study of schedule robustness for job shop with uncertainty. In: Geffner, H., Prada, R., Machado Alexandre, I., David, N. (eds.) IBERAMIA 2008. LNCS (LNAI), vol. 5290, pp. 31–41. Springer, Heidelberg (2008)
Van Laarhoven, P., Aarts, E., Lenstra, K.: Job shop scheduling by simulated annealing. Operations Research 40, 113–125 (1992)
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)
Taillard, E.D.: Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing 6(2), 108–117 (1994)
Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA Journal of Computing 3, 149–156 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Puente, J., Vela, C.R., Hernández-Arauzo, A., González-Rodríguez, I. (2010). Improving Local Search for the Fuzzy Job Shop Using a Lower Bound. In: Meseguer, P., Mandow, L., Gasca, R.M. (eds) Current Topics in Artificial Intelligence. CAEPIA 2009. Lecture Notes in Computer Science(), vol 5988. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14264-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-14264-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14263-5
Online ISBN: 978-3-642-14264-2
eBook Packages: Computer ScienceComputer Science (R0)