Bounds for LPT Schedules on Uniform Processors
From MaRDI portal
Publication:4117391
DOI10.1137/0206013zbMath0347.68043OpenAlexW1978732961MaRDI QIDQ4117391
Oscar H. Ibarra, Teofilo F. Gonzalez, Sartaj K. Sahni
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0206013
Related Items
A survey on makespan minimization in semi-online environments, A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem, Parametric analysis of the quality of single preemption schedules on three uniform parallel machines, A modified LPT algorithm for the two uniform parallel machine makespan minimization problem, New approximation bounds for LPT scheduling, Approximations and auctions for scheduling batches on related machines, Semi-online scheduling with bounded job sizes on two uniform machines, Moderately exponential approximation for makespan minimization on related machines, Semi-online scheduling with known maximum job size on two uniform machines, Worst-case analysis of LPT scheduling on a small number of non-identical processors, Efficient scheduling of tasks without full use of processor resources, The price of anarchy on uniformly related machines revisited, Optimizing performance and reliability on heterogeneous parallel systems: approximation algorithms and heuristics, Bounds for parallel machine scheduling with predefined parts of jobs and setup time, Approximate strong equilibria in job scheduling games with two uniformly related machines, An efficient polynomial time approximation scheme for load balancing on uniformly related machines, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Parametric bounds for LPT scheduling on uniform processors, A comment on scheduling on uniform machines under chain-type precedence constraints, A study of scheduling problems with preemptions on multi-core computers with GPU accelerators, Deterministic monotone algorithms for scheduling on related machines, A note on LPT scheduling, Job Tardiness in Unequal Parallel Processor Systems, Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers, Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms, A Unified Approach to Truthful Scheduling on Related Machines, Related machine scheduling with machine speeds satisfying linear constraints, The Price of Anarchy on Uniformly Related Machines Revisited, Selfish load balancing for jobs with favorite machines, A linear compound algorithm for uniform machine scheduling, NP-Complete operations research problems and approximation algorithms, Closing the Gap for Makespan Scheduling via Sparsification Techniques, Approximation algorithms for scheduling unrelated parallel machines, A note on MULTIFIT scheduling for uniform machines, An approximation algorithm for multi-agent scheduling on two uniform parallel machines, Tighter approximation bounds for LPT scheduling in two special cases, Semi-online machine covering for two uniform machines, Approximation scheduling algorithms: a survey, Coordination mechanisms for scheduling selfish jobs with favorite machines, Single parameter analysis of power of preemption on two and three uniform machines, First fit decreasing scheduling on uniform multiprocessors
