Name
Title | ||
|---|---|---|
Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights |
Abstract | ||
|---|---|---|
This paper focuses on the solution, by exact exponential-time algorithms, of just-in-time scheduling problems when jobs have symmetric earliness/tardiness weights and share a non restrictive common due date. For the single machine problem, a Sort & Search algorithm is proposed with worst-case time and space complexities in $$\mathcal {O}^*(1.4143^n)$$. This algorithm relies on an original modeling of the problem. For the case of parallel machines, an algorithm integrating a dynamic programming algorithm across subsets and machines and the above Sort & Search algorithm is proposed with worst-case time and space complexities in $$\mathcal {O}^*(3^n)$$. To the best of our knowledge, these are the first worst-case complexity results obtained for non regular criteria in scheduling. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s10878-019-00512-z | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Single machine, Parallel machines, Just-in-time, Exponential time algorithms | Dynamic programming,Mathematical optimization,Search algorithm,Tardiness,Exponential function,Scheduling (computing),sort,Spacetime,Algorithm,Mathematics,Theory of computation | Journal |
Volume | Issue | ISSN |
39 | 3 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent T'kindt | 1 | 203 | 21.04 |
| Lei Shang | 2 | 0 | 0.34 |
| Federico Della Croce | 3 | 399 | 41.60 |