Python Forum

Hello!
I had started this project thinking it was relatively straight-forward. However, I hit several road-blocks along the way and the program kept getting longer, and kept giving unexpected results.

Purpose of the program:
To make duty rosters for night duties (in, say, hospitals)

Specifications:

Number of duties
1. Number of residents posted in a night duty is 1 or 2
2. All weekends have 2 residents on duty
3. All holidays other than weekends have two residents on duty
4. There may be optional days apart from weekends and holidays on which 2 residents are required on a duty
5. No resident should get more than 2 weekend duties in a month ideally
6. If a resident has to be given more than 2 weekend duties in a month, reduce 1 weekday duty for each extra weekend duty
7. Allow for a method to let 1 or 2 residents select preferred days to (not) work
8. If required number of duties is less than total number of duties the residents posted can do, reduce duties for S1 types --> S2 --> S3...

Types of residents:
Residents who can be on duty are divided into various types
1. S1: Can do up to 6 duties in a month
2. S2: Can do up to 5 duties in a month
3. S3: Can do up to 4 duties in a month
4. S4: Can do up to 3 duties in a month
5. S5: Can do up to 2 duties in a month
6. S6: Can do up to 2 duties in a month
7. S1 and S6 cannot do any duty alone
8. S1 and S2 cannot be posted together on the same day

Number of residents:
The number of residents ranges from 15-20 each month.
I kinda hit a wall with this as well; i do not know the minimum number of residents that will be required to satisfy all the above criteria.

Here is the code i have written:

#import libs
import calendar
import openpyxl
import random
import datetime
from itertools import repeat

n = 10
wb = openpyxl.load_workbook('r3.0.xlsx')
sheet = wb['Sheet1']
year = int(sheet.cell(1,10).value)
month = int(sheet.cell(1,9).value)

big_list_count = {}
completion = {}
resident_info = {}
resident_duty_info = {}
sem_dict = {1:0,2:0,3:0,4:0,5:0,6:0}


all_days = [day for day in range(1,calendar.monthrange(year,month)[1]+1)]
dates = [x for x in range(3,len(all_days)+3)]

#updating the dates in excel sheet
for row in range (3,len(all_days)+3):
	sheet.cell(row,1).value = all_days[row-3]
weekends = []
#getting weekends from calendar
for date in range (1, len(all_days)+1):
	if datetime.date(year, month, date).weekday() in [5,6]:
		weekends.append(date)
		dates.append(date+2)

#For debugging
holidays = [1,2,3]
optional_cover_duties = [4,5]
for date in holidays+optional_cover_duties:
	dates.append(date+2)

#contains each residents name max duty number of times
big_list = []

#max number of duties in a month that can be done by all residents
duties = 0
#actual number of duties in a month
num_duties = 0
#the minimum number of duties (6th and 5th sem get this)
duty_constant = 0
#final number of duties per sem got by adding constant to the sem value
add_to_constant = {6:0, 5:0, 4:1, 3:2, 2:3, 1:4}
#Keeps track of how many ppl are assigned duty on a particular day
duties_day_dict = {}

def initial_values():
	global big_list_count, duty_constant, sem_dict, duties, completion, num_duties ,resident_info, resident_duty_info, all_days, dates, weekends, holidays, optional_cover_duties, big_list
	duties = 0
	sem_dict = {1:0,2:0,3:0,4:0,5:0,6:0}
	num_duties = 0
	big_list_count = {}
	resident_info = {}
	resident_duty_info = {}
	all_days = [day for day in range(1,calendar.monthrange(year,month)[1]+1)]
	dates = [x for x in range(3,len(all_days)+3)]	
	#list of weekends got from calendar
	for row in range (3,len(all_days)+3):
		sheet.cell(row,1).value = all_days[row-3]
	weekends = []
	for date in range (1, len(all_days)+1):
		if datetime.date(year, month, date).weekday() in [5,6]:
			weekends.append(date)
			dates.append(date+2)
	holidays = [1,2,3]
	optional_cover_duties = [4,5]
	for date in holidays+optional_cover_duties:
		dates.append(date+2)
	big_list = []
	duty_constant = 0

