Exponential-time algorithms for parallel machine scheduling problems

Olivier Ploton () and Vincent T’kindt ()
Additional contact information
Olivier Ploton: Université de Tours
Vincent T’kindt: Université de Tours

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 11, 3405-3418

Abstract: Abstract In this paper we consider the problem of scheduling a set of jobs on unrelated parallel machines in the presence of job release dates and deadlines, and we deal with the minimization of any general regular, either maximum or sum, objective function. We describe a generic exact exponential algorithm, solving a problem in two phases. In the first phase, given a threshold objective value, the algorithm counts the number of schedules whose objective value is at most the threshold. For this purpose, by using Inclusion-Exclusion, it solves multiple relaxed single-machine problems by means of dynamic programming. In the second phase, the algorithm uses this counting procedure to determine the optimal objective value and build, step by step, an explicit optimal schedule. The strength of this algorithm is to manage a wide class of parallel machine scheduling problems, and to achieve, on a theoretical point on view, moderate exponential time and pseudopolynomial space worst-case complexity bounds. While not the fastest in practice compared to specialized algorithms, this generic algorithm enhances the state-of-the-art theoretical worst-case complexity bounds of several particular parallel machine scheduling problems.

Keywords: Parallel-machine scheduling; Worst-case complexity; Inclusion-Exclusion (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00901-x 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:44:y:2022:i:5:d:10.1007_s10878-022-00901-x

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

DOI: 10.1007/s10878-022-00901-x

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 ().