Перевод названия: Nature-Inspired Algorithms for Solving a Hierarchical Scheduling Problem in Short-Term Production Planning
Тип публикации: статья из журнала
Год издания: 2019
Идентификатор DOI: 10.18698/0236-3933-2019-3-46-63
Ключевые слова: задача составления расписания, оперативное планирование производства, эвристика Лина --- Кернигана, муравьиный алгоритм, генетический алгоритм, scheduling problem, short-term production planning, Lin --- Kernighan heuristic, ant colony optimization, genetic algorithm
Аннотация: Рассмотрена задача составления расписания, которая находит свое применение во многих областях, таких как проектное управление, составление расписаний в учебных заведениях и планирование производства. Практическое использование оптимизационных методов для решения задачи составления расписания существенно осложнено тем, что в реальноПоказать полностьюсти постановка задачи неразрывно связана с большой размерностью, сложным производственным процессом и множеством нетривиальных ограничений. Все эти особенности приводят к тому, что трудной задачей является даже поиск допустимого решения, а, следовательно, и к необходимости использования проблемно-ориентированных эвристик для решения задачи за приемлемое время. Стабильность производственного процесса требует тщательного соблюдения всех ограничений, но в то же время оперативное планирование производства сопряжено с необходимостью быстрого нахождения решения при любом изменении состояния. Предложено использовать иерархическую структуру, где на верхнем уровне располагается задача коммивояжера, а вложенная задача планирования проекта с ограниченными ресурсами заменена имитационной моделью. Рассмотрено применение таких алгоритмов, как эвристика Лина --- Кернигана, генетический алгоритм и алгоритм муравьиных колоний. Исследована эффективность применения перечисленных алгоритмов при решении задачи составления расписания в предложенной постановке The paper deals with the scheduling problem relevant in many fields, such as project management, lesson scheduling or production scheduling. In practice, using optimisation methods to solve the scheduling problem is considerably restricted by the fact that in the real world, problem statement involves high dimensionality, high production process complexity and many nontrivial constraints. These specifics mean that even merely searching for a feasible solution becomes a difficult task. Consequently, in order to solve the problem in a reasonable amount of time it is necessary to use problem-oriented heuristics. Ensuring manufacturing process stability involves respecting all constraints, but at the same time, short-term production planning demands fast solutions whenever there is a change of state. We propose to implement a hierarchical problem structure that puts the travelling salesman problem at the top and replaces the nested resource-constrained project scheduling problem with a simulation model. The paper considers using such algorithms as the Lin --- Kernighan heuristic, the genetic algorithm and the ant colony optimization. We study the efficiency of employing the algorithms mentioned above to solve the scheduling problem in the statement proposed
Журнал: Вестник Московского государственного технического университета им. Н.Э. Баумана. Серия Приборостроение
Выпуск журнала: № 3
Номера страниц: 46-63
ISSN журнала: 02363933
Место издания: Москва
Издатель: федеральное государственное бюджетное образовательное учреждение высшего образования Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)