Metaheuristics for Logistics

6The Flow-Shop Problem

The permutation flow-shop scheduling problem (FSSP) is one of the scheduling problems that receives the most attention from the scientific literature. With a fully-stacked and well-documented library of cases, it is an ideal problem, like that of the traveling salesman, for those who want to test new ideas.

I had the opportunity, in the course of my research activities, to adapt the ejection-chain ideas to this problem. It is this experience, which helped me to acquire very good results, even though it was not widely published and remains poorly known, that I would like to share in this chapter.

The flow-shop problem is presented in section 2.5.1.

6.1. Representation and assessment of a solution

The permutation flow-shop problem is characterized by the order in which parts enter the workshop, and that order remains the same for all machines. It is, therefore, natural to represent a solution by a permutation. The flow-shop includes many different solutions as there are permutations; namely n! if n is the number of parts.

To assess this solution, we assume that an operation starts as soon as all conditions necessary for its execution are met. Schedules built this way are called semi-active. It is not possible to move forward with the execution of an operation without calling into question the order of parts of machines. This assumption is not restrictive at all because it was shown that at least an optimum solution exists among all semi-active schedules. ...