学校時間割り自動編成
吉川 昌澄……l制‖州‖川‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝川＝＝‖‖‖‖‖＝‖州‖州Il……l…l…W‖冊＝川‖皿＝…………ll川‖＝‖‖‖‖‖‖‖‖＝‖‖＝＝‖‖‖＝‖‖＝＝‖‖＝‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖川‖‖‖‖＝川＝‖……l…帖‖刷Il川Il川l…

有限個の制約Cl，…，CMからなる．制約Cjは，その1． はじめに制約に関与する変数の組（vkl，…，VkMj）と，関与変数各高校では毎年春休みに次年度の毎週の時間割りをの値の組が満足すべき条件（例えば論理式）編成している．大規模な学校では，この作業は梅めてCjkl，…，kMj（vkl，…，VkMj）を持つ．ここで，1変数に関与困難であり，150人目もの労力を掛けているのが実情する制約をユナ））（unary）制約，2変数の場合をバである．また，大学や予備校など，各種の学校では時イナ））（binary）制約，一般にN変数間（Nqary）間割り編成のために2〜3人程度の要員を配置してい制約と呼ぶ．問題は，すべての制約Cjを同時に充足る例もある．このように，時間割りの編成は極めて困するような各変数viの値Ⅹiを対応する候補集合Di難な作業であり，その自動化が望まれている．

中から選択する組み合わせ探索問題である［15，16］．

筆者は，これまでに，学校時間割り編成問題を制約CSPの例として三色問題がある．これは，日本の充足問題（CSP：ConstraintSatisfactionProblems）

都道府県区分図のように，平面上の線により区切られとして定式化し，汎片川勺なアプローチで自動解決技術た各領域を，隣接する領域が同色にならないように三を開発してきた．現在では，中学校・高等学校・I大学色で塗り分ける問題である．各隣接領域の組の間で同向けのソフトウェアパッケージとして広く利用されて色とならないという条件を制約（Cl東京・神奈川（x，y）…Ⅹいる．

≠y；C2舶1T■葉（Ⅹ，y）…x≠y；…）とすれば，制約充足

一般に制約充足問題はNP完全であり万能の解法問題として定式化可能である．その他のトイブロブレは存在しない．そこで高速の近似解法やユーザ編集機

ムの例として，NLQueen問題［7］，SAT問題，各種能が重要となる．また，現実世界の問題をいかに定式グラフ問題，パズルなどがある．

化し，不完全な解法を用いてシステム化するかという2．2 学校時間割り編成問題

モデリングの問題が極めて重要となる．

高校の時間割り編成問題（図1）は，1週間の授業

本稿では，筆者らが開発した学校時間割り自動編成や会議の予定を決定する問題である．クラス数30・技術を概言見するとともに，汎用的制約問題解決技術の先生70人程度の大きな学校では，述べ100〜150人口重要性について概観し，学校時間割り自動編成システという工数を掛けて時間割りを編成している．各授業

ムと大学時間割り自動編成システムについて述べる．に出席する先生や対象クラス，利用する特殊教室など

最後に，今後の課題と展望について考察する．の属性はあらかじめ与えられる．ここでは，各授業を2．学校時間割り編成問題の定式化

開催する曜日時限がCSPの変数となり，1週間の時限（月1，…，上4）が候補集合となる．主な制約はここでは，まずモデルとなる制約充足問題について，続いて学校時間割り編成問題について述べる．
3−10

2．1制約充足問題（CSP）

CSPは，有限個の変数vl，…，VNと，各変数の取り

古文

月1 数Ⅰ

田中佐藤

月1 数Ⅰ

古文

うる値の有限集合である候補集合Di＝（Ⅹi．，…，Ⅹi。i）と，
土4 現文

よしかわ まさずみ
ソフトバンク・イーシー

ホールディングス株式会社〒103−0015束京都中央区「i本橋箱崎町24−1（本研究は著者がNEC在籍中の成果）
2001年9月号

幾何（わクラス時間割り表

現文

土4 幾何

（り先生時間割り表

図1高校時間割り編成問題のイメージ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（3）461次の通り．

Cl同じクラス・先生の授業が同じ時限に重ならない．

C2 選択授業など同時開催の授業や，芸術など連続開催の授業がある．
C3 特殊教室での同時開催授業数の制限．
C4 先生などの予定により不都合な時限がある．

C5 各クラスの同じ教科・科目の授業は異なる曜日にする．

