Contextual Investigation of Constraint-Based Dynamic Scheduling

提案0705103“基于约束的动态调度的上下文研究”PI：Martha Pollack of Michigan大学本项目旨在开发各种重要的调度问题的技术，这些问题经常出现，但目前的技术不能充分解决这些问题。这项研究将在一个特定的应用背景下进行--医疗诊所的患者排班，它将涉及密歇根州一家治疗创伤性脑损伤患者的诊所。此应用程序上下文具有三个使其具有挑战性的特征。首先，它是动态的，因为事件，如患者预约，以及对事件时间的限制随着时间的推移而变化。其次，它既涉及硬约束(例如，任何预约都不能早于给定时间安排)，也涉及代表对可选日程的偏好的所谓的“软”约束(例如，特定患者更喜欢下午的预约，或者患者在给定的一天的预约之间最好不要有太大的差距)。第三，它是交互式的：人类负责指定事件、约束和偏好。为了创建有效的调度器，我们将扩展一类研究得很好的约束满足系统：可满足性模理论(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.