2018 · 22 citations · 28 references
ComputingComputer ScienceMathematicsAlgorithmsResource ScarcitySchedulingCharging SystemsOnline AlgorithmsOnline SchedulingScheduling TheoryVehicle SchedulingCapacity-constrained Vehicle SchedulingCompetitive RatioComputational Complexity Of AlgorithmsElectric Vehicle SchedulingRandomized Online AlgorithmsScheduling Algorithms
This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the processing rate limit of jobs and charging station capacity constraint. The problem lies in the category of time-coupled online scheduling problems without availability of future information. This paper proposes two online algorithms, both of which are shown to be (2-[1/U])-competitive, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. The first proposed algorithm is deterministic, whereas the second is randomized and enjoys a lower computational complexity. When U grows large, the performance of both algorithms approaches that of the state-of-the-art for the case where there is processing rate limits on the jobs. Nonetheless in realistic cases, where U is typically small, the proposed algorithms enjoy a much lower competitive ratio. To carry out the competitive analysis of our algorithms, we present a proof technique, which is novel to the best of our knowledge. This technique could also be used to simplify the competitive analysis of some existing algorithms, and thus could be of independent interest.
28
A scheduling model for reduced CPU energy
Fei Yao, Alan Demers, Scott Shenker · 2002 · 1.5K citations
Scheduling for Reduced CPU Energy
1994 · 1.1K citations
Online auctions with re-usable goods
Mohammad Taghi Hajiaghayi · 2005 · 161 citations · Full text