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

DOI10.1007/S10951-018-0596-7zbMATH Open1427.90161OpenAlexW2907439023MaRDI QIDQ2283293FDOQ2283293

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

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)

Cites Work

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

Cited In (4)

• Scheduling lower bounds via AND subset sum
• Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
• Equitable scheduling on a single machine
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• Parallel machine scheduling with precedence constraints and setup times 👍 👎
• Scheduling preemptive jobs with precedence constraints on parallel machines 👍 👎

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)