{'fraction_non_alphanumeric': 0.037600071961860215, 'fraction_numerical': 0.027723306647476836, 'mean_word_length': 4.180911548140553, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Efficient Algorithm to the Integrated Shift and Task Scheduling Problem

This paper deals with operational models for integrated shift and task scheduling problem. Staff scheduling problem is a special case of this with staff requirements as given input to the problem. Both problems become hard to solve when the problems are considered with flexible shifts. Current literature on these problems leaves good scope for potential research. In this article, we propose a new method to solve the integrated problem and its special case, the staff scheduling problem. We consider these problems with wide flexibility - a feature that is addressed in a limited way in the existing literature. We introduce a new technique to solve the problem with large demand efficiently. When the objective function is the number of workers, we provide a tight lower bound that is easily computable. Through a number of numerical experiments with live and simulated problem instances, we demonstrate huge savings in the solution times over the existing ones.


Introduction
Personnel scheduling problems arise in a variety of applications and deal with assignment of shifts to workforce over a planning horizon. A large number of applications involve flexible work schedules. Workforce requirements over the planning horizon are induced by task characteristics such as duration, number of workers required to perform the task, deadlines, etc. Demand, the number of workers required, in each time period of the planning horizon, may be known exactly or assumed according to a predictable pattern, is necessary for the purpose of planning. The flexibility in staff (or work) schedules has two components: (i) type of shift which specifies duration, breaks and their positioning within shift, etc., (ii) time gap between successive shifts, bounds on the number of shifts in the planning horizon, bounds on the total number of workerhours, days-off, etc. The constraints in the latter component, part of the tour scheduling process, are imposed due to labour laws, company regulations, employees preferences and so on. The complexities and challenges are aggravated by the flexibilities of staff and task schedules. One of the factors that is ignored in much of the existing literature is not including breaks within shifts (see Thompson and Pullman (2007)). Breaks can be included using implicit formulations (see Sungur et al. (2017), Aykin (1996)), but this would dramatically increase the size of the problem.
In this article, we are concerned with two versions of personnel scheduling problem over a discrete planning horizon. In the first version, staff schedules are flexible but the tasks are fixed and the demand of resources (number of personnel required) for each time period of the planning horizon is specified. The second version is an extension of the first and it allows tasks to be scheduled within specified time periods and the tasks may have precedence relationships. The workforce demand is a result of task scheduling. The objective in both versions is to minimize the number of workers or an associated cost. The second version is referred to as integrated shift and task scheduling problem (ISTSP). The problem is so complex that it calls for special formulations and methods for solving it. Stolletz (2010) computes the possible tours in a further restricted case of first version of the problem (shifts without breaks, shifts restricted to 4 am to 9 pm) to the tune of 10 19 . ISTSP is intractable for exact solution approaches. A common mathematical programming approach to solving ISTSP uses set covering formulation or its variants (Dantzig (1954)). Solution approaches presented in Maenhout and Vanhoucke (2016) and Volland et al. (2017) are some of the recent contributions in this direction.
To the best of our knowledge, the methods for staff scheduling or ISTSP in the existing literature have not considered a wide range of problems. For example, Stolletz (2010) and Brunner and Stolletz (2014) have considered discontinuous tour scheduling problems and not the problems with continuous demand. While the former considers shifts without breaks, the latter considers shifts with only one break. Similarly, Volland et al. (2017) does not consider breaks within shifts. Moreover, these articles implicitly express that problems with larger demands (by classifying them under small, medium and large) are harder to solve. Against this backdrop, we believe that this article makes an important and significant contribution. The main contribution of this article is that we provide a new method for ISTSP that can • reduce solution times drastically, • solve problems with large demands in approximately the same time taken for problems with small demands, and • handle wide flexibility in shifts resulting from multiple breaks.
The organisation of the rest of this article is as follows. In the next section, we start with the genesis of this work and present a brief discussion on the extensions of the model assumptions and their consequences. This will be followed by a brief literature review with focus on recent contributions relevant to this paper. In Section 3, we present the problem description, our formulations, solution approach and a discussion on their applications. Section 4 describes our numerical experiments with data from live problems and simulation. The simulation exercises are carefully planned so as to compare our approach with existing methods. Section 5 presents the summary of the experimental results. The article is concluded in Section 6, with a summary and possible scope for future research.

Motivation and Literature Review
This work is an extension of a problem that we received from a software company. For ease of cross referencing, we shall call this the Software Industry Problem (SIP) in this article. The requirement was to develop a method for determining staff schedules with flexible shifts to meet workforce demand specified for every 30-minute time period (TP) over one week planning horizon (336 TPs) with an objective of minimizing the number of workers. Demand for a selected week is shown in Fig. 1. The admissible shifts in this problem should satisfy four conditions: (i) shift has two tea breaks each of 15 minutes duration and one lunch break of 60 minutes, (ii) no break in the first 90 minutes, (iii) at least 90 minutes gap between any two successive breaks, and (iv) the duration of the shift including breaks is 9 hours.
This work is the outcome of our effort to solve the SIP in its full flexibility. Encouraged by the results and the nature of our approach, we noticed that it can be extended to ISTSP.
There is vast literature on personnel scheduling problem. The problem has been classified into different categories depending upon the areas of applications, models and solution approaches. For a detailed review on personnel scheduling problems, see Ernst et al. (2004) and Van den Bergh et al. (2013), and references therein. Different approaches are pursued for solving staff scheduling problems (see Alfares (2004), Bellenguez-Morineau and Néron (2007) and Brunner et al. (2010)). The main hurdle in solving staff scheduling problems is their size. In SIP, there are 260 different shifts satisfying the stated conditions. Since a shift can commence at the beginning of any of the TPs, there are 12480(= 48 × 260) possible shift schedules within a day. High scheduling flexibility results in huge number of personnel schedules. Mathematical programming formulations for solving staff scheduling problem are mostly based on the set-covering formulation of Dantzig (1954). As the set covering formulation requires the all personnel schedules, decomposition and column generation techniques through implicit formulations are commonly used to handle the situation. Implicit formulations are developed for several applications (see Thompson and Pullman (2007), Thompson (1995), Jarrah et al. (1994), Jacobs and Brusco (1996), Aykin (1996), Jacobs and Brusco (1996) and Brunner et al. (2009), andSungur et al. (2017)). Yet, the problem remains complex as the implicit formulations often result in large number of constraints (see Bellenguez-Morineau and Néron (2007) and Brunner et al. (2009)). Decomposition technique is used to breakdown the problem into stages so as to reduce the size of the problem (see Jarrah et al. (1994), Alfares (2004), Stolletz (2010) and Brunner and Stolletz (2014)). Also see Brucker et al. (2011) for a discussion on models and complexities in personnel scheduling problems.
The work in this article is closely related to three articles: (i) Stolletz (2010), (ii) Brunner and Stolletz (2014) and (iii) Volland et al. (2017). The first two of these deal with staff scheduling with given resource input, and the the third one deals with ISTSP. First, we shall brief the contributions of these articles and other works related to them. Stolletz (2010) introduced a reduced set covering formulation to solve a personnel touring problem for check-in systems at airports. His model considers a fortnightly planning horizon comprising 30-minute TPs. The staff requirements are needed only in the TPs confined to time between 4 am to 9 pm. The restrictions on the shifts are that they must start and end between 4 am and 9 pm, no breaks are allowed and their durations must be between 6 TPs to 20 TPs (i.e., between 3 hours to 10 hours).
With these restrictions, there are 330 staff schedules; and using these, the problem was solved through a binary integer programming formulation. Brunner and Stolletz (2014) expanded the scope of the problem by incorporating one period lunch break in the shifts. They report poor convergence of the column generation subroutine and introduce stabilized column generation procedure.SIP is similar to the one considered by Brunner and Stolletz (2014) but with higher complexity as it involves multiple and more flexible breaks in the shifts (12480 personnel schedules per day). Though SIP is also discontinuous (i.e., workforce is required only between 8 am to 10 pm), we considered the more general problem of continuous case, that is, staff requirements may be there in all TPs. Therefore, our model is more general and more complex, in terms of the size of the problem, compared to that of Brunner and Stolletz (2014). Stolletz and Zamorano (2014) develop a rolling planning horizon-based heuristic for the tour scheduling problem for agents with multiple skills and flexible contracts in check-in counters at airports.
When supply vector is fixed, ISTSP reduces to the well known resource constrained project scheduling problem (RCPSP) with personnel as resources. See Hartmann and Briskorn (2010) for a survey on RCPSP and its extensions. The published literature on ISTSP is limited. For applications of the problem see Beliën and Demeulemeester (2008), Maenhout and Vanhoucke (2013), Di Martinelly et al. (2014), Kim and Mehrotra (2015), Volland et al. (2017) in health sector; Beliën et al. (2013) for scheduling problem in an aircraft maintenance company; and Bassett (2000) for a scheduling problem in an agro-based industry. On the solution methods for the problem, see Alfares and Bailey (1997), Bailey et al. (1995), Bassett (2000), Beliën and Demeulemeester (2008) and Beliën et al. (2013) for some early papers on the subject. Maenhout and Vanhoucke (2016) decompose the problem into a master problem and a personnel scheduling subproblem. The personnel schedules used in the restricted master problem are generated iteratively through the personnel scheduling subproblems. Thus, the approach comprises decomposition and column generation techniques. In their model, the TPs are days, and therefore, shifts within days are not considered. Volland et al. (2017) propose an ILP formulation (referred to as MIP in their article) for ISTSP with a weekly planning horizon and develop a column generation method to derive a good starting feasible solution with a lower bound for solving the MIP. The method uses implicit formulations for two subproblems -the shift scheduling subproblem (S-SP) and the task scheduling subproblem (T-SP). The two subproblems are linked to a restricted LP relaxation of the MIP to generate personnel and task schedules. The process is continued iteratively by augmenting the restricted master problem with newly generated personnel and task schedules until the optimum objective value of the LP relaxation is attained. Let FLPR stand for the final LP relaxation. After building the (personnel and task schedule) columns of FLPR, they drop a set of task columns (by retaining only a selected set of high quality task columns) from FLPR, and add additional personnel schedule columns to it if possible, and solve it as an ILP. Taking the optimal solution of this ILP as a warm start, they solve the MIP.
Our model for ISTSP and the approach to solve it differ from those of Volland et al. (2017) in three ways: (i) breaks within shifts are more flexible (Volland et al. (2017) does not incorporate breaks), (ii) we do not use column generation approach, and (iii) we do not solve the MIP which is more complex. To get a solution for ISTSP, we decompose it into two ILP subproblems. Solving the two subproblems produces an optimal solution if the objective function depends only on the shift patterns and their positioning, and near optimal solutions if the objective is to minimize the number of workers. The decomposition scheme in our model is based on shift patterns. All shift patterns (allowing full admissible flexibility) can be listed using a simple computer program instead of deriving them through a complex traditional approach of using implicit ILP formulations. Further, we provide a lower bound for the number of workers when there is an upper limit on the number shifts per worker.

Problem description and Formulation
In this paper, we consider ISTSP over a cyclic planning horizon of one week split into T TPs of equal duration of length ω minutes (ω = 15 or 30 are considered for the instances of this paper). In staff scheduling, a personnel schedule assigns shifts to a worker over the planning horizon fulfilling work schedule restrictions. Each personnel schedule will yield a binary vector in R T with 1s representing availability of the worker, who is assigned the schedule, in the respective TPs. Sum of all assigned personnel schedule vectors is a nonnegative integer vector (the supply vector), and its j th coordinate specifies the number of available workers in TP j. On the other hand, task scheduling involves determining start TP of each task satisfying precedence relationships. This will yield a non-negative integer vector in R T (the demand vector) specifying the number of workers required in each TP. Under the considered ISTSP, the problem is to determine the personnel schedules (to be assigned to workers) and a task schedule so that the resulting supply vector is greater than or equal to the resulting demand vector. The objective is to minimize the number of assigned personnel schedules or sum of their given associated costs. See Table 1 for notation and input parameters.
The planning horizon is T = [1, 2, . . . , T ]. Given K tasks, numbered 1 through K, task k has the following inputs: (i) start window [l k , u k ] in which the task must start, where l k , u k ∈ T with l k ≤ u k , (ii) d k , duration of the task specified as the number of TPs, and (iii) the resource vector r k = (r k1 , r k2 , . . . , r kd k ), where r kj is the number of workers required in the j th TP of task k, j = 1, 2, . . . , d k . For the precedence relationships among tasks, the input is a set of task pairs P. If (k, k ) ∈ P, it means task k should precede task k . We use the notation k ≺ k to imply that (k, k ) ∈ P.
For the staff scheduling, the following inputs/flexibility types are considered: (i) shifts with or without breaks (as specified) having length between a specified minimum (SL min ) and a maximum (SL max ), (ii) shift start window is the range of TPs within a day during which a shift can start, (iii) gap between any two successive shifts assigned to a worker in terms of number of TPs must be greater than or equal to a specified lower limit SG min , and (iv) an upper limit either on the number of shifts or total hours assigned to Parameters T number of time periods in the planning horizon K Number of tasks q number of shift patterns l k earliest start period of task k u k latest start period of task k d k duration of task k in number of TPs τ number of shift schedules from stage 1, = ij x ij r k = (r k1 , r k2 , . . . , r kd k ) demand vector of task k, where r kj is the number of workers required in the j th TP of task k SL min /SL max minimum/maximum limits on the length of a shift SG min minimum gap (in number of TPs) to be maintained between two successive shifts s = (s 1 , s 2 , . . . , s m ) shift pattern of length m TPs, s 1 , . . . , s m are worker availabilities in the appropriate TPs (s i , j) shift schedule, shift pattern s i starting at TP j

Sets and vectors
T is the planning horizon and T is the number of TPs [l k , u k ] start time window of task k S = {s 1 , . . . , s q } set of shift patterns P set of task pairs, (k, k ) ∈ P means k ≺ k , that is, task k must be completed before starting task k R = (R 1 , R 2 , . . . , R T ) t the demand vector, R j = the number of workers required in TP j S = (S 1 , S 2 , . . . , S T ) t the supply vector, S j = the number of workers available in TP j U 1 , U 2 , . . . , U τ assigned shift schedules from stage 1 arranged in the ascending order of their start TPs Variables y kj indicator variable which is one if task k is assigned to TP j x ij number of shift schedules (s i , j) (determined in stage 1 and assigned to x ij workers in stage 2) z uv indicator variable, = 1 if U v is assigned to worker u any worker in the week. Note that (ii) above is pertinent to certain specific instances. For example, the 330 shifts referred to in Stolletz (2010) must start between 4 am and 6:30 pm but it depends on the shift length as well; the start window for a 3-hour shift is 4 am to 6:30 pm, and start window for a 3.5 hour length shift is 4 am to 6 pm, and so on. Even in the case of SIP, no shift can start from 10 pm to 8 am (from Fig. 1 it can be observed that there is no demand during this period).
The traditional approach to handle ISTSP with flexible schedules is to use implicit formulations and iterative methods using column generation techniques. In Volland et al. (2017), a staff schedule is implicitly formulated for the entire planning horizon combining shifts and their assignment. In order to mitigate the complexity, Stolletz (2010) used a reduced set covering formulation where predetermined daily shifts are implicitly embedded in the planning horizon. In this paper, we reduce the complexity further. We present a two-stage approach to solve this problem directly without using implicit formulations for shift patterns, iterative procedures and the column generation techniques. We achieve this by using shift patterns as the key to the entire planning. We first define shift pattern formally.

What is a shift Pattern?
A shift pattern of length m is a binary m-vector that satisfies all the shift constraints such as SL min ≤ m ≤ SL max and the shift break period rules. We shall denote a shift pattern by s = (s 1 , s 2 , . . . , s m ).

What is a shift schedule?
A shift schedule, denoted by (s, t), is a combination of a shift pattern s and a TP t. A shift schedule is used to specify that a worker who is assigned (s, t) must start a fresh shift at TP t and work according to shift pattern s. The t in (s, t) may be specified relative to a day (in this case, t ranges from 1 to 48 with ω = 30) or relative to the entire planning horizon (in this case, t ranges from 1 to 336 with ω = 30). In our models in this paper, t is relative to the entire planning horizon. Stolletz (2010) used shift schedules relative to day and generated 330 of them. The shift patterns (embedded in his shift schedules) have only 1s as their coordinates (as no break periods are considered) and their lengths vary from 6 to 20. Similarly, in the model used by Volland et al. (2017), there are 25 underlying shift patterns containing only 1s as their coordinates (as no break periods are considered). For SIP, we have 260 shifts patterns because we consider tea and lunch breaks. Each of these patterns can be described using shift patterns of length 18 with exactly fourteen 1s, two consecutive 0s and two 0.5s. For example, s = (1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0.5, 1, 1, 0.5, 1, 1, 1, 1). The two 0s (s 5 and s 6 ) stand for a lunch break and the two 0.5s (s 11 and s 14 ) stand for the two tea breaks 1 . The numbers 0, 0.5 and 1 are the proportions of a TP that a worker is available. It must be noted that these shift patterns can be generated implicitly through ILP formulations but that becomes very complicated. Instead, we can use a simple computer program to generate all the shift patterns effortlessly as we did for this problem.
We are now ready to present our two-stage solution method for ISTSP. The basic idea is that we first determine the shift schedules in stage 1, and assign them to workers in stage 2. The stage 1 problem is described in Section 3.1 and stage 2 in Section 3.2.

Shift Pattern Subproblem -Stage 1
In this stage we consider two sets of decision variables. The first set of decision variables assigns the TPs to task starting times. The second set of variables decide the number of shift patterns assigned to TPs so as to meet the required workforce demands. These decisions yield the supply of workforce in each TP, and the two sets of decision variables are linked through supply-demand constraints. The objective function of the problem will be taken as the cost of shifts.
Let S = {s i : i = 1, 2, . . . , q} be the set of all shift patterns and let m i be the length of s i , i = 1, 2, . . . , q. Let y kj be 1 if task k starts in TP j, and equal to 0 otherwise. Let x ij be the number of shift schedules (s i , j), i = 1, 2, . . . , q and j ∈ T .
Similarly, X = (x ij ) induces a supply vector S = (S 1 , S 2 , . . . , S T ) t , where S j is the number of workers available in TP j. The expression for S j is given by where s i = (s i 1 , . . . , s i mi ) and θ(·) is the wrap function defined above.
Let c ij be the cost of shift schedule (s i , j). Then our stage 1 problem for ISTSP, corresponding TP.
is given by T j=1 y kj = 1 for k = 1, 2, . . . , K, x ij s are nonnegative integers for all i, j.
Above, (4) is the supply-demand constraints, (5) takes care of the precedence relationships, (6) and (7) ensure that all tasks start in their designated start windows [l k , u k ] 2 . The objective function is the total cost of assigned shifts.
Remark 3.1. If we change the objective function of (3) to q i=1 mi t=1 s i t x iθ(j−t+1) , the total supply, and minimize it, then we will be minimizing the over cover (=total supply minus total demand) because the total demand is a constant that does not depend on task scheduling.

Staff Assignment Problem -Stage 2
From stage 1 solution, we have the shift schedules that will meet the staff demand requirements satisfying the shift constraints. We now assign these shift schedules to workers, maintaining staff scheduling constraints involving minimum/maximum number of shifts/hours per worker, days-off per worker, etc. The stage 2 formulation requires preparation of inputs. This process will be described first.
From stage 1 output, collect all shift schedules (s i , j) for which x ij > 0 and sort them according to the ascending order of j. The number of such shift schedules is τ = ij x ij . Let U 1 = (s i1 , j 1 ), U 2 = (s i2 , j 2 ), . . . , U τ = (s iτ , j τ ) be the τ shift schedules. Note that j 1 ≤ j 2 ≤ . . . ≤ j τ , and a shift schedule (s i , j) with corresponding x ij is repeated x ij times in the list.
Choose a large positive integer w representing maximum number of workers available for scheduling during the planning horizon. Label the workers as 1, 2, . . . , w. Define the decision variables of stage 2 as follows: z uv = 1 if worker u is assigned shift schedule U v , z uv = 0 otherwise, u = 1, 2, . . . , w, v = 1, 2, . . . , τ .
In order to meet the supply-demand constraints, we must assign each of the τ shift schedules to workers. Note that f (v) = w u=1 uz uv is worker label to which shift schedule v is assigned to. Therefore, stage 2 objective function is max v f (v) which we minimize to minimize the number of workers. This objective function is linearized by introducing a dummy variable ξ and a constraint as follows.
Next, we formulate the constraints of stage 2 problem.
Assignment Constraints: Each of U 1 to U τ must be assigned to workers. This translates to w u=1 z uv = 1 for v = 1, 2, . . . , τ.
Maximum number of shifts: Suppose a worker can have at most b shifts in the planning horizon. This translates to τ v=1 z uv ≤ b, for u = 1, 2, . . . , w.
Rest period: Rest period, the gap between any two successive shifts assigned to a worker, must be at least g TPs. For this, we first define a overlapping pair of shift schedules To ensure rest period, any worker can be assigned at most one of U v and U v if (v, v ) is a overlapping pair. This translates to z uv + z uv ≤ 1 for every u and every overlapping pair (v, v ).
Total Hours: The total time of any worker must not exceed H TPs. Note that τ v=1 m iv z uv is the total duration, in number of TPs, of worker u over the planning horizon. Therefore, the constraints are τ v=1 m iv z uv ≤ H, u = 1, 2, . . . , w.
Days-Off: We shall assume that day-off must start from the first TP of a day. In a 5-day week, a worker must get two consecutive days off. We shall formulate the constraints taking ω = 30 and one week planning horizon (we can imitate the same for other values of ω). Constraints for a 6-day week can be derived in a similar fashion. A two-day period can be represented by the shift patterns withs i = 1 for i = 1, 2, . . . , 96. Introduce dummy shift schedules U v = (s, j v ), v = τ +1, . . . , τ +7, where j 1 , j 2 , . . . , j 7 are the starting TPs of days 1 to 7 respectively (i.e., j 1 = 1, j 2 = 49, j 3 = 97, and so on). With an abuse of convention, we shall interpret the dummy shift schedules as days-off. That is, z u(τ +1) = 1 will be interpreted as worker u having first two days of the week off. Interpret z u(τ +2) = 1 as 2nd and 3rd days of the week off, and so on. With this, the two-days-off constraints for worker u, u = 1, 2, . . . , w, can be written as τ +7 v=τ +1 z uv = 1, and for every overlapping pair(v, v ) Thus, constraints for stage 2 problem can be picked from (12) to (17) depending upon the context, and perhaps can be augmented with some more if necessary.
Optimality of solutions obtained by the two-stage method (TSM) depends upon the nature of objective function. The following theorems are useful in this regard.
Theorem 3.1. If the objective function of ISTSP is a function of shift schedules, then the two-stage method produces an optimal solution.
Proof. Suppose the objective function of the ISTSP is a function of shift schedules. Assume that the problem has an optimal solution. Solving the Stage I of the two-stage method, we obtain for the original minimization problem, an optimal number of shift schedules and a minimum cost associated with the shift schedules. As the Stage II problem minimizes the number of workers in the organization, it does not affect the total number of shift schedules to be assigned to the workers, i.e., the Stage I solution.
As the feasible region for the stage I problem is the same as the feasible region for the ISTSP, the two-stage method produces an optimal solution.
Theorem 3.2. If the objective of ISTSP is to minimize the number of workers with one of the constraints as 13, then B b is a lower bound for the number of workers, where B is any lower bound for stage 1 objective function, the number of shift schedules assigned.
Proof. Suppose, the objective of ISTSP is to minimize the total number of workers and the number of shifts that can be assigned to a worker is limited by b (constraint 13). The two-stage method in this case may not provide an optimal solution, however, we can compute a lower bound to the optimal solution. As a maximum of b shift schedules can be assigned to each worker, assume the best case scenario. That is, each worker in the organization can be assigned b shift schedules out of B obtained in Stage I, without overlap. This gives a lower bound, B b to the number of workers in the organization.
One of the factors that appears to have a significant bearing on the solution time of ISTSP is the total demand j R j . In the existing literature, the problem instances are classified as small, medium and large based on this factor. We introduce a split technique to handle problems with large demands. It has a cascading effect on reducing the solution time of ISTSPs with large demands.

The Split Technique
Consider an ISTSP and suppose that R is a demand vector that is optimal or near optimal. We split the demand vector R into sum of two new demand vectors R 1 and R 2 so that R = R 1 + R 2 . Then, we solve two new subproblems with fixed demand vectors R 1 and R 2 separately using the two-stage approach and combine the solution to get a solution to the original problem. If w 1 and w 2 are optimal (or near optimal) objective values of the two subproblems, then we have a solution for the ISTSP with w 1 + w 2 workers. We shall explain this approach with the help of some examples. Table 3) is a problem with fixed R (no task scheduling) and has a total demand 3736 worker-hours. Solving this using twostage method, stage 1 was solved to near optimality in 32 seconds with a lower bound of 499; but stage 2 got abandoned due to insufficient memory. Then, we solved the two subproblems taking R 1 j = Rj 2 and R 2 j = R j − R 1 j , j = 1, 2, . . . , 336. The resulting subproblems have demands 1836 (for R 1 ) and 1900 (for R 2 ). Solving these two problems using two-stage method yielded the following results. The R 1 -subproblem resulted in a near optimal solution (in 201 seconds) with 52 workers, and the R 2 -subproblem resulted in a near optimal solution (in 198 seconds) with 54 workers. Combining the solutions of the two subproblems, we have a solution to the original problem with 106 workers. From Theorem 3.2, 100 (= 499 5 ) is a lower bound for the problem. Therefore, the solution with 106 workers is at least 94% (= 100 − 106−100 100 × 100) optimal, and the problem is solved in less than 7 minutes.

