Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates

Deteriorating jobs scheduling problems can be found in many practical situations. Due to the essential complexity of the problem, most of the research focuses on the single-machine setting. In this paper, we address a total completion time scheduling problem in the mm-machine permutation flow shop. First of all, we propose a dominance rule and an efficient lower bound to speed up the searching for the optimal solution. Second, several deterioration patterns, which include an increasing, a decreasing, a constant, a V-shaped, and a ΛΛ-shaped one, are investigated in order to study the impact of the deterioration rates. Finally, the performance of some well-known heuristics under various deterioration patterns is evaluated.