1

给定一家软件公司,其中开发人员在多个不同项目的团队中工作。项目需要指定开发人员的特定技能。出于我的目的,我想保持简单并将其限制为一种技能,即编程语言。所以有些项目需要Java,有些需要C等。项目有固定的持续时间,每个项目应该有两个开发人员分配给它。

在任何时间点,一些项目正在进行中,新项目进来,需要在未来的某个时间点进行计划。我想计算一个时间表,哪些开发人员应该在什么时间和什么项目上工作。

我不是在寻找最佳解决方案(如果可能的话)。我对人类经理可以创建的时间表感到满意。

我读过关于资源约束调度问题和分配问题的文章,但我很少接受正式的 CS 培训,而且我经常迷失在这些问题的不同变体中的所有细微差别中。

我认为我的问题是作业车间调度的一个更简单的变体,其中作业是项目,开发人员是机器,因此作业需要同时多台机器。只有一个先例约束,即运行中的项目不能中止,因此必须先完成。

从我读过的所有可能的解决方案中,我倾向于使用遗传算法,主要是因为我读过人们使用它们得到了很好的结果,并且因为我前一段时间将一个用于另一个项目。我也读过线性规划的好结果,但我对此知之甚少。

遗传算法是否是此类问题的可行解决方案?还是有更好的解决方案?

4

2 回答 2

1

创建一个二分图,一方面是开发人员,另一方面是需要的项目成员。“需要的项目成员”是指如果一个项目P需要 3 个开发人员,您将添加 3 个节点,可能命名P0P1P2

如果开发人员具有该项目所需的所有技能,请在开发人员和所需的项目成员之间划清界限。然后,您的问题会简化为在该图中找到匹配项;您可以使用标准算法来执行此操作。

于 2012-05-13T20:44:24.483 回答
0

使用遗传算法是一种可行的方法,但它非常雄心勃勃。

贪心算法开始。

于 2012-05-13T14:57:49.670 回答