Improved semi-online makespan scheduling with a reordering buffer

摘要

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.