Scheduling flow shops with operators

Abstract

This paper addresses the problem of assigning a number of operators, less than the number of machines, in a flow shop environment. We study two different problems. The first is the assignment of operators subject to a fixed job sequence; the second is on handling simultaneously the assignment of operators and the scheduling of jobs on the machines. We present complexity results and develop a new lower bound. Heuristic algorithms are designed for both problems. An experimental study is then conducted to evaluate the quality of our solving methods. The results show that the appropriate approach depends on the parameters of the problem, including the number of operators. The methods also provided results close to the theoretical lower bound in most of the cases.

Keywords:

• scheduling
• flow shop
• operators
• makespan
• complexity analysis

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 In the rest of the paper, we use the word ‘classical’ to denote problems without resource constraints.

2 Without permutation constraints.

3 which corresponds to operation S(i, j), $1\le i\le m$, $1\le j\le n$.

4 An operation becomes available when all its preceding operations as well as all the operations of job j on machines $M_{i^{\prime }},i^{\prime }<i$, have been completed.

5 which is its c-th operation.

6 These solution meet the permutation structure. Indeed, we had noticed that generating random solutions for the standard flow shop produced terrible results.