Ozkarahan nurse scheduling benchmark

1989年ということですので、最も古いNSP問題ということになりそうです。

現在では、0secで解ける問題です。

ptpmcrender.fcgi (europepmc.org)

驚くべきは、すでにこの時代から、個人毎のスタッフ契約体系になっていることで、土日働けない人の考慮がなされています。

import sc3

for person in [2]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'3_1',1)
for person in [3]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'4_1',1)
for person in [6]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'7_1',1)
for person in [7]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'8_1',1)
for person in [8]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'9_1',1)
for person in [12]:
	clist=[]
	for day in AllDays:
		vlist=[]
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if day in Sat :
			if day +1 in AllDays :
				v=sc3.And(~sc3.GetShiftVar(person ,day+0,'Y'),~sc3.GetShiftVar(person ,day+1,'Y'))
				vlist.append(v)
		if len(vlist) >= 1:
			clist.append(sc3.Or(vlist))
	sc3.AddSoft(sc3.SeqError(0,0,3, clist),'13_1',1)