The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints

DOI10.1007/s10951-018-0596-7zbMath1427.90161OpenAlexW2907439023MaRDI QIDQ2283293

Odile Bellenguez-Morineau, Tianyu Wang

Publication date: 30 December 2019

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-018-0596-7

zbMATH Keywords

precedence constraintsparallel machine schedulinglevel-order

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (3)

Scheduling lower bounds via AND subset sum ⋮ Equitable scheduling on a single machine ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time

Cites Work

• How useful are preemptive schedules?
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Opposing Forests
• Scheduling
• On preemption redundancy in scheduling unit processing time jobs on two parallel machines

This page was built for publication: The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints