The General Task-based Shift Generation Problem (GTSGP) - Benchmark Instances

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.

Instance EX   Best 15
Instance 00   Best 6
Instance 01   Best 53
Instance 02   Best 25
Instance 03   Best 15
Instance 04   Best 22
Instance 05   Best 146
Instance 06   Best 100
Instance 07   Best 110
Instance 08   Best ??
Instance 09   Best 60
Instance 10   Best 205
Instance 11   Best 371
Instance 12   Best 441
Instance 13   Best 585
Instance 14   Best 615
Instance 8I   Best 40


The Extended Shift Minimization Personnel Task Scheduling (ESMPTSP) - Benchmark Instances

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):

KEB 4 53
  5 62
  9 233
  11 30
  13 32
  15 694
  17 97
  22 524
  28 1497
  29 69
  30 78
  35 3558
  45 114
  59 85
  68 49539
  75 84
  77 1053
  79 131
  80 219
  89 95
  94 115
  98 113
  106 146
  107 146
  108 232
     
SWMB 1 45
  2 42
  3 117
  4 114
  5 60
  6 129
  7 59
  8 80
  9 99
  10 116
     
FL 28 4051
  29 4296
  31 4535
  33 5933
  35 5393
  39 4224
  45 8461
  46 9702
  54 11321
  60 9698
  61 17646
  62 19497
  63 13191
  64 7524
  68 18682
  69 16045
  77 20986
  79 22056
  80 20154
  84 22110
  94 30342
     
KN 1 43
  2 57
  3 235
  4 456
  5 89
  6 101
  7 147
  8 1375
  9 76
  10 1271
  11 118
  12 1378
  13 220
  14 1160
  15 128
  16 2621
  17 131
  18 3150
  19 152
  20 2933
  21 12101
  22 6888
  23 2654
  24 25835
  25 11778
  26 795 (316 shifts)
  27 66171
  28 51277
  29 5190 (445 shifts)
  30 3187* (495 shifts)

*New solutions found after the publication of the paper

The Shift Minimization Personnel Task Scheduling (SMPTSP) - New Benchmark Instances and Best Solutions

The new NKC instances and the best solutions prosented 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 (on review).

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

The best solution values published in [4]:

KN 01 20
  02 25
  03 30
  04 35
  05 40
  06 45
  07 50
  08 55
  09 60
  10 65
  11 70
  12 75
  13 80
  14 85
  15 100
  16 110
  17 120
  18 130
  19 140
  20 149
  21 160
  22 180
  23 199
  24 239
  25 279
  26 314
  27 356
  28 399
  29 444
  30 491
NKC 00 283
  10 285
  11 287
  12 285
  13 287
  14 285
  15 287
  16 284
  17 285
  18 288
  19 284*
  20 285
  21 287
  22 284
  23 285
  24 287
  25 287
  26 285
  27 288*
  28 292*
  29 300
  30 262
  31 264
  32 272
  33 277
  34 282
  35 290
  36 296
  37 299
  38 X
  39 X
  40 284
  41 286
  42 285
  43 283
  44 284
  45 285
  46 283
  47 285
  48 285
  49 283
  50 289
  51 285
  52 X
  53 286
  54 289
  55 300
  56 300
  57 284
  58 286
  59 300
  60 300
  61 286
  62 300
  63 286
  64 288
  65 287
  66 284
  67 300
  68 300
  69 300
  70 300
  71 X
  72 300
  73 X
  74 300
  75 X
  76 X
  77 300
  78 X
  79 X

*New solutions found after the publication of the paper



cimmo.nurmi@samk.fi
Updated 04-February-2024