# Two Scenario-Based Heuristics for Stochastic Shift Design Problem with Task-Based Demand
## 1 Introduction  
General workforce scheduling aims at balancing supply and demand for labor. The process of workforce scheduling can be decomposed into the following seven main steps [1]: Forecasting Demand, Determining Staffing Requirements, Shift Design [2], Rostering [3], Staff Management or Tour Scheduling [4, 5], Task Assignment [6] or Staff Scheduling [7], and Re-scheduling [8, 9, 10, 11]. Among these processes, shift design can be the most significant because it determines the labor costs and human resource allocation for each period. In addition, a reasonable allocation of human resources can guarantee the comfort of employees at work and the successful performance of tasks. Since [PERSON] [12] introduced the first shift design model, many subsequent shift design models just considered deciding which shift types to use among a limited number of alternative shifts and allocating the appropriate workforce for the chosen shift type so that the staffing allocation for each time slot can satisfy the staffing requirements for the corresponding time slot to some extent. However, when the source of staffing requirements is the workforce required to perform the task, this approach of independently meeting the staffing demands for each time period and ignoring the relationship between the demands for successive periods is unreasonable. As in the example in Figure 1, DSR refers to Determining Staffing Requirements, SD refers to Shift Design, and TA refers to Task Assignment. The demand curve in the middle is converted from the workforce required for task 1 and task 2 (assuming one staff is required to perform task 1 and task 2, respectively). For this demand curve, an optimal solution can be found via the traditional shift design model: shift 1 and shift 2 (assumingboth shift 1 and shift 2 are allocated one staff). However, it is clear that for task 1, neither shift 1 nor shift 2 can perform. The shift plan is not feasible for the actual demand (tasks). If the manager uses these two shifts when making task assignments, what is likely to happen is that the employee assigned to shift 1 is made to perform task 1 by working overtime. Obviously, via such operations, not only the actual labor costs will be increased (overtime usually requires triple the hourly wage), but also a great disruption will be caused to employees' personal lives, and the job weariness of employees will be strengthened [13]. Meanwhile, employees' well-being will be significantly reduced under such a constantly changing schedule [14], easily leading to resignation. To avoid this phenomenon, for task-based demand, it seems to be a good option to consider shift design and task assignment in an integrated manner. For example, multiple task sequences (each task sequence can be carried out by one person) are first generated for each alternative shift type. Then, a set cover model is used to select the appropriate shifts (task sequences). Indeed, this was a common practice in early studies of shift design with task-based demand [15]. However, the limitation of this approach lies in the fact that generating task sequences is an NP-hard problem, and enumerating all possible task sequences based on optional shift types as input to the set cover model is even more of an impossibility. Therefore, the performance of the shift plan designed via this approach depends on the sequences of tasks fed to the set cover model. There is another common approach for shift design with task-based demand: Firstly, generating sets of tasks that can be performed by each alternative shift type and allocating sufficient workforce to each alternative shift, then considering each workforce as a different shift. Finally, using a set cover model to select the appropriate shifts/employees to minimize the number of shifts/employees used. The second method is the one that has been studied most frequently, and it was first proposed to solve the Shift Minimization Personnel Task Scheduling Problem (SMPTSP). [PERSON] et al.