How to solve faster?
Consider a case where the total demand is so large that even after splitting the demand vector, we still have a problem. Even for such cases, we solve only two subproblems to get a solution. Consider the problem with a total demand of 5136 worker-hours (see P20 in Table 3). For this problem, we take R 1 j = Rj 3 and R 2 j = R j − 2R 1 j 3 , j = 1, 2, . . . , 336. With this, the demands for R 1 and R 2 subproblems are 1669 and 1798 worker-hours respectively. Note that R = 2R 1 + R 2 . Solving the two subproblems, we found a solution for R 1 -subproblem with 57 workers, and for R 2 -subproblem with 58 workers. To obtain a solution for the original problem, we apply the solution of R 1 -subproblem to two sets of 57 workers each, and apply the solution of R 2 -subproblem to another set of 58 workers. The resulting allocation is a solution to the original problem with 172 (= 2×57+58) workers. To find the optimality percentage, we use the lower bound of the stage 1 problem with original demand vector. For the instance in question, the stage 1 problem with the original demand vector with demand of 5136 worker-hours produced an optimal solution (in 2 seconds) with 852 shift schedules. From Theorem 3.2, the number of workers is at least 171, and hence the solution obtained using split technique is at least 98.8% optimal. The whole process took 6 minutes and 22 seconds.
Consider another instance with a total demand of 5615 worker-hours (P21 in Table 3). Splitting R = 2R 1 + R 2 with R 1 = R 3 and solving this problem took 10 minutes 18 seconds. The number of workers in this case is 183 and the lower bound from stage 1 solution is 181 (stage 1 took 2 seconds). Taking R = 3R 1 + R 2 with R 1 = R 4 and solving this problem (P22) took only 4 minutes 2 seconds. The number of workers in the resulting solution is 182. In general, we can use R 1 = R ρ , where the splitting factor ρ > 1. Choosing large ρ will reduce the solution time but will affect the optimality. Therefore, we should choose ρ judiciously.
Remark 3.2. Under the split technique, we solve only two subproblems with demand vectors R 1 and R 2 and use the solutions to derive a solution to the original problem.
Remark 3.3. The split technique is found to be very effective in solving problems with large demands. However, this method requires the demand vector R. For problems of ISTSP, the optimal demand vector is to be obtained first in order to apply the split technique. It must be noted that stage 1 of our approach produces optimal or near optimal demand vector R very efficiently even for the cases where the demand is very high (see Table 3). Thus, our two stage approach clubbed with the split technique (if needed) can solve ISTSPs even with large demands very efficiently.
Based on our empirical experience, we make the following proposition.
Proposition 3.1. The total demand does not appear to be a factor that affects the complexity of ISTSP.

