Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights

Vincent T’kindt (), Lei Shang () and Federico Della Croce ()
Additional contact information
Vincent T’kindt: University of Tours
Lei Shang: University of Tours
Federico Della Croce: DIGEP

Journal of Combinatorial Optimization, 2020, vol. 39, issue 3, No 7, 764-775

Abstract: 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)$$O∗(1.4143n). 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)$$O∗(3n). To the best of our knowledge, these are the first worst-case complexity results obtained for non regular criteria in scheduling.

Keywords: Single machine; Parallel machines; Just-in-time; Exponential time algorithms (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00512-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:3:d:10.1007_s10878-019-00512-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00512-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().