We study an on-line scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit or maximum the number of satisfied requests. Each ride request specifies the pick-up time, the pick-up location, and the drop-off location. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time).
We investigate the problem from some specific cases to the general case. The online car-sharing problem is studied on different networks (two locations, star network, and general network), different numbers of servers (one server, two servers, and k servers) and different booking variants (fixed bookings and variable bookings). The lower bound and upper bound are matched in most cases. Some of our analyses extend to maximize the number of satisfied users where each user may submit more than one request.
Joint work with Thomas Erlebach and Yinfeng Xu.
2019-04-09 15:00 ~ 16:00
Kelin Luo, Xi’an Jiaotong University
Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics