Minimizing the maximum flow time for flexible job shop problem with parallel machines

This paper studies a flexible job shop problem with parallel machines considering release time. The objective aims to minimize the maximum flow time. Based on the specific characteristics of the problem, we find a property which can reduce the 2d dimension of solution space to d dimension, where d is the total number of operations. To solve the small-scale problem, a branch-and-bound algorithm is proposed. For the medium-scale problem, a heuristic based on a differential evolution algorithm is proposed. The LSPT-DS heuristic is tried to solve the large-scale problem. Through computational experiments, the proposed algorithms are proved to be both effective and efficient in solving this flexible job shop problem. Besides experiments are also conducted to verify that the objective to minimize the maximum flow time is reasonable.

Automated summary

This paper studies a flexible job shop problem with parallel machines, aiming to minimize the maximum flow time. Based on problem characteristics, a property is discovered to reduce the solution space dimension. A series of algorithms are proposed to solve problems of different scales, and computational experiments demonstrate their effectiveness and efficiency.