3.7.158. Multi-site employee scheduling with calendar constraints

modelling: multi-site employee scheduling with calendar constraints An international software company located in France and Germany has offices in Paris, Lyon and Marseille as well as in Berlin, Hamburg and Munich. Four types of activities are performed by its employees, namely (1) software development, (2) software deployment, (3) software training courses, and (4) business trips. Software developments tasks and training courses are performed within company's offices, while software deployment and business trips are done at customer's sites. Scheduling activities to employees is typically done on a yearly basis from Jan. 1 of current year to Apr. 30 of next year. Considering the first four months of the next year is done in order to absorb eventual overload and to anticipate the effect of Christmas and winter vacations. Without loss of generality we assume that our planning period is from Jan. 1, 2010 to Apr. 30, 2011. The level of granularity is the individual day. Since employees are located on different home sites, one has to consider the following holidays:

  • Public holidays that do not fall on a weekend (i.e., a Saturday or a Sunday) are listed below.

    • France: Jan. 1, Apr. 5, May 13, May 24, July 14, Nov. 1, Nov. 11 in 2010, and Apr. 25 in 2011.

    • Germany: Jan. 1, Apr. 2, Apr. 5, May 13, May 24 in 2010, and Apr. 22, Apr. 25 in 2011.

  • In the context of Germany, regional holidays related to the federal state where a home site is situated. For Munich (Bavaria) we have the following additional days off, that all fall outside a weekend: Jan. 6, June 3, Nov. 1 in 2010 and Jan. 6 in 2011.

  • Each home site is closed for a known fixed period of nine consecutive days that is located during summer school vacations. In addition each employee has five consecutive days off, a priori known, crossing winter school vacation. Summer and winter school vacations are linked to the country and the area where a home site is located. Regarding school vacations, France is partitioned in three zones, while Germany is divided in 16 federal states. Paris, Lyon and Marseille are located in distinct zones, while Berlin, Hamburg and Munich are situated in different federal states. Summer vacations periods are:

    • From July 3, 2010 to Sept. 1, 2010 in Paris, Lyon and Marseille.

    • From July 7, 2010 to Aug. 21, 2010 in Berlin.

    • From July 8, 2010 to Aug. 18, 2010 in Hamburg.

    • From Aug. 2, 2010 to Sept. 13, 2010 in Munich.

    Winter vacations periods are:

    • From Feb. 20, 2010 to Mar. 7, 2010 and from Feb. 13, 2011 to Feb. 27, 2011 in Paris.

    • From Feb. 14, 2010 to Feb. 28, 2010 and from Feb. 27, 2011 to Mar. 13, 2011 in Lyon.

    • From Feb. 7, 2010 to Feb. 21, 2010 and from Feb. 20 2011 to Mar. 7, 2011 in Marseille.

    • From Feb. 1, 2010 to Feb. 6, 2010 and from Jan. 31, 2011 to Feb. 5, 2011 in Berlin.

    • Jan. 29, 2010 and Jan. 31, 2011 in Hamburg.

    • From Feb. 15, 2010 to Feb. 20, 2010 and from Mar. 7, 2011 to Mar. 11, 2011 in Munich.

The goal is to schedule a given set of known tasks to employees in such a way that each employee has 30 days off in 2010, some of them corresponding to the mandatory public and regional holidays depending of the home site of an employee. Each task has:

  1. A type (i.e., software development, software deployment, software training courses, and business trips).

  2. An earliest start in 2010.

  3. A latest end in 2010. Tasks which cannot be allocated with respect to their 2010 time windows must be scheduled in early 2011, i.e., from Jan. 1, 2011 to Apr. 30, 2011.

  4. A duration.

  5. A number of required employees.

  6. A list of home sites qualified to perform the task.

Business trips, training courses and software deployment cannot be interrupted at all, while software development tasks cannot be interrupted by summer vacation. Business trips have to start on a Monday or a Tuesday since the general company policy is to prevent people staying abroad during weekends. Each task has to be allocated to employees, which are all based on the same home site, in such a way that the same set of employees takes care of the task from its start towards its completion. Each employee has:

  1. A home site (i.e., Paris, Lyon, Marseille, Berlin, Hamburg or Munich).

  2. A five days period of winter 2010 vacation.

  3. A five days period of winter 2011 vacation.

  4. A list of task types (i.e., software development, software deployment, software training courses, business trips) it can handle.

Finally, each home site has a nine days period of summer 2010 vacation where the home site is closed down.