スケジューリング問題の一種である時間割編成を制約充足問題として捉え、 制約により問題を表現し、解を得る対話型システムを開発した。
時間割編成問題は探索空間が膨大で、 多種多様なユーザの要求をすべて制約で表現することは難しいという問題点があり、 自動的に実用的な時間割を得ることは困難である。 そこで、本システムでは探索をユーザの指示によって行うものとして、 システムとユーザが協調して探索を進めるシステムを開発した。 また探索手法として、制約違反点数を導入した制約違反最少化戦略による山登り法を提案した。
本システムの特徴は、制約違反点数に基づいた手動割当や探索が、 ユーザに制約違反の情報を示しながら対話によって時間割を編成できるところにある。 そこで、本システムを筑波大学情報学類の時間割編成に対し適用し、 時間割編成問題に対する有効性を確認した。
大学の時間割編成問題を制約充足問題として捉え、 制約により問題を表現し、解を得る対話型システムを開発した。
時間割編成問題は探索空間が膨大で、 多種多様なユーザの要求をすべて制約で表現することは難しいという問題点があり、 自動的に実用的な時間割を得ることは困難である。 そこで、本システムでは探索をユーザの指示によって行うものとして、 システムとユーザが協調して探索を進めることにした。 また探索手法として、制約違反点数を導入した制約違反最少化戦略による山登り法を提案した。
本システムの特徴は、ユーザに制約違反の情報を示しながら対話によって時間割を編成できるところにある。
We developed an interactive system to solve the university timetabling problems which are considered as constraint satisfaction problems.
The timetabling problems have the following problems: First, search space is very large. Second, it is difficult to represent all various kinds of requirements by constraints. Therefore it is hard to produce practical timetables automatically. In order to resolve it, our approach takes advantage of interactions in cooperating with the user to guide its search. We propose the min-conflicts hill-climbing method with violation points for timetabling problems.
Our system can make timetables interactively by showing information of constraint violations.
近年、時間割編成問題や室内レイアウト問題などを計算機を用いて、効率的に解く方法が検討されている。 上記のような問題を解くには専門的な知識が必要で、その多くが計算機内で表現しにくく、表現できても膨大な計算時間と記憶領域を要する。 これらは制約充足問題などで定式化され、現在様々な研究が行われているが、 それぞれの事例ごとに制約条件が異なるために有効な解法が見つけられておらず、 問題解決には人手に頼らざるを得ないのが現状である。
本研究では、これらの問題を対話的に解くシステムの開発を通して、 その性質の解明、および制約条件の整理を行い、 一般的な対話型問題解決システムの枠組みを提案することを目的とする。