図2 COASTOOLアーキテクチャ

C6 先生の1日，または，連続の授業数の制限．

C7 週2コマの授業はなるべく間を1日以上あける．
ここで問題となるのは，例えば，制約C7に「なる（def−Set 授業 数Il−1a 数Il−1b．．．）；；変数の集合（def・Set 時限 月1月2．．．土4）；；候補集合（deFconstraint 非常勤田中先生の都合；；制約：variable（（Ⅴ 田中授業））；；関与変数

べく」とあるように，絶対とは言わないが充足が望ま：condition（notGs−a V 田中不在時間））；；条件しいという制約があることである．現に実際の高校で：penaltyl（カは一部の制約を違反した時間割りが運用されている．
このように絶対制約と考慮制約を持つ問題を定式化する枠組みとして，CSPを若干修正した制約緩和問題（CRP：Constraint Relaxation Problem）を定義する．CRPは，CSPのモデルに加えて各制約が違反時；；違反点数（def−PrOblem 時間割り編成問題：variables（0受業 時限））；；CRP；；変数と候補集合：constraints（非常勤田中先生の都合．．．）；；制約：minimize 制約違反点数の総和）；；目的関数

図3 COASTOOL／Lispによる問題記述例の罰則となる違反点数を持つ．問題は，違反している制約の違反点数の合計が最小となるような割り付け2）．ユーザは現実問題を制約問題に定式化し，宣言的（各変数とその値の組）を探索する組み合わせ最適化

問題記述言語を用いてこれを記述し（図3），その間問題である．絶対制約と考慮制約が混在する場合，絶題にふさわしい解法を選択することにより問題を解決

対制約には十分大きい違反点数を，考慮制約にはそのできる．ここで重要な点は，問題自身とその解決方法重要度に応じた違反点数を与えることにより，現実問が独立であることである．したがって，1つの問題に題の要求に即した定式化が可能となる．

異なる解法を適用すること，また逆に，異なる問題に

3．学校時間割り編成問題のモデリング
筆者らは，制約ベース計画シェルCOASTOOL

1つの解法を再利用することが可能である．また，過当な解法がない場合には，割付ライブラリの制約伝播等の機能を用いて，個別の解法を開発する．

（Constraint¶based Assignment and Scheduling 筆者らは，COASTOOL／Lispを用いて久喜北陽高TOOL）［13，22］を開発し，各種時間割り編成問題や校の時間割り問題をモデル化した［22］．まず高校を訪生産計画問題に適用してき一た．ここでは，COAS−

問し3時間程度のインタビューでデータを入手，1．5

TOOLを中心に，現実問題のモデリングについて述八日の工数で問題（制約500行，データ1，000行）をべる．

記述した．COASTOOLが編成した時間割りを先生

3．1COASTOOL／Lispによるモデリングにファックスしてコメントをいただき，データの修正，COASTOOLは汎用的なスケジュー1）ング問題解

制約の追加・削除・違反点数の調整などのフィードバ決を目指すシェルである．前章で述べたように，制約ックを10回程度繰り返した．これにより，わずか3問題は現実の時間割り問題のモデルとして有効である．

入日程度で人手並に高品質の時間割りを自動編成する

しかし，その一方で，制約問題はNP完全問題であことに成功，エキスパートシステムのエンジン部分のり，無二万能の解法は存在しないという課題がある．

開発を完了した．この成功の要因としては，問題と解

そこで，COASTOOLは制約問題モデルに基づく宣法が独立であり解法のヒアリングや実装が不要なこと，言的問題記述言語と，ある範囲の問題に有効な汎用的宣言的な制約問題のモデルによりモデル化が容易なこ解法を集めた割付ライブラリとから構成される（図と，フィードバックが容易で緻密なプロトタイピング

462（4）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

が可能なことなどが考えられる．

違反時にどの変数を直せばよいか不明瞭であるという

3．2 COASTOOL／C＋＋による制約の実装課題がある．そこで，両者を組み合わせて，それぞれスケジューリングシステムはデータベース（DB）の利点を利用可能にしたのが仮想制約である．すなわ

上のデータをメモリ上の制約問題データ構造に展開し，ち，常に後者の形の制約1個（C。）を持ち，制約違反解法アルゴリズムにより自動立案を行い，画面インタが発生した場合にはその部分に関して動的に前者の形フェース（GUI）を通してユーザ編集を行う．一般にの制約（C．，C2，C3）を生成する．仮想制約により，制制約問題はNP完全のため，メモリ上での効率的な約の個数を制限し，かつ，制約違反時に変更すべき変データの実装方法，高速かつ高品質な解法アルゴリズ数が明らかになる．

