Integrated Project Scheduling and Staff Assignment with Controllable Processing Times

Research Article Integrated Project Scheduling and Staff Assignment with Controllable Processing Times Victor Fernandez-Viagas and Jose M. Framinan IndustrialManagement,SchoolofEngineering,UniversityofSeville,CaminodelosDescubrimientos,s/n,41092Seville,Spain Correspondence should be addressed to Victor Fernandez-Viagas; vferna[email protected] Received 11 January 2014; Accepted 19 February 2014; Published 24 April 2014 Academic Editors: J. G. Barbosa and D. Oron Copyright © 2014 V. Fernandez-Viagas and J. M. Framinan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. This paper addresses a decision problem related to simultaneously scheduling the tasks in a project and assigning the staff to these tasks, taking into account that a task can be performed only by employees with certain skills, and that the length of each task depends on the number of employees assigned. This type of problems usually appears in service companies, where both tasks scheduling and staff assignment are closely related. An integer programming model for the problem is proposed, together with some extensions to cope with different situations. Additionally, the advantages of the controllable processing times approach are compared with the fixed processing times. Due to the complexity of the integrated model, a simple GRASP algorithm is implemented in order to obtain good, approximate solutions in short computation times. 1. Introduction The lead time required to carry out a project—project makespan—has turned to be one of the main sources of competitive advantage for companies (see, e.g., [1,2]). Since, in many cases, the processing times of the tasks that compose a project depend on the resources allocated to the task (see, e.g., [3]), it is clear that the project lead time depends both on the scheduling of the tasks and on the allocation of staff to these tasks. Regarding task scheduling, it encompasses thesequencetobefollowedbyeachtaskovertime,andit is usually regarded as an important aspect of the industrial organization [4]andproduction[5]. On the other hand, staff assignment is essential in a project [6]anditcanbe defined as the allocation of company workers to different tasks. Traditionally, staff assignment is included within the manpower planning as one of its steps. Thus, several authors [7–10] have considered the following structure: (1)planning; (2)scheduling; (3)allocation. In staff assignment, worker’s satisfaction tends to be maximized whereas makespan and production costs are often minimized in task scheduling. To execute a task, it is essential that a particular employee is available at that time; otherwise the realization of such task should be postponed until the employee becomes available and, consequently, staff assignment directly influences task schedule. Due to the importance of the scheduling and the assignment in a project environment and since both are very related, it is critical to address both problems in an integrated manner. Furthermore, the majority of scheduling problems in the literature consider fixed processing times [11] and most of the rest assume that processing times depend linearly on the amount of resources assigned [12]. As lead times strongly depend on the processing times of the task, and since the processing time of a task depends on the number of employees assigned to this task, in this paper we explicitly take into account this relationship. In this paper, an integration of project scheduling and staff assignment (PSSA) problem with controllable processing times (CPT) is presented using renewable resources and nonpreemptive tasks. Minimization of the makespan has been chosen as the objective function since delays can lead to an increase in costs and even to the loss of customers. This problem can be placed within the project management process. According to Demeulemeester and Herroelen [13], theprojectlifecycleisasfollows. Hindawi Publishing Corporation e Scientific World Journal Volume 2014, Article ID 924120, 16 pages http://dx.doi.org/10.1155/2014/924120 2The Scientific World Journal Table 1: Names for the integrated problem. Reference Name used for the integrated problem Bellenguez and N´ eron [14], Bellenguez-Morineau and N  eron [15] Multiskill project scheduling problem Brucker and Knust [16], Drezet and Billaut [17] Project scheduling with labor constraints Vairaktarakis [18] Resource-constrained job assignment problem Valls et al. [19] Skilled workforce project scheduling Corominas et al. [20]Problem of assigning and scheduling a set of tasks to a set of workers Drexl [21] Scheduling of project networks by job assignment Dodin and Elimam [22] Problem of audit staff scheduling HeimerlandKolisch[23], Kolisch and Heimerl [24], Gutjahr et al. [25], and Gutjahr et al. [26]Project scheduling and staffing Wu and Sun [27] Project scheduling and staff assignment (i) Concept Phase. There is a need of a customer to perform a project. This need is transmitted to the company. (ii) Definition Phase.First,thegoaloftheprojectis defined. Next, the work content is defined and, finally, a project strategy is elaborated to achieve the goal. (iii) Planning Phase. The project is divided into tasks. Then, their processing times are estimated and both the resources requirements and the precedence relationships between tasks are identified. (iv) Scheduling Phase.Bothtaskschedulingandthe amount of resources in each period of time are defined in this phase (v) Control Phase. In this phase it is controlled that the project is implemented following the aspects defined intheplanningandschedulingphases. (vi) Termination Phase. This phase corresponds to the delivery of the results of the project. Note that between the scheduling phase (where the amount of resources is known) and the control phase there must be an assignment of resources to the tasks if the resources are not identical. For these cases, an additional phase is therefore needed. This phase—named “resources assignment phase”—must be placed between the scheduling phase and the control phase. Alternatively, integration between the scheduling and the resources assignment phases can be done. The latter is the adopted approach in this paper, which is organized as follows: a state of the art and a description of the problem are shown in Section 2.An extended explanation of the CPT is also presented, while the problem statement and a formulation of the integer linear programming model are shown in Section 3. Additionally this integer linear programming model is compared with a multimode formulation. In Section 4, we define a simple GRASP heuristic algorithm for the problem. Section 5 contains computational experiments based on a test bed. Besides, a comparison between the model with and without CPT is shown there. Lastly, conclusions are described in Section 6. 2. Literature Review The model presented in this paper includes two decision problems: task scheduling and staff assignment. Task scheduling is traditionally denoted in the literature as project scheduling problem (PSP). Furthermore, if limitations regarding the number of resources per activity are assumed, it is named resource-constraint project scheduling problem (RCPSP). This problem has been extensively studied in the literature, and recent reviews can be found in Węglarz et al. [32]andHartmannandBriskorn[33]. Staff assignment is a type of assignment decision problem that has also been extensively addressed [34]. Nevertheless, the integration between project scheduling and staff assignment has not been so comprehensively studied, and hence there is still no consensusaboutthenameofthisjointproblem(seeinTable 1 differentnamesthathavebeenusedtodenotetheproblem). Inourwork,weconsiderthename“projectschedulingand staff assignment” as denomination for the problem. Our problem is related to several contributions in the literature, which are summarized in Table 2.Bassett[29] presents a model of project scheduling and staff assignment considering time windows for the completion times of the tasks. Vairaktarakis [18] adds precedence relationships to the integrated problem. However, no time units are used in the linear programming model (the order of the tasks defines the schedule of the project). Time units are included in a similar problem by Bellenguez and N´ eron [14] and Bellenguez- Morineau and N´ eron [15] where some lower bounds are calculated in the former reference, while in the latter the authors implement a branch and bound algorithm. External and internal resources constraints are considered by Kolisch and Heimerl [24]. Wu and Sun [27] present the integrated problem proposing a nonlinear model, which is solved by a genetic algorithm. Although learning effect (i.e., the longer an employee works on a task, the greater his/her efficiency is) is considered in the model, neither precedence relationships nor skill constraints are used in their model. Gutjahr et al. [26] consider portfolio selection and skills in the integrated problem with learning effect but with precedence relationship which are included by Gutjahr et al. [25]. Precedence relationships are also included by Corominas et al. [20]inan The Scientific World Journal 3 Table 2: Summary of related papers. Project sched. Staff assign. Prec. relations Release time Due dates Preemp.- nonPreemp. Learning effect CPTSkill CPT𝑁∘of workers Move const. Outsourcing staff Project selection Resources per task Skill Objective function Exact methods and solvers Aprox. alg. Alfares and Bailey [28]XGlobal X X NP Data1Cost 2Heuristic Bassett [29]XX XNP 1 X Cost CPLEX Heuristic Bellenguez and N´ eron [14]XX X NP nXMakespan Branch and bound Bellenguez- Morineau and N´ eron [15] XX X NP nXMakespan Lower bound Corominas et al. [20]X X X X P X 1 Makespan CPLEX Dodin and Elimam [22]XX X NP Data11CostLindo Drexl [21]XXX NP Data11Cost Branch and bound Monte Carlo Drezet and Billaut [17]XX X XX NP X nXLatenessCPLEXTabusearch Gutjahr et al. [25]X X X X X P X X n XMultiobjectiveCPLEX Greedy procedure Gutjahr et al. [26]X X X X P X X n XMultiobjectiveCPLEX NSGA-II and P-ACO Hachicha et al. [30]X Data1Cost and preference Lingo Heimerl and Kolisch [31]XX Non Linear XCost COIN-OR’s Ipopt Kolisch and Heimerl [24]XX X XX NP X nX Cost CPLEX Genetic alg. and tabu search Valls et al. [19] X X X X X NP Linear 1 X Multiobjective Genetic alg. Vairaktarakis [18]X X X 1XMakespan Lower bound Heuristics Wu and Sun [27] X X X P X X 1 Cost CPLEX Genetic alg. This paper X X X X NP Piecewise linear X n X Makespan CPLEX Gurobi GRASP 1Processing times are preprocessed depending on the number of assigned employees or on the level of skills of the assigned employee(s) and then they are introduced in the model as data. 2An integer programming model is solved, although the way to do it is not explained. 4The Scientific World Journal integrated problem, similar to the problem of Wu and Sun [27], also with learning effect. Drezet and Billaut [17]propose alinearprogrammingmodelforaprojectschedulingandstaff assignment problem. However, they do not consider learning effects in the model and include move constraints (i.e., the number of assignment movements of the employees from one nonfinished task to another is bounded). Moreover, the number of employees assigned to each task at each period of time is set between a minimum and a maximum depending on the level of skills of the workers. However, the processing times of the tasks are assumed to be fixed and not depending on the number of employees assigned. Since no solutions can be found for medium-sized instances of the problem, a tabu search algorithm was implemented using a greedy algorithm as initial solution. A common feature in all the aforementioned works is that none of them include variable processing times. Regarding CPT, Hachicha et al. [30]proposeastaffassignment model considering multiskilled employees, preference of the employees for some tasks, and skill-based processing times (i.e., the processing times of the tasks depend on the skills of the employee). Nevertheless, they are preprocessed before solving the model, which means that the processing times do not change during the planning horizon. More specifically, processing times are first calculated depending on the skills ofeachemployeeandthenintroducedinthemodelas data. Heimerl and Kolisch [31]analyzeastaffassignment problem without scheduling considering learning effect on the employees, so the processing times are now variables of the problem as they depend on the experience of the staff. In order to solve this problem, a nonlinear model is implemented. Hachicha et al. [30] and Heimerl and Kolisch [31] use CPT in their models, although none of them solve the integrated problem (only the staff assignment problem). Variable processing times in a scheduling problem can be found in Alfares and Bailey [28]. They use a linear programmingmodeltoschedulethetaskofaprojectandtoassignthe number of employees to each task; that is, the variables of the problem are the starting times of each task, the processing times, and the number of employees per period. Regarding the processing times, they are chosen to minimize the costs, but they do not depend on any variable. Moreover, staff assignment for each employee is not considered there. CPT in an integrated PSSA problem are considered in Drexl [21], Dodin and Elimam [22]withtheobjectiveof costs minimization. However, in their models, the processing times depend on the skills of the employee assigned (and consequently are introduced in the model as data), but not on the amount of resources allocated; that is, processing times aredefinedbyamatrixoftwodimensionswheretherows are the processing times of the tasks and the columns the employees. In Valls et al. [19], each task has to be performed by a single employee and its processing time increases or decreases depending on the efficiency of the employee. Nonpreemptive tasks with release times and due dates are taken into account, as well as precedence relations with time lags. No programming model is implemented, but a hybrid genetic algorithm is developed to solve the cost minimization problem. This contribution is the one most related to our problem, since the authors implement an integrated PSSA with CPT. However, in our paper, a linear programming model is considered to minimize the makespan of the project where the processing times of the tasks depend piecewise linearly on the number of employees assigned instead of the efficiency level of the employee and multiple assignments to each task are also allowed as well, while in Valls et al. [19] each task must be implemented by a single employee. To the best of our knowledge, the proposed model has not been analyzed before. 3. Model Proposal for the Integrated PSSA Problem 3.1. Problem Statement. This paper presents a PSSA problem in which a company is responsible for the implementation of a project consisting of 𝐽tasks (with task 𝑗 = 1,...,𝐽) with (known) precedence relations between tasks (i.e., some tasks should be finished before carrying out others). The order of execution of each task has to be decided to minimize the corresponding objective function. Each task must be performed by some workers from total of 𝐸employees (employee 𝑒=1,...,𝐸) with certain skills in each 𝑡period (𝑡=1,...,𝑇)of the planning horizon 𝑇. It is assumed that each task 𝑗has a release time 𝑟𝑗,so it must always start after this time. Furthermore, once a task starts, it runs continuously until its end (nonpreemptive approach). One employee can be assigned to a task if the employee possesses the required skills for the task. We assume that there is an optimal number of employees, 𝑅𝑗,tobe assigned to each task, although overcoverage and undercoverage of employees are allowed by the model. Under- and overcoverage would lead to different values of the efficiency of the employees and, consequently, to different processing times of the tasks. 3.2. Controllable Processing Times (CPT). In this paper, we assume that processing times depend on the resources (or employees, as we would use both terms as equivalent in this paper) assigned. Such type of processing times has been studied in the literature as a function of the resources allocated and of the experience of the workers (level of skills). The relationship between time and amount of resources has been mainly analysed under two different approaches, namely, linear and convex (see the review by [12]). In the linear approach (see, e.g., [35]), a linear relationship between the processing times of a task and the resources allocated to this task is assumed. Denoting 𝑝𝑗as the processing time of task 𝑗and 𝑢𝑗as the number of resources allocated to this task, this relationship can be expressed as 𝑝𝑗=𝑎−𝑏⋅𝑢 𝑗, with 𝑎and 𝑏constants. However, this approach is not well suited to many realistic situations, since according to Belbin [36], there must be 𝑅𝑗anoptimalnumberofemployeesto be assigned to task 𝑗in order to achieve maximum workers’ The Scientific World Journal 5 Convex c=1 0 1 2 3 Processing time Piecewise linear Number of resources u0u1u2u3 L1 L2 L3 S1 S2 S3 us1 us2 us3 p0 Figure 1: Piecewise linear relationship and convex relationship with 𝑐=1. Subscripts are removed for simplicity in the figure. efficiency (point [𝑅𝑗,𝑝𝑑𝑗]). Therefore, it is easy to see that the linear approach is not flexible to this concept, at least for values to each side of the efficiency level since the efficiency pointofworkermustalwaysbeinanextremeoftheline(see, e.g., Figure 2(a), where the efficiency point is placed for 𝑎/𝑏 resources). In the convex approach it is assumed that there is an inverse relationship between processing times and employees (see, e.g., [37]), where 𝑐and 𝑊𝑗(normally denoted workload of the task 𝑗) are constants: 𝑝𝑗=(𝑊𝑗 𝑢𝑗)𝑐.(1) For 𝑐=1, the number of resources and the processing times are inversely proportional (e.g., doubling the employees would cut the processing time by half and vice versa; see the red line of Figure 1). The convex relationship is closer to real life than the linear and it has been used for many actual government and industrial projects [38], distributed communication network, time-sharing computing system, and chemical plant or commercial construction projects [39]. Nevertheless, its nonlinearity would preclude modeling the problem using linear programming. Thus, in this paper a piecewise linear relationship to represent the relationship between processing times and amount of resources assigned to the task is proposed. The relationship is shown in (2), 𝑆𝑖 𝑗 beingtheslopeofeachsectionforatask𝑗in the piecewise linear relationship and 𝑢𝑠𝑖 𝑗the number of employees fulfilled of that task in each section, where section 𝑖has a length (𝐿𝑖𝑗). This piecewise linear relationship can be adjusted to the convex relationship (with 𝑐=1) as shown in the blue line of Figure 1. This relationship is over the convex relationship representing a safer configuration of processing times and amount of resources: 𝑝𝑗=𝑝0 𝑗+𝑆1 𝑗⋅𝑢𝑠1 𝑗+⋅⋅⋅+𝑆𝑘 𝑗⋅𝑢𝑠𝑘 𝑗, with 𝑢𝑠𝑖 𝑗=𝐿𝑖𝑗∀𝑖<𝑚 0<𝑢𝑠𝑚 𝑗<𝐿𝑖𝑗, 𝑆𝑖 𝑗=𝑝𝑖 𝑗−𝑝𝑖−1 𝑗 𝑢𝑖 𝑗−𝑢𝑖−1 𝑗. (2) The superscript for processing times, 𝑝𝑖 𝑗,andforthe amount of resources, 𝑢𝑖 𝑗, denotes that they correspond to point 𝑖. According to Lanigan [40], the convex relationships between the processing time of a task and the number of employees assigned do not entirely match the reality, and there shall be a penalty due to assigning different numbers of employees. On the one hand, if 𝑢𝑗>𝑅 𝑗,thenapenalty for communication exists. In contrast (see, e.g., [41,42]), if 𝑢𝑗<𝑅 𝑗then there is a penalty for lack of specialization [43]. Hence, each feasible point different than the optimum (𝑅𝑗,𝑝𝑑𝑗)must be placed over the convex curve; otherwise many optima would exist and there would be no penalties for under- and overcoverage. The feasible area formed by thesepointsisrepresentedbythelightredareainFigure 2(a) (this feasible area is also taken into account by [44,45]). Moreover, it shall be considered that the processing time of a task decreases when the number of employees increases; otherwise it would make no sense to assign more employees to the tasks. Thus, the feasible area can be reduced by considering that the processing time of a task cannot increase when the number of employees increases (Figure 2(b)). In this way, the feasible relationships between both aspects must be in this area. Therefore, we propose using a piecewise linear relationship with a maximum and minimum possible number of workers on each task. Depending on the maximum and minimum possible number of workers, the slopes of the lines must be different to avoid that both lines are under theconvexcurve(i.e.,intheinfeasibleregion)inanypoint. The directions of the slope of the piecewise relationships are placed in the feasible region and shown in Figure 2(c).By doingso,linearprogrammingcanbeusedtomodelandsolve the problem. Furthermore, the piecewise relationship is on thesafesidewithrespecttotheconvexrelation,sincethe piecewise relationship is always over the convex relation. To define the slopes of the lines, we propose introducing the parameters 𝑘𝑟and 𝑘𝑙. The higher these parameters are, the bigger the penalties for under- and overassignment of employees with respect to the optimal value, and consequently the closer the problem to the PSSA with fixed processing times (FPT). In the most extreme case, both problems are the same. The piecewise linear relation left and right of the optimum can be written as follows (see Figure 2(d)): Left: 𝑝𝑗=𝑝𝑑𝑗⋅(1+𝑘𝑙⋅𝑅𝑗−𝑢𝑗 𝑅𝑗) Right: 𝑝𝑗=𝑝𝑑𝑗⋅(1−𝑢𝑗−𝑅𝑗 𝑘𝑟⋅𝑅𝑗). (3) 6The Scientific World Journal Convex Linear Processing time Number of resources 1 R pd (a) Convex Linear Processing time Number of resources 2 R pd (b) Processing time Number of resources 3 R pd Convex Linear Piecewise linear (c) Convex Linear Processing time Number of resources 4 R pd Piecewise linear (d) Figure 2: Relation between processing times and number of employees (shaded area). Analogously, let us now consider 𝑅𝑗−𝑢 𝑗as ℎ+ 𝑗the undercoverage of task 𝑗and 𝑢𝑗−𝑅𝑗astheovercoverageof task 𝑗,ℎ− 𝑗: Left: 𝑝𝑗=𝑝𝑑𝑗⋅(1+𝑘𝑙⋅ℎ+ 𝑗 𝑅𝑗) Right: 𝑝𝑗=𝑝𝑑𝑗⋅(1− ℎ− 𝑗 𝑘𝑟⋅𝑅𝑗). (4) 3.3. Formulation of the Model 3.3.1. Proposed Integer Linear Programming Model. In the previous section, we have presented a mechanism for formulating a realistic relationship between the processing times of the task and the number of employees assigned. Furthermore, this relationship can be embedded into a piecewise linear function; therefore a linear programming model can be formulated for the PSSA. In this section, a formal description of this model is given. Data 𝑟𝑗: earliest starting time (release time) of task 𝑗. 𝑏𝑒𝑗 {1if the employee 𝑒can perform task 𝑗 0otherwise. 𝑝𝑟𝑖𝑗 {1iftask𝑖precedes task 𝑗 0otherwise. 𝑅𝑗: optimal number of employees of task 𝑗. 𝑝𝑑𝑗: processing time of task 𝑗for the optimal number employees 𝑅𝑗. The Scientific World Journal 7 𝐿𝑉𝑗: maximum allowed undercoverage for task 𝑗. 𝑈𝑉𝑗:maximumallowedovercoveragefortask𝑗. 𝑘𝑑,𝑘𝑛: constants related to the slopes of the lines defining the processing times. Variables 𝑥𝑗𝑡 {1iftask𝑗starts in period 𝑡 0otherwise. 𝑦𝑒𝑗𝑡 {1 if employee 𝑒performs task 𝑗during period 𝑡 0otherwise. ℎ+ 𝑗: undercoverage in task 𝑗. ℎ− 𝑗:overcoverageintask𝑗. 𝑝𝑗: processing time of task 𝑗. Auxiliary Variables 𝑧𝑗𝑡 {1iftask𝑗is being processed at the begin of period 𝑡 0otherwise. 𝑠𝑡𝑗: starting time of task 𝑗. 𝑐𝑡𝑗: completion time of task 𝑗. 𝐶max:projectmakespan. 𝑎ℎ𝑗𝑡:auxiliaryvariable.Itisusedtoenforcethat the constraint set (18) is satisfied if 𝑧𝑗𝑡 is zero since the auxiliary variable takes the value of the over- or undercoverage. Model Min 𝐶max (5) 𝑇 ∑ 𝑡=1𝑥𝑗𝑡 =1 ∀𝑗=1,...,𝐽 (6) 𝑠𝑡𝑗=𝑇 ∑ 𝑡=1𝑥𝑗𝑡 ⋅𝑡 ∀𝑗=1,...,𝐽 (7) 𝑐𝑡𝑗=𝑠𝑡𝑗+𝑝𝑗−1 ∀𝑗=1,...,𝐽 (8) 𝑠𝑡𝑗≥𝑟𝑗∀𝑗=1,...,𝐽 (9) 𝐶max ≥𝑐𝑡𝑗∀𝑗=1,...,𝐽 (10) 𝑦𝑒𝑗𝑡 ≤𝑏𝑒𝑗 ⋅𝑧𝑗𝑡 ∀𝑒=1,...,𝐸,∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (11) 𝑠𝑡𝑗−𝑠𝑡𝑖≥𝑝𝑖⋅𝑝𝑟𝑖𝑗 −𝑁⋅(1−𝑝𝑟𝑖𝑗)∀𝑖,𝑗 (12) 𝐸 ∑ 𝑒=1𝑦𝑒𝑗𝑡 +𝑎ℎ𝑗𝑡 +(ℎ+ 𝑗−ℎ− 𝑗)=𝑅𝑗⋅𝑧𝑗𝑡 ∀𝑗=1,...,𝐽, ∀𝑡=1,...,𝑇 (13) 𝑎ℎ𝑗𝑡 ≤(1−𝑧𝑗𝑡)⋅𝑁 ∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (14) 𝑎ℎ𝑗𝑡 ≥−(1−𝑧𝑗𝑡)⋅𝑁 ∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (15) ℎ+ 𝑗≤𝐿𝑉 𝑗∀𝑗=1,...,𝐽 (16) ℎ− 𝑗≤𝑈𝑉 𝑗∀𝑗=1,...,𝐽 (17) 𝐽 ∑ 𝑗=1𝑦𝑒𝑗𝑡 ≤1 ∀𝑒=1,...,𝐸,∀𝑡=1,...,𝑇 (18) 𝑝𝑗≤1 2+𝑝𝑑𝑗⋅(1− ℎ− 𝑗 𝑘𝑟⋅𝑅𝑗+𝑘𝑙⋅ℎ+ 𝑗 𝑅𝑗) ∀𝑗=1,...,𝐽 (19) 𝑝𝑗>−1 2+𝑝𝑑𝑗⋅(1− ℎ− 𝑗 𝑘𝑟⋅𝑅𝑗+𝑘𝑙⋅ℎ+ 𝑗 𝑅𝑗) ∀𝑗=1,...,𝐽 (20) 𝑇 ∑ 𝑡=1𝑧𝑗𝑡 =𝑝𝑗∀𝑗=1,...,𝐽 (21) 𝑧𝑗𝑡 ≥𝑥𝑗𝑡 ∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (22) 1−𝑧𝑗𝑡 ≥𝑡−𝑐𝑡𝑗 𝑇∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (23) 1−𝑧𝑗𝑡 ≥𝑠𝑡𝑗−𝑡 𝑇∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (24) 𝑧𝑗𝑡,𝑥𝑗𝑡 ∈{0,1},𝑎ℎ 𝑗𝑡 free ∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (25) 𝑦𝑒𝑗𝑡 ∈{0,1}∀𝑒=1,...,𝐸,∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇 (26) 𝑐𝑡𝑗,𝑠𝑡𝑗,ℎ+ 𝑗,ℎ− 𝑗,𝑝𝑗≥0 ∀𝑗=1,...,𝐽 (27) 𝐶max ≥0. (28) Objective function (5) minimizes the project makespan. Constraint set (6)guaranteesthateachtaskmuststartexactly once. Constraint sets (7)and(8) define the starting and completion times of each task, respectively. Constraint set (9) assures that a task cannot start before its release time. Constraint set (10) serves to obtain the makespan. Constraint set (11)ensureswith𝑏𝑒𝑗 =0that an employee cannot perform a task if he/she does not possess the skills required. Moreover, the variable 𝑧𝑗𝑡 is added to the constraint to preclude work at a time when the task is not being processed. Constraint set (12) establishes the precedence relationships. Constraint set (13) defines over- and undercoverage for each task at each period. The auxiliary constraint sets (14)and(15)ensurethat constraint set (13) is satisfied for every period. Constraint sets (16)and(17) limit the maximum possible under- and overcoverage, respectively. Constraint set (18)enforcesthat anemployeecanworkatmostinonetaskateachperiod. Constraint sets (19)and(20) are used to determine the CPT. Constraint set (21)forces𝑧𝑗𝑡 to be 1 if and only if task 𝑗 is active. Constraint set (22) ensures that task 𝑗must be performed (𝑧𝑗𝑡 =1)wheneveritstarts(𝑥𝑗𝑡 =1). Constraint 8The Scientific World Journal sets (23)and(24) model the nonpreemptive assumption: (23) determines that a task cannot be performed (𝑧𝑗𝑡 =0)afterits completion time, and (24)statesthatitcannotbeperformed (𝑧𝑗𝑡 =0) before its starting time. Equations (25), (26), (27), and (28) define the variables employed in the model. 3.3.2. Extension 1: Limitation of Moves. The model presented above allows moving the staff from a task to another. These moves can be detrimental for the service company since they may involve setup and learning times as well as instability in the team composition that performs each task. This limitation of moves can be easily incorporated in the model adding the following two constraints: 𝑦𝑒𝑗𝑡 ≥𝑤𝑒𝑗 −(1−𝑧𝑗𝑡) ∀𝑒=1,...,𝐸, ∀𝑗=1,...,𝐽, ∀𝑡=1,...,𝑇 (29) 𝑦𝑒𝑗𝑡 ≤𝑤𝑒𝑗 ∀𝑒=1,...,𝐸,∀𝑗=1,...,𝐽, (30) where 𝑤𝑒𝑗 yields 1 if the employee 𝑒is assigned to the task 𝑗,0 otherwise. Constraints (29)and(30)forcethatanemployee have to be assigned to the task during the whole duration of the task when 𝑤𝑒𝑗 is equal to 1. 3.3.3. Extension 2: Generic Piecewise Linear Relationship. In Section 3.2 a piecewise linear relationship with two sections was presented to model the relationship between the processing time of a task and the amount of resources assigned to such task. In order to include a generic piecewise linear relationship with ksections, the constraints (31)–(38)must replace the constraints (19)-(20): 𝑝𝑗=𝑝0 𝑗+𝑘 ∑ 𝑖=1𝑆𝑖 𝑗⋅𝑢𝑠𝑖 𝑗∀𝑗=1,...,𝐽 (31) 𝑢𝑠𝑖 𝑗≤𝑠𝑎𝑖 𝑗⋅𝐿𝑖+𝑠𝑙𝑖 𝑗⋅𝐿𝑖∀𝑖=1,...,𝑘,∀𝑗=1,...,𝐽 (32) 𝑢𝑠𝑖 𝑗>(𝑠𝑎𝑖 𝑗−1) ∀𝑖=1,...,𝑘,∀𝑗=1,...,𝐽 (33) 𝑢𝑠𝑖 𝑗<(2−𝑠𝑎𝑖 𝑗)⋅𝐿𝑖∀𝑖=1,...,𝑘,∀𝑗=1,...,𝐽 (34) 𝑢𝑠𝑖 𝑗≥𝑠𝑙𝑖 𝑗⋅𝐿𝑖∀𝑖=1,...,𝑘,∀𝑗=1,...,𝐽 (35) 𝑘 ∑ 𝑖=1𝑠𝑎𝑖 𝑗=1 ∀𝑗=1,...,𝐽 (36) 𝑠𝑎𝑖 𝑗≤𝑠𝑙𝑚 𝑗∀𝑗=1,...,𝐽,∀𝑖,𝑚 𝑚<𝑖 (37) 1−𝑠𝑎𝑖 𝑗≥𝑠𝑙𝑚 𝑗∀𝑗=1,...,𝐽,∀𝑖,𝑚 𝑚≥𝑖, (38) where 𝑠𝑎𝑖 𝑗is an auxiliary variable yielding 1 only in the section 𝑖,where𝑢𝑠𝑖 𝑗is over 0 and lower than 𝐿𝑖(represented by the constraints (33)-(34), (36)). Generic piecewise linear relationshipisdefinedinconstraint(31). 𝑠𝑙𝑚 𝑗is introduced to define with 1 the sections with 𝑢𝑠𝑖 𝑗=𝐿 𝑖,0otherwise(constraint (35)). Finally, constraint (32)delimitstheuppervalueofthe variable 𝑢𝑠𝑖 𝑗and the constraints (37)-(38)establish𝑠𝑙𝑚 𝑗=1in each section 𝑚preceding the section, where 𝑠𝑎𝑖 𝑗=1,𝑠𝑙𝑚 𝑗=0 otherwise. Thereby, any piecewise linear relationship could be considered in the model by means of these constraints. To adjust this relationship to the convex relationship with 𝑐=1, it is necessary only define the parameter 𝑆𝑖replacing the term 𝑝(𝑢)by 𝑘/𝑢in (2)(seetheslopein(39) assuming that the length 𝐿𝑖=𝐿=(𝑈𝐿−𝐿𝑉)/𝑘for each section 𝑖): 𝑆𝑖=(𝑘/(𝐿𝑉+𝐿⋅𝑖))−(𝑘/(𝐿𝑉+𝐿⋅(𝑖−1))) 𝐿.(39) 3.4. Additional Models 3.4.1. Model with Fixed Processing Times (FPT). In this section, the PSSA problem without CPT is analyzed. The goal is to compare the PSSA model with CPT (PSSA-CPT in the following) with the model with FPT (PSSA-FPT model). To the best of our knowledge, it is the first time that the PSSA problem is solved with processing times depending on the number of employees allocated, so it is relevant to assess the benefits of the assumption. Both models are similar, but there are two main changes. First, in the PSSA-FPT model, processing times do not depend on the number of employees assigned (i.e., this number is fixed and equal to the optimum). Second, over- and undercoverage are not allowed in this model; that is, ℎ+ 𝑗-, ℎ− 𝑗-, and 𝑎ℎ𝑗𝑡-related constraints are not taken into account. The constraint sets (13)–(17), (19)-(20)are then replaced by 𝐸 ∑ 𝑒=1𝑦𝑒𝑗𝑡 =𝑅𝑗⋅𝑧𝑗𝑡 ∀𝑗=1,...,𝐽,∀𝑡=1,...,𝑇. (40) Thus, the PSSA-FPT model consists of the constraint sets (6)–(12), (18), and (21)–(28), where the above 𝑝𝑗variable is now a data of the problem. Obviously, the PSSA-CPT problem is harder than the PSSA-FPT since it has more variables and constraints. It will be analyzed again in the computational results. 3.4.2. Formulation of the Model Using Discrete Time/Resource Trade-Off Problem (DTRTP) Approach with Staff Assignment. The model presented in this paper could be also modeled using a DTRTP approach adding the staff assignment and the release times constraints. However, the results found by this approach were considerably worse in computational time and in average relative percentage deviation. When both models were compared for each instance presented in Section 5.1 (several instances are shown in Table 3), only 363 optimal solutions were found using the DTRTP approach compared tothe567oftheproposedmodelandthecomputational time by the DTRTP approach presented a deviation of 287.1% over our proposed model (the deviation runtime is calculated considering only the instances which were optimal solutions found for both models; the amount of these instances is presented in the column of Table 3 denoted by “Both optimum”) as well, justifying the PSSA-CPT model proposed here. The Scientific World Journal 9 Table 3: Comparison of runtimes between models using DTRTP approach and PSSA with CPT approach. Instances DTRTP and staff assignment PSSA with CPT Both optimum Deviation runtime #O #F #N Runtime #O #F #N Runtime 30-1.5-0.25-0.2 10 0 0 54.0 10 0 0 13.1 10 380% 30-1.8-0.50-0.5 10 0 0 330.2 9 0 1 177.2 9266% 30-2.1-1.00-1.0 0010 — 901 — 0— 60-1.5-0.25-0.2 8 0 2 708 7 0 3 376.6 7135% 60-1.8-0.50-0.5 109 — 604 — 0— 60-2.1-1.00-1.0 0010 — 514 — 0— Global 363 14 583 376.08 567 20 373 165.26 345 287.1% Table 4: Some examples on the number of constraints and variables. Instances Constraints Variables Integer variables Binary variables 30-1.5-0.25-0.2 93120 65701 60661 60480 30-1.8-0.50-0.5 156330 123031 117181 117000 30-2.1-1.00-1.0 237895 204241 198871 198690 60-1.5-0.25-0.2 433887 325801 305461 305100 60-1.8-0.50-0.5 633915 529561 510661 510300 60-2.1-1.00-1.0 1427967 1286641 1262821 1262460 3.5. Complexity of the Problem. The PSSA can be reduced to the identical parallel machine problem with two machines (𝑃2 | prec, 1≤𝑝 𝑗≤2,𝐶max according to Graham et al. [46]), when 𝐸=2,𝑏𝑖𝑗 =𝑅𝑗=1,and𝐿𝑉𝑗=𝑈𝑉 𝑗=𝑟𝑗=0are considered. As this problem is NP-hard [47]andourproblem is a generalization of it, the PSSA is NP-hard. On the other hand, the constraint sets (6)–(23)approximately form a total of 9⋅𝐽+8⋅𝐽⋅𝑇+𝐸⋅𝑇+𝐸⋅𝐽⋅𝑇+𝐽⋅𝐽/2 constraints. Regarding the variables, there are 6⋅𝐽+3⋅𝐽⋅ 𝑇+𝐸⋅𝐽⋅𝑇in the model, where 2⋅𝐽⋅𝑇+𝐸⋅𝐽⋅𝑇are binary (i.e., 𝑥𝑗𝑡,𝑧𝑗𝑡,and𝑦𝑒𝑗𝑡). The number of constraints and variables is calculated in Table 4 for some instances of the test beds presented in Section 5.1. Since the PSSA with CPT is an NP-hard problem and since the number of constraints and variables for medium-large size of the problem is very high, exact solvers for integer programming problems have difficulties to find feasible and optimal solutions in such instances and therefore approximate algorithms have to be implemented. In the next section, a simple GRASP algorithm is presented to get feasible solutions in lower computational times. 4. A Simple GRASP Heuristic Algorithm Given the complexity of the problem, a greedy randomized adaptive search procedure (GRASP) is presented in this section to solve the PSSA problem with CPT. GRASP was first introduced by Feo and Resende [48]andithasbeenwidely applied to several combinatorial optimization problems. A review of the application fields of this algorithm is done in Festa and Resende [49]. The algorithm consists of two phases: first a constructive phase is implemented, and then alocalsearchphaseismadetofindbettersolutionsinthe neighborhood. The constructive phase is usually employed to find a feasible solution for the problem, while the local search phase is performed to improve the solution found in the constructive phase. Both phases are repeated until the stopping criterion is reached (see Procedure 1). In our problem, fixed processing times are considered during the constructive phase. In the local search phase, the task schedule is fixed and more employees are gradually assigned to each task in order to decrease the processing times and thus possibly improving the makespan of the project. In summary, a project scheduling problem is solved in the constructive phase, a CPT problem in the local search phase, while the staff assignment problem is treated in both phases (see Figure 3). In the next subsections the phases are explained in detail. 4.1. Constructive Phase. The constructive phase consists in the successive allocation of employees and starting times to tasks. The goal is to assign the tasks as early as possible until all tasks are scheduled. In this phase, both the processing times and the number of assigned employees are kept fixed. The number of employees allocated to each task (𝑛𝑒𝑗)is randomly assigned within the upper and lower limits. The processing times of each task are calculated for the soobtained number of employees using the expressions shown in Section 3.Withrespecttothetasktobechosenateachstep, a restricted candidate list (RCL) is defined based on the tasks’ precedence relations. According to these relations, the tasks are classified into sets: set 𝑆1corresponds to tasks without predecessors, set 𝑆2is tasks which only have predecessors of set 𝑆𝑘, and, in general, set 𝑆𝑖contains tasks with predecessors in sets 𝑆𝑖−1,𝑆𝑖−2,...,𝑆1. The tasks are iteratively inserted in the schedule according to the following procedure. First, the RCL contains all tasks in set 𝑆1. A task is randomly chosen from the RCLtobeplacedintheschedule.Theprocessisrepeateduntil the RCL is empty. Then, the tasks of set 𝑆2are moved to. The same procedure is carried out until each task is introduced in the schedule. Once a task is chosen from the RCL, it has to be placed into the schedule. To do this, the earliest possible start time for the task is calculated. Next, the starting time of the task is fixed to this earliest time and employees (from those having the required skills for the task) are assigned until the 16 The Scientific World Journal times and assignable due dates,” Computers and Operations Research,vol.29,no.10,pp.1417–1439,2002. [36] R. M. Belbin, Management Teams, Butterworth-Heinemann, Oxford,UK,3rdedition,2010. [37] D. Shabtay and M. Kaspi, “Minimizing the total weighted flow time in a single machine with controllable processing times,” Computers and Operations Research,vol.31,no.13,pp.2279– 2289, 2004. [38] C. L. Monma, A. Schrijver, M. J. Todd, and V. K. Wei, “Convex resource allocation problems on directed acyclic graphs: duality, complexity,” Special Cases, and Extensions, Mathematics of Operations Research,vol.15,pp.736–748,1990. [39] C. Lee and L. Lei, “Multiple-project scheduling with controllable project duration and hard resource constraint: some solvable cases,” Annals of Operations Research,vol.102,no.1–4, pp. 287–307, 2001. [40] M. J. Lanigan, “Task estimating: completion time versus team size,” Engineering Management Journal,vol.4,no.5,pp.212–218, 1994. [41] P. C. Pendharkar and J. A. Rodger, “An empirical study of theimpactofteamsizeonsoftwaredevelopmenteffort,” Information Technology and Management,vol.8,no.4,pp.253– 262, 2007. [42] K. G. Smith, K. A. Smith, J. D. Olian, H. P. Sims Jr, D. P. O’Bannon, and J. A. Scully, “Top management team demography and process: the role of social integration and communication,” Administrative Science Quarterly,vol.39,pp.412–438, 1994. [43] M. A. Cusumano and R. W. Selby, Microsoft Secrets,TheFree Press, New York, NY, USA, 1995. [44] E. Demeulemeester, B. de Reyck, and W. Herroelen, “The discrete time/resource trade-off problem in project networks: a branch-and-bound approach,” IIE Transactions (Institute of Industrial Engineers), vol. 32, no. 11, pp. 1059–1069, 2000. [45] M. R. Ranjbar and F. Kianfar, “Solving the discrete time/ resource trade-off problem in project scheduling with genetic algorithms,” Applied Mathematics and Computation,vol.191,no. 2, pp. 451–456, 2007. [46] R.L.Graham,E.L.Lawler,J.K.Lenstra,andA.H.G.R.Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics,vol. 5, pp. 287–326, 1979. [47] J. K. Lenstra and A. H. G. R. Kan, “Complexity of scheduling under precedence constraints,” Operations Research,vol.26,no. 1,pp.22–35,1978. [48] T. A. Feo and M. G. C. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,” Operations Research Letters,vol.8,no.2,pp.67–71,1989. [49] P. Festa and M. G. C. Resende, GRASP: An Annotated Bibliography, pp. 325–367, Kluwer Academic Publishers, Boston, Mass, USA, 2001. [50] R. Kolisch and A. Sprecher, “PSPLIB—a project scheduling problem library,” EuropeanJournalofOperationalResearch,vol. 96,no.1,pp.205–216,1997. [51] R. Kolisch, A. Sprecher, and A. Drexl, “Characterization and generation of a general class of resource-constrained project scheduling problems,” in Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems: Easy and Hard Instances, Institute for Operations Research and the Management Sciences, 1992. Submit your manuscripts at http://www.hindawi.com Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Mathematics Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Mathematical Problems in Engineering Hindawi Publishing Corporation http://www.hindawi.com Differential Equations International Journal of Volume 2014 Applied Mathematics Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Probability and Statistics Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Mathematical Physics Advances in Complex Analysis Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Optimization Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Combinatorics Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 International Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Operations Research Advances in Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Function Spaces Abstract and Applied Analysis Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 International Journal of Mathematics and Mathematical Sciences Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 The Scientific World Journal Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Algebra Discrete Dynamics in Nature and Society Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Decision Sciences Advances in Discrete Mathematics Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Stochastic Analysis International Journal of