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

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 443#
  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 300
  40 284
  41 286
  42 285
  43 283
  44 284
  45 285
  46 283
  47 285
  48 285
  49 283
  50 288
  51 285
  52 299
  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 300
  74 300
  75 X
  76 X
  77 300
  78 X
  79 X

#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]:

CN  LBBestGURCMHGFA
  000283283X285283
  001224227227X227
  002274XXXX
  003282287XX287
  004325325X325325
  005376379X379379
  006213213213213213
  007332332X332332
  008253253X253253
  009345XXXX
  010380392XX392
  011259262X262X
  012258258258258258
  013287289289XX
  014309XXXX
  015211214X214214
  016309311X312311
  017329329329X329
  018215215X215215
  019382XXXX
  020370374374374374
  021233233X233233
  022309XXXX
  023254257257257257
  024314314X314314
  025219219219219X
  026354357357XX
  027285285X285285
  028292304XX304
  029202208XX208
  030262XXXX
  031284287X288287
  032317327327X327
  033194194X194194
  034297303X305303
  035255282XX282
  036341XXXX
  037350355X355355
  038205205X206205
  039260264X264264
  040241242242XX
  041278XXXX
  042378383X383384
  043300302X303302
  044203208X208208
  045232232232XX
  046249251X252251
  047281XXXX
  048338345X346345
  049279279X281279
  050363363X364363
  051199200X200200
  052319326X327326
  053293XXXX
  054296296X296296
  055311316X316317
  056310311X311311
  057370371X373371
  058289290X291290
  059302303X303303
  060268268268268268
  061318XXXX
  062304304X305304
  063366367X367367
  064317317X318317
  065258259X259259
  066308317X319317
  067328345XX345
  068360360X361360
  069364364X370364
  070265267X267X
  071289290X290X
  072320XXXX
  073352XXXX
  074228231XX231
  075349359XX359
  076306316X319316
  077362362X364362
  078312314314XX
  079285XXXX
  080199199X199199
  081248249X249249
  082348350X352350
  083351353X353353
  084223227227227227
  085212213X213214
  086200200200200200
  087225226226226226
  088325327327X327
  089238238X238239
  090300304X304304
  091304XXXX
  092324325325XX
  093207207207207207
  094270270X271270
  095271272X272272
  096217XXXX
  097247247X248247
  098340354XX354
  099320321321X321
  100213213213213213
  101228228X228229
  102322322X322323
  103374XXXX
  104293295X295295
  105282282X283282
  106270XXXX
  107221223X223223
  108319319X320319
  109336XXXX
  110310320XX320
  111243243243243243
  112311315X315315
  113226236XX236
  114342348X350348
  115305313X314313
  116387387X388387
  117357XXXX
  118224224224224224
  119294299X299299
  120201202202202202
  121250254254254254
  122226230X230230
  123277XXXX
  124386XXXX
  125367XXXX
  126345XXXX
  127298307XX307
  128361365X365366
  129357366X369366
  130386XXXX
  131359359X359359
  132204208208208208
  133302302X303302
  134369372X372373
  135304307X307307
  136242251251251251
  137266XXXX
  138288XXXX
  139314315X315315
  140313317X317317
  141271275X275275
  142199201201201201
  143323331X331331
  144364371X371372
  145320320X321320
  146232233233233233
  147220220220220220
  148261265265X265
  149256256256256256
  150223231231231231
  151340343X343344
  152334346X346346
  153350365365X365
  154235242XX242
  155233238XX238
  156248248X248248
  157382382X385382
  158345349X351349
  159211217X219217
  160199199X199199
  161259XXXX
  162293XXXX
  163347350X350350
  164270276X277276
  165269XXXX
  166252252XX252
  167370383XX383*
  168332338X340338
  169231233X233233
  170249249X249249
  171363366X366366
  172226XXXX
  173330336X336336
  174351353X353353
  175219219X219219
  176376376X377376
  177217XXXX
  178277278X278278
  179257XXXX
  180358364X365364
  181360360X361360
  182363373X376373
  183323XXXX
  184339339X339339
  185344349X349349
  186251257XX257
  187343357XX357
  188233XXXX
  189329XXXX
  190333333X333333
  191204XXXX
  192255259X259259
  193275275X275275
  194243244X244245
  195318322X322323
  196383395XX395
  197328329X331329
  198373XXXX
  199202XXXX
  200362369X371369
  201315315X316315
  202373375X375375
  203323XXXX
  204351XXXX
  205212219XX219
  206243248248X248
  207400400400XX
  208224224224224224
  209354355X355355
  210361XXXX
  211211212X212212
  212344XXXX
  213304306306XX
  214305XXXX
  215308308308X308
  216335XXXX
  217324325X325325
  218252255X255255
  219333XXXX
  220261268XX268
  221281282X282283
  222207XXXX
  223384384XX384
  224267268X270268
  225268268X268X
  226247XXXX
  227298298298XX
  228244249X249249
  229286294294X294
  230234234234234234
  231348XXXX
  232394XXXX
  233295XXXX
  234269XXXX
  235255262XX262
  236370382X382382
  237319XXXX
  238218218X218X
  239228228228228228
  240261263263263263
  241219219219219219
  242214214214214X
  243299303303303303
  244330XXXX
  245241XXXX
  246332XXXX
  247277XXXX
  248196203203X203
  249372XXXX
  250301XXXX
  251201XXXX
  252256XXXX
  253328XXXX
  254378XXXX
  255305XXXX
  256376XXXX
  257364XXXX
  258290XXXX
  259237XXXX
  260243XXXX
  261265XXXX
  262237237X237X
  263277XXXX
  264256263X264263
  265231231231XX
  266327336X336336
  267350XXXX
  268278XXXX
  269371XXXX
  270326XXXX
  271381XXXX
  272361368X368368
  273359XXXX
  274256XXXX
  275306312X313312
  276383394XX394
  277345XXXX
  278216216216216X
  279367XXXX
  280338349X349349
  281257263X266263
  282218222XX222
  283321XXXX
  284383XXXX
  285291XXXX
  286304XXXX
  287319XXXX
  288216XXXX
  289313XXXX
  290330XXXX
  291220XXXX
  292235XXXX
  293302304X304304
  294308313X313313
  295360367X367368
  296342XXXX
  297210210210210210
  298319327X328327
  299390XXXX
  300231231XX231
        
