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

DOI10.1007/S10951-018-0596-7MaRDI QIDQ2283293zbMATH OpenOpenAlexFDO

Authors Tianyu Wang, Odile Bellenguez-Morineau

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

parallel machine schedulingprecedence constraintslevel-order

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of scheduling unrelated parallel machines with limited preemptions
• On a parallel machine scheduling problem with precedence constraints
• Scheduling of uniform parallel machines with s-precedence constraints
• scientific article; zbMATH DE number 6263704
• Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints
• A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
• scientific article; zbMATH DE number 4023000
• Parallel machine scheduling with precedence constraints and setup times
• Scheduling preemptive jobs with precedence constraints on parallel machines

Cites work

• A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• How useful are preemptive schedules?
• On preemption redundancy in scheduling unit processing time jobs on two parallel machines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• 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
• Scheduling Opposing Forests
• Scheduling. Theory, algorithms, and systems.

Cited in

(10)

• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Scheduling lower bounds via AND subset sum
• Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
• Scheduling lower bounds via and subset sum
• Scheduling unit-length jobs with precedence constraints of small height
• Parallel machine scheduling with a simultaneity constraint and unit-length jobs to minimize the makespan
• A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Equitable scheduling on a single machine
• On the complexity of scheduling unit-time jobs with or-precedence constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283293)