Journal of Combinatorial Optimization Applied Mathematics
Semi-online scheduling with non-increasing job sizes and a buffer
Abstract
Abstract This work considers a semi-online version of scheduling on m identical machines, where the objective is to minimize the makespan. In the variant studied here, jobs are presented sorted by non-increasing sizes, and a buffer of size k is available for storing at most k jobs. Every arriving job has to be either placed into the buffer until its assignment, or else it has to be assigned immediately to a machine. We prove a lower bound greater than 1 on the competitive ratio of the problem for any m and any buffer size. To complement this negative result, we design a simple algorithm for any m whose competitive ratio tends to 1 as the buffer size grows. Using those results, we show the best possible competitive ratio is $$1+\Theta (\frac{m}{k})$$ 1 + Θ ( m k ) . We provide additional bounds for small values of m . In particular, we show that for $$m=2$$ m = 2 the case $$k=1$$ k = 1 is not different from the case without a buffer, while $$k=2$$ k = 2 admits an improved competitive ratio.