# Two Scenario-Based Heuristics for Stochastic Shift Design Problem with Task-Based Demand
## 2 Problem Description  
The shift design problem for task-based demand can be stated as follows:  
For a given set of tasks \(K\) and a set of alternative shifts \(H\), the decision maker needs to select the appropriate shift types from \(H\) and allocate the appropriate manpower to each selected shift type so that all the tasks in \(K\) can be assigned sufficient manpower so that the individual tasks can be performed successfully. And each shift \(h\) in the set of shifts \(H\) has the parameters \(\{s_{h},e_{h},w_{h}\}\), \(s_{h}\) refers to the start time of the shift \(h\), \(e_{h}\) refers to the end time of the shift \(h\), and \(w_{h}\) refers to the workforce configured for the shift \(h\). Note that \(w_{h}\) is the decision variable in the shift design model and is replaced by \(x_{h}\). Similarly, each task \(k\) in \(K\) has parameters \(\{s_{k},e_{k},w_{k}\}\), where \(s_{k}\) refers to the start time of task \(k\), \(e_{k}\) refers to the end time of task \(k\), and \(w_{k}\) refers to the workforce required to perform task \(k\). The following constraints are followed when designing a shift plan:  
1. All tasks are uninterruptible;
2. manpower can be transferred from a shift to perform a task only if the start time as well as the end time of the task fall within this shift's working duration;
3. A single manpower can only perform a single task at the same time;
4. manpower to perform a task can come from more than one shift. In solving this problem, the optimization direction is to minimize the cost of the designed shift plan. For instance, as shown in Figure 2, suppose that we have designed shift 1 based on task 1 and task 2, where \(s_{1}\), \(s_{2}\), and \(s_{3}\) are the start time of task 1, task 2, and shift 1, respectively; \(e_{1}\), \(e_{2}\), and \(e_{3}\) are the end times of task 1, task 2, and shift 1, respectively; \(w_{1}\) and \(w_{2}\) are the required workforce for task 1 and task 2, respectively, and \(w_{3}\) is the staffing allocated for shift 1, where \(w_{2}=2w_{1}=2w_{3}\). Then we call \(w_{3}*(t_{1}+t_{2})\) the overstaffing and \((e_{2}-s_{2})*(w_{2}-w_{3})\) the understaffing. Both overstaffing and understaffing are part of the objective function regarding the cost of the shift design model. It is important to note that the cost of understaffing referred to here does not mean that tasks can be performed without enough workforce required, but rather that dispatchers need to ensure the successful execution of tasks by outsourcing tasks, delaying the departure time of employees on duty or urgently calling back employees who are on leave. Since the model proposed in this paper is based on the traditional shift design model 12, i.e., we need to discretize the workforce required for a single task into the workforce required for each of its work periods. The work periods of a single task are determined, as shown in Figure 3. Suppose the start and end times of task \(k\) are located at the time slot \(t_{i}\) and \(t_{i+3}\), respectively, then we consider time slots \(t_{i}\) to \(t_{i+3}\) as work periods of task \(k\). The more periods the planning period is discretized into (the shorter the duration of each period), the more accurate this description will be, but at the same time, it will also make the model more difficult to solve. Unlike the traditional shift design model, the model proposed in this paper considers the correlation between the staffing requirements at successive periods, i.e., the tasks from which the staffing requirements at each period originate. The model can be described as model M1 in Appendix A. Further, for deterministic problems, the start time, and the end time of the task \(k\in K\) are fixed, i.e., \(e_{kt}\) and \(s_{kk}\) are constants. However, in reality, the start time and the end time of the task are often random, which means that \(e_{kt}\) and \(s_{kk}\) are actually random 0-1 variables.