Better Bounds for Online Scheduling
From MaRDI portal
Publication:4268892
DOI10.1137/S0097539797324874zbMath0943.68183OpenAlexW2095518199WikidataQ63353545 ScholiaQ63353545MaRDI QIDQ4268892
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539797324874
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35)
Related Items (63)
A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ 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 ⋮ Tight upper bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ 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 ⋮ Scheduling resource allocation with timeslot penalty for changeover ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Improved lower bounds for the online bin stretching problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On-line hierarchical job scheduling on grids with admissible allocation ⋮ On the value of job migration in online makespan minimization ⋮ Rejecting jobs to minimize load and maximum flow-time ⋮ Scheduling web advertisements: a note on the minspace problem ⋮ Scheduling parallel jobs to minimize the makespan ⋮ Improved lower bounds for online scheduling to minimize total stretch ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ Improved semi-online makespan scheduling with a reordering buffer ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ Semi-online scheduling problems on a small number of machines ⋮ Multiprofessor scheduling ⋮ Online hierarchical scheduling: an approach using mathematical programming ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Machine covering in the random-order model ⋮ Online scheduling with rearrangement on two related machines ⋮ Improved algorithm for a generalized on-line scheduling problem on identical machines ⋮ 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 ⋮ Tight Bounds for Online Vector Scheduling ⋮ Online scheduling with rejection and withdrawal ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ On Approximation Algorithms for Two-Stage Scheduling Problems ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Scheduling In the random-order model ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ On the on-line maintenance scheduling problem ⋮ Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines ⋮ Semi-on-line scheduling on two parallel processors with an upper bound on the items ⋮ Minimizing the maximum starting time on-line ⋮ Randomized on-line scheduling on two uniform machines ⋮ On-line algorithms for packing rectangles into several strips ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Preemptive multiprocessor scheduling with rejection ⋮ Utilization of nonclairvoyant online schedules ⋮ Online scheduling of jobs with favorite machines ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Extension of algorithm list scheduling for a semi-online scheduling problem ⋮ 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 ⋮ On scheduling inclined jobs on multiple two-stage flowshops ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum ⋮ 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 ⋮ Semi-online scheduling jobs with tightly-grouped processing times on three identical machines ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ Delayed information and action in on-line algorithms
This page was built for publication: Better Bounds for Online Scheduling
