International Journal of Foundations of Computer Science · 2014 · 11 citations · 16 references
ManagementComputer EngineeringComputer ScienceAlgorithmsOptimizationSchedulingBuffer ManagementMachine SchedulingMakespan MinimizationOnline AlgorithmsOnline SchedulingScheduling TheoryCompetitive RatioMakespan OptimizationMin-max SchedulingOnline Makespan MinimizationSingle Machine Makespan Minimization
In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results: (i) for m > 51 identical machines, we give a 1.5-competitive online algorithm with a buffer of size ⌈1.5m⌉; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for m uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + ε to 2 − 1/m+ ε, where ε > 0 is sufficiently small and m is a constant.
16
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
Rudolf Fleischer, Michaela Wahl · Journal of Scheduling · 2000 · 155 citations