Live Instances and Numerical Experiments
In this section we assess the performance of the two-stage approach clubbed with split technique (where necessary) with a number of live and simulated instances. For this, we consider two categories of problems. The first one corresponds to the type of problems considered in Stolletz (2010) and Brunner and Stolletz (2014) where the tasks are already scheduled and we have a demand vector R as input to the problem. The second category of problems corresponds to the type of problems dealt with in Volland et al. (2017) where both tasks and shifts have to be scheduled, that is, proper ISTSPs. The live instances for the first category are taken from requirements from software industry, airport checkin counter staff requirements and call center data. For the second category of problems, we use simulated data. For the purpose of comparison, the data are simulated using the distributions specified in Volland et al. (2017) as well as some new distributions. We also have one live data from emergency medical services (108 service in India) for this category. For the first category of problems, we consider ω = 30 and T = 336, and for the second category, ω = 15 and T = 672. All problems are treated with cyclic planning horizon.

Types of shift patterns
For our numerical experiments, we considered four types of shift patterns described below. The first three of them are used in problems with ω = 30 and T = 336. The fourth one, FX29, is used in problems with ω = 15 and T = 672.   In all, we solved 40 instances (see tables 3 and 4). All problems are solved using the LINGO professional solver Version 13.0 on an i7 64-bit processor with 2.80GHz clock speed and 16 GB RAM running on a Windows 10 platform. Unless specified otherwise, the objective for all the problems is taken as minimizing the number of workers. The instances are described in the following subsections. Their results are discussed in Section 5.

