Shift generation is the process of determining the shift structure, along with the tasks to be carried out in particular shifts and the competences required for different shifts. The General Task-based Shift Generation Problem (GTSGP) is to create anonymous shifts and assign tasks to these shifts so that employees can be assigned to the shifts. The targeted tasks must be completed within a given time window. Tasks may have precedence constraints and transition times between tasks are considered. The goal is to maximize the number of shifts employees are able to execute.

The problem was introduced in [1] K. Nurmi, N. Kyngäs and J. Kyngäs, "Workforce Optimization: the General Task-based Shift Generation Problem", IAENG International Journal of Applied Mathematics, Vol. 49(4), pp. 393-400, 2019.

The mathematical formulation of the problem is given in [2] N. Kyngäs, K. Nurmi and D. Goossens, The General Task-based Shift Generation Problem: Formulation and Benchmarks”, in Proc of the 9th Multidisciplinary Int. Scheduling Conf.: Theory and Applications (MISTA), Ningbo, China, 2019.

The General Task-based Shift Generation Problem includes the following assumptions, constraints and goal:

Assumptions
(B1) Each task will be assigned to a shift
(B2) Preemption of tasks is not allowed
(B3) Each task is processed only once without interruption
(B4) Each employee can execute only one task at a time

Hard constraints
(H1) The tasks in the shift do not overlap in time (overlap)
(H2) Some tasks may have shift-local precedence constraints, that is, a task may not be executed after some other tasks in the same shift (precedence
(H3) Each shift can be executed (C1-C4 hold) by one or more employees (shift)
(H4) Each shift can be assigned to an employee s.t. all shifts are assigned to someone and no employee is assigned to multiple shifts (combination)

Goal
(G1) Maximize the sum of number of feasible (shift, employee) pairs over all pairs

Criteria (note, that an employee can be assigned to a shift only if the following criteria hold)
(C1) He/she possesses all the skills indicated by the task types of the tasks assigned to the shift(skill)
(C2) The total working time of the tasks in the shift is within his/her time limits for the working day(working time)
(C3) He/she is available to execute all the tasks in the shift(availability)
(C4) He/she has enough transition time to move between the tasks in the shifts(transition time)

The GTSGP can also include for example the following soft constraints (not used in the benchmark instances):

Soft constraints
(S1) Shifts of less than k1 and over k2 timeslots in length must be minimized
(S2) The average shift length should be as close to k3 timeslots as possible
(S3) Shifts that start between timeslots k4 and k5 must be minimized
(S4) Shifts that end between timeslots k6 and k7 must be minimized
(S5) Each shift should contain at most k8 switches from one task to another

Benchmark instances

The instances 00-14 are the test instances introduced in paper [2]. The instance EX is the sample instance used in the paper. The instance 8I was introduced in paper [1]. The transition matrices of this instance do not obey the triangle inequality. Note, that the best solution also gives an example of the starting time slots of the tasks. The first value of the number of feasible pairs corresponds to this setup. The value in the parentheses shows the number of feasible pairs when all the possible starting times of the tasks are considered.

Currently, we do not see a need for a formal XML or other structured representation for the problem or for the problem instances. Some representations are more appropriate for metaheuristics, some for constraint programming and some for other algorithms. We model the GTSGP using simple text file formats.

The Extended Shift Minimization Personnel Task Scheduling Problem (ESMPTSP) is a significantly simplified version of the General Task-based Shift Generation Problem (GTSGP) described earlier in this web page. Furthermore, ESMPTSP is a slight modification of the Shift Minimization Personnel Task Scheduling Problem (SMPTSP). The goal of the problem is to first minimize the number of employees required to perform the given set of tasks, and then for these employees to maximize the number of feasible (shift, employee) pairs.

The problem was introduced along with the mathematical formulation in [3] N. Kyngäs and K. Nurmi, “The Extended Shift Minimization Personnel Task Scheduling Problem”, Annals of Computer Science and Information Systems, Vol. 2?, 2021.

The Extended Shift Minimization Personnel Task Scheduling Problem includes the following assumptions, constraints and goal:

Assumptions
(B1) Each task will be assigned to a shift
(B2) Preemption of tasks is not allowed
(B3) Each task is processed only once without interruption
(B4) Each employee can execute only one task at a time

Hard constraints
(H1) The tasks in the shift do not overlap in time (overlap)
(H3) Each shift can be executed (C1 and C3 hold) by one or more employees (shift)
(H4) Each shift can be assigned to an employee s.t. all shifts are assigned to someone and no employee is assigned to multiple shifts (combination)

Goal
(G1) Minimize the the number of employees required to perform the given set of tasks
(G2) For the minimum number employees, maximize the sum of feasible (shift, employee) pairs over all pairs

Criteria (note, that an employee can be assigned to a shift only if the following criteria hold)
(C1) He/she possesses all the skills indicated by the task types of the tasks assigned to the shift(skill)
(C3) He/she is available to execute all the tasks in the shift(availability)

Benchmark instances

The paper [3] presents 86 test instances for ESMPTSP:

• 25 KEB instances
• 21 FL instances
• 10 SWMB instances
• 30 KN instances.

The first three instance sets were derived from the well-known SMPTSP instances. They are available in here.
The KN instances were introduced in [3].

All test instances in the GTSGP format.
KN instances in the SMPTSP format.

The best solution values published in [3] (the actual solutions can be found here):

*New solutions found after the publication of the paper

The new NKC instances and the best solutions presented here were published in [4] K. Nurmi, R. Chandrasekharan, J. Kyngäs and N. Kyngäs, “A Study on the Hardness of the Shift Minimization Personnel Task Scheduling Problem”, In Proc. of the 7th International Conference on Dynamics of Information Systems, 2024.

NKC instances in the SMPTSP format (the instances are wrongly named as KNC)

The best solution values published in [4]:

#New KN solutions found and reported in [5] N. Kyngäs and K. Nurmi, “Finding Optimum Solutions to the Shift Minimization Personnel Task Scheduling Problem With a New Pack-based Approach”, in Proc. of the 8th International Conference on Mathematics and Computers in Sciences and Industry (MCSI), pp. 59-67, 2024.

*New solutions found after the publication of the papers.

The new CN instances and the best solutions presented here were published in [6] R. Chandrasekharan and K. Nurmi, “Instance space analysis of the list coloring problem on interval graphs with applications to personnel scheduling”, (in review)

CN instances in the SMPTSP format

The best solution values published in [6]: