Dynamic online resource allocation problems

Yu, Ge

Permalink

https://hdl.handle.net/2142/100930 Copy

Description

Title

Dynamic online resource allocation problems

Author(s)

Yu, Ge

Issue Date

2018-04-05

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon H.

Doctoral Committee Chair(s)

Jacobson, Sheldon H.

Committee Member(s)

• Srikant, Rayadurgam
• Hajek, Bruce
• Chekuri, Chandra

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Online assignment
• resource allocation problems

Abstract

Online resource allocation problems consider assigning a limited number of available resources to sequentially arriving requests with the objective to maximize rewards. With the emergence of e-business, applications such as online order fulfillment and customer service require real-time resource allocation decisions to guarantee high service quality and customer satisfaction. Other typical applications include operation room scheduling, organ transplant, and passenger screening in aviation security. This dissertation approaches the dynamic online resource allocation problem by considering two models: multi-objective sequential stochastic assignment problems and online interval scheduling problems. Multi-objective sequential stochastic assignment problems are a class of matching problems. A fixed number of jobs arrive sequentially to be assigned to one of the available workers, with an n-dimensional value vector revealed upon each arrival. The objective is to maximize the reward vector given by the product of the job value vector and worker's success rate. We conduct a complete asymptotic analysis for three classes of Pareto optimal policies, with convergence rates and asymptotic objective values provided. Online interval scheduling problems consider reusable resources, where an adversarial sequence of jobs with fixed lengths are to be assigned on available machines. The objective is to maximize the total reward for completed jobs given by the product of the job value and the machine weight. For homogeneous machines, we propose a Pairing-m algorithm, which is 2-competitive for even m and (2+2/m)-competitive for odd m. For heterogeneous machines, two classes of approximation algorithms, Cooperative Greedy algorithms and Prioritized Greedy algorithms, are compared using competitive ratios with respect to varying machine weight ratios. We also provide lower bounds for competitive ratios of deterministic online scheduling algorithms in various scenarios. Stochastic online interval scheduling problems consider a sequence of jobs drawn from a given distribution. For identically and independently distributed jobs with a known distribution, we propose 2-competitive online algorithms for both equal-length and memoryless-length jobs. For job sequences with a random order of arrivals, we propose e-competitive and e^2/(e-1)-competitive online algorithms for both equal-length and memoryless-length jobs. We further extend these results to jobs with a random order of arrivals and geometric arrivals with parameter p. We propose a primal-dual analysis framework for online interval scheduling algorithms for both adversarial and stochastic job sequences. We formulate the online interval scheduling as a linear program with a corresponding dual program. For stochastic job sequences, we use complementary slackness conditions and weak duality to derive optimal algorithms and upper bounds for the optimal reward, respectively. For adversarial sequences, we use weak duality to compute the competitive ratios of scheduling algorithms.

Graduation Semester

2018-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/100930

Copyright and License Information

Copyright 2018 Ge Yu

Owning Collections