NKC  LBBestGURCMHGFA
  000283283X285283
  010285285300286285
  011287287X287287
  012285285300286285
  013287287300287287
  014285285300285285
  015287287X288287
  016284284X284284
  017285285X286285
  018288288X288288
  019284284XX284
  020285285X285285
  021287287299287287
  022284284X284284
  023285285X285285
  024287287X287287
  025287287X287287
  026285285X286285
  027283288X291288
  028288292X298292
  029285300XX300
  030262262287262262
  031264264300264264
  032272272295272272
  033277277X277277
  034282282X282282
  035290290X291290
  036296296X296296
  037298299X299299
  038300XXXX
  039300300300XX
  040284284X285284
  041286286X286286
  042285285X285285
  043283283X284283
  044284284X285284
  045285285X286285
  046282283X284283
  047285285X285285
  048285285X285285
  049283283X284283
  050287288288296289
  051285285285287285
  052286299299XX
  053286286X286286
  054289289X289289
  055300300300300300
  056287300XX300
  057284284299285284
  058286286X286286
  059300300300300300
  060300300300300300
  061285285X289285
  062300300300300300
  063286286X286286
  064288288300288288
  065284287XX287
  066284284292284284
  067300300300300300
  068300300300300300
  069300300300300300
  070300300300300300
  071300XXXX
  072300300300300300
  073300300300XX
  074300300300300300
  075300XXXX
  076300XXXX
  077300300XX300
  078300XXXX
  079300XXXX
        
KN  LBBestGURCMHGFA
  000283283X285283
  0012020202020
  002252525X25
  003303030X30
  0043535353535
  0054040404040
  0064545454545
  007505050X50
  0085555555555
  0096060606060
  0106565656565
  011707070X70
  0127575757575
  013808080X80
  014858585X85
  015100100100100100
  016110110110110110
  017120120120120120
  018130130130130130
  019140140140140140
  020149149149149149
  021160160160160160
  022180180180180180
  023199199199200199
  024239239X239239
  025279279X280279
  026309314XX314
  027356356360356356
  028399399X399399
  029443443X447443
  030488491X496491

*New solutions found after the publication of the papers.



cimmo.nurmi@samk.fi
Updated 5-July-2025