Hi,

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
212
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).

link

answered 03 Nov '10, 22:29

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
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.

http://www.mail-archive.com/help-glpk@gnu.org/msg02672.html

link

answered 24 Aug '10, 12:37

larrydag%201's gravatar image

larrydag 1 ♦
3.2k51326
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 :)

link

answered 03 Nov '10, 08:02

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
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

By RSS:

Answers

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

Tags:

×190

Asked: 20 Aug '10, 16:12

Seen: 1,771 times

Last updated: 03 Nov '10, 22:29

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