ムが重要となる．COASTOOL／Lispには，問題の記例として，制約C6「先生の1軒授業数の制限」を述能力，メモリ容量，速度性能，DBやGUIとの連考える（COASTOOL／Lispでは実装されていない）．

携などの課題があり，COASTOOL／C＋＋を開発しある先生の授業が15個あり，1Fl授業数の制限が4た［23］．coASTOOL／C＋＋は一種のオブジェクトだとすると，違反する5個の変数の組み合わせは（先指向フレームワークで，宣言的問題解決言語の代わり生1人につき）15C5＝3003通りある．この大量の制約に，変数や制約など制約問題解決に必要なクラスライも，1つの仮想制約と違反している制約の実体によりブラリを提供する．ユーザはクラスライブラリを用い置き換えることができる．COASTOOL／C＋＋では，て，メモリ上に制約問題データを構築し（図4），割仮想制約を用いることにより，メモリ容量を1／10に付ライブラリの解法を適用する（または，ライブラリ削減，立案時間を1／20に短縮することに成功したを用いて個別解法を開発する）．

［23］．仮想制約のメカニズムは複雑であり，その実現COASTOOL／C＋＋の最大の特長は，仮想制約と方法は決して簡易ではない．しかし，さまざまな制約呼ぶ制約管理方法である．例えば，制約Cl「同じ先をシステム上に実装し効率的に処理するためには，こ生の授業が同じ時限に重ならない」を考える．今，あのような実現方法の工夫が必要である．

る先生が3つの授業x，y，Zを持つとしよう．この制約には，2通りの実装方法が考えられる．1つは，この先生が受け持つ相異なる2つの授業の組み合わせすべてに対して，同じ時間にならないというバイナリ制
約（ClX，y（Ⅹ，y）…Ⅹ≠y；C2y，Z（y，Z）…y≠z；C3Z，Ⅹ（z，X）…

4．学校時間割り編成問題の解法
主なCSPの解法には，無矛盾姓（consistency）手法，バックトラック法，局所探索手法がある［15，16］．
学校時間割り編成問題において，1週間の時限数34，z≠Ⅹ）を定義する方法である．もう1つは，この先生

クラス数30の高校では，授業の仝駒数は約1，000弱が受け持つすべての授業の組に対して，重なりがないとなる（選択授業など複数クラスにまたがる授業があという1つの制約（CoX，y，Z（x，y，Z）…（x≠y）＜（y≠z）＜る）．したがって変数は約1，000個の授業，候補集合（z≠Ⅹ））を定義する方法である．前者は制約の個数がは34の時限となり，その組み合わせの数は341，000≒

組み合わせ的に爆発するという課題がある（一般に，101，531となる．このような膨大な探索空間において，先生がn個の授業を持つ場合は。C2個）．後者は制約

無矛盾性手法，バックトラック法（あるいは分杖限定法）は計算量爆発の問題がある．また，制約緩和の可能性があるため，杖刈りによる探索空間の限定は困難

Class TbacherAbsence：public Constraint〈Tbacher ☆Jea；
TimeSlotVhriable ☆＿Var；

Public：TbacherAbsence（恥acher ＊t，Lesson ＊1）：Jea（t），Jar（l−＞timeslotO）％；

virtualint doCheckO const（return（isTbacherAbsentAt（㌔掬a，Jar＞valueO））である．
そこで近年注目されているのが局所探索法である．

局所探索法は，まず，乱数などを用いて初期割付を作成する．通常，初期割付は何らかの制約を違反している．次に，制約違反が小さくなるように（または目的関数を改良するように）繰り返し改良操作を施し，解）；

virtualnoat penaltyO const（returnlO．0；〉；または近似解を求める．解発見の完備性がない反面，制限時間内に何らかの近似解を得られる点，制約緩和）が可能な点などが時間割−）への応用に過している．

図4 COASTOOL／C＋＋による問題記述例
2001年9月号

改良操作の内容と繰り返しの制御方法によりさまざ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）463

まな■方法がある．山登り法は改悪となる改良操作を行

果は，再度，制約伝播で残りの変数へ伝播される．候わない手法である．MCHC（min−COn創ctshill−Climb−

