Computers, Materials & Continua DOI:10.32604/cmc.2021.017710 | |

Article |

A Compromise Programming to Task Assignment Problem in Software Development Project

1Department of Computer and Information Sciences, Universiti Teknologi Petronas, Seri Iskandar, 32610, Malaysia

2Department of Information and Communication Technology, FPT University, Hanoi, 100000, Vietnam

3Department of Computer Science, National University of Computer and Emerging Sciences, Chiniot-Faisalabad Campus, Chiniot, 35400, Pakistan.

*Corresponding Author: Ngo Tung Son. Email: sonnt69@fe.edu.vn

Received: 08 February 2021; Accepted: 29 April 2021

Abstract: The scheduling process that aims to assign tasks to members is a difficult job in project management. It plays a prerequisite role in determining the project’s quality and sometimes winning the bidding process. This study aims to propose an approach based on multi-objective combinatorial optimization to do this automatically. The generated schedule directs the project to be completed with the shortest critical path, at the minimum cost, while maintaining its quality. There are several real-world business constraints related to human resources, the similarity of the tasks added to the optimization model, and the literature’s traditional rules. To support the decision-maker to evaluate different decision strategies, we use compromise programming to transform multi-objective optimization (MOP) into a single-objective problem. We designed a genetic algorithm scheme to solve the transformed problem. The proposed method allows the incorporation of the model as a navigator for search agents in the optimal solution search process by transferring the objective function to the agents’ fitness function. The optimizer can effectively find compromise solutions even if the user may or may not assign a priority to particular objectives. These are achieved through a combination of non-preference and preference approaches. The experimental results show that the proposed method worked well on the tested dataset.

Keywords: Makespan; RCPSP; scheduling; MOP; combinatorial optimization; compromise programming; genetic algorithm;

In software project management, scheduling plays a critical role in the success of a project. Scheduling starts with the work breakdown structure (WBS), which allows the whole project to be broken down into smaller tasks, which are assigned to project team members based on their skills and knowledge according to the working plan. In reality, projects run under constraints, including those of human resources, budget, and time. The lack of a helpful management toolset makes it difficult to achieve the goals of the shortest critical path, lowest cost, and highest quality. We develop an approach based on a multiobjective optimization model and a metaheuristic algorithm that generates an optimal project schedule to meet the above goals. Fig. 1 depicts the scheduler, which takes a list of tasks, project team members’ profiles, and decision-makers’ preferences as the model’s inputs. The output is a detailed schedule. The time to complete a project depends on the available time, the similarity of tasks, and their interdependence. These factors also affect the cost and quality of the project.

Scheduling problems that deal with workforce constraints have the form of a resource-constrained project scheduling problem (RCPSP) [1–5]. Habibi et al. classified many RCPSP problem variations and mentioned modeling and algorithms to find optimal solutions for this type of problem in a 2018 survey [6]. Vanhoucke and Coelho presented an overview of state-of-the-art RCPSP algorithms [7]. The situation described in the first section of this paper is a multiobjective problem [8]. A primary objective is to solve the makespan problem, i.e., to complete the project in the shortest duration [9]. Makespan scheduling is described as follows: Assume

The interdependence of tasks often is expressed as a directed graph. Two fake tasks, the head (task 0) and tail (task N + 1), of zero duration, are added to formulate a single started/ended graph, as shown in Fig. 2. The makespan is now computed by any traversal method, such as breadth-first search (BFS). As mentioned in Section 1.1, the makespan may be affected in several ways. The tasks’ interdependence determines the best critical path by the longest path in the graph. This constraint combines with the personnel’s sequential workload, and their schedules may increase the critical path’s length.

