Combinatorial Optimization and Schedule Generation Using Deep Bipartite Assignment

dc.contributor.authorSalgo, Alexanderen
dc.contributor.departmentComputingen
dc.contributor.supervisorRivest, Francois
dc.contributor.supervisorGivigi, Sidney
dc.date.accessioned2021-10-14T15:55:03Z
dc.date.available2021-10-14T15:55:03Z
dc.degree.grantorQueen's University at Kingstonen
dc.description.abstractRecent advances in deep reinforcement learning (DRL) have allowed it to contribute to areas which were previously the domain of traditional algorithms. Operations research (OR), however, has lagged behind in this respect. OR problems often involve data with properties that are difficult for deep learning techniques to handle, and there is a concomitant lack of background research to draw from when designing new DRL approaches in this area. A 2019 paper introduced Deep Bipartite Assignment (DBA), a neural network architecture which allows DRL to be applied to simple bipartite assignment problems such as the Weapon-Target Assignment problem (WTA). In this work, we accomplish two objectives. First, we demonstrate that DBA can be extended to address more complex scheduling problems, including the Nurse Scheduling Problem and the Spatio-Temporal WTA. Second, we use DBA as a starting point to research the effects of various design choices on performance when solving scheduling and assignment problems using DRL. We identify patterns in hyperparameter choice, network structure, and training algorithm choice which can be used by future researchers to design better performing DRL agents for OR problems.en
dc.description.degreeM.Sc.en
dc.identifier.urihttp://hdl.handle.net/1974/29495
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsQueen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada*
dc.rightsProQuest PhD and Master's Theses International Dissemination Agreement*
dc.rightsIntellectual Property Guidelines at Queen's University*
dc.rightsCopying and Preserving Your Thesis*
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.*
dc.rightsAttribution-ShareAlike 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-sa/3.0/us/*
dc.subjectAIen
dc.subjectMachine Learningen
dc.subjectCombinatorial Optimizationen
dc.subjectOperations Researchen
dc.subjectSchedulingen
dc.subjectWTAen
dc.subjectNSPen
dc.subjectNurse Scheduling Problemen
dc.subjectDeep Reinforcement Learningen
dc.subjectDeep Learningen
dc.subjectAttentionen
dc.subjectBipartite Assignmenten
dc.subjectAssignment Problemsen
dc.subjectNeural Networksen
dc.titleCombinatorial Optimization and Schedule Generation Using Deep Bipartite Assignmenten
dc.typethesisen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Salgo_Alexander_JB_202110_MSC.pdf
Size:
1.58 MB
Format:
Adobe Portable Document Format
Description:
Thesis Document
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed upon to submission
Description: