スケジュールナースで時間割作成出来る？
Pythonまで使えば、フレキシブルに作成することが出来ると思います。
例として、Qiita記事 数理最適化による時間割作成
でのデータを基にタスクを用いて実装してみます。
スケジュールナースの記述能力の高さを示すデモプロジェクトです。
シフト版については、時間割作成問題 をご参照ください。 タスク版は、シフト版に比べ少しだけ遅くなりましたが、コーディングのし易さについては、シフト版よりも直観的に記述できるかもしれません。
マッピング
スケジュールナース、タスク勤務表では、スタッフ、Dayおよびシフトとタスクが変数対象となります。当然、そのままでは、時間割のイメージとにマッチしません。
そこで時間割を次のようにマッピングします。
| 項 | 時間割 | スケジュールナースプロジェクト |
|---|---|---|
| 1 | クラス | スタッフ |
| 2 | 限 | フェーズ |
| 3 | 曜日 | 曜日 |
| 4 | 科目 | タスク |
クラス名の定義
スタッフプロパティシート上に記述します。
科目の定義
タスクとして実装します。
時限の設定
6時限まであるので、フェーズ0－5まで定義します。
限、曜日の定義
適当な月曜日から金曜日までを表示期間として、それをそのまま月曜から金曜までの時間割とします。
| 項 | 時間割 | スケジュールナース |
|---|---|---|
| 1 | 月曜 | 月曜 |
| 2 | 火曜 | 火曜 |
| 3 | 水曜 | 水曜 |
| 4 | 木曜 | 木曜 |
| 5 | 金曜 | 金曜 |
カレンダ設定は、どこでもよいのです。
タスク予定は、次のように各曜日6時限のマスが出来ました。
各教科は、1週間の必要授業数を行う
時間割上の1週間は、プロジェクト上今月期間全体になります。英国数社理については、週あたり4コマを制約します。以下同様に制約します。
各教科は、1日の授業数の上下限を守る
Qiita記事を参照し、各科目の1日の授業数は、1以下としました。各曜日分制約する必要があります。
体育など移動教室は連続しない
体育、音楽、技術、家庭の全ての組合わせを禁止します。
移動科目は、次のタスク集合です。
総合と道徳は6限に行う
列制約を用いて記述します。6限以外の総合と道徳は禁止します。
総合と道徳は学年で曜日を統一して行う
ペア制約を用いて記述します。最初の行は、1年の代表クラスが総合ならば、全1年クラスが(かつ)総合になる、という制約です。
総合と道徳は異なる学年で同じ時間には行わない
列制約を用いて記述します。上で、学年を統一した動きとしているので、学年を代表する１クラスについて制約すれば十分です。
ここまでは、GUIで記述できました。GUIで記述する利点は、一つ一つ記述しながら、即求解し、記述の正当性を確認しながら進められることです。この作業は、意外に楽しいです。
以降は、GUIで記述するのが難しい、もしくは、Pythonで記述した方が楽なので、Pythonで記述します。
教員の制約
Qiita記事中のソースで、csvファイルをダウンロードしています。
lesson_df = pd.read_csv("https://raw.githubusercontent.com/ryosuke0010/opt_test/master/composition.csv")
このファイルを眺めてみると、grが学年列、clがクラス名であり、例えば3年1組の英語は、教員6という具合に、クラスが決まれば、担当科目の教員はこの表により決まることが分かります。
教員6は、3年1組以外にも全ての3年のクラスの英語授業を担当し、3年3組の総合と、道徳に関しても担当することが分かります。
gr,cl,英語,数学,国語 理科,社会,美術,音楽,体育,技術,家庭科,総合,道徳
3,1,教員6,教員9,教員15,教員14,教員18,教員0,教員1,教員2,教員5,教員21,教員9,教員9
3,2,教員6,教員9,教員15,教員14,教員20,教員0,教員1,教員2,教員5,教員21,教員2,教員2
3,3,教員6,教員11,教員15,教員13,教員18,教員0,教員1,教員2,教員5,教員21,教員6,教員6
3,4,教員6,教員9,教員15,教員13,教員18,教員0,教員1,教員2,教員5,教員21,教員18,教員18
3,5,教員6,教員9,教員15,教員13,教員18,教員0,教員1,教員2,教員5,教員21,教員15,教員15
2,1,教員7,教員10,教員16,教員12,教員19,教員0,教員1,教員3,教員5,教員21,教員3,教員3
2,2,教員7,教員10,教員16,教員12,教員19,教員0,教員1,教員3,教員5,教員21,教員19,教員19
2,3,教員7,教員10,教員16,教員12,教員19,教員0,教員1,教員3,教員5,教員21,教員10,教員10
2,4,教員7,教員10,教員16,教員12,教員19,教員0,教員1,教員3,教員5,教員21,教員7,教員7
1,1,教員8,教員11,教員17,教員13,教員20,教員0,教員1,教員4,教員5,教員21,教員11,教員11
1,2,教員8,教員11,教員17,教員13,教員20,教員0,教員1,教員4,教員5,教員21,教員17,教員17
1,3,教員8,教員11,教員17,教員14,教員20,教員0,教員1,教員4,教員5,教員21,教員14,教員14
1,4,教員8,教員11,教員17,教員14,教員20,教員0,教員1,教員4,教員5,教員21,教員8,教員8
1教員が同一限に担当するのは、1科目
1教員が同一限に2個以上担当することがないようにします。
各教員のあり得るシフト(科目)を列挙して、同一限で、その総和が1以下となるように制約します。下記ソースがその記述部です。
def empty_work(dic,dic_units):#1教員あたり、同一限で2個以上の授業は不可 1日あたりの授業数平準化
for name in dic:
for day in 今月:
week_vlist=[]
for ph in dayphase_list:
ph_val=ph[1]
vlist=[]
for tp in dic[name]:
subject=list_of_rows[0][tp[1]]
Class=tp[0]-1
#print(Class,day,subject)
v=sc3.GetTaskVar(Class,day,ph_val,subject)
vlist.append(v)
sc3.AddHard(sc3.SeqLE(0,1,vlist),'教員ひとりにつき同一コマは一個以下_'+name)
v=sc3.Or(vlist)
week_vlist.append(v)
div=dic_units[name]/5
print(name+' コマ数平準化',math.floor(div),math.ceil(div))
sc3.AddHard(sc3.SeqLE(math.floor(div),math.ceil(div),week_vlist),name)
各教師が1日に行う授業数は平準化を行う。各曜日で大きく違わないようにする
これは、私が勝手に想像した制約で、Qiita記事ではありません。各教員毎に担当コマ数は異なるので、各教員毎の平準化を行った方がよいだろうという、勝手な判断によるものです。
教師が決まれば、時間割一日あたりの平均コマ数は確定します。単純に平均値のfloorとceilにより上限下限をハード制約で記述しています。今回は、ハード制約で記述していて、解が存在しました。ここで解がないようなら、ソフト制約に変更する必要がありましたが、解は存在したので、ハード制約のまま、としています。 以上の記述も上のソースで行っています。
各学年毎に、所属学年の教師が、各限に行う授業数は、平準化を行う。(空コマ数の各限毎の平準化と同義)
これも、Qiita記事にはありません。各学年毎の各コマ毎の授業数上の平準化を行うものです。学年毎に、各コマの平均コマ数は決まるので、単純に平均値のfloorとceilにより上限下限をハード制約で記述しています。今回は、ハード制約で記述していて、解が存在しました。ここで解がないようなら、ソフト制約に変更する必要がありましたが、解は存在したので、ハード制約のまま、としています。 以上の記述を下のソースで行っています。
def empty_frame_avg(dic,grade_list,empty_avg_frames):#学年毎の1限あたりの空き教員数の平準化
for day in 今月:
for ph in dayphase_list:
ph_val=ph[1]
Vlist={}
for name in dic:
vlist=[]
for tp in dic[name]:
subject=list_of_rows[0][tp[1]]
Class=tp[0]-1
#print(Class,day,subject)
v=sc3.GetTaskVar(Class,day,ph_val,subject)
vlist.append(v)
v=sc3.Or(vlist)
grade=get_grade(name,grade_list)
if grade not in Vlist:
list=[]
list.append(~v)
Vlist[grade]=list
else:
Vlist[grade].append(~v)
for item in Vlist:
f=empty_avg_frames[item]
s=str(item)+'年空き教員数平準化 '+str(ph_val+1)+'限'
print(s,math.floor(f),math.ceil(f))
sc3.AddHard(sc3.SeqLE(math.floor(f),math.ceil(f),Vlist[item]),s)
全体ソース
import sc3
import csv
import urllib.request
import math
import re
def get_grade(name,grade_list):
t_ind = int(re.sub(r"\D", "", name))
grade=grade_list[t_ind]
return grade
def empty_work(dic,dic_units):#1教員あたり、同一限で2個以上の授業は不可 1日あたりの授業数平準化
for name in dic:
for day in 今月:
week_vlist=[]
for ph in dayphase_list:
ph_val=ph[1]
vlist=[]
for tp in dic[name]:
subject=list_of_rows[0][tp[1]]
Class=tp[0]-1
#print(Class,day,subject)
v=sc3.GetTaskVar(Class,day,ph_val,subject)
vlist.append(v)
sc3.AddHard(sc3.SeqLE(0,1,vlist),'教員ひとりにつき同一コマは一個以下_'+name)
v=sc3.Or(vlist)
week_vlist.append(v)
div=dic_units[name]/5
print(name+' コマ数平準化',math.floor(div),math.ceil(div))
sc3.AddHard(sc3.SeqLE(math.floor(div),math.ceil(div),week_vlist),name)
def empty_frame_avg(dic,grade_list,empty_avg_frames):#学年毎の1限あたりの空き教員数の平準化
for day in 今月:
for ph in dayphase_list:
ph_val=ph[1]
Vlist={}
for name in dic:
vlist=[]
for tp in dic[name]:
subject=list_of_rows[0][tp[1]]
Class=tp[0]-1
#print(Class,day,subject)
v=sc3.GetTaskVar(Class,day,ph_val,subject)
vlist.append(v)
v=sc3.Or(vlist)
grade=get_grade(name,grade_list)
if grade not in Vlist:
list=[]
list.append(~v)
Vlist[grade]=list
else:
Vlist[grade].append(~v)
for item in Vlist:
f=empty_avg_frames[item]
s=str(item)+'年空き教員数平準化 '+str(ph_val+1)+'限'
print(s,math.floor(f),math.ceil(f))
sc3.AddHard(sc3.SeqLE(math.floor(f),math.ceil(f),Vlist[item]),s)
def get_list_of_rows():
url="https://raw.githubusercontent.com/ryosuke0010/opt_test/master/composition.csv"
response = urllib.request.urlopen(url)
lines = [l.decode('utf-8') for l in response.readlines()]
#print(lines)
reader=csv.reader(lines)
list_of_rows=list(reader)
return list_of_rows
def get_teacher(Class,subject,list_of_rows):
ind= list_of_rows[0].index(subject)
return list_of_rows[Class+1][ind]
def get_teacher_ind(Class,subject,list_of_rows):
name=get_teacher(Class,subject,list_of_rows)
t_ind = int(re.sub(r"\D", "", name))
return t_ind
def post_main():
print('Executing Post Main')
grade_list=[3,3,3,2,1,1,3,2,1,3,2,1,2,1,1,3,2,1,3,2,3,2]
list_of_rows=get_list_of_rows()
tmap={}
grade_map={}
for Class in 全スタッフ:
for D in 今月:
for ph in dayphase_list:
ph_val=ph[1]
day=D*len(dayphase_list)+ph_val
subject=task_solution[Class][day]
t_ind=get_teacher_ind(Class,subject,list_of_rows)
grade=grade_list[t_ind]
if grade not in grade_map:
list=[0]* len(今月)*len(dayphase_list)
list[day]+=1
grade_map[grade]=list
else:
grade_map[grade][day]+=1
#print(teacher,subject)
Day=D
if t_ind not in tmap:
list=[0,0,0,0,0]
list[Day]+=1
tmap[t_ind]=list
else:
tmap[t_ind][Day]+=1
tmap2=sorted(tmap.items())
#print(tmap2)
#print(grade_map)
print('各教員の各曜日に対する授業数平準化結果')
print(' 月 火 水 木 金')
for t in tmap2:
print('教員'+str(t))
print('')
print('各学年毎の各限に対する授業数の平準化=空き授業数の平準化結果')
for g in grade_map:
print(str(g)+'学年:')
print(' 月 火 水 木 金')
for i in range(len(dayphase_list)):
print(str(i+1)+'限 ',end='')
for day in 今月:
print(grade_map[g][day*len(dayphase_list)+i],' ',end='')
print('')
print('')
list_of_rows=get_list_of_rows()
print(list_of_rows)
dic={}
dic_units={}
grade_units={}
grade_list=[3,3,3,2,1,1,3,2,1,3,2,1,2,1,1,3,2,1,3,2,3,2]
for list in list_of_rows:
col=0
subject_units=[0,0,4,4,4,4,4,2,2,2,1,1,1,1]
for item in list:
if '教員' in item:
if item not in dic:
l=[]
c=list.index(item)
dic_units[item]=subject_units[c]
l.append((list_of_rows.index(list),list.index(item)))
dic[item]=l
else:
dic_units[item]+=subject_units[col]
dic[item].append((list_of_rows.index(list),col))
col+=1
for item in dic_units:
grade=get_grade(item,grade_list)
if grade not in grade_units:
grade_units[grade]=dic_units[item]
else:
grade_units[grade]+=dic_units[item]
print(grade_units)
print(dic)
print(dic_units)
empty_work(dic,dic_units)
teachers={1:grade_list.count(1),2:grade_list.count(2),3:grade_list.count(3)}
print(teachers)
empty_avg_frames={}
for t in teachers:
empty_avg_frames[t]=(teachers[t]*6*5-grade_units[t])/(6*5)#平均空きコマ数を求めて、そのfloor,ceilを制約範囲とする
print(empty_avg_frames)
empty_frame_avg(dic,grade_list,empty_avg_frames)
解
検証
解が出た後に、ポスト処理で、解の妥当性について検証しています。
最初は、各教員の月～金授業数に偏りがないかのチェックです。平均値についてfloor,ceilしているので、偏差は1以内となっています。
次に、各学年の授業数の偏りチェックです。これも平均値についてfloor,ceilしているので、偏差は1以内となっています。
制約した通りに動いているようです。
以上のpython記述部は、post_mainです。
Algorithm 1 Solving Process Started..
Python プロパティファイルの生成が終わりました。
_____________________________________
| | | |
| Weight | Errors | Cost |
|___________|___________|_____________|
| | | |
|___________|___________|_____________|
| | |
| Total | 0 |
|_______________________|_____________|
*********UB=0(0) 1.818(cpu sec)
o 0(0)
解探索が終了しました。 3 (秒)
解が得られました。
ポスト処理を実行します。ソルバを呼び出し中です。
Executing Post Main
各教員の各曜日に対する授業数平準化結果
月 火 水 木 金
教員(0, [5, 6, 5, 5, 5])
教員(1, [5, 5, 5, 6, 5])
教員(2, [2, 2, 3, 2, 3])
教員(3, [2, 2, 2, 2, 2])
教員(4, [2, 2, 1, 1, 2])
教員(5, [3, 2, 2, 3, 3])
教員(6, [5, 5, 4, 4, 4])
教員(7, [4, 4, 3, 4, 3])
教員(8, [4, 4, 3, 3, 4])
教員(9, [3, 4, 4, 4, 3])
教員(10, [4, 3, 4, 4, 3])
教員(11, [5, 4, 5, 4, 4])
教員(12, [4, 3, 3, 3, 3])
教員(13, [4, 4, 4, 4, 4])
教員(14, [3, 4, 4, 3, 4])
教員(15, [4, 5, 5, 4, 4])
教員(16, [3, 3, 3, 3, 4])
教員(17, [3, 4, 4, 4, 3])
教員(18, [3, 3, 4, 4, 4])
教員(19, [3, 3, 4, 4, 4])
教員(20, [4, 4, 4, 4, 4])
教員(21, [3, 2, 2, 3, 3])
各学年毎の各限に対する授業数の平準化=空き授業数の平準化結果
1学年:
月 火 水 木 金
1限 4 4 3 4 4
2限 4 4 4 4 4
3限 4 4 4 3 4
4限 4 4 4 3 4
5限 4 4 4 4 4
6限 4 4 4 4 4
3学年:
月 火 水 木 金
1限 6 5 6 5 5
2限 5 6 5 5 5
3限 5 6 6 6 5
4限 5 5 6 6 5
5限 5 6 6 6 6
6限 5 6 5 5 6
2学年:
月 火 水 木 金
1限 3 4 4 4 4
2限 4 3 4 4 4
3限 4 3 3 4 4
4限 4 4 3 4 4
5限 4 3 3 3 3
6限 4 3 4 4 3
ポスト処理を終了しました。 1 (秒)
求解速度
| アルゴリズム | 速度 | 備考 |
|---|---|---|
| 1 | 1.8秒 | |
| 2(Highs) | 174秒 |
プロジェクト
プロジェクトは、以下です。
ダウンロード
して、実装の参考にしてください。