The Software Industry Problem
The background of this problem was described at the beginning of Section 2. For this problem, ω = 30, T = 336, q = 260, m i = m = 18 for i = 1, 2, . . . , q. This problem is similar to the discontinuous tour scheduling problem of Stolletz (2010). There is no demand during the periods 10pm to 8am on all days. For an instance of this problem, the total demand is 1258 worker-hours (see P1 in Table 3), and the number of workers required over TPs varies from 0 to 25 (see Fig. 1) with an average of 6.4 workers per TP. The problem is solved using FX260 shift patterns without imposing any restriction on the start times of shift patterns. Additional restrictions imposed on the problem are: (i) at most 5 shifts per worker and (ii) at least 12 hours gap between any two successive shifts of any worker. For simplicity, we have not imposed the day-offs to be consecutive.
The stage 1 problem was solved in 11 seconds with an optimum objective value of 220 shift schedules. Stage 2 problem was solved in 77 seconds with the optimum objective value of 44 workers. Since this objective value is equal to the lower bound (44 = 220 5 ), the solution is optimal for the problem.

Airport Check-in Counter Requirement Problem
In this problem, we consider agent requirements to man the check-in counters. Airline departures over a season (spanning about 6 months) are planned in advance based on weekly roster. The number of counters allocated to each airline varies over time depending on the departures of that airline. In Lalita et al. (2020), these requirements were worked out for various airlines' schedules from a major international airport in India. The weekly departures of an airline gives rise to agent requirements over the week. Taking domestic and international departures separately of three airlines, coded as JAW, AAW and BAW, we formed five demand vectors for JAW-I, JAW-D, BAW-I, BAW-D and AAW-D. From these, we derived 10 instances by combining them with the three shift pattern types FX260, FL15 and FL135, objective function type and the type of constraint on the worker load. These 10 instances correspond to P2 to P15 in Table 3. For example, P2 instance is formed by taking the departures of BAW-I, FX260 shift patterns, worker-load constraint as the maximum number of shifts per worker in the week and the objective function as the number of workers. For details of other instances, see the note under Table 3. P7 to P10 correspond to the instance but solved under different constraints and different objective functions (see Fig 3). The demands vary from 608 to 3752 agent-hours (see Table 3). Unlike the discontinuous tour scheduling problem considered in Stolletz (2010), P2 to P15 have continuous requirements over the planning horizon.
We shall discuss the results of our approach of solving two instances -P4 and P5 with demands 3736 and 1467 agent-hours respectively. Assuming that the agents can start their shifts at the beginning of every half hour, the requirements were computed based on 30-minute TPs for weekly planned departures. Fig 2 presents the demand patterns for the two problems.
Note that Stolletz (2010) starts with 330 shift schedules (per day) and uses them in his model to obtain staff schedules over the entire planning horizon. For problems with FX260, ω = 30 and T = 336, there are 12480(= 260 × 48) shift schedules per day. Brunner and Stolletz (2014) observed that with one flexible lunch break, the number of shift schedules (per day) rises to 2690 and point out that they were not able to solve the problem with their model using standard MIP software. The major difference between the two problems (P4 and P5) and the discontinuous tour scheduling problem considered in Stolletz (2010) is the continuous requirement of agents over the planning horizon. With FX260 patterns and continuous requirements over one week cyclic planning horizon, the number of possible shifts combinations per worker is approximately 10 19 . The results of solving the two problems, P4 and P5, are summarized below.

