Crew scheduling/rostering problem, Some questions

Crew scheduling/rostering problem, Some questions

Post by bilalsinge » Thu, 10 Apr 2008 19:37:39


Dear everybody,

I am currently doing an internship at a public transport company. I
have a couple of questions and I wonder if you could help me with
these questions. In the internship, my task is to solve a crew
scheduling/rostering problem for one specific day.

The characteristics of the problem are as follows:
There are a number of activities with start/end-time and start/end-
location and qualifications needed for executing this activity.

There are a number of specific employees each having a number of
qualifications and having a time-window in which this employee can
work.

There are a number of restrictions concerning shift length, breaks,
qualifications and availability of the employees.

The goal is to create a number of shifts that cover all activities and
that can be executed by the given employees.

In the literature I found concerning this subject I usually find a
decomposition of this problem in two parts:
1) Creating a number of anonymous shifts that covers all activities
and that takes into account the restrictions concerning shift duration
and breaks.
2) Assigning these shifts to the available employees.

This decomposition is not possible in my problem because the employees
all have certain qualifications and time-windows which restrict the
possible shifts that can be assigned to this employee. So the
anonymous shifts that are selected in step 1 will usually not be able
to be assigned to the given employees. The shifts created therefore
have to be personalized and take into account the specific
characteristics of the employees.

I could not find literature that solves this type of problem. I
believe that this problem is a combined crew scheduling and crew
rostering problem.

I came up with an idea/heuristic to tackle this problem:
1) For every employee generate all possible shifts that can be
executed by this employee looking at all constraints.
2) Solve a set partitioning/covering problem (using Integer
Programming) that demands that each employee can only execute one of
his possible shifts and that each activity has to be executed. It is
also possible to add costs to each possible shift.

It is important to indicate that the problems in this company are not
of huge size so the number of possible shifts for each employee will
not be that big.

I have a couple of questions regarding this problem:
1) What are the possible solutions for solving this problem? And can
you refer me to an article where I can read more about this solution.
2) Are there other types of solutions for this type of combined
scheduling/rostering problems that do not include a set partitioning
approach?
3) Could you indicate whether my approach for solving this problem is
a correct one and give some enhancement tips for this heuristic.

Thank you very much for all your ideas and input.

Kind regards,

Bilal Singer
Business Mathematics and Informatics
Vrije Universiteit Amsterdam
 
 
 

Crew scheduling/rostering problem, Some questions

Post by mekl » Fri, 11 Apr 2008 09:18:11

ere is an example of "crew scheduling problem" in Alice ML:

http://www.ps.uni-sb.de/alice/manual/cptutorial/node56.html

Solving it in eclipse:

/*
Crew Allocation
A small air-line has to assign their 20 flight attendants to 10 flights.
Each flight has to be accompanied by a certain number of cabin crew
that has to meet a couple of constraints. First, to serve the needs of
international clients the cabin crew has to be able to speak German,
Spanish, and French. Further, a minimal number of stewardesses (resp.
stewards) have to attend a flight. Finally, every cabin crew member
has two flights off after an attended flight. (see given flights and
attendants data below).
*/

:- lib(ic).
:- lib(ic_sets).
:- import subset/2 from ic_sets.

flights(
[flight( 1,crew:4,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 2,crew:5,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 3,crew:5,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 4,crew:6,stewards:2,stewardesses:2,french:1,spanish:1,german:1),
flight( 5,crew:7,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
flight( 6,crew:4,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 7,crew:5,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 8,crew:6,stewards:1,stewardesses:1,french:1,spanish:1,german:1),
flight( 9,crew:6,stewards:2,stewardesses:2,french:1,spanish:1,german:1),
flight(10,crew:7,stewards:3,stewardesses:3,french:1,spanish:1,german:1)]
).

attendants(
stewards:[tom,david,jeremy,ron,joe,bill,fred,bob,mario,ed],
stewardesses:[carol,janet,tracy,marilyn,carolyn,cathy,inez,jean,heather,juliet],
french:[inez,bill,jean,juliet],
german:[tom,jeremy,mario,cathy,juliet],
spanish:[bill,fred,joe,mario,marilyn,inez,heather]
).

crew :-
attendants( stewards:Stewards,
stewardesses:Stewardesses,
french:French,
german:German,
spanish:Spanish),

append(Stewards,Stewardesses,Attendants),
length(Stewards,Nmales),
length(Stewardesses,Nfemales),
Nattendants is Nmales + Nfemales,

% map all symbolic sets to integer sets
( foreach(A,Attendants), count(I,1,Nattendants),
foreach(I,SetAttendants),
fromto(FrenchSet,FrIn,FrOut,[]),
fromto(GermanSet,GrIn,GrOut,[]),
fromto(SpanishSet,SpIn,SpOut,[]),
param(French,German,Spanish)
do
(member(A,French) -> FrIn = [I|FrOut] ; FrOut=FrIn ),
(member(A,German) -> GrIn = [I|GrOut] ; GrOut=GrIn ),
(member(A,Spanish) -> SpIn = [I|SpOut] ; SpOut=SpIn )
),

StartFemales is Nmales + 1,
( for(I,1,Nmales), foreach(I,SetMales) do true ),
( for(I,StartFemales,Nattendants), foreach(I,SetFemales) do true ),

flights(Flights),

( foreach(F,Flights),
foreach(Crew,Crews),
param(SetAttendants,SetMales,SetFemales,FrenchSet,GermanSet,SpanishSet)
do
F=flight(_,crew:C,stewards:Nwards,stewardesses:Ndesses,french:NFr,spanish:NSp,german:NGr),
Crew subset SetAttendants,
#(Crew,C),
#(Crew /\ SetMales,Cmales), Cmales #>= Nwards,
#(Crew /\ SetFemales,Cfemales), Cfemales #>= Ndesses,
#(Crew /\ FrenchSet,CFr), CFr #>= NFr,
#(Crew /\ GermanSet,CGr), CGr #>= NGr,
#(Crew /\ SpanishSet,CSp), CSp #>= NSp
),

Crews = [Crew1,Crew2|_RestCrews], % in case of circular assignments assure
append(Crews,[Crew1,Crew2]