A New Contribution for Solving Dynamic Scheduling Problems Using a Tabu Search

摘要

Many real-world optimisation problems are eventually dynamic. New jobs are to be added to the schedule, the quality of the raw material may be changing, new orders have to be included into the problem etc. In such cases, when the problem changes over the course of the optimisation, the purpose of the optimisation algorithm changes from finding an optimal solution to being able to continuously track the movement of the optimum through time. This paper starts by presenting a new scheduling method based on Tabu Search for the resolution of the dynamic Job-Shop Scheduling Problem, which considers job release times, job due dates and different assembly levels (parallel operations). This framework is based on a decomposition of the Job-Shop Scheduling Problem into a series of deterministic Single Machine Scheduling Problem (SMSP) and on a Tabu Search Algorithm, which solves each SMSP whose solutions are, then, integrated. An inter-machine activity coordination mechanism is described. Finally, the used approach adapts the resolution of the deterministic problem to the non-deterministic one in which changes may occur continually. This takes into account dynamic occurrences in a manufacturing system and adapts the current neighbourhood to a new regenerated neighbourhood.