Databases
StackOverflow2013
Postsdbo
POOn-call night scheduling algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOn-call night scheduling algorithm
    primarykey
    data
    text
    <p>I work in a residence hall at my college as an RA, and each night we need two RAs to be on call (able to respond to incidents and emergencies). Each month, RAs submit the nights they cannot be on call (due to a conflict of some sort). There are both male and female RAs. I am trying to come up with an effective algorithm to find the best arrangement of on-call nights for any particular month that satisfies the following requirements:</p> <ul> <li>No RA is scheduled for a night he or she has listed as unavailable.</li> <li>No RA is on-call more than a specified number of nights per month.</li> <li>No RA is on-call twice within any given three-night span.</li> <li>Each night has exactly two RAs on call.</li> <li>Each night has, if possible, one male and one female RA on call.</li> </ul> <p>Doing some research, I've found that this is a resource-constrained scheduling problem, and it is considered NP-complete. Therefore, I don't need to find the optimal solution, just any solution that works.</p> <p>So far, I've considered the following approaches:</p> <ul> <li>A simple 2d array of RAs x nights where each cell holds a boolean value answering whether or not that RA is on call for that night. I could hold the RAs in two priority queues (one male and one female) sorted by how many nights they've had so far, how long it has been since their last on call night, and simply iterate through the nights, selecting one RA from each queue, and then backtracking if I hit a dead end where nobody can work a particular night.</li> <li>A tripartite graph with male RAs on one side, female RAs on another, and nights on the last side. In the solution, each night would have an edge to one male and one female RA. I would start with all edges connected and then remove edges until a solution is found.</li> <li>Some sort of genetic approach using the above structures.</li> </ul> <p>What sort of approach do you suggest I use? Is there something I haven't thought of that might work better? This is not a homework question; I am trying to develop a website that would make it easy for my staff and possibly other staffs on campus to submit date preferences and then generate a schedule that works for everybody.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USKevin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload