I am considering having someone help me make a program to do the scheduling for the residents who work in the ER at my hospital. The program would have to be able to formulate a shift schedule grid based on certain set criteria (ie total number of shifts, can’t work more than 6 days in a row, must have at least 24 hours between shifts, no working monday and tuesday nights) as well as being able to input personal preferences (ie days off requested, prefer nights, prefer blocks of shifts).
Does such a program exist already? Where can I get one? If not…
What would be the best programming language and where should I go for help? Local collegiate computer science department? Commercial programmer? Anyone on the SDMB interested in helping out for a free or for a negotiable fee?
First, be very clear what you are after. Are you looking for a program that will take a list of constraints and provide a schedule that meets them, or are you looking for a calendar that will keep track of a given schedule and alert you if a problem arises. The first is a much harder problem than the second, and the implementation may depend on the kind of constraints that you care about.
If you are lucky, there’s already some software out there that can be used or modified. I took a quick look at sourceforge.net, but didn’t see anything that popped out at me as being a good solution, but I may have missed something, or there might be a commercial solution. Googling for “shift schedule software” brought up some possibilities.
I’d explore those options before I went looking for a custom job. A good custom program will likely be orders of magnitude more expensive than using some off-the-shelf product.
If you don’t mind using MicroSquash products MS Access could do this with a not-too-extensive amount of VBA coding. A custom solution or one based on a commercial database software (like Oracle or PeopleSoft, who are now one in the same) is going to run you big bucks; probably more than it’s worth, but you could look into it. I don’t know if there are any dedicated freeware apps for scheduling, but you could try looking around/asking on Slashdot.
If it’s a small group of people, it may just be easier to lay it out in a spreadsheet and do it manually. I speak from experience; after setting up a couple of scheduling/time card apps in ToolBook for departments back when I was in college and dealing with all of the debugging, user input errors, and so forth, it just turned out not to be worth the effort.
I agree with this evaluation. On the surface this type of program seems fairly simple because our minds can think about several constraints at once, but the computer has to consider one at a time. The constraints, and constraint relationships, can get very complicated, very rapidly.
I worked on the development of a system similar to this once. The chief architect projected it would take 3 programmers about 3 months to finish. End the end, we had 5 programmers working over 6 months, and we still only had about 3/4 of code finished.
If you decide to go the programmer route, begin by having them develop pseudo-code for your system, that way you won’t have to re-write the software several times. If you can walk through the pseudo-code and agree the system does what you want it to do, then think about how long it will take to program.
One of the great challenges is HOW are you going to describe the constraints in “computer terms”?
Yes, I would like to be able to give a list of constraints and have the program produce a schedule grid, month by month. Although the other choice is appealing as well to provide a safety net to avoid mistakes.
It is a relatively small group of people; 25-28 residents in any given month. Although a majority of them would be people with many of the same preferences each month.
There are two residents who are in charge of the schedule each month and currently they are doing it by Excel spreadsheet. This takes up a good chunk of their free time. I was thinking that a program that would do this given a finite number of constraints would pay for itself in time saved over a short time, but it seems that it may be a pipe dream at this point.
If you know how to program and know what all the issues are for scheduling, you should be able to add macros to your excel sheets that will allow you to do what you want. So if you are willing to learn programming, then that would be my recommendation. There are books on just this subject.
Other than that, it is my belief that any software which has attempted to do stuff like this has failed miserably just because adding in the options for inputting every possible kind of constraint becomes so difficult that essentially you end up needing to have people add macros and make the logic themselves.
“I can come in every Friday, except the third Friday of each month because I have to babysit my sister’s kids that day.” <- Things like that kill genericized software. Constraints are fine, but constraints with modifiers will get you.
With that many people it might be worth some kind of automation. On a very simple level it woudn’t be hard to implement in Excel or Access.
What I would envision for your system is a simple elimination schema. You’d have a “card” for each person, the card being a set of parameters on what days they can’t work. You “overlay” all cards, which gives you a set of people for each day who are available. You then have a straightforward routine that selects people available for each day (from most preferred day to least), in a quasi-random fashion based on a weighting system. Everytime somone is picked, you reduce their weight value so they are less likely to be picked for their next opportunity until all their “weight” is used up and they can’t be picked at all, so that people who haven’t yet been picked are are more likely to be selected next. If you want to let people express preferences for particular days or shifts then you have a weight factor for each day, giving them initial preference for a particular. Of course, this system won’t let you express compound requirements like “I either want to work Tuesday and Thursday OR Monday and Wednesday”; you’d have to manually fix those kinds of things, or else make the algorithm much more complicated.
I hope that explaination is clear. As for writing it into code, it’s straightforward but nontrivial in terms of the sorting operations. I agree with ccwaterback that if you elect to do this you should work it all out in pseudocode and then implement it in some fairly flexible language, as you are likely to need to make further changes. Python and the object-oriented approach actually lend themselves quite well to this, and you could dump the output to a text file, a spreadsheet, or an HTML-formatted document pretty easily. This is not a trivial undertaking, though, even for an experienced coder; if you have compound requirements as indicated above you are going to need a lot of different object methods which will quickly become convoluted; it’s a little like creating branch-pruning algorithms for chess solvers. Expect a single programmer to spend something like two or three months (part time) to come up with a functional basic engine and another month or two for a flexible and user-friendly interface and that’s assuming the programmer is familiar with hacking this type of application. There probably isn’t really a need for more than one coder on a project this small, unless you wanted to break up the interface and sorting work between two people.
It’s kind of a neat little problem for someone who has gotten beyond learning syntax and needs experience in writing actual code. You might try contacting a community or local college with a CIS or computer science department and seeing if they can’t work it into some kind of senior project, or if there aren’t some kids willing to put something together for low cost in exchange for experience. With this large a group, and as much of a headache as it sounds to do it manually, it’s worth looking into, anyway. Just don’t be under the impression that it’s going to be a weekend project.
I don’t see it as all that complex. One constraint would be “minimum amount of time between shifts”, and another could be “preferred amount of time between shifts”.
Sounds about right. But this next part:
I think it probably would be beyond the abilities of students to fashion a good system to handle this problem. Functional, maybe.
In thinking about it, the complexity can very quickly grow. For example, one element might be a “routine” variable. Some people strongly prefer to work as consistent a schedule as possible, coming in and leaving at the same time for each shift, and some people might not care so much.
All in all, a fascinating programming problem. It is an actual example of a programming problem that requires fairly involved logical elements. Those kind of projects are a programmer’s dream.
The problem that comes is that different people may have conflicting constraints which then require some kind of arbitration. For instance, let’s say Janice wants to work (Monday and Wednesday) OR (Thurdsay and Saturday). Joseph wants to work (Monday and Tuesday) OR (Wednesday and Thursday). Your near the end of filling your schedule and you only have open slots on Wednesday, Thursday, Saturday, and Tuesday. Joe can’t work Tuesday 'cause he also needs to work Monday, and Janice can work Wednesday for the same reason. Either of them could work Thursday and fulfill their requirements, but they can’t both work Thursday, so…a human being says, hey, somebody’s got to give, but an algorithm throws an exception (if properly designed) or spins off in a loop (if not). You could give the people with conditions priority for their days, but then that’s not really fair to others and won’t work if everybody has conditions. It can get ugly real quick unless you have some kind of presorting/pruning strategy to accomodate these complex conditionals, and this is non-trivial to say the list.
I totally agree, and that’s why it would be a great project for advanced students (or fledgling programmers with a good grasp of syntax and structure) to really cut their teeth on writing an appliation with tricky and nonintuitive challenges. It really is “pure” programming (as opposed to hacking CGI scripts or SQL queries) and borders on artificial intelligence in the sense of having to resolve an open form problem with incomplete solutions (though I don’t expect the application is going to start refusing to open the Pod Bay Doors or finding fallicious faults in the AE-35 unit.) Another approach might be to create simultaneous equations and run a Monte Carlo-type set of parameters to hunt for an appropriate or optimal solution.
It’s definitely beyond the means of your typical webpage designer, but I don’t think it’s too advanced for a senior-level comp sci student (or shouldn’t be anyway) or skilled amateur programmer. A fun little project for someone who has the time and interest, to be sure.
Stop, you’re making me drool. Everytime a conflict comes up, and there is a choice among equally imperfect shifts, whoever gets hosed has their “I’ve been hosed” counter incremented, and next time the first people eliminated are the ones with the higher “I’ve been hosed” counts.
Also, people are fickle, and their situations change, so no rule should be expected to be permanent. How elaborate should the rules be? Each user ranks all the shifts in order of preference? Nah, too cumbersome and unwieldy. And that wouldn’t handle conditional preferences. (Ala you’re Monday & Wednesday OR Tuesday & Thursday.) Users can select their ideal week, their second choice week, etcetera? But what about when Mom comes for a visit and you have to pick her up at the airport? She’s staying for a week, and your normal schedule is less than ideal for that week.
No, probably the ideal solution would be to churn out all possible schedules that meet all requirements, if not necessarily preferences. Each schedule would then contain a score of how many preferences were overridden. Then the user picks the one with the fewest overrides, or peruses a bunch of them and picks the best one. Or even better, while perusing, refine the possibilities by locking in some of the shifts and letting the system regenerate a new set of possible schedules based on the locked in shifts.
sigh
The most complex application I ever got to design was a dynamic rate chart system, allowing variable rows, columns, and cells. It was fun designing it, especially the data model, but the nightmare of the DBGrid control was a hell I never care to revisit.
Why is it that most programming jobs are incredibly straight-foward and boring? I guess it’s because most programs are written to solve repetitive tasks, which humans find immensely boring.
Another program I worked on similar to this system had an additional feature called a “process network”. The users wanted to say which processes were dependent on other processes, and which processes were independent of other processes, on a per process basis. This is all fine and dandy if they would define their network and leave it alone, but they wanted to change the dependencies at any time. I spent a lot of time explaining to them how they just defined a circular dependency and how their process flow would run forever without ending. But of course, my stupid program was supposed to know that process B depends on process A being complete ONLY IF process A had a certain type of image file associated with it. And so on …
Knocking out a program to solve USCDiver’s specific scheduling problem would be non-trivial but feasible (in programmer-months maybe). But I don’t think this is the way anyone would want to approach the problem. You’d want to solve a generalised scheduling problem with pretty open constraints.
Solving generalised scheduling is a nightmare. The company I work for develops and sells commercial packages that (attempt to) optimise various people/task-scheduling problems. Though it’s not my area I know that programmer-years of work have gone into these systems.
FWIW I would use a paper-glue-and-scissors***** approach to USCDiver’s problem. It’s much easier to solve a packing problem by hand/eye than to write a program to do it.
*****Maybe virtual paper-glue-and-scissors, that could be fun.
But the “I’ve been hosed” counter has to be weighted by each person’s “convenience profile” because Christians may refuse to work on Sunday, and Jews may refuse to work on Saturday, and so forth.
After reviewing all the dependencies in a system like this a while back, I arrived at the conclusion that the best way is to tell them when they’re hired: “We’ll do the best we can, but if you want to keep your job, you’ll work when you’re told to work.”
I think I can narrow my particular problem down mightily by giving you our very basic scheduling criteria (feel free to continue to discuss the generic issues to your heart’s content).
We work 12 hour shifts. There are 2 main shifts labelled A and C(7a-7p and 7p-7a) that have 4 residents each working. There is one ‘swing’ shift from 12n-12m that has two residents working (B). Each resident is given a “score” based on their level of training (0, 1, 2, or 3). At any one time A+B and B+C must equal 10 to have adequate experience working in the department. Residents with Scores of 0 and 1 work 18-19 shifts a month, Score 2 works 16-17 and Score 3 works 14-15 (obviously in any given month the number of residents is 3>2>1>0)
A typical day’s schedule might look like (with residents denoted by initials):
A(7a-7p): HW JE PU SH
B(12-12): CL JR
C(7p-7a): CR LR WL WO
There are governmental regulations on the number of shifts we can work in a row and the amount of time off we must have between shifts. We also have specific policies in our department (ie everyone works 2 weekends and gets 2 weekends off)
Residents are allowed to express preference for [ol]
[li]specific days off (ie “I want the 22-23rd to be one of my weekends off”)[/li][li]preference for working blocks or not (ie “I want to work 5 days in a row and have 3 days off” or “I prefer to work 2-3 in a row, have one day off then 2-3 in a row”)[/li][li]Day shift vs night shift vs swing[/li][/ol]
There is no Monday and Thursday or Wednesday and Friday stuff going on.
Hope this helps narrow the conversation somewhat for my purposes, but I encourage you to continue discussing the complexities of scheduling program nightmares.
I worked on specifying, designing and managing a similar system for a big industrial company. We we doing monthly work schedules for multiple groups of 20 to 250 workers.
It took 3 years and cost $2 million to bring the vendor’s product up from a v1.0 on-the-market product to real working ready-for-primetime software. But when it was done it worked great. The software company we bought it from has since been bought out, but here’s a URL http://www.kronos.com/ad-opt/. (No, I don’t have any connection to them now.)
As the others have said, scheduling with constraints and preferences sounds easy to a person, but as you discover when doing it by hand with even a few workers, it rapidly gets very, very hard.
We went through 3 other vendors who had existing systems that tried and failed at this. It’s easy to solve the problem when the constraints are loose. But as they get tighter, it takes very advanced computer science, not just hobby-level programing in Excel, to predict and avoid painting yourself into a corner.
USCDiver, Google “workforce management software”. This search will yeild many companies that have already invented the wheel you seek. I am personally familiar with the scheduling product of Global Management Technologies (www.gmtcorp.com). It will handle all of the tasks you mention, including all of the constraints, preferences and issues mentioned in this thread. It’s very powerful software that can schedule thousands of employees. The drawback is, of course, it ain’t cheap. There are lots of companies doing this kind of stuff. If you can’t find an affordable off-the-shelf package that suits your needs, at least you can get some ideas for features to include in a home grown solution.
USCDiver, did you ever find or build your scheduler? I got bored and played around in Filemaker for a few minutes and have a simple 2-file solution that fills slots with people who are available for those slots, using those not previously assigned if any exist, then those only assigned to one other slot, then whoever is available, all keyed off times that each individual is available to be scheduled.
If you’d like I’ll modify it to match your specs above.
