Journal
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 58, Issue 2, Pages 487-508Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2019.1597291
Keywords
Flexible job shop; job shop scheduling; branch and bound; mixed integer linear programming; column generation
Categories
Funding
- Natural Science Foundation of China [71871203, 51305400]
- Zhejiang Provincial Natural Science Foundation of China [LY18G010017, LY18G020018]
Ask authors/readers for more resources
Job shop scheduling, as one of the classical scheduling problems, has been widely studied in literatures, and proved to be mostly NP-hard. Although it is extremely difficult to solve job shop scheduling with no-wait constraint to optimality, the two-machine no-wait job shop scheduling to minimise makespan could be solvable in polynomial time when each job has exactly two equal length operations (proportionate job shop). In the present paper, an extension is attempted by considering a proportionate flexible two-stage no-wait job shop scheduling problem with minimum makespan, and a set-covering formulation is put forward which contains a master problem and a pricing problem. To solve this problem, a column generation (CG)-based approach is implemented. In comparison, a mixed integer programming model is constructed and optimised by Cplex. A series of randomly generated numerical instances are calculated. And the testing result shows that the mixed integer model handled by Cplex can only solve small scale cases, while the proposed CG-based method can conquer larger size problems in acceptable time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available