A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations

The flexible job shop scheduling problem (FJSP) is an extension of the classical job shop scheduling problem (JSP) which allows an operation to be processed by any machine from a given set of machines. FJSP is NP-hard and presents two major difficulties. The first is to assign each operation to a machine out of a set of capable machines; and the second deals with sequencing the assigned operations on the machines. However, it is quite difficult to obtain an optimal solution to this problem in medium and large size problems with traditional optimization approaches. In this paper, a memetic algorithm (MA) for flexible job shop scheduling with overlapping operations is proposed that solves the FJSP to minimize makespan. We also proposed a heuristic that uses the critical path method (CPM) in order to improve the results of MA and reduce the objective function. The experimental results of MA and CPM show that our approach is capable of achieving the optimal solution for small size problems and near-optimal solutions for medium and large size problems in a reasonable time.