Generating robust and flexible job shop schedules using genetic algorithms

The problem of finding robust or flexible solutions for scheduling problems is of utmost importance for real-world applications as they operate in dynamic environments. In such environments, it is often necessary to reschedule an existing plan due to failures (e.g., machine breakdowns, sickness of employees, deliveries getting delayed, etc.). Thus, a robust or flexible solution may be more valuable than an optimal solution that does not allow easy modifications. This paper considers the issue of robust and flexible solutions for job shop scheduling problems. A robustness measure is defined and its properties are investigated. Through experiments, it is shown that using a genetic algorithm it is possible to find robust and flexible schedules with a low makespan. These schedules are demonstrated to perform significantly better in rescheduling after a breakdown than ordinary schedules. The rescheduling performance of the schedules generated by minimizing the robustness measure is compared with the performance of another robust scheduling method taken from literature, and found to outperform this method in many cases.