Makespan minimization in reentrant flow shop problem with identical jobs

A. A. Romanova ; V. V. Servakh ; V. Yu. Tavchenko

Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 99-111

Résumé

We consider the reentrant flow shop problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$ with identical jobs and makespan criterion. We prove its NP-hardness in the ordinary sense. The proof is performed by polynomial reduction of the problem $J3|n =3|C_{\max}$ to the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$ with three identical jobs. Using the input data of the problem $J3|n=3|C_{\max}$, we have constructed a special type of job for the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$. In the proof, we analyze all possible variants of critical paths in the constructed instance. We also propose a dynamic programming algorithm to find the optimal solution of the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$. Analysis of the time complexity of the algorithm showed that the problem with fixed number of jobs is pseudopolynomially solvable. Next, we study the use of cyclic schedules to construct approximate solutions. A cyclic schedule with a minimum cycle time can be found in polynomial time. We propose a polynomial algorithm for finding an approximate solution. This algorithm is based on the construction of a cyclic schedule with a minimum cycle time and its subsequent compaction at the beginning and at the end. We construct an upper bound of the makespan of cyclic schedules. This bound depends on the number of jobs processed in one cycle. The paper provides numerous examples characterizing cyclic schedules from both the positive and negative sides to solve the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$.

Détail

Keywords: schedule, identical jobs, NP-hardness, theory of NP-completeness.
Mots-clés : pseudopolynomial algorithm