0

I noticed that for problems such as Cloudbalancing, move factories exist to generate moves and swaps. A "move move" transfers a cloud process from one computer to another. A "swap move" swaps any two processes from their respective computers.

I am developing a timetabling application.

  1. A subjectTeacherHour (a combination of subject and teacher) have only a subset of Periods to which they may be assigned. If Jane teaches 6 hours at a class, there are 6 subjectTeacherHours each which have to be allocated a Period, from a possible 30 Periods of that class ;unlike the cloudbalance example, where a process can move to any computer.
  2. Only one subjectTeacherHour may be allocated a Period (naturally).

It tries to place subjectTeacherHour to eligible Periods , till an optimal combination is found.

Pros

The manual seems to recommend it.

...However, as the traveling tournament example proves, if you can remove a hard constraint by using a certain set of big moves, you can win performance and scalability...

...The `[version with big moves] evaluates a lot less unfeasible solutions, which enables it to outperform and outscale the simple version....

...It's generally a good idea to use several selectors, mixing fine grained moves and course grained moves:...

While only one subjectTeacher may be allocated to Period, the solver must temporarily break such a constraint to discover that swapping two certain Period allocations lead to a better solution. A swap move "removes this brick wall" between those two states.

So a swap move can help lead to better solutions much faster.

Cons

A subjectTeacher have only a subset of Periods to which they may be assigned. So finding intersecting (common) hours between any two subjectTeachers is a bit tough (but doable in an elegant way: Good algorithm/technique to find overlapping values from objects' properties? ) .

Will it only give me only small gains in time and optimality?

I am also worried about crazy interactions having two kinds of moves may cause, leading to getting stuck at a bad solution.

4

1 に答える 1

1

スワップの動きは非常に重要です。

満室の部屋に割り当てられた 2 つのコースを考えてみましょう。スワッピングがなければ、競合する部屋に 1 つのコースを移動し、その移動をステップとして選択するには、厳しい制約を破る必要があります (これはありそうもないことです)。

組み込みの汎用スワップ MoveFactory を使用できます。独自に記述する場合は、いずれかの側を不適格な期間に移動するときに、スワップ移動 isDoable() false と言うことができます。

于 2012-02-08T11:50:44.207 に答える