Crew scheduling/rostering problem, Some questions
- From: bilalsinger@xxxxxxxxx
- Date: Wed, 9 Apr 2008 03:38:22 -0700 (PDT)
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
.
- Prev by Date: Re: Algorithm for inserting numbers in a list?
- Next by Date: Re: Algorithm for inserting numbers in a list?
- Previous by thread: Automatic text tagging
- Next by thread: find all directed paths between a source and destination
- Index(es):
Relevant Pages
|
