Monday, May 4, 2009

Задача Job Shop

Занялся написанием кода для данной данной задачи. Выбрал кодировку для своего эволюционного алгоритма, в аглоязычной литературе она называется "operation-based". Автор на которого обычно ссылаются при её использовании Christian Bierwirth (вторая статья в списке). Выражается кодировка в том, что каждый ген представлен номером работы, который повторяется столько раз, сколько данная данная работа имеет операций в задаче, обычно число операций равняется числу машин. Хромосома в результате имеет длину n× m, где n-число работ в задаче, и m-число машин.
Есть ещё такой алгоритм Гиффлера-Томпсона (первая статья), который считается наиболее эффективным для генерации активных расписаний для данной задачи.

No comments:

Post a Comment