Instance P5
The total demand for this problem is 1467 agent-hours. The stage 1 model for this problem produced a solution with 227 shift schedules in 59 seconds with a lower bound 1 of 224 on the objective function. The best objective value remained at 227 even after five minutes CPU running time. We aborted the solver and took the solution with 227 shift schedules and solved stage 2 problem. This produced an optimal solution in 78 seconds with 46 agents. Applying Theorem 3.2 on the lower bound 224, the number of agents must be at least 45. Therefore, solution obtained for this problem with 46 agents is at least 97.7% optimal.

Instance P4
Recall the discussion about this problem under the introduction of split technique. While solving stage 2 model for this problem, the solver aborted the solution process reporting insufficient memory. We observed this phenomenon whenever we tried to solve stage 2 problem with huge demand. The reason is that high demand requires large number of shift schedules which in turn results in large number of overlapping shift schedule pairs. As a result, the number of constraints under (14) increases dramatically (for this problem the number of constraints is 5054445 and the number of variables is 87041). Applying the split technique, this problem was solved in less than 7 minutes and the optimality gap is at most 6%.

Instances with cost objective and work load constraints
Since there are shifts with short lengths, we solved stage 2 problem once with the constraint on the number of shifts per week per worker (maximum 5 shifts) and once with the constraint on maximum number of worker-hours per week per worker (maximum 50 hours). Again, with respect to objective function, we have two options, number of workers and cost. Thus, we have four combinations which are represented by instances P7 to P10 (see Fig 3). For simplicity, cost is taken as a function of shift duration alone. We took the costs as shown in

