On-line scheduling revisited

DOI<343::AID-JOS54>3.0.CO;2-2 10.1002/1099-1425(200011/12)3:6<343::AID-JOS54>3.0.CO;2-2zbMath0966.90032MaRDI QIDQ1592757

Rudolf Fleischer, Michaela Wahl

Publication date: 25 January 2001

Published in: Journal of Scheduling (Search for Journal in Brave)

zbMATH Keywords

list scheduling; competitive analysis; MR

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Unnamed Item, Online Makespan Scheduling with Job Migration on Uniform Machines, Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines, Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming, Streaming algorithms for bin packing and vector scheduling, Algorithms for single machine scheduling problem with release dates and submodular penalties, Parallel solutions for preemptive makespan scheduling on two identical machines, Improved approximation algorithms for multiprocessor scheduling with testing, Online early work maximization on three hierarchical machines with a common due date, A case study on the application of an approximated hypercube model to emergency medical systems management, Semi-online scheduling problems on a small number of machines, Lower bounds for online makespan minimization on a small number of related machines, New upper and lower bounds for online scheduling with machine cost, Semi-online scheduling revisited, Robust algorithms for preemptive scheduling, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Online bin stretching with bunch techniques, On robust online scheduling algorithms, Semi-on-line multiprocessor scheduling with given total processing time, Online hierarchical scheduling: an approach using mathematical programming, Online scheduling with rearrangement on two related machines, Online scheduling with rejection and withdrawal, Improved bounds for online scheduling with eligibility constraints, Scheduling with testing on multiple identical parallel machines, Online makespan minimization with budgeted uncertainty, Semi on-line scheduling on three processors with known sum of the tasks, List's worst-average-case or WAC ratio, Online parallel machines scheduling with two hierarchies, Scheduling web advertisements: a note on the minspace problem, Scheduling parallel jobs to minimize the makespan, An efficient algorithm for semi-online multiprocessor scheduling with given total processing time, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Online scheduling with reassignment, On-line scheduling of multi-core processor tasks with virtualization, Preemptive online scheduling: Optimal algorithms for all speeds, Priority algorithms for the subset-sum problem, A survey on makespan minimization in semi-online environments, Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Improved lower bounds for online scheduling to minimize total stretch, Algorithms better than LPT for semi-online scheduling with decreasing processing times, Minimizing the maximum starting time on-line, Pseudo lower bounds for online parallel machine scheduling, Offline file assignments for online load balancing, Scheduling In the random-order model, An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time, Starting time minimization for the maximum job variant, Online makespan scheduling with job migration on uniform machines, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model, New results on competitive analysis of online SRPT scheduling, Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing, An optimal online algorithm for scheduling with general machine cost functions, Online scheduling of jobs with favorite machines, Tight lower bounds for semi-online scheduling on two uniform machines with known optimum, Online makespan minimization with parallel schedules, Separating online scheduling algorithms with the relative worst order ratio, On the value of job migration in online makespan minimization, Improved algorithm for a generalized on-line scheduling problem on identical machines, An efficient algorithm for bin stretching, Load balancing of temporary tasks in the \(\ell _{p}\) norm, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, Semi-online scheduling: a survey, ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER, WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION, Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures, ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST

Cites Work

• A lower bound for randomized on-line multiprocessor scheduling
• New algorithms for an ancient scheduling problem.
• Online algorithms. The state of the art
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• New lower and upper bounds for on-line scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• A Note on "An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling"
• A Better Algorithm for an Ancient Scheduling Problem
• Bounds for Certain Multiprocessing Anomalies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item