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 in questo prodotto:
File Dimensione Formato  
TKindt2020_Article_ExponentialTimeAlgorithmsForJu.pdf

non disponibili

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

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2948112