Permutation Schedules Are Good For Realistic Flow Shop

Colloque avec actes et comité de lecture. internationale.International audienceIt is well known that the permutation flow shop solutions are dominant subsets for problems with two machines to minimize any regular criterion and for problems with three machines to minimize the makespan. For m ³ 4, Potts et al. (1991) showed that the ratio (the best makespan for permutation solutions) / (the best makespan for general solutions) can increase to infinity with the number of jobs and the number of machines. Röck and Schmidt (1983) proved that this ratio is limited by half the number of machines. This work is an attempt to show that permutation solutions remain good when the shop satisfies some simple conditions which are natural and realistic for an industrial workshop. Some new results are proved for small particular cases