A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints
From MaRDI portal
Publication:582203
DOI10.1016/0377-2217(89)90216-6zbMath0689.90045MaRDI QIDQ582203
Publication date: 1989
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(89)90216-6
graph; polynomial algorithm; distributed system; independent interchangeable processors; independent memory; optimal job scheduling; tree-like precedence constraints
68Q25: Analysis of algorithms and problem complexity
90C90: Applications of mathematical programming
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68N25: Theory of operating systems
Related Items
Parallel Machine Scheduling with Uncertain Communication Delays, Sensitivity bounds for machine scheduling with uncertain communication delays, A polynomially solvable class of quadratic semi-assignment problems, Scheduling inverse trees under the communication model of the LogP-machine, Tree scheduling with communication delays, Scheduling complete intrees on two uniform processors with communication delays, Lower bounds for the quadratic semi-assignment problem, Scheduling UET-UCT outforests to minimize maximum lateness, Scheduling unitary task systems with zero--one communication delays for quasi-interval orders, A standard task graph set for fair evaluation of multiprocessor scheduling algorithms, Optimal preemptive scheduling on a fixed number of identical parallel machines
Cites Work