Among recent studies on RCPSP and its variants Kumar et al. [10] proposed an algorithm to solve the classical RCPSP and minimize the makespan. Arian [11] designed an evolution algorithm to solve RCPSP, with the objective to minimize project cost, using binary decision variables to represent the time-unit when the activities started. Laurent et al. [12] and Stiti et al. [13] introduced a variant of multiside RCPSP, considering mobile and fixed resources in the transportation system. A variant of RCPSP subjected the project to renewable resources, each available for limited periods during the project life cycle, and applied a penalty cost for keeping resources for extra periods [14]. Quoc et al. [15] introduced Real-RCPSP, a variant of MS-RCPSP, and {R-CSM}, an algorithm to solve it based on cuckoo search. Hosseinian et al. [16] tried to maximize modularity to find high-quality employee communities and arrange them for tasks based on them. Nadjafi [17] proposed a mixed-integer programming formulation of RCPSP to minimize the total project cost, considering earliness-tardiness and preemption penalties. Ahmadpour et al. [18] presented a model of RCPSP by viewing a working calendar for project members and determining the skill factor of any member using the efficiency concept. Kellenbrink et al. [19] introduced two subproblems of RCPSP, the first to select activities, and the second to minimize makespan and total cost. Joshi et al. introduced a model to minimize the makespan or entire project duration. The objective was subject to activities’ resource requirements at some finite integer value other than 1. The resources were staff members mastering one or more skills [20]. Tesch et al. [21] developed a mixed-integer programming formulation for RCPSP, improving the optimal problem-solving method over the previous approach by investigating relationships between event-based and time-indexed models.

Many other issues can arise in real-world situations, such as the division of labor in an organization, members’ concentration in different project phases, and similarities of tasks. Project managers often assume that if a worker is assigned many similar tasks, then the job’s cost will increase or decrease [22]. As in other engineering disciplines, to reuse previous work is critical to the progress and quality of software projects. In short, the more similar things a worker does the lower the cost. These aspects affect the objectives of project management.

RCPSP is combinatory optimization [23], and algorithms may not exist to find the optimal solution in polynomial time. In this case, metaheuristics have proved efficient in many case studies [24]. Tao et al. [25] introduced a procedure based on simulated annealing. Zhang et al. [26] designed a genetic algorithm with renewable resources and a single mode to perform each activity. Van et al. [27] introduced a genetic algorithm (GA) to solve both multimode and preemptive multimode RCPSP. However, most of these studies are in the form of problem-algorithm-result, and are not applicable to the proposed problem due to different business requirements. Based on results of previous studies, we construct a multiple-objective optimized mathematical model. Human resources, including skills, available time, salary, and task similarity, are constrained, in addition to constraints such as budget and deadline. We design a genetic algorithm to solve the model.

In this research, we designed a new multi-objective optimization model for RCPSP problems that applies to software development in addition to our case study. It may be helpful in other task scheduling and project management work. Our model generates a detailed project schedule. The aim is to complete a project with the shortest duration while maintaining quality at a reasonable cost. It expresses the significant considerations of the decision-makers in the planning process. The model introduces some new rules related to human resources essential to software project management (and other engineering areas). We combine the preferred and non-preference approaches to transform the multi objective problem to a single-objective problem. Both methods have advantages and disadvantages and are suitable for different decision-makers. They are combined to leverage their benefits and cover each other’s drawbacks. Section 2 of this paper describes the model.

The second contribution is to propose a new GA to solve the model. Unlike the usual mathematical programming or heuristic approach, the proposed method allows incorporation of the MOP approach in the algorithm design. To guide individuals in the search process, we use a distance-based objective function as their fitness. Section 3 describes the algorithm’s implementation. The experimental procedure on the real dataset and its results are discussed in Section 4. We relate our conclusions in Section 5. Researchers in scheduling, planning, project administration, operations, and management can benefit from this research.

2 Multi-Objective Optimization Model

We define some frequently used variables:

•

•

•

•

•

•

•

•

•

•

•

•

•

• Decision variables:

The project has three objectives:

• Minimize the critical path/makespan:

Factors such as the concentration of members and similarity between tasks affect the time to complete the task.

• Minimize the cost of hiring team members:

• Maximize the experience of selected candidates. Experience dramatically affects the quality of the project. The more experienced the candidate the less likely are errors:

