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 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
