A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
From MaRDI portal
Publication:1812291
DOI10.1007/s001860200228zbMath1064.90016MaRDI 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
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Equitable scheduling on a single machine, Fast LP models and algorithms for identical jobs on uniform parallel machines, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Normal-form preemption sequences for an open problem in scheduling theory, Ideal schedules in parallel machine settings, Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time, A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time, How small are shifts required in optimal preemptive schedules?, Minimizing total completion time for UET tasks with release time and outtree precedence constraints, Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints, A new polynomial algorithm for a parallel identical scheduling problem