Anzeige
Erschienen in:
17.12.2019
Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.