{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113064"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113064","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fair allocation of operations and makespan minimization for multiple robotic agents","abstract":"We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The algorithm also guarantees an upper bound of 1.618 for 2 uniformly related agents and (1+√(4n−3))/2 for n uniformly related agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable, reactive and robust. A new protocol named as the Decentralized Random Group Formation (DRGF) Protocol is presented for implementing the Operation Trading Algorithm in a decentralized manner and for dealing with communication failures. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market-based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric pruning further improves the upper bound to 1.5, which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on randomly generated problem instances.","abstract_html":"We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The algorithm also guarantees an upper bound of 1.618 for 2 uniformly related agents and (1+√(4n−3))/2 for n uniformly related agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable, reactive and robust. A new protocol named as the Decentralized Random Group Formation (DRGF) Protocol is presented for implementing the Operation Trading Algorithm in a decentralized manner and for dealing with communication failures. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market-based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric pruning further improves the upper bound to 1.5, which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on randomly generated problem instances.","abstract_has_math":false,"creators":["Sengupta, Raunak"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:46:53Z","date_published":"2022-01-12T21:46:53Z","updated_at":"2026-07-22T22:24:53Z","subjects":["Makespan Minimization","Fair Allocation","Decentralized Task Allocation","Approximation Factor"],"languages":["en"],"rights":["Copyright 2021 Raunak Sengupta"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113064","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh"]},{"key":"dc:creator","label":"Author","values":["Sengupta, Raunak"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:46:53Z","2021-07-20","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["Makespan Minimization","Fair Allocation","Decentralized Task Allocation","Approximation Factor"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Raunak Sengupta"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113064"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The algorithm also guarantees an upper bound of 1.618 for 2 uniformly related agents and (1+√(4n−3))/2 for n uniformly related agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable, reactive and robust. A new protocol named as the Decentralized Random Group Formation (DRGF) Protocol is presented for implementing the Operation Trading Algorithm in a decentralized manner and for dealing with communication failures. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market-based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric pruning further improves the upper bound to 1.5, which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on randomly generated problem instances.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Raunak Sengupta, accepted the attached license on 2021-07-16 at 11:28.","The student, Raunak Sengupta, submitted this Thesis for approval on 2021-07-16 at 11:51.","This Thesis was approved for publication on 2021-07-20 at 16:49.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16983 on 2022-01-12 at 12:46:08","Made available in DSpace on 2022-01-12T21:46:53Z (GMT). No. of bitstreams: 2 SENGUPTA-THESIS-2021.pdf: 823476 bytes, checksum: f4eaa444a5ae3ba69c6cf9e5876660ee (MD5) LICENSE.txt: 4212 bytes, checksum: ea258d07836b948c5f57f74881971957 (MD5) Previous issue date: 2021-07-20"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Fair allocation of operations and makespan minimization for multiple robotic agents"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh"],"dc:creator":["Sengupta, Raunak"],"dc:date":["2022-01-12T21:46:53Z","2021-07-20","2021-08"],"dc:description":["We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The algorithm also guarantees an upper bound of 1.618 for 2 uniformly related agents and (1+√(4n−3))/2 for n uniformly related agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable, reactive and robust. A new protocol named as the Decentralized Random Group Formation (DRGF) Protocol is presented for implementing the Operation Trading Algorithm in a decentralized manner and for dealing with communication failures. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market-based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric pruning further improves the upper bound to 1.5, which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on randomly generated problem instances.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Raunak Sengupta, accepted the attached license on 2021-07-16 at 11:28.","The student, Raunak Sengupta, submitted this Thesis for approval on 2021-07-16 at 11:51.","This Thesis was approved for publication on 2021-07-20 at 16:49.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16983 on 2022-01-12 at 12:46:08","Made available in DSpace on 2022-01-12T21:46:53Z (GMT). No. of bitstreams: 2 SENGUPTA-THESIS-2021.pdf: 823476 bytes, checksum: f4eaa444a5ae3ba69c6cf9e5876660ee (MD5) LICENSE.txt: 4212 bytes, checksum: ea258d07836b948c5f57f74881971957 (MD5) Previous issue date: 2021-07-20"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113064"],"dc:language":["en"],"dc:rights":["Copyright 2021 Raunak Sengupta"],"dc:subject":["Makespan Minimization","Fair Allocation","Decentralized Task Allocation","Approximation Factor"],"dc:title":["Fair allocation of operations and makespan minimization for multiple robotic agents"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}