# Two Scenario-Based Heuristics for Stochastic Shift Design Problem with Task-Based Demand
## 1 Introduction
[16] first defined SMPTP and discussed its properties, which was a variant of the Personnel Task Scheduling Problem (PTSP) but with the objective of minimizing the number of shifts/persons required to perform all tasks, and described the basic model of the problem as well as developed a heuristic algorithm that could find feasible solutions in the face of large-scale problems. Most of the subsequent research is centered on the algorithm for solving this problem, such as [PERSON] and [PERSON] [17] proposed a three-stage heuristic algorithm for the SMPTSP, where a constructive heuristic algorithm was used in the first stage to quickly obtain the initial solution of the problem, an iterative greedy algorithm was used in the second stage to improve the initial solution and obtain the near-optimal solution, and finally the near-optimal solution was used as the initial solution, and used the commercial solver to further find the optimal solution. [PERSON] et al. [18] developed a time-based constructive matheuristic (CMH): a decomposition-based method where sub-problems are solved to optimality using exact techniques, and the optimal solutions of sub-problems are subsequently utilized to construct a feasible solution for the entire problem, which firstly solved all the difficult instances introduced by [PERSON] et al. [19] to optimality. The current input of this method generally involves the problem of finding the maximum group of mutually exclusive tasks, which is also an NP-hard problem, so it is generally difficult to consider too many shift types and tasks. Furthermore, determining the initial number of workers for each shift type is also a problem. Too many initial configurations will lead to a sharp increase in the difficulty of solving the model, while too few will lead to no  
Figure 1: The simple workforce planning processes. feasible solution for the model. In addition, most of the researchers of this method work on the algorithm based on a given public test set (given the optional shifts/workers and the corresponding set of performable tasks directly, with the shift type generation process hidden) without discussing the nature of the problem in more depth. Both of the above two shift design methods with task-based demand have completed the assignment of tasks while carrying out the shift design, which has introduced other NP-hard problems and increased the difficulty of solving the problem. We believe that even in the face of task-based demand, we should return to the original intention of shift design, i.e., focus on the configuration of labor resources, while the assignment of tasks is non-essential. In this paper, we propose a new shift design model with task-based demand, which focuses more on the configuration of the workforce than the matching of workforce and demands/tasks. Further, since, in reality, the start time of a task often deviates from the planned time, i.e., the start time of tasks is with a certain degree of randomness, if only the planned start time of a task is used for shift design, once a task arrives early or late, many tasks cannot be executed in time on the operation day, thus leading to a series of unpredictable consequences. We are therefore convinced that the uncertainty in the start time of tasks must be considered when modeling shift design with task-based demand to make the designed shift plan robust. Such a robust shift plan can guarantee that the corresponding cost of overstaffing and understaffing will not change significantly when the staffing requirements estimated are deviated [20]. However, there is a paucity of literature on the problem of shift design with stochastic demand and even less on the stochastic problem of shift design with task-based demand. [PERSON] et al. [21] considered the shift design and task assignment problem with uncertain demand by adjusting the original shifts, reassigning tasks, and scheduling temporary shifts before the operating day to meet the demand where the randomness has become sufficiently small.