def get_resident_info(sheet):
#Get info from the excel sheet
	global resident_info
	trial = 20
	row, column = 3, 6
	while trial > 0:
		name, sem = sheet.cell(row,column).value, sheet.cell(row,column+1).value
		if name == None:
			break
		else:
			resident_info[name] = sem
			row 	+= 1
			trial 	-= 1


def get_num_duties():
#How many duties are there?
	global all_days, holidays, weekends, optional_cover_duties, num_duties
	#Get number of days (p)	
	num_days = len(all_days)
	#Get number of weekends+holidays (q)
	hols_set = set(holidays)
	weekends_set = set(weekends)
	covers_set =set(optional_cover_duties)

	hols = len(weekends_set.union(hols_set))
	#Get number of optional covered duties (r)
	covers = len(covers_set.difference(hols_set.union(weekends_set)))
		#make default all cover duties
	#Total number of duties = p+q+r
	num_duties = num_days+hols+covers
	#populate the duties dict

def pop_duties(list_, diff):
	for i in list_:
		for res in big_list:
			try:
				while diff > 0:
					if resident_info[res] == i:
						big_list.remove(res)
						print('Removed one duty. Current size,', len(big_list))
			except:
				pass


def sem_wise_duties():
#Which sem does how many duties?
	#Logic:
		#6th:n duties, 5th:n, 4th:n+1, 3rd:n+2, 2nd:n+3, 1st:n+4
		#Get the number of duties possible in a xn + y format
		#Equate it to number of duties and solve for n
	global num_duties, duty_constant, duties, sem_dict

	nums = [1,2,3,4,5]
	n=1
	while n<len(nums):
		duties = 0
		for res, sem in resident_info.items():
			duties += add_to_constant[sem]+n
			sem_dict[sem] += 1
		if duties >= num_duties:
			duty_constant = n
			break
		else:
			n+=1

#Decrease duties if too many
	diff = duties - num_duties
	if diff > sem_dict[1]+sem_dict[2]+sem_dict[3]:
		pop_duties([1,2,3], diff)
	if diff > sem_dict[1]+sem_dict[2] and diff < sem_dict[1]+sem_dict[2]+sem_dict[3]:
		pop_duties([1,2], diff)
	if diff > sem_dict[1] and diff < sem_dict[1]+sem_dict[2]:
		pop_duties([1], diff)
	if diff < sem_dict[1]:
		pop_duties([1], diff)		

def update_excel_max_duties():
	row, column = 3, 8
	while sheet.cell(row, column-1).value != None:
		sheet.cell(row,column).value = duty_constant + add_to_constant[sheet.cell(row, column-1).value]
		#Make a list with each resident's name (number of duties) times
		big_list.extend(repeat(sheet.cell(row, column-2).value,sheet.cell(row,column).value))
		row+=1
		wb.save('r3.0.xlsx')

def adder_remover(res, date):
	global dates, big_list
	dates.remove(date)
	big_list.remove(res)

def searcher(res, date):
	#defining a dynamic search field two rows on either side of the random date
	search_field = [sheet.cell(date-1,2).value, sheet.cell(date-2,2).value, sheet.cell(date+1,2).value,sheet.cell(date+2,2).value,
					sheet.cell(date-1,3).value, sheet.cell(date-2,3).value, sheet.cell(date+1,3).value,sheet.cell(date+2,3).value,
					sheet.cell(date,2).value, sheet.cell(date,3).value]
	if res in search_field:
		return 0
	else:
		return 1

