Network-based Models for Scheduling under Uncertainty

点击翻译按钮获取中文摘要

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.