subject to:

• All tasks are assigned to members:

• A task is assigned to only one member:

• A member does not simultaneously perform two tasks:

• Dependent tasks cannot be executed at the same time:

• A task is assigned to the only member who qualifies:

• The project ends on time:

• Costs do not exceed the budget:

Ignizio said there is no one best approach to all types of multiobjective mathematical programming problems [28]. Solutions to multiobjective optimization problems (MOPs) are categorized as either preference or non-preference [29]. The first approach is to use preference information archived by interviewing the decision-maker to determine the solution that best satisfies these preferences. The second approach assumes that no decision-maker was available, and that we can identify a compromise solution without preference information. Decision-makers often cannot determine priorities, which leads them to try many parameters and select one of several solutions. It is challenging in practice to define meaningful ranges of parameters. The computational cost of a search algorithm is a barrier to finding appropriate parameter values to determine a final solution. Compromise programming allows a one-shot solution.

Compromise programming can solve the above problem by identifying an ideal solution [30] as a point of reference and finding a solution as close as possible to the ideal point. Ngo et al. [31] applied it to their MOP, introducing the concepts of “deep” and “wide” to access the skills of candidate teams. Xiong et al. [32] proposed two levels of compromise programming to allocate resources between pavement and bridge deck maintenance. Poff et al. [33] used compromise programming to represent 20 objective functions to determine the preferred decision variable value and assign a closeness level to an ideal solution. Ngo et al. [34] introduced CP as the difference between the perfect and actual points to solve a multiobjective timetabling problem, and tried to answer strategic questions as decision-makers in simple terms. In such a situation, we answer three questions, and we believe a decision-maker would do the same. What is the earliest time the project can be completed? The shorter the better. What is the lowest cost? The lower the better. At what level should the project quality be? The higher the better.

The answers above can represent the decision-maker’s aspirations when unable to define any preferred objectives.

Instead of maintaining the three goals of the original MOP, we have just the goal to find the point

Many situations can occur during project planning. We need to assign a priority to each goal. The considered problem has three targets, which can be graphically visualized to better realize the effects of strategies. This is hard to achieve with compromise programming, although it is straightforward to explain that the decision-maker wants to balance goals. Another approach is to scalarize a MOP, i.e., to formulate a single-objective optimization problem whose solutions are Pareto optimal solutions to the MOP. The original multiobjective functions are scalarized and written as

where the

3.1 Introduction to Genetic Algorithm

Evolutionary algorithms (EA) are mainstream stochastic methods for MOP [36]. In the family of EA, genetic algorithms (GA) are popular choices for engineering applications [37]. It starts searching for the optimal solutions in solution space by forming a population/set of possible solutions. Then new solutions are created by breeding the best fitness individual from the population to generate the new generation. Over the iterations, the population retains the best genetic hybridization combined with mutations to create a better next generation. GA gives a guideline for solving the problem. However, each issue needs a different scheme design. In this study, we introduce a version of the GA to solve the MOP model.

Denote:

•

• G denotes the convergence condition.

•

•

where:

•

• Our proposed genetic algorithm’s scheme described as following:

• Initialize

•

•

The Genetic Algorithms expressed in 6 steps as follows:

Step 1: Randomly generate the

Step 2: Compute fitness value corresponding to

Step 2.1: Update

The needed duration to complete a task

where:

Step 2.2: Define

•

•

•

•

Step 2.3: The fitness values

Step 2.4: Sort the

Step 3: Elitism Selection: keep an individual

Step 4: Crossover and mutation: Denote

For each

Step 4.1: Create 2 new populations with a size of

and

where:

Step 4.2: Create best genes from

Set

where:

Step 5: Constraint validation checking: if there is an individual

Step 6: Return to Step 2 with

