A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)

DOI10.1007/s001860200228zbMath1064.90016OpenAlexW2002473393MaRDI QIDQ1812291

Peter Brucker, Sigrid Knust, Johann L. Hurink

Publication date: 23 June 2003

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001860200228

zbMATH Keywords

schedulingparallel machinescomplexity resultsouttree

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Equitable scheduling on a single machine, Normal-form preemption sequences for an open problem in scheduling theory, A new polynomial algorithm for a parallel identical scheduling problem, Minimizing total completion time for UET tasks with release time and outtree precedence constraints, Ideal schedules in parallel machine settings, Fast LP models and algorithms for identical jobs on uniform parallel machines, A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time, Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time, Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints, How small are shifts required in optimal preemptive schedules?