解决软件项目的评审和蚁群优化调度问题

K.N.Vitekar¹,S.A.Dhanawe²,D.B.Hanchate³

我第二年,部门的计算机工程,VPCOE, Baramati,浦那(印度马哈拉施特拉邦
我1年,部门的计算机工程,VPCOE, Baramati,浦那(印度马哈拉施特拉邦
助理教授,部门的计算机工程、VPCOE Baramati,浦那(印度马哈拉施特拉邦

文摘

SPSP调度任务和员工的问题。SPSP是一个np难度(非多项式)的问题。SPSP是个RCPSP问题相关的问题。为解决这样的问题的模型了。数量的元启发式算法也应用于解决此类问题(例如GA)。本文的调查方法和模型放入历史背景。SPSP分割任务和分配员工任务节点的奉献。作者提出了一种配电网元启发式方法来解决SPSP问题。作者用ACO求解等问题因此他称之为一个ACS: SPSP。本文的结果与遗传算法来解决SPSP相比。 The proposed algorithm is very efficient and promising and obtains more accuracy.

关键字

软件项目调度问题(SPSP),资源约束项目调度问题(RCPSP)、遗传算法(GA),蚁群优化(ACO),元启发式方法

介绍

发展有效的和高效的项目管理工具是一个具有挑战性的和关键的任务。项目管理是一个应用程序的知识、技能、工具和技术来解决项目调度问题。在项目开发项目调度是非常重要的任务。SPSP[4]是一个np难问题。这个问题由数量的资源,重要的资源是人类即软件工程师。这个工程师分配一个特定的任务与最低工资和最低持续时间和完成一个项目在项目调度基本要求。SPSP RCPSP有关,找到最优的调度满足优先级需求和减少项目持续时间和成本[1]。比RCPSP SPSP不同是SPSP员工被认为是与多个技能和RCPSP数量的资源。经典的元启发式方法应用于解决SPSP遗传算法等问题。

GA非常灵活和高效的软件项目调度[1]。很多工作已经完成解决SPSP使用遗传算法。在[4]作者描述的基于时间线的模型与3 d SPSP GA。遗传算法的成功率SPSP并不令人满意。采取华元启发式的优势,提出一种有效的和有效的算法来解决SPSP。

有效算法是用来解决许多np难组合问题如ACS: TSP(旅行推销员问题)[8]。配电网的作业车间调度[9],火车调度使用配电网技术[7]。配电网是RCPSP的第一应用[2]。作者使用两种技术解决SPSP问题。1日是使用算法解决SPSP,二是领域知识发现有利于提高调度算法的性能。

本文的组织结构如下:软件项目调度问题是覆盖在第二节。第三节介绍了蚁群优化,第四节描述配电网SPSP, ACS: SPSP在第五节与GA相比。我们在第六节总结本文。

软件项目调度问题(SPSP)

问题描述

SPSP是找到一个最优的问题为软件项目进度,这样所有的约束,如优先约束和满意这计划减少工资和持续时间。SPSP模型需要输入作为一个任务和任务的细节,如id、任务努力,需要技巧来完成这一任务,maxhead计数的任务。SPSP也把员工作为输入和员工如雇员id的细节,员工salaryand员工每个任务的最大奉献,每个员工的技能列表。SPSP TPG(任务优先级图)作为输入,TPG = {V,}, V =组任务和任务i和j之间=边缘。基本符号和符号用于ACS: SPSP纸,

使用任何的努力和员工计算COCOMO模型[8]。为调度任务和员工必须满足以下约束。

1)每项任务必须包括至少一名员工。

在那里,

Mij——员工的奉献程度ei tj的任务。

2)员工参与到任务应该能够提供所有所需的技能这一任务。

3)可行解不应该让员工加班。

4)每个任务满足优先约束。

在SPSP评估软件项目的质量计划,成本计算项目的项目和持续时间。

计算时间,每个任务的开始和结束时间是使用这个方程计算。

每个任务的开始时间和结束时间计算:

计算软件项目的总持续时间:

项目的总时间计算项目的甘特图。

这个方程是用来计算任务的持续时间。

这将计算软件项目的总时间。

计算项目的总成本:

1使用下面的公式计算每个任务的成本。

一旦所有任务的成本计算和成本的任务是项目的成本。

员工的加班使用斜坡函数计算。

蚁群优化(ACO)

路径是由意大利作家民宿设计这元启发式方法用于解决许多np难问题。ACO[10]是一种算法,基于真实蚂蚁的行为找到最短路径从源到食物。该算法利用的行为真正的蚂蚁在寻找食物。已经观察到蚂蚁存款一定数量的信息素在其路径旅行时从蚁巢到食物。再次返回时,蚂蚁被遵循同样的路径的信息素沉积和存款路径的信息素。这样蚂蚁短路径后将返回之前,因此增加信息素沉积的速度比蚂蚁更长的路径。配电网的灵感来自蚂蚁的觅食行为。这些蚂蚁存款信息素在地上为了纪念一些有利的路径,其他成员应遵循的殖民地。然而,信息素是被蒸发后,一定以恒定速率一定的间隔,因此蚂蚁的路径访问频繁,仅作为信息素沉积,而蚂蚁路径很少访问的损失由于缺乏信息素沉积在路径和结果是新的蚂蚁只打算按照常用的路径。因此,所有的蚂蚁开始他们的旅程可以学习以前游客蚂蚁留下的信息和指引短路径由信息素沉积。 In ACO, a number of artificial ants build solutions to the considered optimization problem at hand and exchange information on the quality of these solutions via a communication scheme that is pheromone deposit on the path of the journey performed by it. At the present time, many algorithms have been suggested based on the improvement of ACS algorithm and used for solving various problems such as TSP, Train scheduling, nurse scheduling, job shop scheduling etc.

