We help IT Professionals succeed at work.

# Shift scheduling: Does it have to be np hard?

on
674 Views
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

## View Solution Only

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)

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.

###### 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

Deciding to stick with EE.

Mohamed Asif

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

Carl Webster
CTP, Sr Infrastructure Consultant
###### 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

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

• Troubleshooting
• Research
• Professional Opinions
Unlock the solution to this question.

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.