1

我正在编写一个项目调度优化库，这是一种特殊的作业车间调度问题。为简单起见，到目前为止，我的算法仅适用于作为项目唯一资源的工人，并且到目前为止只有两种类型的约束：

1）每个工人对他可以从事的项目都有限制。只有部分工人具有熟练从事同一项目（例如：W1、W3、W7 工人可从事 P2 项目；W2、W3、W5 可从事 P3 项目等），但同一工人可熟练从事多个项目，并允许在不同的时间从事多个项目（例如：W1连续5天在P1工作，然后他切换到P2工作4天，然后他回到P1，等等）

2）每个工人每天可以工作多少小时都有一个限制——这应该代表一个工人的效率

首先，我创建了一个简单的时间表，其中仅包含 4 个项目和 4 个工人。

项目：

  • P1; 开始时间：5月1日；截止日期：30天；所需工作时间：300
  • P2; 开始时间：7月1日；截止日期：60 天；所需工作时间：150
  • P3; 开始时间：5月15日；截止日期：45天；所需工作时间：50
  • P4; 开始时间：4月20日；截止日期：20天；所需工作时间：150

工人：

  • W1; 效率：10小时/天；适用于项目：P1、P2、P3、P4
  • W2; 效率：5小时/天；可用于项目：P1、P3
  • W3; 效率：8小时/天；可用于项目：P1、P4
  • W4; 效率：6小时/天；可用于项目：P2、P4

像这样设置一个问题，遗传算法的染色体应该是什么样子，换句话说 - 如何将此数据转换为 GA 将知道如何使用的 GA 染色体（计算其上的数值适应度）？一个例子Java将是完美的。

4

2 回答 2

1

像flup的答案中的直接解决方案很可能会导致突变几乎不会产生任何有效的时间表。交叉会更糟。

问题是做错事太容易了。从一个最佳调度的工作人员那里，只需一步就可以过度调度他们。由于最优值通常是某个 n 维多面体的顶点，因此它与无效状态接壤。

因此，我建议使用染色体部分进行一些间接表示，例如“如果可能，将 W2 分配给 P3”。对于你日程安排的每一个小时，你都要检查染色体部分，如果可能的话，应用它的规则。

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

实际上，上述问题很可能完全可以通过观察只有几个相关的时间点来解决，即项目的开始和截止日期。在它们之间，所有时间在以下意义上是等效的：当您将 5 月 1 日的时间表和 5 月 2 日的时间表互换时，您将得到完全相同的结果。使用这种等价性，这个问题可能是蛮力的。

于 2016-04-21T00:23:32.850 回答
1

我想我会接受工人和他们每天从事的项目。因此，对于安排好的每一天，为每个工人写下他们将从事的项目。

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

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

于 2016-04-07T09:32:56.660 回答