Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns

Abstract

The job-shop scheduling problem (JSSP) is considered to be one of the most complex combinatorial optimisation problems. In our previous attempt, we hybridised a Genetic Algorithm (GA) with a local search technique to solve JSSPs. In this research, we propose an improved local search technique, Shifted Gap-Reduction (SGR), which improves the performance of GAs when solving relatively difficult test problems. We also modify the new algorithm for JSSPs with machine unavailability and breakdowns. We consider two scenarios of machine unavailability. First, where the unavailability information is available in advance (predictive) and, secondly, where the information is known after a real breakdown (reactive). We show that the revised schedule is mostly able to recover if the interruptions occur during the early stages of the schedules.

Keywords:

• evolutionary computation
• job shop
• job shop scheduling
• decision support systems
• evolutionary algorithms
• scheduling
• production planning
• combinatorial optimisation
• flexible flow shop
• neural networks