Car-sharing between two locations: online scheduling with two servers

Kelin Luo, Thomas Erlebach, Yinfeng Xu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)
16 Downloads (Pure)

Samenvatting

In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The length of the time interval between the submission of a request (booking time) and the pick-up time is fixed. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted. We present lower bounds on the competitive ratio for this problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.

Originele taal-2Engels
Titel43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
RedacteurenIgor Potapov, James Worrell, Paul Spirakis
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's14
ISBN van geprinte versie9783959770866
DOI's
StatusGepubliceerd - 1 aug 2018
Extern gepubliceerdJa
Evenement43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, Verenigd Koninkrijk
Duur: 27 aug 201831 aug 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume117
ISSN van geprinte versie1868-8969

Congres

Congres43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
LandVerenigd Koninkrijk
StadLiverpool
Periode27/08/1831/08/18

Vingerafdruk Duik in de onderzoeksthema's van 'Car-sharing between two locations: online scheduling with two servers'. Samen vormen ze een unieke vingerafdruk.

Citeer dit