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]
Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
T'kindt V.;Della Croce di Dojola F.
2020
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 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.File | Dimensione | Formato | |
---|---|---|---|
TKindt2020_Article_ExponentialTimeAlgorithmsForJu.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
415.18 kB
Formato
Adobe PDF
|
415.18 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2948112