算法对SPSP

SPSP使用算法解决的问题包括重要的算法是ACS: SPSP算法和建筑图选择任务的每个员工的奉献和启发式信息计算通过使用六个策略和设计信息素之一来解决通信问题。

建筑图

算法被广泛用于解决组合问题。SPSP应用算法的第一步是构建图,将任务分配每个员工的奉献精神。每个员工提出了一些致力于这项任务,这可以分配给任务通过使用建筑图。建筑图设计的把任务分解为节点,这个节点的数量取决于员工的数量,如果最低奉献价值。首先我们计算节点的密度即。

,最低的是员工的奉献任务j。

奉献的价值从0开始,它是思想的倍数增加。密度的值是5,当思想的价值是0.25。在TPG的分割操作任务描述如下:

1)选择节点和投入列0开始

2)根据员工的数量,创建E数量的列,给名字column1 ColumnE,每一列包括密度的节点数量。

3)识别结束节点和添加ColumnE + 1

4)从columnito构造所有可能的边缘columni + 1。

分裂后的ant任务选择一个接一个边缘,到达下一个任务。这条路是直接的。没有任何向后返回路径。蚂蚁选择边缘据员工的奉献精神的任务。蚂蚁从每一列选择只有一个边,去下一列。最后当蚂蚁到达的节点即结束任务,时间总任务被分配给员工和一个旅游就完成了。后,根据员工的奉献精神评估解决方案的质量。

实现ACS-SPSP

我们构造图,将有助于分配员工任务的奉献。旅游完成后的质量检查解决方案通过使用适应度函数ACS,得到最好的解决方案的最大的健身价值。适应度函数被定义为项目成本和项目的加权和持续时间。我们考虑项目成本的重要性和持续时间等于适应度函数和权重是用来调整项目成本和时间相同的数量级。给出了适应度函数如下:

ACS-SPSP的细节如下:

1)初始化算法中使用的所有参数。如α、β、0,ρ,Ngen Nant。α和β是用来评估历史信息和启发式信息的重要性。Ρ调整信息素更新,0平衡勘探和开发行为,Ngenis代ACO, Nant是蚂蚁的数量。

2)初始化信息素值。所有的值都是0。

3)蚂蚁选择路径得到的解决方案。每只蚂蚁选择下一节点构造图使用选择方案。每只蚂蚁维护自己的解矩阵,结果贡献值存储到矩阵。

4)使用适应度函数评价矩阵的质量。计算项目的成本和持续时间以及负载的员工。

5)选择最好的解决方案和更新信息素值使用信息素更新公式。

6)3 - 5步重复直到终止条件不满足。终止条件生成的数量或质量的解决方案。

7)选择最佳解决方案的成本和时间根据适应度函数。

信息管理-

蚂蚁选择路径在建筑图使用选择方案和旅游时,意味着所有任务成功完成分配给员工,通过适应度函数我们检查质量的解决方案,如果解决方案是最好的信息素值更新。更新信息素值的两倍。信息素的更新τij边缘以Nij实现由以下方程:

广告战略意味着启发式信息与员工的奉献ei已经为其他任务。

比较

SPSP是一个np难问题,所以这些问题的时间复杂度非常高。这样通过使用许多技术问题已经解决了。手动计算这样的问题不是一个解决方案。这个问题是通过使用元启发式方法来解决。在SPSP元启发式方法是通过使用遗传算法和算法来解决。通过比较的结果GA算法,算法比遗传算法。的平均命中率和项目时间总是比GA算法的解决方案。但ACS-SPSP或遗传算法不能获得可行的解决方案与30个任务实例。

结论

SPSP是np难问题。调度任务和员工不是一个简单的任务。其时间复杂度非常高。由于其复杂性很少有算法实现来解决这样的问题。也有少数的元启发式算法的遗传算法等方法提出了。GA也是很好的方法来解决np难问题。遗传算法也应用于解决SPSP问题,但其成功率并不令人满意。与GA方法相比,该方法如ACS: SPSP是有效的,并承诺在以下方面。

1)基于图搜索方法即把任务通过分发员工的奉献精神和建筑图生成。

2)六个启发式机制用于使用领域知识包括总奉献任务和分配员工的奉献。

这方面被认为是和六个启发式机制分配员工的奉献其他启发式任务达到最好的结果。所以ACS: SPSP SPSP优于GA方法。

引用

Alba E,奇卡诺人摩根富林明。软件项目管理。信息科学2007;177 (11):2380 - 401。
布鲁克P,那个,莫尔R,诺伊曼K, Pesch大肠资源受限的项目调度:符号、分类、模型和方法。欧洲运筹学杂志1999;112 (1):3-41。
张Chang C,克里斯腾森& t .遗传算法为项目管理。《软件工程2001;11 (1):107 - 39。
约翰逊Garey M, d .电脑和棘手:np完全的理论指南。w·h·弗里曼;1979年。
Heerkens GR,编辑器。麦格劳-希尔;2002年
静肖Xian-TingAo YongTang”,解决软件项目调度问题蚁群优化”。
k . Sankar列车调度使用算法技术。
马可•多日卢卡玛丽亚Gambardella。ACS:合作学习方法旅行推销员问题。
会发生van der zwaan&carlos品牌,为作业车间调度算法。
张Wei-Neng陈,小君,“蚁群优化软件项目与一个基于事件调度器调度和人力资源”。