2026-07-24T00:56:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10012 2024-03-06T10:45:20Z ddc:004 open_access

Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings Luo, Kelin Erlebach, Thomas Xu, Yinfeng Car-sharing system Competitive analysis On-line scheduling We study 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 k 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 scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval (called the booking horizon) that precedes the pick-up time. We present lower bounds on the competitive ratio for both variants and propose a balanced greedy algorithm (BGA) that achieves the best possible competitive ratio. We prove that, for the fixed booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the fixed booking length is not less than the travel time between the two locations; for the variable booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the length of the booking horizon is less than the travel time between the two locations, and BGA is 5/3-competitive if k=5i ( i in N) and the length of the booking horizon is not less than the travel time between the two locations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kelin Luo and Thomas Erlebach and Yinfeng Xu 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.64 urn:nbn:de:0030-drops-100122 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.64 eng https://creativecommons.org/licenses/by/3.0/legalcode