Efficient scheduling of a no-wait flexible job shop with periodic maintenance activities and processing constraints

Document Type : Research Paper


1 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

2 Kharazmi University

3 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran



Flexible job-shop scheduling problem (FJSP) is an extension of job shop scheduling problem which allows an operation to be performed by any machine amongst a set of available machines in each stage. This paper addresses a no-wait flexible job shop scheduling problem with machines availability constraints for maintenance activities and machines processing capability to minimize total weighted tardiness. The study is organized in two steps. In the first step, a new nonlinear mathematical model is developed for the considered problem, and then it is converted into a linear mathematical model using the techniques in the literature. Since the structure of the problem is NP-hard, thus in the second step, an Imperialist competitive algorithm is proposed to solve real-size instances of the problem. In the proposed algorithm, an effective solution representation with an efficient and greedy decoding methodology is adopted to reduce the search space. Numerical experiments are used to evaluate the performance of the developed algorithm. It is concluded that in small instances, solving the mathematical model by GAMS leads to the optimal solution, but with the increased size of instances, this method loses its efficiency and ICA performs better under these conditions.