A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints

Process planning and scheduling are two important functions in a modern manufacturing system. Although integrating decisions related to these functions gives rise to a hard combinatorial problem, due to the impressive improvement in system performance which is resulted through this integration, developing effective methods to solve this problem is of great theoretical and practical importance. In this research, after formulating the integrated process planning and scheduling problem as a mathematical program, we propose a hybrid genetic algorithm (GA) for the problem. In the proposed algorithm, problem-specific genetic operators are designed to enhance the global search power of GA. Also, a local search procedure has been incorporated into the GA to improve the performance of the algorithm. The model considers precedence relations among job operations, based on which feasible process plans for each job can be represented implicitly. A novel neighborhood function, considering the constraints of a flexible job shop environment and nonlinear precedence relations among operations, is presented to speed up the local search process. In experimental study, the performance of the proposed algorithm has been evaluated based on a number of problems adopted from the literature. The experimental results demonstrate the efficiency of the proposed algorithm to find optimal or near-optimal solutions.