Abstract:
We consider online, nonpreemptive scheduling of equal-length jobs on parallel machines. Jobs have arbitrary release times and deadlines and a scheduler's goal is to maximize the number of completed jobs (Pm | rj,pj=p | Σ (1-Uj)). This problem has been previously studied under two distinct models. In the first, a scheduler must provide immediate notification to a released job as to whether it is accepted into the system. In a stricter model, a scheduler must provide an immediate decision for an accepted job, selecting both the time interval and machine on which it will run. We examine an intermediate model in which a scheduler immediately dispatches an accepted job to a machine, but without committing it to a specific time interval. We present a natural algorithm that is optimally competitive for m=2. For the special case of unit-length jobs, it achieves competitive ratios for m ≥ 2 that are strictly better than lower bounds for the immediate decision model.