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

ABSTRACT

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.

KEYWORDS:

• Flexible job shop problem
• parallel machines
• flow time

Disclosure of potential conflicts of interest

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Liu Changchun

Changchun Liu received his Ph.D. degree in the Department of Industrial Engineering from the Tsinghua University of China. His research interests include operations research on container terminal, production scheduling, logistic. His papers have appeared in IISE Transactions, European Journal of Operational Research, Omega.

Xiang Nengjie

Nengjie Xiang received a bachelor's degree in the School of information science and technology, Northwest University, Xi’an, China.