Reentrant permutation flowshop scheduling with a deteriorating schedule

Abstract

The classic flow shop problem assumes that jobs make only single passes through the processing machines and that the processing times are not affected by the length of the delay before jobs are processed. These assumptions are being relaxed in recent papers that consider reentrance problems and those with schedule deterioration. In this study, these two assumptions are both relaxed, and a model of a reentrant flowshop with a deteriorating schedule is considered. A linear programming formulation of the problem is first presented. Three solution heuristics are considered under different deterioration scenarios. It was observed that both Nawaz Enscor and Ham (NEH) algorithm and Genetic Algorithm (GA) performed much better than the Campbell Dudek and Smith (CDS) algorithm. Overall, when considering both the quality of solution and computational time together, the NEH algorithm seems to have performed much better than the others as the size of problems increases. This model would find useful applications in some metallurgical and manufacturing processes where such problems are usually encountered.