We validated the proposed method with the real datasets obtained after the WBS process of a software project. The results show that the algorithm works well with the tested dataset. It consisted of 417 dependent tasks, 19 candidates of project members, and 27 required skills. The algorithm was implemented in Java-8 and executed on a computer with an Intel Core I5-8250U CPU @1.60 GHz, with 4 GB RAM. It is essential to find appropriate values for parameters when implementing a GA, as this affects the results. There are many methods to find the best set of parameters. We tried many parameter sets at different ranges to tune the algorithm, and selected w = 0.1, σ = 30, and U = 110, based on the minimum returned fitness values. We temporarily set G to reach 500 generations. To determine how job similarity affects completion time, we consulted experienced engineers and defined:

GA does not guarantee an optimum global result, as the results vary by the initialization. We sought the best result, so we ran the algorithm with the best set of parameters. Results of 15 executions with various initialization values are shown in Tab. 1. The fitness value is affected by three criteria, each with a different range of values. To avoid bias between different target values when calculating

A schedule for each candidate for each time unit is shown in Fig. 4. A line represents a candidate, and columns represent the units of times. Assigned jobs have colors different from the background. We can notice that some members were used for a long time, while most were used occasionally. We checked with data on the availability of members. Members 3, 16, and 20 are those with the most registered time on the project, which explains why they took on much important work.

Tasks related to configuration and management of customer relationships and business processing support are lengthy. Fig. 5 shows the number of tasks received by each project member. Some members assigned zero or one tasks can be removed from the project candidates list, depending on conditions.

To test whether the proposed algorithm can find global solutions on smaller datasets, we created a smaller dataset with nine tasks, two candidates, and six skills from the standard dataset, then we compared the brute-force results with the proposed GA. The comparison results are shown in Tab. 2. The GA and the exhausting algorithm result return the same fitness values.

Suppose decision-makers want to define preferences based on different objectives. They may change the values of weight parameters

To illustrate a solution space, we executed the algorithm 100 times with different weights of each objective function. It is hard to guarantee this frontier is Pareto optimal. However, many executions with different parameters provide a visualization of solutions offered by the tool in the decision space. We can consider it as the practical version of the boundary. Fig. 7 shows the Pareto frontier constructed from the practical result.

We proposed an approach to RCPSP. The model attempts to minimize critical paths and costs, and to maintain the quality of the product. The model is subject to classical RCPSP problem constraints, and some additional conditions in real software development projects. The model’s goals are generally consistent with the project’s planning. The model integrates the similarity of tasks and employees’ available working plans, and therefore can be used generically for software projects, and not only applied to the specific cases cited.

Compared to other studies [5], the proposed approach brings two main benefits: (1) The model is formulated to allow decision-makers to understand and validate the structure. We combined both approaches to the proposed MOP, each fitting a different decision-making strategy. The weighted parameter-based method enables the decision-maker to customize the weights of target functions to flexibly achieve a final solution. Compromise programming is crucial in navigating the search, even when decision-makers cannot assign preferences to objective functions. (2) To solve the combinatorial optimization problem, we designed a new GA scheme that derives the individual fitness objective functions. Experimental results show that the introduced algorithm searches well for the solution by navigating the defined distance-based method.

The problem under consideration does not require finding solutions in spaces with large dimensions. However, optimal solutions may lie in high-dimensional space in other cases. It is challenging to visualize the Pareto frontier. In these situations, compromise programming is more suitable. We hope to refine the model to consider new goals and constraints in many situations. Recent methods of evolutionary algorithms show great promise in improving the quality of search results.