補数の少ない変数と他の変数への影響の小さい値を優ing）法［7］は，制約を違反する変数をランダムに選び，先している．途中，候補がなくなった変数は後一山Iしにその変数の伯を違反制約の個数（または違反点数）がして，違反点数が最小となる値を順次割り付ける敲小になる依（同点の場合はランダム）に変更する．

Greedy初期割付法により割付を行う．制約伝播を用

MCHC法は，最適件は低いが大規模問題の高速解決いることにより，MCHC法の結果よりも優れた初期に過している．

割付を作成できた（図5）．

SA（Simulated Annealing）法は，金属の焼きなま

ここで川いている制約伝播はアーク無矛盾性（AC：しを模倣したランダムに改悲するJ‖1所探索法である．

arc consistency）手法［6］である．これは，個々の制制御変数に氾度を設け，高温から徐々に冷やしていく．

約を考えて，充足の叫能性のない値を候補集合から取高配時ほど高い確率で改悪を′受け入れる．ゆっくり冷り除く処理である．例えば，制約x＜yについて，候やせば初期割付によらず崩過角引こ到達するが，かなり補集合Dx＝Dy＝（1，2，3）を絞り込めばDx＝（1，2），Dyの計算時聞を賀する．速度性能よりも最適性を追及す＝〈2，3）となる．いずれの制約伝播も，何らかの変化る問題に過している．

が生じた場合には，最終的に変化がなくなるまで伝播

筆者らは高校峠1削割り編成にバックトラック法を過川したところ，数「Ⅰ計算機を走らせ続けても最初の解には到達しなかった．MCHC法は高速だったが先生点と同等を繰り返す．

また，その後，RFLGを改良し，J‖）所最適解脱山千法を開発した．RFLGの改良は候補がなくなったの手作業が2／3程度完了した時の品質であっ変数を後「lJtしにせず，その時点で繰り返し改良を過刷た．SA法は一品質は少し良いが計算時問が長かった．

する段ド肘l勺立案手法である［4］．り所最適解脱柏手法

そこで，高ぶ一質の初期割付法であるRFLG（Reallyは，同じクラスの授業が同じIl斜眼に重ならない（制約FullLookaheadGreedy）法［22］を開発しMCHC法Cl）を利別して，同じクラスの2つの授業を玉突きと組み合わせたところ，1〜2分で・先生の手作業ののように軌かすことによ−），J．il所最適解から脱出する90％以上の．−，占質の時間割りを自軌編成することに成功

時間割り専別の方法である［2］．これらの改良により，した（lヌ15）．

違反点数をさらに30〜97％削減することに成功し，RFLG法は，制約伝播により候補集合の絞込みを行い，残った候補を順次変数に割り付ける．割付の結より制約の厳しい高校に対しても，先生の人手の時間割りに遜色のない品質を得ることが可能となった［5］．

5．Al学校時間割り自動編成システム「ス700

クールマジック」

600

睦Ⅰ6に，AI学校時間別り自動編成システム「スク500
TL． ．＜． ． ． ▲．▲．∴ 一 1 舶Elた良策炬†∩（E〉

ヽd■． ユ邑400
反点
数300

り／丁けない し ＝点・半石【の○に媛某を入れない
同し哨間に同し先生の回し時間に回しクラスの授業埴j【パ寸りないト 川舟

先生びJ〔】瞬間奴の棚月毛イる

し（t・か200
芸術【鰻合t空一一品三甲 回言喜一】巨木丈一本音：】t見代文量
茶話【英語【体育l奴芋【】l惑言喜】 本義：】ト〔ム〔朋投写古典

回三引 さ史学l休家lす史i引」呆根：】化芋こl出払 lILl疫熟国三喜藁・体妄 †￡史写rl地歴ユ100保健】亙三ヨ】国語】御斗／、酬斗八 敗7几 いれ】化睨代社偶礎】ム典】地霊ん 芸術：一石史芋口 嘲射総今1甲．†丹哀】㈲甲 芥三舞＝軸鮨j屑穂 7謝1：胤竺 柑今煙． 1授業＝→赤更 粂三喜L 唄代た昌明1t垣界丈しし授巣【0較】斗の予定か△1′は授業を人／l射 ？†如ノ予定か×には授業を入′lな（r軍敗】l㌫休雲賀古甲釦り覚浸しL勘封】l典占 和芸【安休抒跡l＝祢芸lや 異くJ某捺」． 雲三冥史界世 祉代現Ⅰ喜‡ヨ【典ム局所最適解脱出 処理時間（sec．）