Call Center Data
We have data on number of agents worked, hour-wise, for 36 weeks from a call center. Like in check-in counters problem, the requirement of agents is round the clock. We combined two weeks (14 days) data to form an instance. For simplicity, we treat the hourly requirements as requirements for 30 minute periods. Data are taken from two different streams with total demand varying from large to very large. There are six instances, P16 to P21 in Table 3. The variation in the demand pattern is shown in Figure 4. The total demands vary from 2155 to 5615 agent-hours. As demands are high, all the six instances had to be solved using split technique. The results are summarized in Table 3. The solutions to these instances demonstrate the efficacy of the split technique. Since P21 took a long time (10 minutes and 18 seconds), we solved this problem again (P22) with R = 3R 1 + R 2 and R 1 = R 4 (see Section 3.3). As a result, the problem could be solved in less than 5 minutes.

Instances for ISTSP
In this section we describe the data for instances on ISTSP which requires task scheduling as well. We have one live data set from emergency medical services (108 service). For the other instances, P23 to P40 of Table 4, data are simulated following Volland et al. (2017). All instances under this case are solved assuming FX29 patterns.

Medical emergency data (P41)
We have historical data on the 108 service pertaining to a province in Andhra Pradesh, India. The service brings patients needing emergency medical care to a hospital. The most commonly reported emergencies (about 70% of the cases) are related to pregnancy, acute abdomen, trauma (vehicular), fevers (infections) and cardiac/cardio vascular issues. Of these, pregnancy cases alone accounted for 23%. Therefore, we took data (number of patients arriving in every 15 minutes) on pregnancy cases for one week (7 consecutive days) of a month. There were 588 such cases. We took the duration of redressal of these cases (tasks) to the nearest 15 minutes, and used the seriousness of the cases to set the start windows and the precedence relations. We took the earliest start time of a task as the arrival TP of the patient, and set the latest start time based on the seriousness of the case. The resulting instance has the following characteristics: K = 588, T = 672, ω = 15, maximum width of start window of task that is not involved in precedence relationships is 4ω, total demand is 1151 worker-hours ( 672 j=1 R j = 4603); number of tasks involved in precedence relationships is 116 with a total of 113 precedence relationships. The demand pattern is shown in Fig. 5. The stage 1 model for this problem produced a near optimal solution with objective value of 118 shift schedules in 119 seconds with a lower bound of 116. We terminated stage 1 at this time and solved stage 2 problem which produced an optimal solution in 235 seconds with optimum objective value of 37 workers. Applying Theorem 3.2 on the lower bound 116, the minimum number of workers is at least 24. In order to find a better lower bound, we took the stage 1 objective function as max j R j and minimized it. The optimum objective value for this was 26. Therefore, the number of workers for this problem cannot be less than 26. We then solved stage 1 problem once again with the original objective function but this time by adding an additional constraint max j R j ≤ 26. This resulted in the same objective value and lower bound as before (118/116) but the solution was different. The resulting solution was used to solve stage 2 problem, and that produced a global optimum objective value of 36 workers. Thus, the final solution was at least 62% (= 100 − 36−26 26 × 100) optimal.

