Improving local search for the fuzzy job shop using a lower bound

Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2009 (13th. 2009. Sevilla, España)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 neighbour