University of Illinois Urbana-Champaign

Generalized sequential assignment problem

Khatibi, Arash

Content Files
KHATIBI-DISSERTATION-2017.pdf

Permalink

https://hdl.handle.net/2142/97329

Description

Title
Generalized sequential assignment problem
Author(s)
Khatibi, Arash
Issue Date
2017-04-11
Director of Research (if dissertation) or Advisor (if thesis)
Jacobson, Sheldon H.
Doctoral Committee Chair(s)
Chen, Xin
Committee Member(s)
  • Forsyth, David A.
  • Sowers, Richard B.
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2017-08-10T19:14:52Z
Keyword(s)
  • Linear program
  • Online matching
  • Secretary problem
  • Sequential assignment
Abstract
The Sequential Stochastic Assignment Problem (SSAP) deals with assigning sequentially arriving tasks with stochastic parameters to workers with fixed success rates. The reward of each assignment is the product of the worker's success rate and the task value assigned to the worker. The objective is to maximize the total expected reward. There has been a surge of interest in studying sequential assignment problems due to their applications in online matching markets, asset selling, and organ transplant. This dissertation studies several variations of SSAP by relaxing the main assumptions. The first part assumes that the workers' success rates are random values coming from a known distribution. This generalization modifies the SSAP from a problem with a single random value (i.e., the task value) at each stage to an online matching problem with several random parameters (i.e., the task value and the workers' success rates). The optimal assignment policy uses backward induction to first solve smaller subproblems, and then use them to optimally assign tasks to workers from the first stage. An approximation algorithm is proposed that achieves a fraction of the optimal reward in a polynomial time. Assuming that the value of sequentially arriving elements are independently drawn from a known distribution is unrealistic in many applications. The second part of thesis relaxes this assumption and uses the well-known Secretary Problem to derive constant-competitive algorithms for SSAP with tasks having a random arrival order. Several deterministic and randomized algorithms are proposed and their performance are compared with the maximum offline reward. These algorithms use the first stages of the problem as a training phase to compute thresholds for the task values. These thresholds are used to assign tasks to workers after the training phase. The third part uses the linear programming technique to derive bounds on the performance of optimal policy for several variations of SSAP. Formulating an online matching problem as a linear program is a useful tool. In addition to deriving bounds on performance of optimal policies, the linear programming technique can be used to formulate extensions of the problem as linear programs by simple changes in the objective function and constraints of the basic formulation. The linear programming formulation of the incentive compatible problem and the sequential assignment problem with unknown number of elements are also proposed. The edge-weighted online bipartite matching problem is used to design assignment policies for each of the formulated problems. The last part relaxes the assumption that at most one task must be assigned to each worker in SSAP. It is assumed that a worker is available for possible future assignments after performing the previously assigned task. The number of stages that the worker is not available due to a prior task assignment is referred to as the task duration. This problem is studied under various models for the task duration. First, it is assumed that the task duration is fixed. Then, assignment policies are proposed for the problem with a memoryless model for the task duration. The proposed algorithms are extensions of the optimal algorithm for the sequential assignment problem. They divide the n-stage assignment process to periods whose lengths are equal to the expected task duration. Then, they assign tasks to workers in each period by applying the optimal algorithm of the sequential assignment problem.
Graduation Semester
2017-05
Type of Resource
text
Permalink
http://hdl.handle.net/2142/97329
Copyright and License Information
Copyright 2017 Arash Khatibi

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering