Chance-constrained Scheduling via Conflict-directed Risk Allocation
Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for the Advancement of Artificial Intelligence
2015
|
| Online Access: | http://hdl.handle.net/1721.1/92982 https://orcid.org/0000-0002-1057-3940 |
| _version_ | 1826189333930967040 |
|---|---|
| author | Wang, Andrew J. Williams, Brian Charles |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Wang, Andrew J. Williams, Brian Charles |
| author_sort | Wang, Andrew J. |
| collection | MIT |
| description | Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work addresses the chance-constrained scheduling problem, where actions’ durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This decomposes the problem into a separate master and subproblem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solutions nearly an order of magnitude faster than prior art does, which considers all constraints in a single lump-sum optimization. |
| first_indexed | 2024-09-23T08:13:26Z |
| format | Article |
| id | mit-1721.1/92982 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:13:26Z |
| publishDate | 2015 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | mit-1721.1/929822022-09-30T08:22:35Z Chance-constrained Scheduling via Conflict-directed Risk Allocation Wang, Andrew J. Williams, Brian Charles Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wang, Andrew J. Williams, Brian Charles Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work addresses the chance-constrained scheduling problem, where actions’ durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This decomposes the problem into a separate master and subproblem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solutions nearly an order of magnitude faster than prior art does, which considers all constraints in a single lump-sum optimization. 2015-01-20T17:03:31Z 2015-01-20T17:03:31Z 2015-01 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/92982 Wang, Andrew J., and Brian C. Williams. "Chance-constrained Scheduling via Conflict-directed Risk Allocation." in Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15), January, 25-30, 2015, Austin, Texas, USA. https://orcid.org/0000-0002-1057-3940 en_US http://www.aaai.org/Conferences/AAAI/2015/aaai15schedule.pdf Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for the Advancement of Artificial Intelligence Wang |
| spellingShingle | Wang, Andrew J. Williams, Brian Charles Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title | Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title_full | Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title_fullStr | Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title_full_unstemmed | Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title_short | Chance-constrained Scheduling via Conflict-directed Risk Allocation |
| title_sort | chance constrained scheduling via conflict directed risk allocation |
| url | http://hdl.handle.net/1721.1/92982 https://orcid.org/0000-0002-1057-3940 |
| work_keys_str_mv | AT wangandrewj chanceconstrainedschedulingviaconflictdirectedriskallocation AT williamsbriancharles chanceconstrainedschedulingviaconflictdirectedriskallocation |