M.Sc Thesis | |

M.Sc Student | Yahav Inbal |
---|---|

Subject | Bid-Based Online Scheduling of Unit-Length Tasks with Hard Deadlines |

Department | Department of Industrial Engineering and Management |

Supervisor | PROF. Avigdor Gal |

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.