On-line bin-stretching

DOI10.1016/S0304-3975(00)00258-9zbMath0984.68195MaRDI QIDQ5958712

Oded Regev, Yossi Azar

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

scheduling; on-line algorithms; load balancing; approximation algorithms; bin stretching; bin-packing

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

Related Items

Online Order Scheduling Problem with the Same Order Size on Two Identical Machines, Online Bounded Analysis, Semi-online scheduling problems on a small number of machines, Semi-online scheduling revisited, Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling, Online bin stretching with bunch techniques, Semi-on-line multiprocessor scheduling with given total processing time, Optimal semi-online preemptive algorithms for machine covering on two uniform machines, Online scheduling with a buffer on related machines, Several semi-online scheduling problems on two identical machines with combined information, Semi-online machine covering on two uniform machines with known total size, Optimal semi-online algorithms for machine covering, Semi-online scheduling problems on two identical machines with inexact partial information, An efficient algorithm for semi-online multiprocessor scheduling with given total processing time, Online scheduling with reassignment, List scheduling for jobs with arbitrary release times and similar lengths, Machine covering with combined partial information, Two semi-online scheduling problems on two uniform machines, Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times, Online makespan minimization with parallel schedules, Improved lower bounds for the online bin stretching problem, An efficient algorithm for bin stretching, Semi-online scheduling with ``end of sequence information, Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New algorithms for an ancient scheduling problem.
• Semi on-line algorithms for the partition problem
• A lower bound for randomized on-line scheduling algorithms
• New lower and upper bounds for on-line scheduling
• On-Line Load Balancing of Temporary Tasks
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• On-Line Load Balancing of Temporary Tasks on Identical Machines
• On-line load balancing with applications to machine scheduling and virtual circuit routing
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies