@article{Wang2027, 
author = {Libo Wang and Wenhua Li and Ran Lin and Xing Chai},
title = {On-Line Scheduling with A Non-Renewable Resource Under Periodic Supply},
year = {2027},
journal = {Tsinghua Science and Technology},
volume = {32},
number = {1},
pages = {285-299},
keywords = {scheduling, on-line algorithm, non-renewable resource, deterioration, competitive ratio},
url = {https://www.sciopen.com/article/10.26599/TST.2024.9010221},
doi = {10.26599/TST.2024.9010221},
abstract = {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  α2+3α=1.}
}