Study on Parallel Machine Scheduling Problem with Buffer

In the papers by Kellerer et al. (1995) and Zhang (1997) the authors investigate a semi on-line version of a classical parallel machine scheduling problem. In the semi on-line version, there is a buffer of length k which is available to maintain k jobs. The jobs arrive one by one and can be temporarily assigned to the buffer if the buffer is not full. The goal is to assign all jobs to m identical machines such that the makespan is minimized. For two machines, Kellerer et al. (1995) presented a lower bound 4/3 of the worst-case ratio and Zhang (1997) presented an optimal algorithm with a buffer of length 1. In this paper, we investigate the problem with m ges 2 machines. First, we design a new algorithm for P_m//C_max with a buffer of length lfloorm/2rfloor and analyze it. Second, we present some lower bounds of the worst-case ratio.