I'm facing a shift assignment problem for a big company, and, although I am quite experienced on this discipline, I'd like to know if someone could give me references and papers about OR applied to this kind of problem.

In my personal experience, I've attacked those kind of problems by using mainly column generation and Constraint Programming, with some little ammount of Local Search, but I'd like to know about another ways to face that problem...

Thanks in advance.

asked 20 Aug '10, 16:12

Javier%20Lafuente's gravatar image

Javier Lafuente
accept rate: 0%

The shift scheduling models I've seen have tended to be fairly straightforward LP or MILP models. (Crew scheduling is a different beast, since it often is fraught with side constraints.) If the set of possible shifts is small, they can be enumerated up front. If it is large, column generation is in order (and IMHO is reminiscent of column generation in 1-D cutting stock problems). I might be tempted to solve the master problem as an LP or MILP but use CP to generate possible shifts (using dual prices from the master to prioritize coverage in new shifts).


answered 03 Nov '10, 22:29

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

I would love to see an example Paul. Do you have anything written online?

(04 Nov '10, 12:51) larrydag 1 ♦

No, I haven't put anything related online anywhere. Were you thinking of an LP/MILP formulation, or specifically something with CP as the column generator. (Using CP as the column generator was a shot from the hip -- I haven't tried it yet for a shift scheduling model, although I've used it for a team formation model.)

(04 Nov '10, 13:22) Paul Rubin ♦♦

Shift assignment is essentially a knapsack or assignment problem. The primary constraints are allocating crew to time slots and satisfying demand of operations. Most of the the time the objective is to minimize cost of labor. Those are the basic elements and a lot could be built given that foundation. I developed a simple example for GLPK's example library.



answered 24 Aug '10, 12:37

larrydag%201's gravatar image

larrydag 1 ♦
accept rate: 9%

I made blog about the design choices I faced when implementing nurse rostering as an example in Drools Planner. I 've used tabu search and simulated annealing to tame it. The source code is available under the business friendly open source apache software license, so feel free to copy :)


answered 03 Nov '10, 08:02

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
accept rate: 6%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 20 Aug '10, 16:12

Seen: 1,830 times

Last updated: 03 Nov '10, 22:29

OR-Exchange! Your site for questions, answers, and announcements about operations research.