Effective job shop scheduling through active chain manipulation

A practical yet effective heuristic algorithm is developed in this paper for solving the make-span reduction job shop scheduling problem. The algorithm iteratively improves an existing job shop schedule through exploring the schedule's neighborhood, using a simple active chain manipulation scheme. A Tabu search technique is employed, as part of the active chain manipulation procedure developed in this paper, to prevent the trap of local optimality. Test results show that the algorithm is capable of efficiently generating very good schedules.