Network-based Models for Scheduling under Uncertainty

不确定性下基于网络的调度模型

• 批准号: RGPIN-2020-06054
• 负责人: Cire, Andre
• 金额: $ 2.26万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741003
• 关键词: Network; based; Models; Scheduling; under

In day-to-day services, scheduling problems often involve quantities that are unknown in advance. For example, when a medical clinic schedules an appointment for a patient, it is uncertain as to how long the appointment will take, or if previous appointments scheduled for that day will run longer than initially anticipated. Schedules that are overly optimistic and assume short patient visits may lead to undesired patient waiting times. In contrast, allowing too much flexibility on appointment lengths can result in idle physicians and a reduced number of patients seen daily at the clinic. Similar scenarios occur in a large array of other applications, such as when scheduling parcel deliveries, jobs in cloud services, rides in shared-economy apps, and service requests in call centers. With the advancement of data analytics, we can now exploit large amounts of data to accurately model this uncertainty. Machine learning and statistical methods have become increasingly more accessible, allowing practitioners to more easily derive accurate probability distributions or to construct sophisticated models to predict, e.g., patient appointment lengths. However, optimization models that leverage this information in order to design better schedules are notoriously difficult to solve. Such models combine complex uncertainty structure with a range of idiosyncratic constraints, severely limiting their applicability to practice and presenting novel theoretical and computational challenges. My proposal, motivated by these challenges, will develop novel optimization methodologies for scheduling under uncertain parameters. The focus of the research is on an alternative modeling perspective based on network encodings of the uncertainty. Specifically, networks are flexible data structures that can compactly represent large amounts of information, such as the set of future outcomes of an unknown variable. They can be used in conjunction with mathematical programming and state-of-the-art optimization techniques to derive better schedules more efficiently, providing new ways to bridge predictive and prescriptive analytics. This proposal focuses on scheduling challenges where network models present unique methodological benefits, such as in scenario-based approaches, integrated machine learning/optimization models, and stochastic dynamic programs. In particular, results will be evaluated using real datasets from collaborations with national and international organizations. The outcome is a series of computationally practical tools that decision makers can use in order to enhance scheduling services in healthcare, transportation, and logistics, to name a few. With this proposal and the training of high-qualified personnel, we aim to position Canada at the forefront of evidence-based management as driven by data, specifically by developing the next generation of analytical tools that extract the value of data through optimization and rigorous methodologies.

在日常服务中，调度问题通常涉及事先未知的数量。例如，当医疗诊所为患者安排预约时，不确定预约将花费多长时间，或者为该天安排的先前预约是否将比最初预期的时间更长。过于乐观的时间表和假设短期的病人访问可能会导致不希望的病人等待时间。相比之下，在预约时间上允许太多的灵活性可能会导致空闲的医生和每天在诊所就诊的患者数量减少。类似的场景也发生在大量其他应用程序中，例如在安排包裹交付、云服务中的作业、共享经济应用程序中的乘车以及呼叫中心中的服务请求时。随着数据分析的进步，我们现在可以利用大量数据来准确地建模这种不确定性。机器学习和统计方法变得越来越容易获得，使从业者能够更容易地获得准确的概率分布或构建复杂的模型来预测，例如，患者预约时间然而，利用这些信息来设计更好的时间表的优化模型是众所周知的难以解决的。这些模型将联合收割机复杂的不确定性结构与一系列特殊的约束条件相结合，严重限制了它们在实践中的适用性，并提出了新的理论和计算挑战。我的建议，这些挑战的动机，将开发新的优化方法调度不确定参数下。研究的重点是基于网络编码的不确定性的替代建模的角度。具体来说，网络是灵活的数据结构，可以复杂地表示大量信息，例如未知变量的未来结果集。它们可以与数学规划和最先进的优化技术结合使用，以更有效地获得更好的时间表，为预测性和规范性分析提供新的方法。该提案侧重于调度挑战，其中网络模型呈现出独特的方法优势，例如基于神经网络的方法，集成机器学习/优化模型和随机动态程序。特别是，将使用与国家和国际组织合作的真实的数据集对结果进行评价。其结果是一系列计算上实用的工具，决策者可以使用这些工具来增强医疗保健，运输和物流等方面的调度服务。通过这一提议和高素质人员的培训，我们的目标是将加拿大置于数据驱动的循证管理的前沿，特别是通过开发下一代分析工具，通过优化和严格的方法提取数据的价值。