Contextual Investigation of Constraint-Based Dynamic Scheduling

提案0705103“基于约束的动态调度的上下文调查”PI：Martha Pollack密歇根大学摘要该项目旨在为频繁发生的各种重要调度问题开发技术，但目前的技术无法充分解决这些问题。这项研究将在一个特定的应用背景下进行--医疗诊所的病人调度，它将涉及密歇根州的一家诊所，该诊所与创伤性脑损伤患者一起工作。这个应用程序上下文有三个特点，使它具有挑战性。首先，它是动态的，因为诸如患者预约的事件以及对事件的时间的约束随时间而改变。其次，它涉及两个硬约束（例如，不能早于给定时间安排约会），以及表示优于备选时间表的偏好的所谓的“软”约束（例如，特定的患者更喜欢下午的预约，或者患者在给定的一天的预约之间最好不要有大的间隙）。三是互动性：人类负责指定事件、约束和偏好。2为了创建有效的调度程序，我们将扩展一类经过充分研究的约束满足系统：可满足性模理论（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.