Improved semi-online makespan scheduling with a reordering buffer

• We study semi-online scheduling on identical parallel machines with a reordering buffer.
• We propose an optimal online algorithm with competitive ratio approaching 1.4659 as number of machines approaches infinity and a suboptimal algorithm with competitive ratio 1.5.
• Both algorithms improve upon the existing results in terms of the required buffer size by a constant fraction of the number of machines.

We study semi-online scheduling with a reordering buffer for identical parallel machines. In this problem, jobs arrive one by one and the online algorithm is equipped with a buffer of limited size, which can be used to reorder the jobs when making scheduling decisions. When the buffer is full, one of the jobs in the buffer must be irrevocably assigned to a machine before the next job can be revealed. No preemption is allowed and the objective is to minimize the makespan. We propose an optimal online algorithm using a buffer size of 2.068m for large m and a 1.5-competitive algorithm using a buffer size of 1.477m, where m is the number of machines. Both results improve upon the best existing buffer sizes for the corresponding competitive ratios by a constant fraction of m.