1

我正在尝试提高生产系统的吞吐量。系统的确切类型不相关（我认为）。

描述

  1. 该系统由一排站（编号为 1、2、3...）和一个ARM组成。
  2. 系统随机接收一个ITEM。
  3. 每个ITEM都有一个与之关联的PLAN（例如，ITEM1可能有一个PLAN表示它需要通过站 3，然后是站 1，然后是站 5）。PLAN包括有关ITEM在每个站点的时间信息（一系列硬最大值/最小值）。
  4. 每个STATION一次只能容纳一件物品。
  5. ARM用于将每个项目从一个站移动到下一个站。每个PLAN还包括ARM的时序信息，这是一个固定值。

目前的做法

我有两个当前（工作）计划解决方案。

第一个维护每个STATION的使用主列表，将其视为“预订”方法。当每个新的 ITEM-N进入时，系统会向前搜索以找到 PLAN-N适合的最早可能的插槽。因此，例如，它会尝试在 t=0 处拟合它，然后逐步尝试更高的延迟，直到找到合适的值（实际上我在这里有一些启发式方法来减少处理时间，但方法仍然有效）

第二个为每个项目维护一个列表，指定它何时开始。当一个新的ITEM-N 进入时，系统会将其PLAN-N与所有现有列表进行比较，以找到合适的开始时间。同样，它从 t=0 开始，然后逐渐尝试更高的延迟。

这两种解决方案都没有利用每个站点允许ITEM的时间范围。假定一个固定时间（中点或最小值）。

理想的解决方案

不言而喻，如果当前的某些ITEM改变了它们在某个STATION中花费的持续时间，无论是通过缩短该持续时间（因此新的ITEM可以进入STATION代替）或延长该持续时间（因此ARM有时间移动 ITEM）。

我正在尝试实现该问题的遗传算法解决方案。我当前的基因包含 N 个数字（介于 0 和 1 之间），其中 N 是当前系统中所有项目中的站点总数以及要添加的新项目。将此基因转换为实际持续时间很简单（0 是最小持续时间，1 是最大持续时间，两者之间呈线性比例）。

然而，这种基因表示始终会产生相互重叠的不可用计划。这样做的原因是，当多个项目已经被理想地安排（在时间上连续，计划明智）时，持续时间不可能发生变化。这是不可避免的，因为一旦项目已经被处理，它们就不能延迟或提前。

上述情况的一个示例，假设ITEMA在STATION3中持续时间 t1 到 t2 和 t3 到 t4。然后ITEMB出现并占用STATION3持续时间 t2 到 t3（因此STATION3在 t1 和 t4 之间被充分利用）。以我目前的基因表示，我几乎可以保证永远找不到有效的解决方案，因为这需要基因的某些元素具有完全正确的值，以免产生重叠。

问题

  1. 有比我上面描述的更好的基因表示吗？
  2. 做一些简单的爬山来找到可修改的时间会更好吗？或者，遗传算法真的适合这个问题吗？
4

0 回答 0