A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
From MaRDI portal
Publication:1812291
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
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?
