  Flow shops are widely studied machine environments in which all jobs must
visit all machines in the same order. While conventional flow shops assume that
each job traverses the shop only once, many industrial environments require
jobs to pass through the shop multiple times before completion. This means that
after traversing the shop and completing its processing on the last machine, a
job must return to the first machine and traverse the shop again until it has
completed all its required loops. Such a setting, referred to as a flow shop
with reentry, has numerous applications in industry, e.g., semiconductor
manufacturing. The planning problem is to schedule all loops of all jobs while
minimizing the total (weighted) completion time. In this paper, we consider
reentrant flow shops with unit processing times. We propose the Least Remaining
Loops First (LRL) priority rule and show that it minimizes the total completion
time. Furthermore, we analyze the complexity of minimizing the total weighted
completion time when the jobs have different weights. We show that this problem
is NP-hard in the ordinary sense and provide a pseudo-polynomial time
algorithm. Additionally, we propose the Weighted Least Remaining Loops First
(WLRL) priority rule and show that it has a worst-case performance ratio of
about 1.2.
