Abstract

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.

Time

4月9日（周二）15:00-16:00

Speaker

Kelin Luo expects to obtain her PhD Degree at School of Management, Xi’an Jiaotong University (2019) under the supervision of Prof. Yinfeng Xu. She spent one year at the Department of Informatics, University of Leicester from September 2017 to September 2018 under the Joint-PhD. Program, hosted by Thomas Erlebach. She obtained her Double Degree: Bachelor of Economics and Bachelor of Management at School of Economics and Management, Northwest University (2014).

She is interested in combinatorial optimization, especially online algorithms, approximation algorithms, and algorithmic game theory. Currently, her research is mainly focused on online scheduling of car-sharing problems, and algorithmic mechanism design.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号