def decider(res, date):
#Rules
#=====
#1. Resident name should not appear in upto two rows above/below as either R1 or R2
#2. A resident in sem 1 can only appear as R2
#3. 5th and 6th sem always have R2 from [2,3,4]
#4. If more than 1 weekend duty, reduce number of duties by 1
#Others
	#5/6 sem res
		#keep as R1
	#1 sem res
		#keep as R2
	#any other sem res
		#keep as R1/R2
	sem = resident_info[res]
	x = searcher(res, date)
	y = check_weekends(res, date)
	print ('x:', x, 'y', y)
	if x == y == 1:
		if not res in resident_duty_info:
			resident_duty_info[res]=[]
		if sem in [5,6]:
			if sheet.cell(date,2).value == None:
				sheet.cell(date,2).value = res
				resident_duty_info[res].append(date)
				adder_remover(res, date)
				wb.save('r3.0.xlsx')
				return
		elif sem == 1:
			if sheet.cell(date,3).value == None:
				sheet.cell(date,3).value = res
				resident_duty_info[res].append(date)
				adder_remover(res, date)
				wb.save('r3.0.xlsx')
				return
		else:
			if sheet.cell(date,2).value == None:
				sheet.cell(date,2).value = res
				resident_duty_info[res].append(date)
				adder_remover(res, date)
				wb.save('r3.0.xlsx')
				return
			if sheet.cell(date,3).value == None:
				sheet.cell(date,3).value = res
				resident_duty_info[res].append(date)
				adder_remover(res, date)
				wb.save('r3.0.xlsx')
				return

def add_duties():
	global all_days		
	print('Dates:', len(dates), 'Big list:', len(big_list))
#Get the last row
#From this list, randomly select a resident and put name in the columns following predefined rules
	run = 100
	while run > 0:
		res = random.choice(big_list)
		date = random.choice(dates)
		decider(res,date)		
		run-=1
	check_completion()

def clear_field():
	global n

	while n>0:
		for row in range (3, len(all_days)+3):
			sheet.cell(row,2).value = None
			sheet.cell(row,3).value = None
		initial_steps()

def check_weekends(res, date):
	if date in weekends:
		we = []
		for d in resident_duty_info:
			if d in weekends:
				we.append(d)
				if len(we) > 2:
					return 0
				else:
					big_list.remove(res)
					return 1
			else:
				return 1
	else:
		return 1

def check_completion():
	global completion, resident_info
	for res, val in resident_info.items():
		completion[res]=0
	completion2 = []
	completion3 = []
	for row in range (3, len(all_days)+3):
		completion2.append(sheet.cell(row,2).value)
		completion3.append(sheet.cell(row,3).value)

	for res in completion2:
		if res != None:
			completion[res]+=1
	for res in completion3:
		if res != None:
			completion[res]+=1

    #checking number of duties each resident got
	for row in range(3,17):
		if sheet.cell(row,6).value != None:
			sheet.cell(row,9).value = completion[sheet.cell(row,6).value]
	wb.save('r3.0.xlsx')

	if None in completion2:
		clear_field()
		# pass
	else:
		print('Successfully done!')
		pass

def initial_steps():
	initial_values()
	get_resident_info(sheet)
	get_num_duties()
	sem_wise_duties()
	update_excel_max_duties()
	add_duties()


if __name__ == '__main__':
	initial_steps()

I know it is a pain to read this code...it is poorly written. But i would greatly appreciate if someone can guide me forward in this mess...Thank u.

Is there a way to calculate the boundary conditions for this problem? Like the minimum number of residents that need to be posted?

It looks like the duties are interchangable, but residents are not.
I see a contradiction in the search for the minimum residents required
on the one hand and the specific naming of S1, S2,... that looks like they are
individuals and not in a pool you can draw from.

Paul

Thank you for the reply Paul :)
S1, S2 etc are classes, each of which contains a variable number of residents. Duties can be allotted to any resident as long as the allotment does not violate the requirements.

OK, i am not going to be able to write out a solution for you.
But i have seen many attemps, more or less succesful,
to develop a scheduling or roster system.
Especially in the eighties when AI was the "new solution" for everything.
Python is listed as a language for AI, next to LISP and PROLOG etc.
The first thing is to find a suitable algorithm/method that will do the job for you.
Then writing the program is piece of cake.
You may find ideas while searching for e.g.
LISP + AI + Scheduling
Especially: "project management resource scheduling"
School/staff roster scheduling.

PS: In fact 90% of the time, "scheduling" is the wrong expression,
because that focusses on the time component.
It is 'resource allocation'.

Hope this helps.
Paul