Multiple Route Job Shop Scheduling with Maintenance Activity Constraints

In scheduling problems, it is often assumed that all machines are available during scheduling horizon. Clearly, a machine may not be available due to breakdown or performing maintenance activities. This paper considers a multi-route job shop configuration, where each part has multiple routes to be produced. In this context, the problem of scheduling jobs together with a set of pre-defined maintenance activities is of interest. Due to the complexity of this problem, no exact mathematical approach can yield solution in reasonable amount of time and, thus, applying heuristic approach is suggested. In this paper, the problem is first formulated as a 0-1 integer program. Then an approach based on the artificial immune system is proposed to face the complexity of the problem. In order to evaluate the performance of the proposed approach 30 cases are designed and solved using the proposed approach and Lingo software, where applicable. The results show that the proposed approach can obtain good solutions in reasonable time.