An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs

In this paper, we deal with the two-machine flow shop scheduling problem having an unavailability interval on the first machine, and nonresumable jobs. We first present an enhancement procedure that, once applied to any arbitrary solution, produces a schedule that is at most equal 2 times the optimal makespan. We then develop an improved heuristic, with a relative worst-case error of 3/2.