Metadata

Ercsey, Zsolt; Kovács, Zoltán Multicommodity network flow model of a human resource allocation problem considering time periods. Cent. Eur. J. Oper. Res. 32, No. 4, 1041-1059 (2024).

Links: doi zbMATH

Authors:

• corresponding: Zsolt Ercsey ercsey.zsolt@mik.pte.hu
• research group
• hp

Summary

• Only partial 2nd model
• Lots of rather weak big $M$ constants

Questions

• Sourcecode?
• Big M values?

Notes

Notation

• switches beween “labourers” and “labour” and “workers” and “work”

Parameters and units of measure

• in table 1
• with units of measure!
• $\delta$ should be in minutes
  • see usage in (16) and (17)
• $480$ in (16) and (17) is a “magic constant”
  • is the $60\times{}8$ minutes in an $8$ hour shift
  • this should be a named constant
• the period duration $P_i$ should be integer
  • but the model can be easily adapted to work around it
• $NoP$ should be $\ge{}2$ for model to make sense, but never mentioned

Model 1

• decision vars
  • indices are always period, then worker, but cardinalities are given in workers, then periods
• flow graph: good explanation in section 2.3
  • but figures 6/8/9 show nodes without up-/down arcs?
  • figure 7 is logical
• single-position or multi-position
  • there is a lot of symmetry between work and rest
  • and event beyond for the multi-position case
• generally:
  • good motivations of the constraints
  • long counting of constraints
  • quantifiers over groups of constraints

Inccorrect conditional constraint

• (12) case 2, if $NoN_i = 0$, then $\sum_{k=1}^{NoL} x_{NoN_i k} = 0$ should be $\sum_{k=1}^{NoL} x_{i k} = 0$

Incorrect integer durations

• there is no reason the $w_{ik}$ and $h_{ik}$ should be integer
• if $P_1=1.1$, then for every some worker
  • $(h_{1k},w_{1k})=(1.1,0)$ or $(0, 1.1)$
  • but both should be integer
• so
  • either restrict $P_i$
  • or just relax the model => integer $P_i$ will force $w$ and $h$ to be integer, automatically

Monotone sawtooth functions

• the functions $h_({ik}){i=1}{NoP}$ counts the rest of worker $k$
  • this function is either strictly monotone rising each period
  • or falls to zero and stays one or more periods there
• the same holds for $w_({ik}){i=1}{NoP}$
• the big $M$ in (1)-(3) and (4)-(6) are different
  • and can be improved a lot
  • their growth is bounded
    • $w_{ik}\le{}\sum_{j=1}^i P_j$ by (5)
    • same for $h$
  • constraint (13) bounds $w_{ik}\le{}XWH$, whence $w_{ik}\le{}\min\left(XWH, \sum_{j=1}^i P_j\right)$
  • the minimum work time (16) implies a reverse bound on the rest $h$
    • let $X$ be the rhs of (16)
    • $h_{ik}\le\left(\sum_{i=1}^{NoP} P_i\right) - X$
    • min this with the first bound

Inflexible labour standards 4 formulation

• the labour standard is inflexible => ok
• but the formulation should not be
• (16) and (17) assume that all days are full working days
  • i.e., not shift planning over businesses including the weekend
  • this would decouple the min/max working time of a single worker from the planning horizon
  • also: no possibility to treat partial holidays
    • you can adjust the number of workers, but not the working hours
• solution: for each worker, give a standard working time (instead of the opaque $480 \times{} NoD$)
  • this constant can still be special cased in the typical cases in section 2.4

Active Workers

• d are monotone increasing
  • (17) would like to maximize $d_{NoPk}$
  • (16) would like to minimize $d_{NoPk}$
  • (O2) would like to minimize $d_{NoPk}$
  • (15) would like to minimize $d_{ik}
• big M in (15) is not optimal
  • TBW
