On the impact of operation flexibility in the flexible job-shop scheduling problem

Due to its complexity and practical interest, the flexible job-shop scheduling problem has become one of the most studied scheduling problems. However, to our knowledge, all studies assume that the flexibility of operations (the possibility for an operation to be assigned to a machine from a given set of machines) is given when solving the problem. In this paper, we analyze the impact of operation flexibility when minimizing the makespan, with a particular focus on optimizing qualification decisions. Qualifying a machine for an operation means making the machine eligible to perform the operation. Only a limited number of non-eligible machines can be qualified, i.e. are qualifiable, for an operation. A bi-objective scheduling problem is introduced, where both the makespan and the qualification cost are minimized. A mathematical model is proposed, and new problem instances are generated to support several analyses. First, the impact of operation flexibility on the makespan is studied. Second, the level of flexibility required to achieve a given makespan is investigated. Third, the trade-off between the makespan and the qualification cost is mapped, and situations in which qualifications are fixed are compared with situations in which qualifications are optimized jointly with scheduling. The numerical results show that determining a limited but well-chosen set of qualifications substantially reduces the makespan, and that jointly optimizing qualification decisions with scheduling reaches the same performance with significantly fewer qualifications than when all qualifiable machines are qualified. Various managerial insights are presented. In particular, the level of operation flexibility available in a flexible job shop has more impact on performance than the choice of the scheduling algorithm. Some limitations of the study and related perspectives are also discussed.