×

Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints. (Chinese. English summary) Zbl 1438.90098

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C05 Linear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI