M.Sc Thesis
M.Sc Student Inbal Yahav Bid-Based Online Scheduling of Unit-Length Tasks with Hard Deadlines Department of Industrial Engineering and Management Full Professor Gal Avigdor

Abstract

We study an online scheduling problem for unit-length tasks with hard deadlines. Each task is specified by its release time, its deadline (after which it is dropped), and a non-negative value. We consider this problem in an economic setting, in which each task is owned by a unique, self-interest agent. Agents submit tasks to a single server on their release time along with a bid. The server uses the bids to prioritize tasks, processing higher bid tasks first. The goal is to maximize the weighted throughput. In addition, we measure the performance of our mechanism in terms of throughput.

The first part of this thesis presents a reduction of the online scheduling problem to a bipartite graph. We use this reduction to formally represent the optimal offline solution as a max-weighted-match problem. This formalization enables us to empirically compare each scheduling scenario resulted from any algorithm to the offline optimal solution. We then introduce our new bid-based algorithm for online scheduling in an economic setting. We use a detailed simulation model and compare our algorithm results to the offline solution and to other known online scheduling algorithms.

Finally, we study our bid-based mechanism in terms of profit by investigating the multi-server case. We compare our bidding approach to a fixed-price approach, under the private evaluation assumption. For the second server, we introduce a variation of the Early-Deadline-First (EDF) algorithm, called EsDF. EDF is proved in this thesis to maximize the throughput, under public knowledge of the tasks true deadline.

For the weighted throughput problem, we mathematically solve the offline schedule problem using an IP program. Using that solution, we empirically show that whereas the upper bound on the competitive ratio is known to be Φ = 2/(√5-1) ≈ 1.618, on average the ratio between our bidding system and the optimal offline solution is greater then 10/9 ≈ 1.11. For the throughput problem we give a ratio of more then 100/95 ≈ 1.05.

In terms of profit, we empirically show that in most cases agents prefer a server with price flexibility. We show that even when competing with a free-of-charge server, a reasonable fraction of users choose to pay, in order to increase their probability of getting processed.