文章基本信息

标题：Nurse Scheduling System based on Dynamic Weighted Maximal Constraint Satisfaction Problem Solution Stability based on the Provisional Constraint
本地全文：下载
作者：Hiromitsu Hattori ; Atsushi Isomura ; Takayuki Ito 等
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2005
卷号：20
期号：1
页码：25-35
DOI：10.1527/tjsai.20.25
出版社：The Japanese Society for Artificial Intelligence
摘要：Scheduling has been an important research field in Artificial Intelligence. Because typical scheduling problems could be modeled as a Constraint Satisfaction Problem(CSP), several constraint satisfaction techniques have been proposed. In order to handle the different levels of importance of the constraints, solving a problem as a Weighted Maximal Constraint Satisfaction Problem(W-MaxCSP) is an promising approach. However, there exists the case where unexpected events are added and some sudden changes are required, i.e., the case with dynamic changes in scheduling problems. In this paper, we describe such dynamic scheduling problem as a Dynamic Weighted Maximal Constraint Satisfaction Problem(DW-MaxCSP) in which constraints would changes dynamically. Generally, it is undesirable to determine vastly modified schedule even if re-scheduling is needed. A new schedule should be close to the current one as much as possible. In order to obtain stable solutions, we propose the methodology to maintain portions of the current schedule using the provisional soft constraints, which explicitly penalize the changes from the current schedule. We have experimentally confirmed the efficacy of re-scheduling based on our method with provisional constraints. In this paper, we construct the nurse scheduling system for applying the proposed scheduling method.
关键词：dynamic weighted maximal CSP ; nurse scheduling ; stability