Car-Sharing Problem: Online Scheduling with Flexible Advance Bookings

摘要

We study an online scheduling problem that is motivated by applications such as car-sharing for trips among a number of locations. Users submit ride requests, and the scheduler aims to accept as many requests as k servers (cars) could. Each ride request, specifies the pick-up time, the pick-up location, and the drop-off location. A request can be submitted at any time during a certain time interval that precedes the pick-up time. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). For the general case in which requests may have arbitrary lengths, L, the ratio of the longest to the shortest request, is an important parameter. We give an algorithm with competitive ratio O(L), where the ratio L is known in advance. It is shown that no O(L~α)-competitive algorithm exists for the fixed booking variant, where 0 < α < 1. It is also proved that no O(L)-competitive algorithm exists for the variable booking variant.