Generalized sequential assignment problem

Khatibi, Arash

Permalink

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

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

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