java - 项目调度基本示例: chromosome for the Genetic Algorithm

Question

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

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

2)每个 worker 每天可以工作多少小时——这应该代表 worker 的效率

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

项目:

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

worker :

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

有了这样的问题，遗传算法的染色体应该是什么样子，换句话说 - 如何将这些数据转换成 GA 知道如何工作的 GA 染色体与(计算其数值适应度)？Java 中的示例将是完美的。

Answer 1

我想我会带上 worker 和他们每天从事的项目。因此，对于安排的每一天，请为每个员工写下他们将从事的项目。

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

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