Генное представление для планирования производства с ограничениями
Я пытаюсь улучшить производительность производственной системы. Точный тип системы не имеет значения (я думаю).
Описание
- Система состоит из LINE станций (пронумерованных 1, 2, 3...) и ARM.
- Система получает ПУНКТ в случайное время.
- Каждый ITEM имеет связанный с ним PLAN (например, ITEM1 может иметь PLAN, в котором говорится, что ему необходимо пройти через станцию 3, затем 1, затем 5). ПЛАН включает в себя информацию о сроках того, как долго будет ДЕТАЛИ на каждой станции (диапазон жестких максимальных / минимальных значений).
- Каждая СТАНЦИЯ может держать один ПУНКТ за один раз.
- ARM используется для перемещения каждого пункта с одной станции на другую. Каждый ПЛАН также включает в себя информацию синхронизации для ARM, которая является фиксированным значением.
Текущая практика
У меня есть два текущих (работающих) планировочных решения.
Первый ведет основной список использования для каждой СТАНЦИИ, считая это подходом "бронирования". Когда каждый новый ITEM-N входит, система ищет впереди, чтобы найти самый ранний возможный слот, в который поместится PLAN-N. Так, например, он попытался бы подогнать его при t=0, а затем постепенно пробовать более высокие задержки, пока не найдет соответствие (ну, на самом деле у меня есть некоторые эвристики, чтобы сократить время обработки, но подход верен)
Второй поддерживает список для каждого ПУНКТА, определяющий, когда это должно начаться. Когда входит новый ITEM-N, система сравнивает свой " PLAN-N" со всеми существующими списками, чтобы найти подходящее время для запуска. Опять же, он начинается с t=0, затем постепенно увеличивается задержка.
Ни одно из двух решений не использует преимущества диапазона времени, в течение которого ITEM допускается на каждой станции. Предполагается фиксированное время (средняя точка или минимум).
Идеальное решение
Совершенно очевидно, что существуют ситуации, когда входящий ПУНКТ сможет начать раньше, чем это возможно, если некоторые из текущих ПУНКТОВ изменят продолжительность, которую они проводят в определенной СТАНЦИИ, будь то путем сокращения этой продолжительности (чтобы новый ПУНКТ мог войти вместо этого СТАНЦИЯ) или удлинить эту продолжительность (чтобы у АРМ было время переместить ПУНКТ).
Я пытаюсь реализовать решение проблемы с помощью генетического алгоритма. Мой текущий ген содержит N чисел (от 0 до 1), где N - это общее количество станций среди всех элементов в настоящее время в системе, а также новый элемент, который необходимо добавить. Преобразовать этот ген в фактическую продолжительность тривиально (0 - минимальная длительность, 1 - максимальная, линейно масштабируемая между).
Тем не менее, это представление гена последовательно производит неиспользуемые планы, которые накладываются друг на друга. Причина этого заключается в том, что, когда несколько элементов уже расположены идеально (последовательно во времени, с точки зрения планирования), изменение продолжительности невозможно. Это неизбежно, потому что, когда элементы уже обрабатываются, они не могут быть отложены или перенесены.
Пример описанной выше ситуации, скажем, ITEMA находится в STATION3 на длительности от t1 до t2 и от t3 до t4. Затем приходит ITEMB и занимает STATION3 в течение времени от t2 до t3 (поэтому STATION3 полностью используется между t1 и t4). С моим текущим представлением гена я практически гарантированно никогда не найду правильного решения, поскольку для этого потребуется, чтобы определенные элементы гена имели точно правильное значение, чтобы не создавать перекрытия.
Вопросы
- Есть ли лучшее представление гена, чем я описал выше?
- Буду ли я лучше выполнять какое-нибудь простое восхождение на холм, чтобы найти изменяемые моменты времени? Или GA на самом деле подходит для этой проблемы?