Simulated data
We simulated data for ISTSP following the procedure described in Section 5.2.2 of Volland et al. (2017). Under this procedure, three types of tasks (day long, peak and precedence) and three problem sizes (small (600 hours), medium (1000 hours) and large (1400 hours)) are considered. For each size, three different distributions of task types (S1, S2 and S3) were used. The parameters for simulation are summarized in Table 2. Thus, there are nine scenarios under this situation. We simulated nine instances, P23 to P31 of Table 4, following the procedure for these nine parameter settings. The corresponding instances from Volland et al. (2017) are listed in Table 5. We ignored the additional instances considered by Volland et al. (2017) (presented in Table 5 of their paper) because those instances are more restricted (either shift patterns are limited to two or start window lengths are reduced by 50%). We simulated the nine instances using the same shift patterns used in Volland et al. (2017), namely FL29 shift patterns. Additionally, we created nine more instances by considering three more distributions Table 2: Parameters for simulation of instances for ISTSP for the three types of tasks, say S4, S5 and S6. These distributions are (81, 17, 2), (79, 17, 4) and (72, 16, 12). These are the resulting distributions if we apply the S1, S2, S3 distributions to number of tasks instead of applying them to number of hours. These additional 9 instances are P32 to P40 in Table 4. Besides the differences in the distributions, one major difference between the two sets, P23 to P31 and P32 to P40, is that in the latter the task start time windows of all tasks have been chosen uniformly throughout the days. However, we have not changed the characteristics of the start window widths and task durations.

Summary of Experimental Results
In this section we shall present the results of our numerical experiments. We have solved 39 problem instances and the results are summarised in Tables 3 and 4. Table 3 presents the results of problems with fixed demand vector where task scheduling is not required. These problems are similar to the ones considered in Stolletz (2010) and Brunner and Stolletz (2014). Table 4 presents the results for problems with task scheduling requirements involving precedence relationships. These problems are similar to the ones considered in Volland et al. (2017). The parameters affecting the complexity of ISTSP are: (i) the length of planning horizon T , (ii) number of tasks, K, (iii) demand and its pattern (d i s, r ik s), (iv) number of precedence relationships and (v) number of shift patterns. The range of these parameters in our instances are such that the results can be compared with the results of the respective papers mentioned above.
To assess the merit of any solution, we consider four parameters: the total demand, solution time, optimality metric and utilization metric. For problems where task scheduling is involved, one should also look at the number of tasks involved in the precedence relationships and the number of precedence relations. Total demand, expressed as total number of worker-hours required, is equal to ( j R j )ω/60. For any solution with objective value O s and lower bound O L , the percentage optimality gap is at most × 100 as the measure of optimality. Utilization metric is taken as 100 times the ratio of total demand to total supply. Stage 1 model plays a crucial role in our solution approach. We shall first discuss the results with respect to stage 1 problems.

