M*: Multidisciplinar Multiobjective Metaheuristics

| TIN2008-06491-C04-01 Ministerio de Ciencia e Innovación (Spain)
| UMA - University of Málaga



list 26th Oct 2011. Incoming, coordination meeting, UMA (Málaga) [AGENDA]

list 11th Mar 2011. Incoming, coordination meeting, UC3M (Leganés) [AGENDA]

list [Engineering Optimization] Special issue on Multiobjective Metaheuristics for Multidisciplinary Engineering Applications

list 16th Jul 2010. Incoming, coordination meeting, UEX (Cáceres)

list [META'10] Special Session on Real Parameter Optimization: From Benchmarking To Real World Applications

list 5th Feb 2010. Coordination meeting, ULL (La Laguna)

list 14th Dec 2009. Coordination meeting, UMA (Málaga)

list 3rd Jul 2009. First Problem's Workshop, UMA (Málaga)

list 17th April 2009. Problem descriptions, instances, codes ... [+]

list 2nd April 2009. M* Web Site Launched




Software Project Scheduling


The Software Project Scheduling problem consists in deciding who does what during the software project lifetime. There exists a set of employees that have to complete a set of tasks. Each employee has a salary and some skills. The tasks are related by a Task Precedence Graph (TPG), wich determines a partial ordering in the set of tasks. The main two objectives are to reduce the completion time and the cost of the whole project. Below we present a detailed description of the problem.


The resources considered are people with a set of skills, a salary, and a maximum dedication to the project. Formally, each person (employee) is denoted with ei where i goes from 1 to E (the number of employees). Let SK be the set of skills, and si the i-th skill for i varying from 1 to S=|SK|. The skills of the employee ei will be denoted with eisk that is a subset of SK, the monthly salary with eisa, and the maximum dedication to the project with eimd. The salary and the maximum dedication are both real numbers. The former is expressed in fictitious currency units, while the latter is the ratio between the amount of hours dedicated to the project and the full working day length of the employee. For example, a maximum dedication of 0.75 means that the employee spends at most 75% of its working day to tasks of the project. A maximum dedication greater than 1.0 means that the employee can work overtime.

The tasks are denoted with ti for i from 1 to T (the number of tasks). Each task ti has a set of required skills associated to it that we denote with tisk and an effort tief expressed in person-month (PM). The tasks must be performed according to a TPG. The TPG indicates what tasks must be completed before the beginning of a new task. The TPG is an acyclic directed graph G(V,A) with a vertex set V={t1, t2, ..., tT} and an arc set A where (ti, tj) belongs to A if the task ti must be completed, with no other intervening tasks, before task tj can start.

Our objectives are to minimize the cost, the duration of the project, and the overtime of the employees. The constraints are that each task must be performed by at least one person and the set of required skills of a task must be included in the union of the skills of the employees performing the task. Once we know the elements of a problem instance, let us proceed to describe the elements of a solution to the problem. A solution can be represented with a matrix X=(xij) of size ExT. The element xij is the dedication degree of the employee ei to the task tj. If the employee ei performs the task tj with a 0.5 dedication degree s/he spends half of his/her working day in the task. If an employee does not perform a task s/he will have a dedication degree of 0 to that task. This information helps to compute the duration of each task and, indeed, the start and end time of each one, i.e., the time schedule of the tasks. From this schedule we can compute the duration of the project. The cost can be calculated after the duration of the tasks accounting also for the dedication and salary of the employees. Finally, the overtime of each employee can be calculated using the time schedule of the tasks and the dedication matrix X.



The problem presented above can be made more realistic in different ways. Adding new elements to the problem description we have new variants of the problem that are briefly described in the following:

  • Brook's law: the time required to complete a task is not the task effort divided by the manpower of the emplyees working on that task (as it is assumed in the base version of this problem). A more realistic assumption is to consider a convex function for the relation between the total dedication of the employees to one task and their total manpower.
  • Uncertainty and robustness: most of the information that a project manager have on a new project is uncertain and usually is estimaed on the base of previous completed software projects. This uncertainty can be modelled using random variables and additional objectives can be added to the problem in order to find robust solutions. That is, solutions with a small variability in their main objectives when the uncertain parameters change.
  • Staff changes: in a real situation the staff of a software company is not stable, it changes due to new incorporations, dismissals, illness, etc. This situations can be modelled in the problem.
  • Staff training: software companies invest a large amount of money in the training of their employees. For a particular software project the training cost depends on the actual assignment of employees to tasks. This situation can be modelled in the problem to take into account the training cost.

Instance generator

We have developed an instance generator for this problem. Click here to see the description of the generator and to get some generated instances.

Instances for Scalability Analysis

We have generated instances with 8 to 256 employees and 16 to 512 tasks in order to study the scalability properties of the search algorithms. In total we have 36 instances that can be downloaded from this link.


Related Bibliography and Papers

[1] E. Alba and F. Chicano, Software Project Management with GAs, Information Sciences, 177 (11):2380-2401

[2] Giuliano Antoniol, Massimiliano Di Penta, Mark Harman, A Robust Search-based Approach to Project Management in the Presence of Abandonment, Rework, Error and Uncertainty, Proceedings of the 10th International Symposium on the Software Metrics (METRICS '04), pp. 172-183

[3] C.K. Chang, M.J. Christensen, T. Zhang, Genetic Algorithms for Project Management, Annals of Software Engineering 11 (2001) 107-139

Last Updated: 14/12/09
For any question or suggestion, click here to contact with us.
joomla counter | Webmaster | Contact Us | ©2009 M* UMA