俺、バカだから数理最適化（整数計画問題）とかよくわかんないけどよぉ、次のようにやれば条件を満たした時間割が作れるんじゃねぇのか？
「俺、バカだからよくわかんないけどよぉ」という有名なフレーズの元ネタは何かと、このセリフでググってみたら、AIによる概要で「そんなことねえよ！」とタメ口で慰められました…そういうとこやぞ。
 |
ジョジョの奇妙な冒険 第4部 ダイヤモンドは砕けない 1 (ジャンプコミックスDIGITAL) 新品価格 |
…ってことで、前回は、プログラムで処理するのに使うデータについて紹介しましたが、今回はいよいよプログラムのアルゴリズムに入ります。
条件の厳しい授業から入れていく
手作業でもそうですが、時間割のコマ入れの基本は「条件が厳しい先生から入れていく」というところ。ほとんどどこでも入れられるような授業は後回しにして、「ここしか入らない！」というような非常勤講師の先生を優先して入れるという戦略です。
究極に条件の厳しい、というのは「この授業は◎曜日の◎時間目で確定！」するケースです。会議などによってはこういうものもあります。
さて、この厳しさをどう評価すればよいのでしょうか。
「自由」をどう計算するか
条件の厳しさを数値化するのは意外に単純です。月1から金４までで、その授業が入れるコマ数をカウントすればよいだけです。前回の授業マスタをちょっといじって説明します。
ここでは先生やクラス名などの情報は不要なので、A列の授業IDの他はP列からの時間ごとの授業可否だけ示します。
授業ごとに、このP列からのAO列までの時間ごとの授業可否の1の数をカウントすれば、その授業のを入れられる時間の数が分かります。この値を「自由度」と呼ぶことにしましょう。
そうしたら、たとえば86行目にある授業ID301の自由度は、エクセルやスプレッドシートの計算式で表せば sum(P86:AO86) ということになりましょうから、これをAP86のセルで表示させます。
これを全ての授業でやれば、AP列は自由度の項目となります。
少ない自由度から授業を入れていく
こうすると、自由度が少ないほど条件がきついということになります。自由度1というのは、この授業は、もうその時間しか入れるしかない、つまり確定ということになります。それは最初に割り振るわけです。
次に、例えば上の授業マスタのデータの一部ですが、この中ではもちろん307個の授業コマの中でも）最も自由度の低い値は4で、授業IDでいうと上の画像の中では授業ID313～316が金1～金4しかあいてないので自由度が4となっています。なお、307個の授業コマの中には、他にも自由度4はいくつもあります。
自由度が4のなかでどれから入れていくかという問題もありますが、そこは深く考えず授業ID順でやってみましょう。
授業を一つ割り振ると
ここでは313の授業を金1に割り当てたとします。割り当て後の授業シートのさっきと同じ部分はこうなります。
どう変わったかというと、大きく2つ、当該の授業に関する変更と、その他の授業の条件に関する変更があります。
具体的には
①313の結果に金1を入れ、自由度を99に上書きし、金1を赤字に変えた。
②301～303、314~316の1を0に変えた。（これに伴い、AP列の自由度がそれぞれ1ずつ減っています）
①の操作は313を金1にしたという宣言です。
プログラム的には自由度を最大値の99にしたのがミソ。自由度が少ない順に割り当てられるので、自由度99は出る幕がありません。
そして、自由度の最小値が99になったとき、つまり全部の授業IDの自由度が99となったときは、すべての授業IDがどこかに割り振られたということでめでたく完成となります。
そして②の処理。1が0になった301～303は313の対象クラスの他の先生による授業です。また、314~316は313を担当する先生の、他のクラスでの授業です。同じ時間に、同じクラス、または同じ先生の他の授業が割り振られないようにしたのです。
で、もし、313の授業に同一曜日指定や家庭科のような連続授業指定など、特殊な縛りがあれば、それに伴い、他の授業の1が0になるところが出てきます。
つまり、一つ授業が割り振られるだけで、多くの授業で自由度がガンガン削られていくわけです。
全授業を割り振り切れば終了
一つの授業を割り振れば、他の授業の自由度が減っていきます。減った時点で、また、残りのまだ割り当てられていない授業のうち、もっとも自由度の低い授業を探し、その授業の何曜日の何時間目にするか開いている時間から割り振っていく。これを繰り返してすべての授業が割り振られたら完成となります。
先ほど説明したように、自由度の最小値が99になったのがプログラム的な終了サインになりそうです。
だが、そんなうまくはいかない
しかし、そんなに簡単に時間割が作れるはずはない、と手作業で作ったことのある人ならわかっていただけると思います。そうです。実際にはこんな簡単にはいきません。
自由度0という行き止まり
一つ授業が割り振られると、他のまだ割り振られていない授業の自由度がガンガン減っていくという話は先ほどしましたが、そうすると、自由度0ということが起こり得ます。というかまず間違いなく起こります。というかきっと何度も起こります。というかしょっちゅう起こります。
自由度０とはどういうことかというと、コマを割り振っていないのに、もうその授業を入れる時間がないという行き詰ってしまった状態です。
これはその時点までの割り振りがまずかった（あるいはそもそもこの条件では時間割完成は不可能だった）ということです。
この場合、どうすればよいのでしょうか。
一手戻ってやりなおす
まず、最後に割り振った授業を別の時間に割り振りなおす
例えば、授業ID101を月曜日の1時間目に割り振って、残りの授業の自由度が減った結果、まだ割り当てていない授業ID201の自由度が0になったとしましょう。
この場合、101を月1に入れたのが悪かったということで、101を他の入れることのできる時間に割り当て直します。たとえば月2があいていたので、月2に入れなおしたとしましょう。このとき、残りの授業の中から自由度が0になるものがなければ101の授業は月2で確定し、残りの授業の中で最も事由度の低い授業の割り振りに移りますし、自由度0がまだあれば、101の授業時間をさらに別の時間で割り当て直していき、残りのすべての授業で自由度が1以上になるまで探していきます。
どの時間でもダメなら、他の授業を割り振る
もし、授業101が割り当て可能な時間のどこに入れても自由度0が生じる場合はどうしたらいいでしょうか。
この場合、授業101を割り当てたことがそもそもの間違いということで101の前の手を割り振り終わった段階に戻ります。
101の前に割り振った授業が901だとしましょう。ここで、いきなり901の授業を割り振りなおすのではなく、901の授業を割り当てた後、101以外で自由度が最も低い授業を探します。これが授業102だとして、今度は授業102に授業可能な時間の中で、授業時間を割り振り、その割り振りをしたときに101を含むまだ割り振られてない授業の中で自由度0がでないか調べます。
でなければその時間で確定、出ればまた次の授業可能な時間でトライ。どの時間でも自由度0が出るようならば、101，102以外で自由度が最も低い授業で…とすべての残りの授業で自由度が1以上になるまで繰り返します。
どの授業でもダメなら、前に決めた授業を再検討する
不幸にして、と言っても確率的にそれなりにありそうな話ではありますが、どの授業をどの時間に入れてもどうしても残りの授業のなかでどれかが自由度0になってしまう場合。これは、一つ前の授業、すなわち授業901を水2にいれたことが不幸の始まりということになります。
ということで、先ほどと同じように授業901を他の時間で入れられないか、それがだめなら授業901以外の授業を自由度の低い順に割り当て可能かを再検討します。
そのいずれもがダメならさらに901の前の授業を入れたことが間違っていたということで…
初手さえダメなら
恐ろしいことに、1手前、さらに1手前と戻っても、しつこく自由度0がどこかで生じて、とうとう初めの1手まで否定されてしまった場合、そもそもこの時間割は条件が厳しすぎて成立しないということになります。
以上が私が考えたプログラムの全貌ですが、もう賢明な皆様にはおわかりだと思います。
そう、人間ではとてもできない、気の遠くなるような作業です。今回も3620字になったし。
コメント