樫札q ■睨代文 芸細‖t色恋〔こ＝′ロ爪史【1昭 、1羊【丁てけ一拍ざⅢ∵・ 鼠丁ドい：即し文 古史芋r】「，軒休和【】ノ古典魚拓ま休憩【1．日本史圧 蓋摘出：首藤史配隠札 ＝：占典郎三慕射て主喜

図5it一丁膏交時l甘割り編成の実験結果：GはGreedy初期割り付け．SAでαは冷却比率，βは同塩での繰返し回数，γは初期混度，プロットは初期割り付け修了
以降のみ
464（6）

図6 スクールマジック画面イメージ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチールマジック」の画面イメージを示す．スクールマジ

自動機能が機敏に対応可能なことが望ましい．

ックは，各種データ編集，制約違反点数の設定，各種結局，スクールマジックにより，従来150入日を要時間割り表示，制約違反状況や推薦移動先の提示など，して時間割りを編成していた高校でも，データ入力か約40種類の画面を備えるパッケージソフトウェアでら開始して2人目程度で時間割りを完成することが可ある．

能となった．スクールマジックは，現在，100を越えスケジューリング問題における違反点数や目的関数を正確に定めることは難しい．また，厳密な定式化ができたとしても，解法の能力が不十分な場合も多い．

そこで，GUI（図6）を通したユーザ編集機能が重要る中学・高校・大学で利用されている［11］．

6．大学時間割り自動編成システム
筆者らは，COASTOOL／C＋＋を用いて，大学版となる．ここでは主導権混在型（mixed−initiative）

スクールマジックを開発，早稲田大学の時間割り編成問題解決法［23］（図7）が有効である．例えば，自新に適用し，実用化に成功した．大学時間割り編成問題

剤付の結果をユーザが確認し一部をフィックス，一部は，教員があらかじめ決められた各講義や会議を，さを修正し，その結果を初期割付とみなして繰F）返し改

まざまな制約を考慮しながら，より多くの制約を満足良を適用する．このように，システムの自動機能とユするように1週間のうちの1つの時限に割り付けるとーザの手動機能を自由に行き来する協調的な問題解決

同時に，講義を開催する教室を割り付ける問題である．

が可能である．局所探索法は，再計矧司様，自動修正

大学時間割−）編成問題は高校時間割り編成問題と類似にも有効である．

であるが，下記の点で異なっている．

情報提示機能としては，制約の違反状況の表示，修① 高校時間割りに比べて問題規模が大きい．

正を施した場合の影響を示すwhatNif解析，最適な修② 時限だけでなく教室の割付が必要．

正方法を示す推薦機能，割付不可能な理由を解析する③ 前期のみ／後期のみ／通年の講義が混在し前期と後説明機能などがある．これら機能を実装する上で，システムが制約問題を宣言的なデータとして保持するこ

期の時間割りを同時に編成する．
④ 講義は選択性のため基本的にクラスはない．しかとが有効である．また，システム側とユーザ側が同一し，同一専修コースの必須科目など，重ねてはいの問題データを対象とすることが重要となる．例えば，

けない講義がある．

ユーザが制約や目的関数を修正した場合，システムの⑤ 先生の希望教室・時限や昨年度の時間割りの割付情報を元に類似の割付を優先する．

筆者らは，COASOOL／C＋＋上に大学時間割り編
成問題を定義し，高校時間割りとまったく同一の割付ライブラリをそのまま適用し，実用化に成功した．すなわち，10分程度の計算時間で，人手並みの高品質な時間割りの自動立案に成功した．これは，COAS−

初期割付法 違反点数 時間（秒）最良の回数

Greedy

399．2
395．1

RFLG
段階RFLG 0．9193．7

03349．2

0704．07（由一部の初期割付情報（前年度時間割り）を利用

初期割付法 違反点数 時間（秒）最良の回数

Greedy

96．9
8．5

RFLG
段階RFLG 26．5

178．1

0678．46837．66払）初期割付情報なしで白紙から自動編成
図7 主導権混在型問題解決のフロー

2001年9月号

図8 大学時間割り編成での実験結果© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）4t；5

TOOL／C＋＋アーキテクチャの汎川性が有効である

記述を可能とするGUIツールとしてハイパーデータことを示している．解法の点では類似の特性を示した

