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 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 O∗(3 n). To the best of our knowledge, these are the first worst-case complexity results obtained for non regular criteria in scheduling.
Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights / T'kindt, V.; Shang, L.; Della Croce di Dojola, F.. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - ELETTRONICO. - 39:3(2020), pp. 764-775. [10.1007/s10878-019-00512-z]
Titolo: | Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights | |
Autori: | ||
Data di pubblicazione: | 2020 | |
Rivista: | ||
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/s10878-019-00512-z | |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
TKindt2020_Article_ExponentialTimeAlgorithmsForJu.pdf | 2a Post-print versione editoriale / Version of Record | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11583/2948112