著者

西森 雄一 狩野 均 西原 清一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.6, pp.1094-1102, 1997-06-15

被引用文献数

4 1

---

時間割編成問題は,制約条件を満たすように,科目を時間帯に割り当てる探索問題である.従来のシステムでは,カリキュラムが単純な高校の時間割編成が対象であったが,本論文では,より複雑な大学の時間割を制約充足パラダイムにより編成する方法を提案する.大学の時間割編成問題は,課せられる制約条件が多種多様であり,また探索空間が膨大である,という問題点がある.そこで本論文では,制約を,個別に科目への制約,2科目間の関係に関する制約,時間割表全体の整合性に関する制約に分類整理することにより,前者の問題点を解決する.また,後者に対しては,制約に違反点数を与え,その違反点数の最小化を規範とする山登り法を導入し,さらに対話によってユーザと協調して探索を進めることにした.本システムは,編成の基になる時間割を作成する初期割当作成と,その時間割から不具合のある割当を反復改善する割当改善の2段階より成る.本システムを筆者らの大学の実際の時間割編成に適用した結果,人手による編成では数時間かかるところを,数十分で編成ができることを確認した.Timetabling is a search problem to assign the subjects to the time-slots so that various constraints are satisfied.Conventional timetabling systems are applicable to comparatively simple problems such as high school timetabling.In this paper,we propose a method for scheduling univerisity timetables,which have two major problems:first,it is hard to represent concretely all various kinds of constraints,and,second,the search space is extremely large.To resolve the first problem,we classify all the constraints into three groups:the constraints claimed per each subject,the binary constraints to be satisfied between two subjects,and the constraints concerning the total consistency of the timetables for the second problem,we introduce penalty per constraint to make the min-conflicts hill-climbing strategy try to minimize the total penalty.Further,our system interacts with the user to exchange suggestions each other.Timetabling is performed in two steps:generation of an initial assignment and iterative improvement of the total penalty to optimize the timetable.Applying our interactive method,we actually constructed timetables for our university,where the planning time is considerably reduced.