Acknowledgement: We thank LetPub (https://www.letpub.com) for its linguistic assistance during the preparation of this manuscript.

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

1. P. Brucker, A. Drexl, R. Mohring, K. Neumann and E. Pesch, “Resource-constrained project scheduling: Notation, classification, models, and methods,” European Journal of Operational Research, vol. 112, no. 1, pp. 3–41, 1999. [Google Scholar]

2. C. Artigues, S. Demassey and E. Neron, Resource Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. London, UK: Wiley-ISTE Ltd., pp. 1–288, 2008. https://onlinelibrary.wiley.com/doi/book/10.1002/9780470611227. [Google Scholar]

3. C. Barnhart and G. Laporte, Handbooks in Operations Research and Management Science: Transportation, 1st ed., vol. 14. North Holland: Elsevier, pp. 1–784, 2007. [Google Scholar]

4. S. Hartmann and D. Briskorn, “A survey of variants and extensions of the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 207, no. 1, pp. 1–14, 2010. [Google Scholar]

5. I. S. Ben and T. Yiliu, “A survey in the resource-constrained project and multi-project scheduling problems,” Journal of Project Management, vol. 5, no. 2, pp. 117–138, 2020. [Google Scholar]

6. F. Habibi, F. Barzinpour and S. J. Sadjadi, “Resource-constrained project scheduling problem: Review of past and recent developments,” Journal of Project Management, vol. 3, no. 2, pp. 55–88, 2018. [Google Scholar]

7. M. Vanhoucke and J. Coelho, “A tool to test and validate algorithms for the resource-constrained project scheduling problem,” Computers & Industrial Engineering, vol. 118, no. 3, pp. 251–265, 2018. [Google Scholar]

8. D. A. V. Veldhuizen and G. B. Lamont, “Multiobjective evolutionary algorithms: analyzing the state-of-the-art,” Evolutionary Computation, vol. 8, no. 2, pp. 125–147, 2000. [Google Scholar]

9. V. V. Vazirani, Minimum makespan scheduling. in Approximation Algorithms. Berlin, Heidelberg: Springer, pp. 79–83, 2003. [Google Scholar]

10. N. Kumar and D. P. Vidyarthi, “A model for resource-constrained project scheduling using adaptive PSO,” Soft Computing, vol. 20, no. 4, pp. 1565–1580, 2016. [Google Scholar]

11. E. Arian, “A new approach for solving resource constrained project scheduling problems using differential evolution algorithm,” International Journal of Industrial Engineering Computations, vol. 7, no. 2, pp. 205–216, 2020. [Google Scholar]

12. A. Laurent, L. Deroussi, N. Grangeon and S. Norre, “A new extension of the RCPSP in a multi-site context: Mathematical model and metaheuristics,” Computers & Industrial Engineering, vol. 112, no. 6, pp. 634–644, 2017. [Google Scholar]

13. C. Stiti and O. B. Driss, “A new approach for the multi-site resource-constrained project scheduling problem,” Procedia Computer Science, vol. 164, no. 1, pp. 478–484, 2019. [Google Scholar]

14. S. C. Ali, “Resource tardiness weighted cost minimization in project scheduling,” Advances in Operations Research, vol. 2017, pp. 1–11, 2017. [Google Scholar]

15. D. H. Quoc, N. T. Loc, N. D. Cuong and X. Naixue, “Effective evolutionary algorithm for solving the real-resource-constrained scheduling problem,” Journal of Advanced Transportation, vol. 2020, no. 2, pp. 1–11, 2020. [Google Scholar]

16. A. H. Hosseinian and V. Baradaran, “Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach,” Journal of Industrial and Systems Engineering, vol. 12, pp. 72–99, 2019. [Google Scholar]

17. B. A. Nadjafi, “Resource constrained project scheduling subject to due dates: Preemption permitted with penalty,” Advances in Operations Research, vol. 2014, pp. 1–10, 2014. [Google Scholar]

18. S. Ahmadpour and V. Ghezavati, “Modeling and solving multi-skilled resource-constrained project scheduling problem with calendars in fuzzy condition,” Journal of Industrial Engineering, vol. 15, no. 1, pp. 179–197, 2019. [Google Scholar]

19. C. Kellenbrink and S. Helber, “Scheduling resource-constrained projects with a flexible project structure,” European Journal of Operational Research, vol. 246, no. 2, pp. 379–391, 2015. [Google Scholar]

20. D. Joshi, M. L. Mittal, M. K. Sharma and M. Kumar, “An effective teaching-learning-based optimization algorithm for the multi-skill resource-constrained project scheduling problem,” Journal of Modelling in Management, vol. 14, no. 4, pp. 1064–1087, 2019. [Google Scholar]

21. A. Tesch, “A polyhedral study of event-based models for the resource-constrained project scheduling problem,” Journal of Scheduling, vol. 23, no. 2, pp. 233–251, 2020. [Google Scholar]

22. M. J. Anzanello and F. S. Fogliatto, “Learning curve models and applications: Literature review and research directions,” International Journal of Industrial Ergonomics, vol. 41, no. 5, pp. 573–583, 2011. [Google Scholar]

23. B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 5th ed., vol. 21. Berlin, Germany: Springer Publishing Company, 2006. [Google Scholar]

24. S. Elsayed, R. Sarker, T. Ray and C. C. Coello, “Consolidated optimization algorithm for re-source-constrained project scheduling problems,” Information Sciences, vol. 418, no. 1, pp. 346–362, 2017. [Google Scholar]

25. S. Tao and Z. S. Dong, “Multi-mode resource-constrained project scheduling problem with alterna-tive project structures,” Computers and Industrial Engineering, vol. 125, no. 6, pp. 333–347, 2018. [Google Scholar]

26. H. Zhang, H. Xu and W. Peng, “A genetic algorithm for solving RCPSP,” in Int. Symp. on Computer Science and Computational Technology, Shanghai, China, pp. 246–249, 2008. [Google Scholar]

27. V. P. Van and M. Vanhoucke, “A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 201, no. 2, pp. 409–418, 2010. [Google Scholar]

28. R. Carlos and R. Tahir, Chapter five compromise programming. in Developments in Agricultural Economics. Vol. 11. Amsterdam, Netherlands: Elsevier, pp. 63–78, 2003. [Google Scholar]

29. C. L. Hwang and A. S. M. Masud, Multiple Objective Decision Making, Methods and Applications: A State-of-the-art Survey, 1st ed., vol. 164. Berling Heidelberg: Springer-Verlag, pp. 1–358, 1979. [Google Scholar]

30. M. Zeleny, Compromise Programming, Multiple Criteria Decision Making, J. L. Cochrane, M. Zeleny (Eds.Columbia, South Carolina, United States: University of South Carolina Press, pp. 262–301, 1973. [Google Scholar]

31. T. S. Ngo, N. A. Bui, T. T. Tran, P. C. Le, D. C. Bui et al., “Some algorithms to solve a bi-objectives problem for team selection,” Applied Sciences, vol. 10, no. 8, pp. 1–19, 2020. [Google Scholar]

32. H. Xiong, Q. Shi, X. Tao and W. Wang, “A compromise programming model for highway maintenance resources allocation problem,” Mathematical Problems in Engineering, vol. 2012, pp. 1–11, 2012. [Google Scholar]

33. B. Poff, A. Tecle, D. G. Neary and B. Geils, “Compromise programming in forest management,” Journal of the Arizona-Nevada Academy of Science, vol. 42, no. 1, pp. 44–60, 2010. [Google Scholar]

34. N. T. Son, J. Jaafar, I. A. Aziz and B. N. Anh, “A compromise programming for multi-Objective task assignment problem,” Computers, vol. 10, no. 2, pp. 1–15, 2021. [Google Scholar]

35. N. T. Son, J. Jaafar, I. A. Aziz and B. N. Anh, “Meta-heuristic algorithms for learning path recommender at MOOC,” IEEE Access, vol. 9, pp. 59093–59107, 2021. [Google Scholar]

36. C. A. Coello Coello, G. B. Lamont and D. A. Veldhuizen, Evolutionary Algorithms for Solving Multi-objective Problems, 2nd ed., vol. 5. US: Springer, pp. 79–104, 2007. [Google Scholar]

37. K. F. Man, K. S. Tang and S. Kwong, “Genetic algorithms: Concepts and applications,” IEEE Transactions on Industrial Electronics, vol. 43, no. 5, pp. 519–534, 1996. [Google Scholar]

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |