Decentralized resource allocation for synchronized tasks through Adaptive Large Neighborhood Search (ALNS)

This thesis explores a method for multiple suppliers to coordinate resource scheduling of task requests from multiple consumers using decentralized planning. A time window is associated with each task and some tasks require simultaneous servicing from multiple resources of specified classes to fulfil a request. The suppliers create schedules for their resources that maximize the value of all tasks fulfilled, while minimizing travel cost, and respecting all time window constraints. This thesis presents Infeasibility Cooling Adaptive Allocation for Resource United Scheduling (ICAARUS), a novel Adaptive Large Neighborhood Search (ALNS) algorithm that is capable of synchronizing tasks across a variable number of resources. A supplier's individual schedule and cost function is kept private from consumers. An e-commerce style of multi-round bidding is introduced to notify suppliers of resource request parameters and to allow consumers to synchronize resources from independent suppliers. A Mixed-Integer Linear Program (MILP) is used by the consumer to select the least costly bids that can be combined to fulfill a task's requirements.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Montgomery, Christian D.(Christian Donovan)

Advisor dc:contributor.advisor

• Hamsa Balakrishnan.

• Aeronautics and Astronautics.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/127078

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/127078