Makespan minimization with OR-precedence constraints

Artikel

We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed—in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563–1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of 4/3-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4/3 - \varepsilon $$\end{document} is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2)$$\end{document} for arbitrary processing times and it can be reduced to O(n) for unit processing times, where n is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.

Object Details

• Language: Englisch

References and Relationships

• Bibliographic citation: Journal: Journal of Scheduling ; ISSN: 1099-1425 ; Volume: 24 ; Year: 2021 ; Issue: 3 ; Pages: 319-328 ; New York, NY: Springer US

Classification and Topics

• Classification: Management
• Subject: Scheduling ; Precedence constraints ; Approximation algorithm ; Makespan

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Happach, Felix
• Event: Veröffentlichung
• (who): Springer US
• (where): New York, NY
• (when): 2021

Further information

• DOI: doi:10.1007/s10951-021-00687-6
• Last update: 10.03.2025, 11:44 AM CET