• alternatives to (7)-(8) or (9)-(11)
  • (7) = (9) ==> only difference in (8) vs (10)-(11)
    • (7) splits in (7a)-(7b), same for (9)
    • (8) is weaker, as it is just the sum of (10) and (11)
  • alternative 1 to (7)
    • $d_{0k}=0$ equals (7b)
    • $i d_{ik}\le\sum_{j=1}^i x_{jk}$
      • mmh, do not know yet how to compare with (7a)
  • alternative 2 to (8) or (10)-(11)
    • $\forall{}j\in[i]:\quad{}d_{ik}\ge{}x_{jk}$
    • disadvantage: this is quadratic in $NoP$
• only really $d_{NoPk}$ needed if (15) can be rewritten
  • (15) does not need “ever active before”, but only “active in last RWH length periods”
  • there is a better formulation

Improved active workers

• $\forall{}1\le{}i\le{}NoP-1:$
  • $p^f_i := \max\{j\mid{} 1\le{}j\le{}NoP-1, \sum_{l=j}^i D_l \ge{} RWH\}\in\{1, …, NoP-1\}$
  • $P^f_i := \{p^f_i, \dotsc, i\}\subseteq\{1, …, NoP\}$
  • These are the indices inhibiting minimum rest.
• New indicator variables $\forall{}1\le{}i\le{}NoP-1,\,1\le{}k\le{}NoL:\qquad{}s_{ik}\in\{0,1\}$.
  • coupling constraints replacing (7)-(8)
    • $\forall{}j\in{}P^f_i:\qquad{} s_{ik} \ge{} x_{jk}$.
    • $s_{ik}\le{} \sum_{j\in{}P^f_i} x_{jk}$.
• Repaclement of (15):
  • $\forall{}1\le{}i\le{}NoP-1,1\le{}k\le{}NoL:\qquad{} h_{ik} \ge{} (x_{(i+1)k} - x_{ik} + s_{ik} - 1) RWH.$
  • bundles up everything and replaces (15)
• in parallel
  • Remove all the $d_{ik}$ except $d_{NoPk}$
  • $d_{NoPk}$ is “worker $k$ has worked during planning horizon”
  • there is a simple coupling
    • $d_{NoPk} \le \sum_{i=1}^{NoP} x_{ik}$
    • $\forall{}1\le{}i\le{}NoP:\qquad{} d_{NoPk} \ge x_{ik}$

Objective

• why not minimize $\sum_{i=1}^{NoP} P_i \sum_{k=1}^{NoL} x_{ik}$?
  • this way the total working time (without overpay, equal to the salaries) is optimised
  • just minimizing the presence of workers seems odd
    • and the given (O1) does not even minimize the workers in each period
      • nor the max number of workers ever working simultaneously
    • There seems to be an implicit assumption of all periods having the same length.
• in (O2) no value/range/indication for the value of the constant $K$ is given
  • the new objective part is useful, if the facility does not support too many worker simultaneously

Typical cases

• case 1: 1 shift per day over several days
  • attention: if a whole week is run, then (16)/(17) as above may schedule workers for all 7 days!
  • technial period with 0 demand between days => obligatory rest
• case 2: multiple shifts per day (but <24h) over several days
  • needs $RWH$ parameter
  • needs technical periods with 0 demand
• case 3: continuous shifts
  • no technical periods anymore

Misformatting

• (C5) the “and”
• subsection 2.3.7
• $i-1$ indices in (8) and (10) are not parenthised
• indices are not separated, as in $d_{ik}$ vs $d_{(i,k)}$

Section 3: multiple positions

• only the case for 2 positions is spelled out
• no example, data etc given

Models

In ASCI-printable Symplex notation.

Model 1 as in paper

• written as in paper
• includes both alternatives of (7)-(8) or (9)-(11)

input NoL
input NoD
input NoP
input NoN[i in ...]
input P[i in ...] in ??? <min>
input NWH in ??? <min>
input XWH in ??? <min>
input RWH in ??? <min>
input delta

