Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Competitive Online Scheduling Algorithms with Applications in Deadline-Constrained EV Charging
Telecom SudParis, Inst Mines Telecom, F-91000 Evry, France. alebi, Mohammad Sadegh.
KTH, School of Electrical Engineering and Computer Science (EECS), Automatic Control.ORCID iD: 0000-0002-1934-7421
Show others and affiliations
2018 (English)In: 2018 IEEE/ACM 26th International Symposium on Quality of Service, IWQoS 2018, IEEE, 2018, article id 8624184Conference paper, Published paper (Refereed)
Abstract [en]

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-\frac{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.

Place, publisher, year, edition, pages
IEEE, 2018. article id 8624184
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-248376DOI: 10.1109/IWQoS.2018.8624184ISI: 000461354300060Scopus ID: 2-s2.0-85062619764ISBN: 978-1-5386-2542-2 (print)OAI: oai:DiVA.org:kth-248376DiVA, id: diva2:1303184
Conference
26th IEEE/ACM International Symposium on Quality of Service, IWQoS 2018; Banff; Canada; 4 June 2018 through 6 June 2018
Note

QC 20190409

Available from: 2019-04-09 Created: 2019-04-09 Last updated: 2019-05-23Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Talebi Mazraeh Shahi, Mohammad Sadegh

Search in DiVA

By author/editor
Talebi Mazraeh Shahi, Mohammad Sadegh
By organisation
Automatic Control
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 140 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf