Bounds for List Schedules on Uniform Processors
From MaRDI portal
Publication:3891758
DOI10.1137/0209007zbMath0446.68025OpenAlexW4251714866MaRDI QIDQ3891758
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209007
Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Related Items
Online-bounded analysis, A survey on makespan minimization in semi-online environments, The shortest first coordination mechanism for a scheduling game with parallel-batching machines, Makespan minimization on uniform parallel machines with release times, Fast approximation algorithms for bi-criteria scheduling with machine assignment costs, Coordination Mechanisms for Selfish Parallel Jobs Scheduling, Optimal Coordination Mechanisms for Unrelated Machine Scheduling, A new algorithm for online uniform-machine scheduling to minimize the makespan, Separating online scheduling algorithms with the relative worst order ratio, Semi-online scheduling with bounded job sizes on two uniform machines, List scheduling revisited, Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines, ONLINE SCHEDULING OF MIXED CPU-GPU JOBS, Coordination mechanisms for parallel machine scheduling, Online scheduling on uniform machines with two hierarchies, Online algorithms for scheduling with machine activation cost on two uniform machines, Semi-online scheduling with known maximum job size on two uniform machines, Lower bounds for online makespan minimization on a small number of related machines, Preemptive online scheduling with rejection of unit jobs on two uniformly related machines, Smoothed performance guarantees for local search, An on-line algorithm for some uniform processor Scheduling, Coordination mechanisms with hybrid local policies, Strategic Scheduling Games: Equilibria and Efficiency, Efficient scheduling of tasks without full use of processor resources, The price of anarchy on uniformly related machines revisited, Scheduling games with rank-based utilities, Competitive ratio of list scheduling on uniform machines and randomized heuristics, A note on makespan minimization in two-stage flexible flow shops with uniform machines, General parametric scheme for the online uniform machine scheduling problem with two different speeds, Bounds for parallel machine scheduling with predefined parts of jobs and setup time, Performance guarantees of jump neighborhoods on restricted related parallel machines, Non-clairvoyant scheduling games, Inefficiency of Nash equilibria with parallel processing policy, Worst-case equilibria, Approximate strong equilibria in job scheduling games with two uniformly related machines, Semi-online scheduling on two uniform machines with the known largest size, Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling, Scheduling games with machine-dependent priority lists, Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem, Performance guarantees for scheduling algorithms under perturbed machine speeds, A coordination mechanism for a scheduling game with parallel-batching machines, Deterministic monotone algorithms for scheduling on related machines, On the optimality of list scheduling for online uniform machines scheduling, Semi-online scheduling on two uniform processors, Online Scheduling on a CPU-GPU Cluster, Online Bounded Analysis, Randomized on-line scheduling on two uniform machines, Semi-on-line scheduling with ordinal data on two uniform machines, Online scheduling with reassignment on two uniform machines, On-line load balancing of temporary tasks revisited, Minmax scheduling problems with a common due-window, Online scheduling of jobs with favorite machines, Decentralized utilitarian mechanisms for scheduling games, 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, Coordination mechanisms for selfish scheduling, Online scheduling on two uniform machines to minimize the makespan, Starting time minimization for the maximum job variant, Improved price of anarchy for machine scheduling games with coordination mechanisms, Online scheduling with general machine cost functions, Tighter approximation bounds for LPT scheduling in two special cases, Approximation scheduling algorithms: a survey, Optimal and online preemptive scheduling on uniformly related machines, Scheduling on uniform parallel machines to minimize maximum lateness, Coordination mechanisms for scheduling selfish jobs with favorite machines, Flexible flow shop scheduling with uniform parallel machines, A lower bound on deterministic online algorithms for scheduling on related machines without preemption, Performance guarantees of local search for minsum scheduling problems
