Abstract:

This paper considers the distributed permutation flow shop scheduling problem with eligibility constraints, which means that there exists an available factory set for each job. The processing time of each job in different factories may not be the same. We present a mixed integer linear programming based on position of jobs in all factories. The general problem and three special cases are analyzed and several heuristic algorithms are proposed with performance guarantee. A heuristic algorithm based on greedy algorithm, LFJ and NEH is carried out to obtain an approximate solution. The branch and bound method based on the approximate value is proposed to find optimal scheduling. At last, an example is used to explain the computing process of NEHg2 and the branch and bound method; numerous experiments prove the effectiveness of the NEHg heuristics.

Key words: distributed permutation flow shop scheduling, machine eligibility constraints, mathematic programming, heuristic algorithm, branch and bound method