General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

DOI10.1137/S0097539799361737zbMath1095.68010OpenAlexW2068946514MaRDI QIDQ5470701

Lorant Porkolab, Klaus Jansen

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799361737

zbMATH Keywords

linear programmingapproximation algorithmsscheduling problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (2)

A simple linear time approximation algorithm for multi-processor job scheduling on four processors ⋮ Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques

This page was built for publication: General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time