scheduling/ matching/ preference algorithm -

i have problem not sure algorithm belongs to.

we trying make scheduling system users can choose time preferences , grouped classes preferred time.

let have 100 users. users have time preferences. want divide them 4 -> 6 class 20 -> 25 students in each class. question is

• how schedule them class time preferred least amount of classes used ?

(another constraint factor have amount of teachers have , maximum hours week can teach. want able have makeup class. eg: students miss class week can reschedule next week. )

one way go multi-objective optimization problem find solution satisfies 1 objective, , use local search attempt satisfy remaining constraints.

for example, if ignore constraint minimize number of classes used, can treat variant on stable marriage problem (or weighted bipartite graph matching problem) - has nice property can solved in polynomial time. variant on problem similar "hospitals/residents" problem (assigning many residents few hospitals based on preference).

this leave several classes few students in them, next perform local search satisfy "minimize number of classes" constraint (if formulated stable marriage algorithm correctly should have satisfied "no class exceeds 25 students" constraint) - there have 2 options:

1. sort classes fewest students , close classes fewest students, reassigning evicted students remaining classes

2. continue take students' preferences account , sort classes least-preferred most-preferred (so if have 5 students in class assigned weight of 10 first close class 10 students assigned weight of 2).

you perform local search satisfy teachers' hours constraints - perform "teachers can't teach more x hours" search after perform "minimize number of classes" search, since latter optimization make easier perform former optimization.

if resulting algorithm fast enough can randomize , run few dozen times, saving best result. example, rather closing class fewest students first, randomly select class close (weight selection selects smallest class - completely random search won't perform well)

it's possible you'll find 1 of constraints causing lot of conflicts, e.g. when satisfying teachers' hours constraint discover you're having rearrange large percentage of students. if occurs change constraint ordering, satisfying teachers' hours done on second or first pass rather on third pass.

the makeup-class-constraint might belong @ top of constraint list (even though it's got low priority), depending on specifications. example, may have requirement makeup class occur before other class (so e.g. student class on tuesday can have makeup class on monday , caught prior regular class); though makeup class constraint has low priority, has tightest requirements, , needs ordered first.