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.

doi:10.1007/s10878-019-00512-z

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:	T'KINDT, VINCENT Shang L. DELLA CROCE DI DOJOLA, Federico mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2020
Rivista:	JOURNAL OF COMBINATORIAL OPTIMIZATION
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

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

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

PORTO @ Archivio Istituzionale della Ricerca

File in questo prodotto: