Journal of Scheduling · 2012 · 11 citations · 16 references
ManagementComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingCombinatorial OptimizationJob SchedulingMachine SchedulingMakespan MinimizationOnline SchedulingScheduling TheoryAlgorithmic Lower BoundsLower BoundsMachine AssignmentMakespan OptimizationOnline Makespan MinimizationOnline Single-machine SchedulingSingle Machine Makespan Minimization
In online makespan minimization, the jobs characterized by their processing time arrive one-by-one and each has to be assigned to one of the m uniformly related machines. The goal is to minimize the length of the schedule. We prove new combinatorial lower bounds for m=4 and m=5, and computer-assisted lower bounds for m≤11.
16
Bounds for Certain Multiprocessing Anomalies
Ronald Graham · Bell System Technical Journal · 1966 · 1.6K citations
On-line load balancing with applications to machine scheduling and virtual circuit routing
James Aspnes, Yossi Azar, Amos Fiat et al. · 1993 · 215 citations · Full text
Rudolf Fleischer, Michaela Wahl · Journal of Scheduling · 2000 · 155 citations