Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • 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, Skolan för elektroteknik och datavetenskap (EECS), Reglerteknik.ORCID-id: 0000-0002-1934-7421
Visa övriga samt affilieringar
2018 (Engelska)Ingår i: 2018 IEEE/ACM 26th International Symposium on Quality of Service, IWQoS 2018, IEEE, 2018, artikel-id 8624184Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
IEEE, 2018. artikel-id 8624184
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-248376DOI: 10.1109/IWQoS.2018.8624184ISI: 000461354300060Scopus ID: 2-s2.0-85062619764ISBN: 978-1-5386-2542-2 (tryckt)OAI: oai:DiVA.org:kth-248376DiVA, id: diva2:1303184
Konferens
26th IEEE/ACM International Symposium on Quality of Service, IWQoS 2018; Banff; Canada; 4 June 2018 through 6 June 2018
Anmärkning

QC 20190409

Tillgänglig från: 2019-04-09 Skapad: 2019-04-09 Senast uppdaterad: 2019-05-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Talebi Mazraeh Shahi, Mohammad Sadegh

Sök vidare i DiVA

Av författaren/redaktören
Talebi Mazraeh Shahi, Mohammad Sadegh
Av organisationen
Reglerteknik
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 190 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf