{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97329"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97329","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Generalized sequential assignment problem","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Khatibi, Arash"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Jacobson, Sheldon H.","Chen, Xin","Forsyth, David A.","Sowers, Richard B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:14:52Z","date_published":"2017-08-10T19:14:52Z","updated_at":"2026-07-22T22:24:32Z","subjects":["Linear program","Online matching","Secretary problem","Sequential assignment"],"languages":["en"],"rights":["Copyright 2017 Arash Khatibi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97329","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jacobson, Sheldon H.","Chen, Xin","Forsyth, David A.","Sowers, Richard B."]},{"key":"dc:creator","label":"Author","values":["Khatibi, Arash"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:14:52Z","2017-04-11","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Linear program","Online matching","Secretary problem","Sequential assignment"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Arash Khatibi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97329"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Arash Khatibi, accepted the attached license on 2017-04-10 at 21:35.","The student, Arash Khatibi, submitted this Dissertation for approval on 2017-04-10 at 21:42.","This Dissertation was approved for publication on 2017-04-11 at 16:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10696 on 2017-08-10 at 13:39:11","Made available in DSpace on 2017-08-10T19:14:52Z (GMT). No. of bitstreams: 2 KHATIBI-DISSERTATION-2017.pdf: 393967 bytes, checksum: 292d0392a7f66e19ee36fd9e0c00508e (MD5) LICENSE.txt: 4210 bytes, checksum: fef02e824a9a0e3480afca145cc0068e (MD5) Previous issue date: 2017-04-11"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Generalized sequential assignment problem"]}]}],"canonical_facts":{"dc:contributor":["Jacobson, Sheldon H.","Chen, Xin","Forsyth, David A.","Sowers, Richard B."],"dc:creator":["Khatibi, Arash"],"dc:date":["2017-08-10T19:14:52Z","2017-04-11","2017-05"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Arash Khatibi, accepted the attached license on 2017-04-10 at 21:35.","The student, Arash Khatibi, submitted this Dissertation for approval on 2017-04-10 at 21:42.","This Dissertation was approved for publication on 2017-04-11 at 16:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10696 on 2017-08-10 at 13:39:11","Made available in DSpace on 2017-08-10T19:14:52Z (GMT). No. of bitstreams: 2 KHATIBI-DISSERTATION-2017.pdf: 393967 bytes, checksum: 292d0392a7f66e19ee36fd9e0c00508e (MD5) LICENSE.txt: 4210 bytes, checksum: fef02e824a9a0e3480afca145cc0068e (MD5) Previous issue date: 2017-04-11"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97329"],"dc:language":["en"],"dc:rights":["Copyright 2017 Arash Khatibi"],"dc:subject":["Linear program","Online matching","Secretary problem","Sequential assignment"],"dc:title":["Generalized sequential assignment problem"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:32Z"}