Contextual Investigation of Constraint-Based Dynamic Scheduling

提案0705103“基于约束的动态调度的上下文调查”PI: Martha pollack密歇根大学摘要该项目旨在开发各种重要的调度问题的技术，这些问题经常发生，但目前的技术还不能充分解决。这项研究将在一个特定应用的背景下进行——医疗诊所的患者日程安排，它将涉及密歇根一家治疗创伤性脑损伤患者的诊所。这个应用程序上下文有三个特点，使其具有挑战性。首先，它是动态的，因为事件（如患者预约）以及对事件时间的限制会随着时间而变化。其次，它既涉及硬约束（例如，不能在给定时间之前安排预约），也涉及所谓的“软”约束，即代表对替代时间表的偏好（例如，特定患者更喜欢下午的预约，或者患者在给定日期的预约之间最好不要有大的间隔）。第三，它是交互式的：一个人负责指定事件、约束和偏好。为了创建一个有效的调度程序，我们将扩展一类研究得很好的约束满足系统：可满足模理论（SMT）解算器。该项目的一个关键目标是使SMT求解器能够有效地执行优化，并开发算法，以最小化解决方案之间的变化，同时仍然产生接近最优的结果。该项目还将开发接口，使非专业用户能够描述丰富的表达约束和时间表偏好。这项工作的广泛影响包括这些技术对关键应用的潜在有用性，包括诊所调度；研究生对语境研究的接触以及为本科课程开发真实世界的问题集。

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.