Results for stage 1 model
In order to apply split technique for large demands in the case of ISTSP, solving stage l model efficiently is crucial (see Remark 3.3). Fortunately, our experiments show that stage 1 model is solved very efficiently despite the fact that it is more complex in the case of problems involving task scheduling with precedence relationships compared to those for which the demand vector is an input. Fig.6 presents the stage 1 model performance. All solutions are at least 96% optimal (65% are 100% optimal), and found in less than two minutes (with one exception which took 228 seconds). Average demand is 2117 worker-hours. It should be noted that the high demand instances took smaller times (see tables 3 and 4).

Results of problem instances with given demand vector
Instances of P1 to P22 are under this category. For each of these instances, ω = 30, T = 336 and the demand varies from 608 to 5615 worker-hours. For all instances with demand (number of worker-hours) less than 1500, we could get solution directly. For the other  Table 3: Results for staff scheduling problem instances Note: P1 is SIP, P2 to P15 are check-in counter problems and P16 to P21 are call center problems. For all problems, P1 to P21, with the exception of P8 and P10, the worker load constraint is on the number of shifts, that is, each worker is assigned a maximum of 5 shifts; for P8 and P10, it is on the number of hours, a maximum of 50 hours per week. Similarly, for all patterns other than P9 and P10, the objective function is number of workers, and for P9 and P10, it is the cost. P11 and P12 are same instance but solved differently. Likewise, P20 and P21 are same instance but solved differently. The columns under Stage 2 present the size of the problem for the stage 2 problem with the original demand vector.
instances, minimum demand is above 2000. For these instances, the problems had to be solved using the spit technique (see the discussion under Instance P4 on page 17). The method used ('Direct' or 'Split(ρ)') is specified in Table 3. Instance P11 is solved twice with ρ = 3, 4. In both cases, the solutions are near optimal (95% and 98%), and the solution times are also close (75 and 81 seconds). Similarly, P21 was solved twice with ρ = 3, 4. Split(3) took 618 seconds and split(4) took 242 seconds. In both cases, the solutions are at least 99% optimal. The necessity for splitting is arising from large demand. To highlight this, the number of variables and constraints of stage 2 model with the original demand vector are presented in Table 3. From the table, it can be seen that for the instances solved with split technique, the number of constraints ranges from 1.7 millions to 16.8 millions. The performance metrics of two stage method (with split technique where needed) as applied to instances of P1 to P22 are presented in the last three columns of Table 3 and in Fig.7. In all but two of the instances, the optimality was at least 94%. In one case, P7, it is 86% and in the other case, P8, it is 63%. The optimality metric µ for P8 is computed using a poor lower bound, namely total demand by the maximum number of hours that a worker can be assigned (recall that P8 constraints are based on maximum number of hours and not the number of shifts, see Fig.3). The average solution time is 2 minutes 40 seconds and the average utilization is 79%. Stolletz (2010) reports the solution times for three different cases. Though our case (continuous demand) is more complex, a comparison is presented in Fig.8 with respect to solution times.

Results of ISTSP problem instances
Instances P23 to P41 are under this category. Task scheduling is a part of the problem. Results are presented in Table 4. For these problems, ω = 15 and T = 672, number of tasks K varies from 100 to 588, and the demand varies from 450 to 3032 with an Table 4: Results for ISTSP instances average of 1266 worker-hours. Instances P23 to P40 are simulated, and P41 is based on a live problem. All simulated instances with the exception of P30 have been solved to optimality by the two stage method (without the need for split technique). The solution to P30 is at least 95% optimal. Utilization in the solutions varied from 75% to 98% with an average of 85%. Solution times varied from 13 to 427 seconds with an average of 111 seconds. The solution for the instance with live data (P41) is at least 58% optimal but the utilization is 98%. The demand for this problem is 1151 workerhours and it took 354 seconds to solve. Fig.9 presents the performance of two stage method. We shall compare the performance of the two stage method with that of Volland et al. (2017). For this, we use the results of instances P23 to P31. Since we do not have the data used in Volland et al. (2017), we use the simulation approach. Recall that instances P23 to P31 are simulated following the procedure stated in Volland et al. (2017). It must be pointed out that the comparison is not based on exact instances but on similar instances. Table 5 presents the one-to-one correspondence between the two sets of problem instances along with respective solution times. The solution times for Volland et al. (2017) are taken from their article. Both methods produced optimal  Note: t total is the total time extracted Table 5 of Volland et al. (2017); t T SM is the total solution time by two stage method (TSM) taken from Table 4. Comparison is made based on similar but not the same instances.

Conclusion
In this article, we considered the integrated staff and task scheduling problem. The problem is hard to solve even for a predetermined task schedule. Several authors have considered the problem and proposed column generation methods to solve. In this article, we proposed a two stage approach to the problem and introduced the split technique to handle problems with large demands. We have demonstrated the efficacy of the two stage method with split technique through a number of numerical experiments in reducing solution times dramatically. In the existing literature, solution methods are assessed at different demand sizes such as small, medium and large. Through the split technique introduced in this article, we are able to handle problems with large demands efficiently. This raises a question that whether demand size has any influence on the complexity of the problem. This point needs to be explored theoretically. Another direction for future research is extending the methods introduced in this article to multi- skill personnel staff scheduling problems.