We help IT Professionals succeed at work.

Shift scheduling: Does it have to be np hard?

mankowitz
mankowitz asked
on
674 Views
Last Modified: 2008-04-24
What is a good way to schedule shifts for various workers? For example, suppose I have 5 workers and 60 consecutive shifts to fill (each is a 12 hour shift in a 30 day month). I would like to have several constraints, such as certain workers will want certain days off. A person can not work two adjacent shifts (24 hours in a row). A person should not work more than 5 days in a row.

Now, one way to do this is compute all the possibilities for the 60 shifts and rank the schedules by goodness of fit. The only problem is that I would have to generate 5^60 schedules (=8.67361738 × 10^41) in order to make sure I've checked everything. Even if it took only 1ms to check each scheduke, the age of the universe is nothing compared to how long this will take. Is there any way to shorten this?
Comment
Watch Question

ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Commented:
There are many techniques, domain pruning, heuristics and so on to solve NP-hard problems, its all part of Constraint Logic Programming (CLP). If you don't want to program everything from scratch, you can use some CLP system (like ECLiPSe: http://eclipse.crosscoreop.com/index.html).

There you usually define your problem as set of variables (shifts in your case), their domains (workers) and constraints that must be met (consecutive shifts must not be done by the same worker, Joe doesn't work on Sundays, etc.).

Then you press the button and let the magic happen :-). Of course the success depends on size of the problem (it is still NP-hard) and suggesting good heuristics to the system also helps. On the above mentioned page are also examples, maybe JobShop (http://eclipse.crosscoreop.com/examples/jobshop.html) fits your problem.

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.