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 delay before jobs are processed. These assumptions are being relaxed in recent papers that consider re-entrance problems and those with schedule deterioration. In this paper, these two assumptions are relaxed together, and a model of re-entrance flow shop with 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 than both Nawaz Enscor and Ham (NEH) algorithm and Genetic Algorithm (NA) 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 or problems increase. This model would find useful applications in a number of metallurgical and manufacturing processes where such problems are usually encountered.