Scheduling Two Stage Hybrid Flow Shop 
with Availability Constraints

Hamid ALLAOUI and Abdelhakim ARTIBA
allaoui@fucam.ac.be


Abstract

The most of papers suppose that machines are always available. 
However in the real life industry, machines may be subject to 
some unavailability periods due to the maintenance activities 
such as the breakdowns (stochastic case) and the preventive 
maintenance (deterministic case). In this paper we investigate 
the two-stage hybrid flow shop scheduling problem with only one 
machine on the first stage and m machines on the second stage to 
minimize the makespan. We consider that each machine is subject 
to at most one unavailability period. The start time and the end 
time of each period are known in advance (deterministic case) and 
only the Non-Resumable case is studied. Firstly we discuss the 
complexity of the problem. After we give the Branch and Bound 
model for this problem. Finally we calculate the worst case 
performances of three heuristics: H heuristic, LIST algorithm and 
the LPT algorithm.