# Two Scenario-Based Heuristics for Stochastic Shift Design Problem with Task-Based Demand
## 3 Solution Approach
### One-Stage Heuristic  
As shown in Figure 4, if the start time of task \(k\) obeys the probability density function \(f_{k}\), then we can randomly generate a large number of scenarios based on this function (task \(a\), \(b\), and \(c\) are one possible scenario for task \(k\), respectively). Based on these scenarios, we can count the probability \(p_{kt}\) that time slot t is a work period for task \(k\). Thus we can introduce the following equation.  
\[e_{kt}=\begin{cases}1,&p_{kt}\geq\theta\\ 0,&\text{\emph{otherwise}}\end{cases} \tag{1}\]  
Formula (1) indicates that when the probability \(p_{kt}\) that time slot \(t\) is a work period for task \(k\) is not less than \(\theta\) (\(\theta\) takes values in the range of \((0,1]\)), then time slot \(t\) is considered a working slot for task \(k\). The closer the value of \(\theta\) is to \(0\), the more working slots task \(k\) has, and if the workforce is allocated to task \(k\) according to these slots via the shift design model, the higher is the probability that task \(k\) can be allocated sufficient workforce on the operation day.  
The one-stage heuristic proposed below is to adjust the value of \(\theta\) to obtain a shift plan that satisfies the probability constraint (A9) and performs well in terms of cost.  
The specific algorithm is as follows:  
1. Count \(p_{kt}\) via \(\Omega\) for \(\forall k\in K,t\in T\). Initialize the parameters \(\mathsf{s}=\theta\), \(\mathsf{t}=1\), \(\theta=\mathsf{s}\), \(\mathsf{q}=0,H^{*}=\varnothing,C^{*}=0,q^{*}=0\), and go to step 2.
2. Update \(e_{kt}\) via constraint (1) and find the corresponding optimal shift plan \(H^{\theta}\) via M3. Generate M scenarios by perturbing the start time of tasks in task set K. Take \(H^{\theta}\) and each of these M scenarios as the input of TAA, respectively, and denote the number of occurrences \(K^{u}=\varnothing\) by Q. Let \(\mathsf{q}=\mathsf{Q}/\mathsf{M},q^{*}=q,H^{*}=H^{\theta}\), and calculate the inherent cost \(c^{\mu^{\theta}}\) and the expected cost \(C^{*}\) of the shift plan \(H^{\theta}\), where \(c^{\mu^{\theta}}=\alpha\sum_{i_{t}^{\theta}<H^{\theta}}w_{i_{t}^{\theta}} \Big{(}e_{t_{t}^{\theta}}-s_{i_{t}^{\theta}}\Big{)}\), \(C^{*}=c^{H^{\theta}}+\mathrm{E}(\delta_{H^{\theta}})\). If \(\mathsf{q}\geq\mathsf{n}\), then go to Step 3; otherwise go to Step 6.
3. Let \(\theta=(s+t)/2\). If \(\mathsf{t}-\theta\leq\epsilon\), then go to Step 6, otherwise go to Step 4.
4. Update \(e_{kt}\) via constraint (1) and update the shift plan \(H^{\theta}\) via M3, respectively. Generate M scenarios by perturbing the start time of tasks in task set K. Take \(H^{\theta}\) and each of these M scenarios as the input of TAA, respectively, denote the number  
Figure 4: The work periods with a probability of task \(k\).  
of occurrences \(K^{u}=\varnothing\) by Q, and let \(\mathrm{q}=\mathrm{Q}/\mathrm{M}\). If \(\mathrm{q}\geq\mathrm{n}\), then go to Step 5; otherwise let \(t=\theta\) and go to Step 3.
* If \(C^{*}\geq c^{H^{\theta}}+\mathrm{E}(\delta_{H^{\theta}})\), then let \(H^{*}=H^{\theta},C^{*}=c^{H^{\theta}}+\mathrm{E}(\delta_{H^{\theta}})\), \(q^{*}=q\), \(\mathrm{s}=\theta\) and go to Step 3; otherwise, let \(\mathrm{s}=\theta\) and go to Step 3.
* Output \(H^{*},C^{*}\) and \(q^{*}\).  
\(H^{*}\) is a shift plan that satisfies the probability constraint (A9) while performs well in terms of the expected cost (the expected cost of this plan is \(C^{*}\)), and the probability that this shift plan can provide a sufficient workforce for all tasks in K on the operation day via TAA is \(q^{*}\).