Title | ||
---|---|---|
An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan |
Abstract | ||
---|---|---|
This paper considers the large-scale mixed job shop scheduling problem with general number of jobs on each route. The problem includes ordinary machines, batch machines (with bounded or unbounded capacity), parallel machines, and machines with breakdowns. The objective is to find a schedule to minimize the makespan. For the problem, we define a virtual problem and a corresponding virtual schedule, based on which our algorithm TVSA is proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution is O(1), which indicates the algorithm is asymptotically optimal. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/s10878-015-9974-7 | J. Comb. Optim. |
Keywords | Field | DocType |
Job shop,Makespan,Batch machine,Flexible machine,Available constrain | Mathematical optimization,Job shop scheduling,Job shop scheduling problem,Computer science,Job shop,Flow shop scheduling,Asymptotically optimal algorithm,Bounded function | Journal |
Volume | Issue | ISSN |
33 | 2 | 1382-6905 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manzhan Gu | 1 | 36 | 4.99 |
Xiwen Lu | 2 | 182 | 21.03 |
Jinwei Gu | 3 | 687 | 39.49 |