シーが，昨年度割付情事帥J用峠は，特に，段階的．立案手法［1，18，19，24］．ハイパーデータシー ト（匪Ⅰ9）は，トを開発し，時l言封割りIlり題の簡易記述に成功したが有効であった［5］（図8）．これは，段階的立案手法

リスト・二次元衷など構造を持つデータシート聞の演が昨年度割付の問題点を早期に解消してから初期割付算と制約を基本とする新しい表計算モデルを持ち，スプレッドシートの簡易性とデータベースの頑強性や二直を進めるためである．

利川性を併せもつ表計算ツールである．構造変換・フ7．今後の課題と展望ィルタ・セル値演算などデータシートの構造に基づく

上記のように，筆者らはCOASTOOLによる汎刷新しい未満算系と，表聞演算処群の日動巾計算機構お的制約問題解決により，逐次改良手法を適用すること

よび一1咋的な違反を許す柔軟かつ強力な制約管理を特により，中学・高校・大学向け時間割り作動編成シス徴とする．特に制約違反衷と呼テム「スクールマジック」を開発し，100以上の学校トを定義することにより，SQLのクエリに相当するで利川されるに至っている．

任意の制約条件を効率的に定義可能である．

まず轟要な点は，大規模複雑な現実の時間割り問題

ハイパーデータシートによリスクールマジックの制に対し，制約伝播を印いた高品質初期割付と高速の繰約】Lり題を定義したところ，すべての制約条件の簡易主i己り返し改良一手・法の組み合わせによる解法が，極めて高述に成功した．Ⅰぎ110に「先生の1‖授業数の制l眼」

い有効性を示したことである．従来の汎用的解法技術（制約C6）の記述例を示す．全制約条件の記述（lヌIに比べて，飛躍的な高速ノ性と高品質性を同時に満足し，ll）に要した記述量は，COASTOOL／C＋＋で約尖用的にも八千とほぼ同等の時間割りのF二ほ力編成を吋

1，000行であるのに対して，ハイパーデータシートで能とした．

は約50のシート演算オペレータで記述■け能である．

次に重要な点は，COASTOOLにおいて問題のモまた，WYSWYGインタフェースにより簡易に記述デリングと解法とを分離したことである．これにより，可能であり，SEレベルの能力を持たない一般エンド

微妙で複雑な現実問題の精緻な定式化が吋能となった．

ユーザでも制約1！り題の記述が叶能となることが期待さ

また，同一の割付プログラムが小学・高校・大学向けれる．

それぞれのスクールマジック製−1いこおいて利別されるに至った．

今後，ハイパーデータシート とCOASTOOL／C＋＋を有機的に結介することにより，汎州別約l！り題

しかし，特に矢川に耐えるCOASTOOL／C＋＋で解決パッケージツールが実現＝摘旨となろう．これは，の制約や制約l！り題の記述には，研究者レベルの専門的現在の数理計画パッケージと類似だが，記号処理によ能力が要求される．このため，個々のl！り題に対して，る制約が吋能であり，学校峠聞割り自軌編成システム膨大な開発努力が必要となるのが現状である．
そこで，筆者らはエンドユーザレベルでの制約問題

図9 ハイパーデータシート1■l巧Irriイメージ

466（8）

図10 ハイパーデータシートによる制約定義の例© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

図11ハイパーデータシートによる！、r校峠l糀別牛偏成問魔の仝制約の．且述や要員業務割当システム等を簡易に構築‖用巨なツール

サービス業における勤務スケジュール，廿動中朝交や軍隊・研修センターなどにおける教育や．溝習のスケジである．

ュール，スポーツ大会の対戦などイベントスケジュー

8．おわりにル，コマーシャルの放映スケジュールなど，いずれも本論文では，筆者らの時間割り廿軌編成システム開類似のⅠ！り題であり枚挙に暇がない．これらサービスシ発を概観し，汎f‖的なアプローチによる制約問題解決ステムのスケジューリングに対して，本稿のI刃容が参への試みについて述べた．筆者の経験では，て、封㈲時聞考になればヰいである．

割りと類似のニッチな問題は多々存在する［10］．例え

Garilは， アルゴリズム設，汁にレシピはない．こば，看護如卜郵便J‖卜交通機関乗務賞など要貢配苫型

