sci.op-research

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