2

对于工作调度应用程序，我需要为 w 周（= 7w 天）生成很多可能的员工时间表。员工时间表包括计划期间每一天的轮班列表（早、晚、晚、休息日）。该应用程序是用 Java 编写的。

此时，我代表一个员工时间表如下：

public class Schedule
{
    /** List with for every day of planning period the assigned shift */
    private Shift[] shiftlist = new Shift[Settings.schedule_days];

    /** Cost of schedule (for measuring its quality) */
    private double cost;

    // A list of variables, representing schedule properties
    // which are referenced often.
    // E.g.: number of workweekends, number of night shifts

    // Also some methods for updating / retrieving information
}

Shift 是一个枚举，表示分配的班次，定义为：

public enum Shift
{
    DAY, LATE, NIGHT, FREE;
}

我在枚举声明和比较属性的方法中也有一些移位属性，但我认为这与这里无关。

每个员工都有一个他可能的时间表列表：

public class Employee
{
    /** Large set of possible schedules for planning period */
    public LinkedList<Schedule> generated_schedules;

    // Variables representing properties of employee
}

我的问题是我实际上有 50 名员工，我想为每位员工生成 100.000 - 1.000.000 个可能的时间表。

时间表实际上生成得很快，因为我的电脑有 8GB 可用内存，所以我可以存储很多。然而，当完成为 30--40 名员工生成时，我的记忆就变得满满当当了。

有人给我的建议是使用字符数组来表示分配的班次，而不是枚举数组。这将使用更少的空间。此外，他表示使用 char 数组列表而不是 Schedule 对象列表也更好。但是，不可能在计划附近的某个地方保存计划属性（例如成本），并且需要经常重新计算它们。我认为这将是一个严重的缺点。

这种观察确实有意义，还是您认为有更好的方法来表达如此大量的数据以使用更少的空间？

4

3 回答 3

0

如果您想减少内存，您需要确定当前使用最多内存的内容以及您可以对该数据类型做出哪些假设以使其更小。如果没有这些信息，你只会猜测。

我建议您使用基于通用算法的方法。

例如;

  • 您只能生成 1000 个计划并对它们进行评分。

  • 500强，你留着

  • 使用这些将它们混合在一起以生成带有一些随机突变的下 1000 个。

重复，直到你的最好成绩没有提高。

重点是; 您可以使用另一种方法在更短的时间内生成更少的计划，但仍会收敛到最佳解决方案。

于 2012-09-14T12:14:01.110 回答
0

类似“小”项目的一次经历：

建议使用也存储在文件系统中的嵌入式数据库。尽管 SQL 很丑陋，但它允许比手动编码的集合遍历更好的查询；并且更容易维护。

这样一来，内存消耗的问题就没有实际意义了。

如果您愿意，可以使用 JPA，例如带有 ORM 的 eclipseLink。

于 2012-09-14T12:14:56.273 回答
0

如果您确实需要同时在内存中使用所有计划，那么最节省空间的编码是使用每天 2 位的 BitSet。

public class BitSetShiftList {
  private BitSet bitset;

  public void BitSetShiftList(int size) {
    bitset = new BitSet(size * 2);
  }

  public void setShift(int day, Shift shift) {
    int ordinal = shift.ordinal();
    assert ordinal >= 0 && ordinal <= 3;

    bitset.set(day * 2, (ordinal & 0x1) != 0);
    bitset.set(day * 2 + 1, (ordinal & 0x2) != 0);
  }

  public Shift getShift(int day) {
    int ordinal = (bitset.get(day * 2) ? 0x1 : 0x0) |
      (bitset.get(day * 2 + 1) ? 0x2 : 0x0);
    return Shift.values()[ordinal];
  }

}
于 2012-09-14T12:20:18.647 回答