项目调度基本实例：遗传算法的染色体

Question

我正在写一个项目调度优化库，一个特殊的作业车间调度问题。为了保持它的简单，到目前为止，我的算法将只与工人是该项目的唯一资源工作，只有2个类型的约束到目前为止：

1）每个工人有什么项目，他的约束可以工作。 只有一些员工能够熟练地从事同一个项目（例如：W1，W3，W7员工可以在项目P2上工作; W2，W3，W5可以在项目P3上工作;等等），但同一个员工可以熟练地工作在多个项目上，并允许在不同时间在多个项目上工作（例如：W1连续5天在P1上工作，然后他切换到P2 4天，然后他回到P1等）

2）每个工人对他能有多少小时每天工作的约束 - 这应该代表工人的效率

首先，我创建了一个简单时间表只包含4个项目和4名工人。

项目：

• P1; 起始：五月一号; 截止日期：：30天; 需要工作时间：300
• P2; 起始：7月1日; 截止日期：60天; 需要工作时间：150
• P3; 起始：5月15日; 截止日期：45天; 需要工作时间：50
• P4; 起始：4月，20日; 截止日期：20天; 工时需要：150

工：

• W1; 效率：10h /天; 可用项目：P1，P2，P3，P4
• W2; 效率：5小时/天; 可用项目：P1，P3
• W3; 效率：8小时/天; 可用项目：P1，P4
• W4; 效率：6h /天; 可的项目：P2，P4

一个问题是建立这样，在遗传算法的一个染色体应该看起来怎么样，换句话说 - 如何将这些数据转换成一个GA染色体GA会知道如何处理（计算它的数值适应度）？ Java中的一个例子是完美的。

Answer 1

我想我会带他们每天工作的工人和项目。 因此，对于计划的每一天，请为每个工作人员写下他们将要处理的项目。

然后，您可以计算每个项目给定分配截止日期之前已完成工作的百分比。

突变可以在某一天将工作人员的分配更改为不同的项目。 交叉可以用一个不同的基因组替换一个或多个工作日的工作人员的分配，或者将一天或多天的所有工作人员的完全分配与不同染色体的分配交换可能更有效

Answer 2

直接的解决方案在flup's answer将最有可能导致突变产生几乎没有任何有效的时间表。交叉会更糟糕。

问题是，做错事太容易了。从一个最佳时间安排的员工那里只需要一个步骤就可以超时安排他们。由于最优化典型地是某个n维多面体的顶点，它接近于无效状态。

所以，我建议一些染色体部分的间接表示，如“如果可能，将W2分配给P3”。对于您的日程安排的每个小时，您都可以通过染色体部分并尽可能应用其规则。

这可以进行相当简单的优化，以便您不必每小时处理一次（下一小时的结果通常相同）。

实际上，上述问题最有可能通过观察只有少数相关时间点，即项目的开始时间和截止时间来完全解决。在他们之间，所有的时间在以下意义上都是相同的：当您将5月1日的日程安排和5月2日的日程安排互换时，您会得到完全相同的结果。使用这种等价性，问题可能会是一种暴力。