sci.op-research

On 9 apr, 11:57, "Bilal" wrote:
> 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

Hi,
I'm only a student Operational Research at Ghent University,
but I'll give it a try:
Before you implement your heuristics/algorithm, make sure that the
complexity of the problem isn't too high.
Try to 'evaluate' the number of possibilities.
If these are exponential, I would opt for a meta-heuristic instead of
exact procedures.
That would save you time in algorithm design.

And second, there is definitely literature for this problem:
you should look at nurse rostering in academic journals (EJOR).

And most importantly, do you need an optimal or a near-optimal
solution?