Improved Bounds for the Online Scheduling Problem

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Recommendations

A better lower bound for on-line scheduling
Better Bounds for Online Scheduling
Lower bounds for online makespan minimization on a small number of related machines
scientific article; zbMATH DE number 1559597
New algorithms for an ancient scheduling problem.

Cited in

(50)

Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead
A better lower bound for on-line scheduling
A survey on makespan minimization in semi-online environments
Improved lower bounds for online scheduling to minimize total stretch
Online scheduling of two job types on a set of multipurpose machines with unit processing times
Pseudo lower bounds for online parallel machine scheduling
Improved competitive algorithms for online scheduling with partial job values
Offline file assignments for online load balancing
Scheduling In the random-order model
Online makespan scheduling with job migration on uniform machines
Online load balancing with general reassignment cost
Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
Improved lower bounds for the online bin stretching problem
A note on the online interval scheduling secretary problem
A semi-on-line scheduling problem of two parallel machines with common maintenance time
Online minimum makespan scheduling with a buffer
Almost sure asymptotic optimality for online routing and machine scheduling problems
Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST
Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling
An on-line scheduling problem of parallel machines with common maintenance time
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
Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs
Semi-online scheduling revisited
Simultaneously load balancing for every p-norm, with reassignments
Online algorithms with advice for bin packing and scheduling problems
Online makespan minimization: the power of restart
Online Makespan Scheduling with Job Migration on Uniform Machines
Approximating the optimal algorithm for online scheduling problems via dynamic programming
Parallel solutions for preemptive makespan scheduling on two identical machines
Improved approximation algorithms for multiprocessor scheduling with testing
Online scheduling with rearrangement on two related machines
Online unrelated-machine load balancing and generalized flow with recourse
Scheduling unit length jobs on parallel machines with lookahead information
Scheduling in the random-order model
Fifty years of research in scheduling -- theory and applications
Lower bounds for online scheduling on four processors
Semi-online multiprocessor scheduling with known largest job processing time
On the optimality of list scheduling for online uniform machines scheduling
Semi-online scheduling with non-increasing job sizes and a buffer
Fully-dynamic load balancing
Improved bounds for online scheduling with eligibility constraints
Fully-dynamic load balancing
Online makespan scheduling under scenarios
List's worst-average-case or WAC ratio
Online parallel machines scheduling with two hierarchies
Improved upper bounds for online malleable job scheduling
Online scheduling with reassignment

This page was built for publication: Improved Bounds for the Online Scheduling Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4706228)