A hybrid algorithm for job shop scheduling problem with consideration of work timetable

A job shop scheduling problem with consideration of work timetable (JSP-WT) is studied in this paper. A mathematical programming model is presented for JSP-WT. A hybrid algorithm combining genetic algorithm, tabu search and key block movement algorithm (GA_TS_KBM) is developed to solve the problem. A comparative experiment is conducted to demonstrate the validity of the algorithm. In the experiment, fifteen cases are designed to be solved by GA_TS_KBM in three different strategies: without consideration of work timetable, consideration of work timetable and operation-interruptible, and consideration of work timetable and operation-uninterruptible. The results and corresponding analyses demonstrate the effectiveness of the algorithm.