Contextual Investigation of Constraint-Based Dynamic Scheduling

基于约束的动态调度的情境研究

• 批准号: 0705103
• 负责人: Karem Sakallah
• 金额: $ 80.19万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0705103&HistoricalAwards=false
• 关键词: Contextual; Investigation; Constraint; Based; Dynamic

Proposal 0705103"Contextual Investigation of Constraint-Based Dynamic Scheduling"PI: Martha PollackUniversity of MichiganABSTRACT This project aims to develop techniques for a variety of important scheduling problems that occur frequently, yet are inadequately addressed by current techniques. The research will be done in the context of a particular application--patient scheduling for medical clinics and it will involve a Michigan clinic that works with patients with traumatic brain injury. This application context has three characteristics that make it challenging. First, it is dynamic, in that events, such as patient appointments, as well as constraints on the times of the events change over time. Second, it involves both hard constraints (e.g., that no appointments can be scheduled earlier than a given time), as well as so-called "soft" constraints that represent preferences over alternative schedules (e.g., that a particular patient prefers afternoon appointments, or that it is better not to have large gaps between the appointments a patient has on a given day). Third, it is interactive: a human being is responsible for specifying events, constraints, and preferences.To create an effective scheduler, we will extend a well-studied class of constraint-satisfaction systems: Satisfiability Modulo Theory (SMT) solvers. A key goal of this project is to enable SMT solvers to perform optimization efficiently and to develop algorithms for solving sequences of problems in a way that minimizes change across solutions while still producing near-optimal results. The project will also develop interfaces that make it possible for lay users to describe richly expressive constraints and preferences on schedules.The broader impact of the work includes the potential usefulness of the techniques to key applications including clinic scheduling; the exposure of graduate students to contextual research; and the development of real-world problem sets for undergraduate courses.

提案0705103“基于约束的动态调度的上下文调查” PI：密歇根州的Martha Pollackuniversity该项目旨在开发针对经常发生的各种重要调度问题的技术，但仍未得到当前技术的解决。这项研究将在特定的应用程序中进行 - 医疗诊所的患者调度，它将涉及密歇根州诊所，该诊所与脑损伤患者一起工作。此应用程序上下文具有三个使其具有挑战性的特征。首先，这是动态的，因为事件，例如患者预约，以及事件时期的限制随着时间的流逝而变化。其次，它涉及两种硬性约束（例如，没有比给定时间更早的预约时间），以及所谓的“软”约束，代表了偏爱替代时间表的偏好（例如，特定患者更喜欢下午的预约，或者最好不要在患者之间有较大的约会差距，而患者对一天的预约差距很大）。第三，它是互动的：一个人负责指定事件，约束和偏好。要创建一个有效的调度程序，我们将扩展一类精心培训的约束 - 满足系统：满意度MODULO理论（SMT）求解器。该项目的一个关键目标是使SMT求解器能够有效地执行优化，并开发用于解决问题序列的算法，以最小化跨解决方案的变化，同时仍会产生近乎最佳的结果。该项目还将开发界面，使外行用户有可能描述时间表上表达性丰富的限制和偏好。该作品的更广泛影响包括该技术对关键应用程序的潜在有用性，包括诊所日程安排；研究生接触情境研究；现实世界中的问题的发展为本科课程设定。