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
Publications
- Article type
- Year
- Co-author
Article type
Year
Open Access
Research Article
Issue
Tsinghua Science and Technology 2027, 32(1): 285-299
Published: 11 September 2026
Downloads:67
Total 1
京公网安备11010802044758号