Name
Abstract | ||
|---|---|---|
We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity $$O(p(n) \\times \\sqrt{2}^n)$$O(p(n)×2n), p being a polynomial function of n. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-016-0054-4 | J. Comb. Optim. |
Keywords | Field | DocType |
Scheduling,Approximation algorithms,Exact exponential approaches | Open shop,Approximation algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Polynomial,Scheduling (computing),Flow shop scheduling,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 1 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Federico Della Croce | 1 | 399 | 41.60 |
| Christos Koulamas | 2 | 427 | 46.71 |
| Vincent T'kindt | 3 | 203 | 21.04 |