A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

Abstract

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.

Keywords:

• Dynamic job shop scheduling problem
• multi-objective method
• hybrid algorithm
• schedule efficiency
• schedule stability

Acknowledgements

The authors would like to thank the editor and anonymous referees whose comments helped a lot in improving this paper. This research work is supported by Program for the Natural Science Foundation of China (NSFC) under Grant No. 51005088, the National Natural Science Foundation of China (NSFC) under Grant No.51121002, and the Hi-Tech Research and Development Program of China under grant No. 2009AA044601.