れは応川面ではイ（運であり矧可いちから設計しなけれ2001年9Jjリー© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（9）46丁ばならない．しかし，研究者は幸運であり研究テーマ［10］TheInternationalSeries of Conferences on theがなくなることはない． と述べた．NP完全性に立Practice and Theory of Automated Timetabling

ち向かえば，これは必然的な結論であるといえる．し（http：／／www．asap．cs．nott．ac．uk／ASAP／ttg／pata卜

かし，それは，上記のような多積多様の問題に対して，簡単に技術を適用することはできないという結論を示（http：／／www．necsoft．com／soft／edusoft／smagic／）

している．Garilの言葉を完全に否定することはできないであろうが，筆者らは高校と大学の時間割F）に同一のアルゴリズムを適用し実用化に成功した．また，
トの開発により，多種多様な問題ハイパーデータシーを簡易にモデリング可能とした．今後，汎用制約問題解決パッケージツー

index．html）［11］NECソフトウェア，スクールマジックホームページ

ルの実現により，多様な問題が簡易に解決可能となればと願っている．

［12］NECソフトウェア，スクールマジックホームページ（http：／／www．necsoft．com／soft／edusoft／smagicu／）［13］吉川，野村，渡辺： 制約ベース計画シェルCOASTの開発と評価 ，AI全大，1993／7．
［14］吉川，金子，山之内，渡辺： 学校時間割自動編成シス

テムの開発と評佃 ，AI全大，1995／7［15］吉川： 制約最適化技術のスケジューリング問題への応用 ，AI学会誌，1998／5．
参考文献［16］吉川： 制約最適化技術のスケジューリング問題への［1］安藤，吉川： 制約データシート（2）：システムの試作と応用，，，COM・SCM・スケジューリング研究部会，1998／

評価 ，AI全大，1999／6．

9．

［17］吉川： 学校時間割り自動編成システム ，円本OR学［2］金子，吉川，山之内，鴻辺： 学校時間割自動編成システ

ムにおける制約緩和手法の提案と評価 ，AI全大，1995／［18］吉川，安藤： 制約データシートによる制約充足問題

7．

［3］金子，吉川，山之内，渡辺： 学校時間割編成問題におけ

記述 ，AI学会KBS研究会，1999／6．

る段階的編成手法の提案と評イ肝，，情処全大，1997／3．

［19］吉川，安藤： 制約データシート（1）：シート間制約に基づく新しい表計算モデルの提案 ，AI全大，1999／6．

［4］金子，吉川，山之内： 大学時間割編成問題への制約緩［20］吉川： 学校時間割り自動編成技術の紹介 ，NIME

和手法の適用と評価 ，情処全大，1997／9．

［5］Kaneko，Yoshikawa，Nakakuki：

Improving a

Heuristic Repair Method for Large SchooITimeta−
blingProblems会シンポジウム，1999／9．

，IntConfonPrinciples＆Practiceof

ConstraintProgramming（CP99），1999／10．
［6］Machworth， The Logic of Constraint Satisfac−
tion ，ArtificialIntelligence，58：3−20，1992．

［7］Minton，et．al．， MinimizingCon貝icts：A HeuristicNewsletter第20号，2000／9．（http：／／www．nime．ac．jp／nnl／news＿COnt．html）［21］Yoshikawa，Wada： ConstraintSatisfactionwith
a Multi−DimensionalDomain，IntConfonAIPlan・ningSystems（AIPS−92），1992／6．

［22］Yoshikawa，Kaneko，Nomura，Watanabe：

Constraint−BasedApproachto High−SchooITimeta−

Repair Method for Constraint Satisfaction andblingProblems：ACaseStudy ，Nat．ConfonArtif・Scheduling Problems

Intel．（AAAト94），1994／8．

，Arti負cialIntelligence，58：［23］Yoshikawa，Kaneko，Yamamouchi，Watanabe：160−205，1992．

［紆Minton， SpeciBcation−By−Demonstration：TheViCCSInterface，AAAISpringSymposium Seriese，

1996．

［9］Minton， AutomaticallyCo埴guringConstraintSat−
isfactionPrograms：ACaseStudy ，Constraintsl（1），1996．

468（10）AA Constrain卜based High−SchooIScheduling Sys−

tem ，IEEEExpert，1996／02．

［24］Yoshikawa： Specifying Constraint Satisfaction
Problems with HyperDataSheet ，Int Conf on Prac−
tice＆Theory of Automated Timetabling（PATAT2000），2000／8．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