On-call night scheduling algorithm -

i work in residence hall @ college ra, , each night need 2 ras on call (able respond incidents , emergencies). each month, ras submit nights cannot on call (due conflict of sort). there both male , female ras. trying come effective algorithm find best arrangement of on-call nights particular month satisfies following requirements:

• no ra scheduled night or has listed unavailable.
• no ra on-call more specified number of nights per month.
• no ra on-call twice within given three-night span.
• each night has 2 ras on call.
• each night has, if possible, 1 male , 1 female ra on call.

doing research, i've found resource-constrained scheduling problem, , considered np-complete. therefore, don't need find optimal solution, solution works.

so far, i've considered following approaches:

• a simple 2d array of ras x nights each cell holds boolean value answering whether or not ra on call night. hold ras in 2 priority queues (one male , 1 female) sorted how many nights they've had far, how long has been since last on call night, , iterate through nights, selecting 1 ra each queue, , backtracking if hit dead end nobody can work particular night.
• a tripartite graph male ras on 1 side, female ras on another, , nights on last side. in solution, each night have edge 1 male , 1 female ra. start edges connected , remove edges until solution found.
• some sort of genetic approach using above structures.

what sort of approach suggest use? there haven't thought of might work better? not homework question; trying develop website make easy staff , possibly other staffs on campus submit date preferences , generate schedule works everybody.

i recommend 2d array, instead of iterating through nights in order first last iterate through nights in order least constrained - in other words, start night has fewest ras available due conflicts. heuristic apply tripartite graph if go approach - it's question of domain representation, algorithm isn't affected @ point.

the question when reach last few nights , find no ras available. @ point local search attempt reach viable solution, example you've selected ra1 nighta ra2 , ra3 available on night, select ra2 or ra3 see if frees ra1 night on did not have available ra.