NEW APPROACH FOR SOLVING SOFTWARE PROJECT SCHEDULING PROBLEM USING DIFFERENTIAL EVOLUTION ALGORITHM

NEW APPROACH FOR SOLVING SOFTWARE PROJECT SCHEDULING PROBLEM USING DIFFERENTIAL EVOLUTION ALGORITHM

• 1.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 DOI:10.5121/ijfcst.2015.5101 1 NEW APPROACH FOR SOLVING SOFTWARE PROJECT SCHEDULING PROBLEM USING DIFFERENTIAL EVOLUTION ALGORITHM Maghsoud Amiri1 and Javad Pashaei Barbin2 1 Assistant Professor, Department of Industrial Management, Faculty of Management and Accounting, Allameh Tabatabaei University, Tehran, Iran 2 Department of Computer Engineering, Naghadeh Branch, Islamic Azad University, Naghadeh, Iran ABSTRACT Software Project Scheduling Problem (SPSP) is one of the most critical issues in developing software. The major factor in completing the software project consistent with planned cost and schedule is implementing accurate and true scheduling. The subject of SPSP is an important topic which in software projects development and management should be considered over other topics and software project development must be done on it. SPSP usually includes resources planning, cost estimates, staffing and cost control. Therefore, it is necessary for SPSP use an algorithmic that with considering of costs and limited resources can estimate optimal time for completion of the project. Simultaneously reduce of time and cost in software projects development is very vital and necessary. The meta-heuristic algorithms has good performance in SPSP in recent years. When software projects factors are vague and incomplete, cost based scheduling models based on meta-heuristic algorithms can look better at scheduling. This algorithm works based on the Collective Intelligence and using the fitness function, it has more accurate ability for SPSP. In this paper, Differential Evolution (DE) algorithm is used to optimize SPSP. Experimental results show that the proposed model has better performance than Genetic Algorithm (GA). KEYWORDS Software Project Scheduling Problem, Differential Evolution, Genetic Algorithm. 1. INTRODUCTION Management and control of software projects based on software engineering standards ensures that the process of implementation of tasks in teams and allocating resources to them perform based on the project application plan and Project Manager in case of observing non-compliance in the implementation process takes corrective actions. Using SPSP cause Project Manager to have strong support for making various decisions throughout the software development cycle. Also the project manager, analysis, designer, and other software development people know how much money and time they need for developing a software project. Without having a suitable scheduling program of time and fee for software projects, the project manager cannot identify how much time and fee need for implementing project and in the case of fault, the project encounters risk or definite fail [1]. SPSP is an important step in the software development process and it is used for the analysis of resources, time and overall project navigation [2]. Setting time dependence for doing a series of related tasks that are forming project in terms of cost is very important. In SPSP, the main aim is
• 2.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 2 the allocation of resources to tasks and sub-activities of the project which this resource can be hardware, software, and human resource. Many classic models, like PERT [3], CPM [4], and GERT [5] have presented for SPSP by researchers. Project manager using the classical model cannot have accurate and reliable scheduling from final status of software projects in terms of time and cost required to complete projects. In the classical models, scheduling factors are usually obtained from experimental data of various projects and previous projects. The performance of these models is carried based on relationships between projects and changes in relationships of tasks leads to several changes in the amount of time. An incorrect value of cost factors may cause major changes in the final results of SPSP. Therefore, in this paper we will evaluate the factors affecting the timing and scheduling of the project using the algorithm DE [6] and will gain more accurate time for SPSP and will compare the results with GA [7]. In software engineering, the issue of SPSP is very important because the human resources and funding must be optimally managed so that the project is terminated successfully. In recent years, much research has been done in the field of SPSP using meta-heuristic algorithms. Today, using the meta-heuristic algorithm has been more common in the optimization of the method of solving the complex problems [8, 9 and 10]. The GA is used to solve SPSP [7]. Assessment is done from various aspects such as start and end times of each project, the project's overall time and total cost of the project. The experimental results show that the GA algorithm has good performances in estimating the cost and time. Ant Colony Optimization (ACO) algorithm is used for SPSP [11]. One of the most important issues in software project management is choosing the best solution for each project constituent tasks, in the case that the end time and cost of the project have the possible least amount of them. Due to the large number of tasks and the solution of choice for any activity, usually this choice has not a unique answer, but will be formed a set of answers. None of the solutions are preferred over others. On the other hand, in actual projects, usually predicted costs to perform tasks normally associated with uncertainty which lead to considerable changes in the cost of the finished project. In classical methods for project scheduling, project's time reduction is in a higher priority than cost. But, in many cases, reducing the time of project causes the increase of cost. They made vast the scheduling search space with presenting the ACO algorithm of the process of scheduling, and also because the performance of ACO algorithm is well shown, its results have been compared with GA algorithms and in many cases ACO algorithms find optimal or near optimal mood. Our overall structure of this paper is organized as follows: in Section 2, we will study SPSP; in Section 3, we will describe the DE algorithm; in Section 4, we will present the proposed model; in Section 5, we will discuss the evaluation and results and finally in Section 6, we will study the conclusions and future works. 2. SOFTWARE PROJECT SCHEDULING PROBLEM Scheduling is setting a sequence of time-dependent functions to perform a set of dependent tasks that make up a project [12]. Dependence of tasks is very important in terms of priority and precedence. So it is possible that doing a task related to doing some tasks which in this case, it is said that project contains priority limitations. Determining a scheduling program has been done with considering the purpose or specified purposes. Almost, there are priorities limitations between tasks in all of the projects, but in addition to this limitations may be there is another kind of limitations between tasks based on resource limitations. So in project scheduling in addition to considering priority limitations, scheduling should be done in such a way as to be consistent with resource constraints. In SPSP, considering a set of applications such as resources and so on are required for tasks. The main factors affecting the SPSP has been shown in Table (1) [7].
• 3.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 3 Table 1. Parameters Affecting the SPSP } ,..., , { | | 2 1 SK s s s SK  Set of skills required in the project management } ,..., , { | | 2 1 TK t t t TK  Set of task } ,..., , { | | 2 1 EM e e e EM  Set of employee V= TK Set of Vertex (task) for TPG in project Scheduling )} , ),...( , ( ), , {( 4 3 2 1 n m t t t t t t A  Set of arc(precedence relation between task) G(V,A) TPG (Task Precedence Graph) in Project Scheduling effort j t Workload of task tj which is in PM (Person-Month) SK tskills j  Set of Required skills of task tj SK eskills i  Set of Skills Of employee ei salary i e The monthly salary of employee ei Maxed i e The Maximum Dedication Of employee ei to task tj start j t Start time of task tj end j t End time of task tj t j tcos Cost of task tj duration j t Duration of task tj duration p Total Duration of Software Project Cost p Total Cost of Software Project Over p Total overwork of Whole Software Project Over i e Overwork of Employee ei T E ij m M   ) ( Solution Matrix of SPSP SPSP is an important step in the software development process and it is used for the analysis of time and resources and the overall guide of the project. In the project scheduling problem, the main aim is the allocation of resources to activities and tasks of the projects on which this resource can be hardware, software and human resource. The goal is optimally allocating resources so that with regarding precedence relationships among tasks, completion time and costs are reduced. Start and end time of each task is done using equations (1) and (2).         else A t t t A t t j k if t j k end k j k start j } ) , ( max{ ) , ( , 0 ) 1 ( duration j start j end j t t t   ) 2 ( The evaluation of execution time of each task is calculated using equation (3).    E i ij effort j duration j m t t 1 ) 3 (
• 4.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 4 The evaluation of execution time of the project is carried out using equation (4). A t t j k t p k j end j duration     ) , ( max{ ) 4 ( Estimating costs for each task is carried out using equation (5). duration j ij E i salary i t j t m e t . . 1 cos    ) 5 ( Estimating the costs of all the project tasks is carried out using equation (6).    T j t j t t p 1 cos cos ) 6 ( Employee performance is done using equations (7, 8 and 9). dt e t e ramp e ded i p t t work i over i duration ) ) ( ( max 0      ) 7 (       0 0 0 ) ( , ifx ifx x x ramp where ) 8 (     end j start j t t t j ij work i m t e { ) ( ) 9 ( Estimating overall task for software projects is done using equation (10).    E i over i over e p 1 ) 10 ( In Figure (1) the number of employees and the cost of each of them for doing software projects are shown in [7]. Figure 1. Factors Affecting the Project In Figure (2), the tasks, relationships between tasks and their performing timing and amount of needed resources to perform each of them in different moods has been shown [7].
• 5.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 5 Figure 2. Display of the Tasks and their Relationships 3. DIFFERENTIAL EVOLUTION ALGORITHM The algorithm DE is of meta-heuristic algorithm which was invented in 1995 [6]. DE algorithm is a population-based probabilistic search algorithm which solves optimization problems. This algorithm using the distance and direction information from the current population carries out the search operations. The advantages of this algorithm are speed, setting the parameters, its effectiveness in finding optimal solutions, being parallel, high accuracy and lack of need to sorting or matrix multiplication. DE Algorithm in order to find the optimal solutions, has the ability to efficiently search the process in the direction of coordinate axes of optimistic variables and also changes in the direction of the coordinate axes in the right direction. DE Algorithm starts the evolutionary search process from a random initial population. Three operators of mutation and selection, and the integration and three control parameters, including the number of population, scale factor and the possibility of integration are very important in the DE algorithm. DE algorithm processes are as follows: Initial Population Generation: in DE algorithm, the initial population with solution vectors is randomly chosen from the problem range. The vector of solutions position is defined according to equation (11). ) ,..., , ( , 2 , 1 , D i i i i x x x X  ) 11 ( ] , 1 [ ], , 1 [ ) ).( 1 , 0 ( min max min D k Np i with x x rand x x k k k ik      ) 12 ( Selection of random numbers ik x from the domain is carried out using equation (12). In equation (12) D is equal to the dimension of the solutions. Np is the initial population. The function of ) 1 , 0 ( rand Random generated random numbers (with uniform distribution) in the interval of (0, 1). Obviously, in the case of using equation (12), obtained values will be for ik x in the range of ] , [ min max i i x x and the vector position of each potential solution is a potential answer to the optimal problem. Mutation Operator: in the mutation phase, three vectors are chosen randomly and mutually. For any vector X in the population, a new solution is generated in each repetition according to equation (13). ) .( , 3 , 2 , 1 1 , G r G r G r G i x x F x v     (13)
• 6.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 6 In equation (13), 3 2 1 , , r r r which are three unequal random numbers are in the interval ] , 1 [ Np . G is the number of generated generation. And F factor is a real, positive and constant number which is often considered to be 0.5. Crossover Operator: crossover operator will increase diversity in the population. This operator is the same as crossover operator in GA [13]. In crossover operator, new vectors are generated with x and v composition according to equation (14).          otherwise x j j or CR r if v u G ji rand j G ji G ji 1 , 1 , 1 , ) ( ) 14 ( In equation (14), CR parameter is in the range [0, 1). Parameter of j r in the range [0, 1] is randomly generated. Also the value of j is ; ,..., 2 , 1 D j  . Selection Operator: in order to select the vectors with the highest fitness, the vectors generated by the mutation and integration operators can be compared and each of them which have more fitness is transferred to the next generation. The selection operator is carried out by equation (15). ) , ( , 1 , 1 , G i G i G i x u Value Fitness x    (15) Stopping Criteria: the search process continues until a stopping criterion is met. Usually, the algorithm's stopping criterion can be the best solution or the algorithm's iteration based on consistency of fitness changes. 4. PROPOSED MODEL There is the probability of error in software project scheduling in classical models and as a result, estimating project cost and time in software projects is difficult. In classical models scheduling affecting values , are not known values, but are considered according to the average and previous projects and therefore cannot easily ensure to the estimated values. Relationships between factors in SPSP have an important impact on project success. For software projects can be create balances among the factors of time and cost and can predict the accurate cost for the software projects. It is ideal for project managers that the project's actual completion time is not significantly increased than the delivery time. On the other hand, it is possible that the condition of some projects may be in the case that under the existence of any variation in the onset time of some activities, the considerable cost be forced on the project's system. In this context, applying an efficient algorithm for finding the optimal solution would be highly desirable. For SPSP can be utilized several algorithms. In this paper we have used the DE for SPSP. SPSP is that at the beginning of software development, detailed information of the operation of system, the project scope and tasks is not available. Therefore, in this paper, we try to minimize different sources for software development such as hardware, software and staffing software using DE. In Figure (3) the Flowchart of the proposed model using DE algorithm is shown.
• 7.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 7 Figure 3. Flowchart of the Proposed Model In Figure (4), quasi code of the proposed model is shown. Figure 4. Quasi Code of the Proposed Model. In the proposed model, calculated the fitness of each vector based on the cost. Then we ordered them based on the obtained value for each vector, and we chose the best vectors which have the least cost and do the mutation and integration operation in order to optimize the vectors. Thus, if the most optimal schedule is not optimal, the mutation and crossover operation over the tasks causes changing tasks operation and the most appropriate solution can be provided for scheduling of activities. In fact, with changing the way of doing various activities and searching among scheduling application forms in any mode of activity, the most optimal schedule program in the output is displayed. In the proposed model, to perform the tasks at any time, an appropriate combination for the resource is selected. 5. EVALUATION AND RESULTS In this section the results obtained from the proposed model has been evaluated with GA [7]. In meta-heuristic algorithms, determining initial parameters is very important to evaluate the results. 1. Begin 2. Initialize Parameters 3. Evaluation 4. Repeat Selection Crossover Selection 5. Train Data 6. Compute operational costs 7. Evaluate Fitness 8. Until (not terminate condition) 9. Evaluation Criteria 10. Display Results
• 8.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 8 Therefore, the meta-heuristic algorithms were very sensitive to its parameters and parameter settings can have a significant impact on their performance. Therefore, parameter setting can result in greater flexibility and efficiency of the proposed model. In meta-heuristic algorithm, selection of populations is very important. If the number of population is low, the problem is suffering from premature convergence and we won't be reach to the desired response and close to the global optimum and if the population is large, much time is needed to reach the convergence of the algorithm. Therefore, the number of issues should be in appropriate limit and in proportion with desired problems in order to achieve the optimal solution. In Table (2) the parameters that most affect the performance of the proposed model are demonstrated. Table 2. Parameter Values Values Parameters 100 No. Population 0.2 Mutation 0.5 Crossover 1.5 F Randomize Selection 50 Generation In Table (3) we have evaluated and compared Employees criterion of the project. The results in Table (3) show that the proposed model when compared with the GA criteria has reduced average time criteria and the number of employees in performing the tasks. Table 3. The Evaluation of Employees Criteria Proposed Model GA [7] Iteration Employees dur P E Avg  . Avg. duration dur P E Avg  . Avg. duration 103.40 20.68 109.40 21.88 87 5 102.30 10.23 112.70 11.27 65 10 128.40 8.56 115.95 7.73 49 15 102.2 5.11 117.60 5.88 51 20 In Table (4) we have evaluated and compared project Skills criteria. Results in Table (4) show that the proposed model in comparison with the GA criteria has reduced average time criteria and cost. Therefore the proposed model is useful for timing and has less error than the GA. Table 4. The Evaluation of Skills Criteria Proposed Model GA [7] Iteration Skills dur t P P Avg / cos . Avg. duration dur t P P Avg / cos . Avg. duration 44,878.72 21.88 45,230.15 21.71 39 2 46,427.73 21.15 45,068.64 21.77 53 4 46,515.70 21.11 44,651.28 21.98 77 6 43,525.99 22.56 44,617.02 22.00 66 8 43,295.70 22.68 44,426.90 22.11 75 10 In SPSP the effective index in cost and time should have optimal state in order to apply the exact timing of the project. Therefore the algorithms must be used that do the tasks in less time and with greater accuracy, and in finding the least resources have good performance.
• 9.
  International Journal inFoundations of Computer Science & Technology (IJFCST), Vol.5, No.1, January 2015 9 6. CONCLUSIONS AND FUTURE WORKS In this paper we have evaluated SPSP using DE. In SPSP, the aim is determining the appropriate timing for allocating resources to tasks in such a way that the overall cost of the project and completion time is optimal. In SPSP, the cost factor for the sake of implementing the project tasks makes the situation of task more complicated due to interdependence of tasks and estimating the time of their implementation. To demonstrate the effectiveness of the proposed model we used a sample of project that was previously estimated using GA. The main objective of this work is to demonstrate the ability of the proposed model in accurate convergence to optimal solutions. The results obtained from implementation showed that the proposed model compared with GA has better performance and has less error. We hope that in the future with presenting this research make optimal the average of time criterion of doing tasks and the cost of tasks using other meta-heuristic algorithms. REFERENCES [1] M.Lu,H.Li,“Resource Activity Critical Path Method for Construction Planning”,Journal of Construction Engineering and Management,Vol.129,No.4, pp.412-420,2003. [2] F.Lunaa,D.L.Gonzalez-Alvarezb,F.Chicanoc,M.A.Vega-Rodríguez,“The Software Project Scheduling Problem: A Scalability Analysis of Multi-Objective Metaheuristics”,Applied Soft Computing,2013. [3] R.J.Freeman,A generalized PERT,Operations Research,Vol.8,No.2,1960. [4] J.E.Kelley Jr.,“Critical path planning and scheduling,mathematical basis,Operations Research,Vol.9,No.3,pp.296-320,1961. [5] W.Fix,K.Neumann,Karlsruhe,“Project Scheduling by Special GERT Networks”Computing,Vol.23,pp. 299-308,Springer-Verlag,1979. [6] R.Storn,K.Price,“Minimizing the Real Functions of the ICEC’96 Contest by Differential Evolution”,International Conference on Evolutionary Computation,Nagoya,Japan,1995. [7] E.Alba,J.F.Chicano,“Software project management with GAs”,Information Sciences,Vol.177,No.11,pp.2380-401,2007. [8] I.Maleki,S.R.Khaze,M.M.Tabrizi,A.Bagherinia,“A New Approach for Area Coverage Problem in Wireless Sensor Network with Hybrid Particle Swarm Optimization and Differential Evolution Algorithms”,International Journal of Mobile Network Communications & Telematics(IJMNCT),Vol.3,No.6,pp.61-75,December2013. [9] F.S.Gharehhopogh,I.Maleki,M.Farahmandian,“New Approach for Solving Dynamic Traveling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization”, International Journal of Computer Applications (IJCA),Vol.53,No.1,pp.39-44,2012. [10] I.Maleki,A.Ghaffari,M.Masdari,“A New Approach for Software Cost Estimation with Hybrid Genetic Algorithm and Ant Colony Optimization”,International Journal of Innovation and Applied Studies,Vol.5,No.1,pp.72-81,2014. [11] J.Xiao,Xian-TingAo,Y.Tang,“Solving Software Project Scheduling Problems with Ant Colony Optimization”,Computers & Operations Research,Vol.40,pp.33-46,2013. [12] A.Mingozzi,V.Maniezzo,S. Ricciardelli,L.Bianco,“An Exact Algorithm for Project Scheduling with Resource Constraints Based on a New Mathematical Formulation”,Management Science,Vol.44,No.5,pp.714-729,1998. [13] J.Holland,“Adaptation in Natural and Artificial Systems”,University of Michigan,Michigan,USA,1975.