Improved Bounds for the Online Scheduling Problem

DOI10.1137/S0097539702403438zbMath1023.90031MaRDI QIDQ4706228

John F. Rudin III, R. Chandrasekaran

Publication date: 19 June 2003

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

zbMATH Keywords

machine schedulingcompetitive ratiolower boundonline scheduling

Mathematics Subject Classification ID

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

Related Items (36)

A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ List's worst-average-case or WAC ratio ⋮ Online parallel machines scheduling with two hierarchies ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ A SEMI-ON-LINE SCHEDULING PROBLEM OF TWO PARALLEL MACHINES WITH COMMON MAINTENANCE TIME ⋮ Online load balancing with general reassignment cost ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Improved lower bounds for the online bin stretching problem ⋮ Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing ⋮ On the value of job migration in online makespan minimization ⋮ Improved lower bounds for online scheduling to minimize total stretch ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ Semi-online scheduling problems on a small number of machines ⋮ 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 ⋮ Offline file assignments for online load balancing ⋮ New upper and lower bounds for online scheduling with machine cost ⋮ Unnamed Item ⋮ 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 ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ Online scheduling with reassignment ⋮ Scheduling In the random-order model ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Pseudo lower bounds for online parallel machine scheduling ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST

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