Two-machine shop scheduling: compromise between flexibility and makespan value

Carl Esswein

Laboratoire d'Informatique,
Ecole d'Ingénieurs en Informatique pour l'Industrie,
64 avenue Jean Portalis,
37200 Tours


We consider the problem of providing flexibility to solutions for the
two-machine flow shop scheduling problem. We use the concept of
group-scheduling to characterize a whole set of schedules so as to provide
many choices to the Decision Maker at any decision instant. A group-schedule
is a sequence of groups of permutable operations defined on each machine
where each group is such that any permutation of the operations inside the
group leads to a feasible schedule. To measure the provided flexibility, we
introduce the number of groups criterion, denoted by #Gps, which is to
minimize. The provided flexibility and the quality of the solution are
conflicting, thus we search for a compromise solution between a low number
of groups and a low makespan. We show that this problem is strongly NP-hard.
An heuristic algorithm is proposed and computational experiments provided.
Finally, some extensions to other shop scheduling problems are proposed: tho
job shop and the open shop cases are considered.