# Two Scenario-Based Heuristics for Stochastic Shift Design Problem with Task-Based Demand
## 1 Introduction
However, this approach relies on the availability of temporary workers and requires that the uncertainty in demand be reduced sufficiently before the operating date. [PERSON] [22] used a multi-scenario approach to solve this stochastic problem to minimize the expected cost when studying the task assignment problem with an uncertain workload. [PERSON] and [PERSON] [23] proposed a model for repairing shift schedules with minimum variation after tasks are perturbed and used a meta-heuristic algorithm to solve the model, which has constraints similar to those of the SMPTSP except that the objective is to minimize perturbations, unlike expressing the staffing to perform tasks in terms of costs for over- and understaffing. [PERSON] et al. [24] studied the stochastic problem of shift design by using the sample average approximation method to convert the stochastic model into a MILP model, then solving this model via the Lagrangian decomposition method and the subgradient method. [PERSON] et al. [25], in their study of the employee scheduling problem in retail stores, considered temporary demand perturbations, developed two robust models of employee scheduling, and used multiple scenarios to simulate real-life situations. [PERSON] and [PERSON] [26] introduce a shift design problem considering delay costs in the context of flight delays. The model takes alternative shifts containing task sequences as input data, and uses methods such as column generation to quickly obtain a shift solution with lower expected costs by continuously optimizing the set of alternative shifts and testing the delay costs of the solution under different delay scenarios. [PERSON] et al. [27] considered the uncertainty of aircraft departure time when studying the task assignment problem at airport check-in counters, described the stochastic problem by building a multi-scenario model, and introduced the objectives and constraints of the risk aversion model, and then solved the problem using the sample average approximation and the progressive hedging algorithm, respectively. From the relevant scientific literature on shift design and task assignment with uncertainty in demand/tasks, there are two main approaches to solving such stochastic problems: one is to wait for the randomness of demand/tasks to reduce to a low enough level to go for rescheduling, while another is to simulate the stochastic demand/tasks of the real environment via multiple scenarios of demand/tasks and find a robust solution based on those scenarios. The former approach requires the demand/task uncertainty to be reduced sufficiently small before the operational day to ensure the rescheduled solution is feasible. The latter approach usually expresses the degree of over- and understaffing in terms of expected cost. However, evaluating the reliability of a solution solely in terms of expected cost is also problematic. This is because what we can know is just the expected cost of the shift plan designed if it is applied in real environments, but not the probability that understaffing will occur. Only when the level of the demand/task's stochasticity is reduced low enough can the dispatchers know what measures to take to cope with the coming demand/tasks, making it difficult to use such a robust shift plan? Therefore, a probability constraint on describing the probability that all tasks in the task set can be performed when using the designed shift plan should be added when constructing the stochastic model of shift design with task-based demand. The contributions of this paper are to propose a shift design model with task-based demand, give a stochastic version of this model with a probability constraint, and develop two heuristics for solving this stochastic model. Besides, the effectiveness of these methods is demonstrated in numerical experiments. The rest of the paper is organized as follows: Section 2 describes the deterministic shift design model with task-based demand and the corresponding stochastic version.