decision x[{1, ..., NoP}][{1, ..., NoL}] in {0, 1}
decision w[{0, ..., NoP}][{1, ..., NoL}] in {0, 1, ... }
decision h[{0, ..., NoP}][{1, ..., NoL}] in {0, 1, ... }
decision d[{0, ..., NoP}][{1, ..., NoL}] in {0, 1}
local P := sum[i in {1, ..., NoP}] P[i]

constraint EQ_1a[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  w[i][k] <= x[i][k] * M

constraint EQ_1b[k in {1, ..., NoL}] is
  w[0][k] = 0

constraint EQ_2[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  w[i][k] <= w[i - 1][k] + P[i]

constraint EQ_3[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  w[i][k] >= x[i - 1][k] + x[i][k] * P[i] + (x[i][k] - 1) * M

constraint EQ_4a[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  h[i][k] <= (1 - x[i][k]) * M

constraint EQ_4b[k in {1, ..., NoL}] is
  h[0][k] = 0

constraint EQ_5[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  h[i][k] <= h[i - 1][k] + P[i]

constraint EQ_6[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  h[i][k] >= x[i - 1][k] + (1 - x[i][k]) * P[i] + x[i][k] * M

constraint EQ_7a[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  d[i][k] <= x[i][k] + d[i - 1][k]

constraint EQ_7b[k in {1, ..., NoL}] is
  d[0][k] = 0

constraint EQ_8[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  d[i][k] => (x[i][k] + d[i - 1][k]) / 2

constraint EQ_9a[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  d[i][k] <= x[i][k] + d[i - 1][k]

constraint EQ_9b[k in {1, ..., NoL}] is
  d[0][k] = 0

constraint EQ_10[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  d[i][k] >= d[i-1][k]

constraint EQ_11[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  d[i][k] >= x[i][k]

constraint EQ_12a[i in {1, ..., NoP}] is
  sum[k in {1, ..., NoL}] x[i][k] >= NoN[i]

constraint EQ_12b[i in {1, ..., NoP}] is
  NoN[i] = 0 ===> sum[k in {1, ..., NoL}] x[i][k] = 0
  // Alternative: sum[k in {1, ..., NoL}] x[i][k] <= [NoN[i] = 0] * NoL

constraint EQ_13[k in {1, ..., NoL}][i in {1, ..., NoP}] is
  w[i][k] <= XWH

constraint EQ_14a[k in {1, ..., NoL}][i in {1, ..., NoP - 1}] is
  w[i][k] >= (x[i][k] - x[i + 1][k]) * NWH

constraint EQ_14b[k in {1, ..., NoL}] is
  w[NoP][k] >= x[NoP][k] * NWH

constraint EQ_15[k in {1, ..., NoL}][i in {1, ..., NoP - 1}] is
  h[i][k] >= (x[i + 1][k] - x[i][k]) * RWH + (d[i][k] - 1) * M

constraint EQ_16[k in {1, ..., NoL}] is
  sum[i in {1, ..., NoP}] x[i][k] * P[i] >= d[NoP][k] * (480 * NoD - delta)

constraint EQ_17[k in {1, ..., NoL}] is
  sum[i in {1, ..., NoP}] x[i][k] * P[i] <= d[NoP][k] * (480 * NoD + delta)

minimize sum[i in {1, ..., NoP - 1}][k in {1, ..., NoL}] x[i][k]

Model 1 rewritten

• with correctly chosen big-$M$ constants
• abstracting over work and rest
• with better active workers
• with duration weighted objective function (O1)

input NumWorkers in {1, 2, ...}
local Workers := {1, ..., NumWorkers}

input NumDays in {1, 2, ...}

input NumPeriods in {2, 3, ...}
local Periods := {1, 2, ..., NumPeriods}
local Instants := {0, 1, ..., NumPeriods}
local Switches := {1, 2, ..., NumPeriods - 1}

input Demand[p in Periods] in {0, ..., NumWorkers}

input Duration[p in Periods] in [0, infty[ <min>
local TotalDuration := sum[p in Periods] Duration[p]

input MinWork in [0, infty[ <min>
input MaxWork in [0, infty[ <min>
input MinRest in [0, infty[ <min>
input MaxDiff in [0, infty[ <min>

local StandardWork := 480 <min>

local RestPeriod[s in Switches] := max { p in Periods | p <= c, sum[q in {p, ..., c}] Duration[q] >= MinRest }
local RestPeriods[s in Switches] := {RestPeriod[s], ..., s} subseteq Switches

local Activity := {Work, Rest}
decision Time[Workers][Activity][Instants] in [0, infty[ <min>
decision Works[Workers][Periods] in {0, 1}
decision HasWorked[Workers] in {0, 1}
decision ShouldRest[Workers][Switches] in {0, 1}


local MaxWorkTime[p in Periods] := 
  min(MaxWork, sum[q in {1, ..., p} Duration[q])

constraint WorkTime_UB[w in Workers][p in Periods] is
  Time[w][Work][p] <= Works[w][p] * MaxWorkTime[p]

constraint WorkTime_Zero[w in Workers] is
  Time[w][Work][0] = 0

constraint WorkTime_Mon[w in Workers][p in Periods] is
  Time[w][Work][p] <= Time[w][Work][p - 1] + Duration[p]

constraint WorkTime_LB[w in Workers][p in Periods] is
  Time[w][Work][p] >= Works[w][p - 1] + Works[w][p] * Duration[p] + (Works[w][p] - 1) * MaxWorkTime[p]


local MaxRestTime[p in Periods] := 
  max(sum[q in {1, ..., p} Duration[q], sum[q in Periods] Duration[q] - StandardWork * NumDays + MaxDiff)

constraint RestTime_UB[w in Workers][p in Periods] is
  Time[w][Rest][p] <= (1 - Works[w][p]) * MaxRestTime[p]

constraint RestTime_Zero[w in Workers] is
  Time[w][Rest][0] = 0

constraint RestTime_Mon[w in Workers][p in Periods] is
  Time[w][Rest][p] <= Time[w][Rest][p - 1] + Duration[p]

constraint RestTime_LB[w in Workers][p in Periods] is
  Time[w][Rest][p] >= Works[w][Rest][p - 1] + (1 - Works[w][p]) * Duration[p] + Works[w][p] * MaxRestTime[p]


constraint ShouldRest_LB[w in Workers][s in Switches]][q in RestPeriods[s]] is 
  ShouldRest[w][s] >= Works[w][q]

constraint ShouldRest_UB[w in Workers][s in Switches] is 
  ShouldRest[w][s] <= sum[q in RestPeriods[s]] Works[w][q]


constraint HasWorked_LB[w in Workers][p in Periods] is
  HasWorked[w] >= Works[w][p]

constraint HasWorked_UB[w in Workers] is
  HasWorked[w] <=  sum[p in Periods] Works[w][p]


constraint EQ_12[p in Periods] is
  cases
    sum[w in Workers] Works[w][p] >= Demand[p] if Demand[p] > 0
    sum[w in Workers] Works[w][p] = 0 if Demand[p] = 0

constraint EQ_13[w in Workers][p in Periods] is
  Time[w][Work][p] <= MaxWork

constraint EQ_14_a[w in Workers][s in Switches] is
  Time[w][Work][p] >= (Works[w][s] - Works[w][s + 1]) * MinWork

constraint EQ_14_b[w in Workers] is
  Time[w][Work][NumPeriods] >= Works[w][NumPeriods] * MinWork

constraint EQ_15[w in Workers][s in Switches] is
  Time[w][Rest][s] >= (Works[w][s + 1] - Works[w][s] + ShouldRest[w][s] - 1) * MinRest
  with M := ???

constraint EQ_16[w in Workers] is
  sum[p in Periods] Works[w][p] * Duration[p] >= HasWorked[w] * (StandardWork * NumDays - MaxDiff)

constraint EQ_17[w in Workers] is
  sum[p in Periods] Works[w][p] * Duration[p] <= HasWorked[w] * (StandardWork * NumDays + MaxDiff)

minimize sum[p in Periods] Duration[p] sum[w in Workers] Works[w][p]