On-Line Scheduling with a Non-Renewable Resource Under Periodic Supply

This is the first paper to address an on-line scheduling problem with a non-renewable resource. Resource is supplied with known quantity periodically. The jobs arriving on-line over time have the same basic processing time and the same required quantity of resource. Each job is revealed until its release time, and a scheduler makes decision without the information of future jobs. If the available quantity of the resource satisfies the resource requirement, a job is processed with the basic processing time by consuming the resource requirement. Otherwise, the job can be processed with deterioration under a longer processing time  by consuming the insufficient resource quantity. The objective is to minimize the makespan. For this problem on a single machine, we derive a lower bound on the competitive ratio by adversary strategy, and provide a best possible on-line algorithm with a competitive ratio of 1+α, where α is the positive root of α²+3α=1.