Назад в библиотеку

РЕШЕНИЕ ПРОБЛЕМЫ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ПРИ ПОМОЩИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Авторы: Saleha Noor, М. Ikram Ullah Lali, М. Saqib Nawaz

Источник:https://www.researchgate.net/publication/281545095_SOLVING_JOB_SHOP_SCHEDULING_PROBLEM_WITH_GENETIC_ALGORITHM

Аннотация

Генетические алгоритмы (ГА) – это алгоритмы поиска, которые используются для решения задач оптимизации теоретической информатики. Задача оперативно-календарного планирования – это комбинаторная задача оптимизации, главная цель которой – найти расписание с минимальным временем работы для обработки j заданий на множестве m машин. График обработки заданий в задаче оперативно-календарного планирования подвергается некоторым ограничениям, например, только одна операция задания может обрабатываться на одной машине за раз, операции задания должны обрабатываться в определенном порядке, а приостановка любой операции – запрещено. В этой статье мы предложили новый генетический алгоритм (ГА) для решения проблемы, который использует новое генетическое представление (кодирование) для планирования заданий и распределения машин. Вслед за генетическим представлением начальная популяция генерируется случайным образом. Затем оператор кроссовера и мутации ГА применяется к популяции для создания новых потомков, пока не будет достигнут какой-либо критерий остановки. Кроме того, проводятся эксперименты, чтобы показать эффективность и применимость предложенной ГА.

1. Введение

Планирование операций считается наиболее важными вопросами управления производственными процессами и планирования. Планирование связано с присвоением рабочих мест производственным ресурсам и указанием последовательности для оптимизации определенных целевых функций. В производственной среде планирование зависит от среды цеха, такой как магазин-мастерская, магазин-магазин и открытый магазин [1]. Проблема оперативно-календарного планирования может быть объяснена как: набор работ j содержит n заданий, и эти задания обрабатываются на одной из машин, выбранных из набора машин m. Каждое задание состоит из операций O = O1, O2, ..., On. Каждый компьютер может обрабатывать одну операцию задания за раз, и когда операция назначается машине, машина должна завершить обработку операции без какого-либо прерывания. Кроме того, операции задания должны обрабатываться в определенном порядке. Проблема заключается в том, чтобы найти расписание операций на станках, имея в виду ограничения приоритета, которые минимизируют использование. Конечное время работы (Cmax) – время завершения всех операций каждого задания. Теория расписаний – это хорошо известная и очень NP-трудная задача [2], а также доказала, что она является сложновычисляемой задачей. Анализ проблем теории расписаний обеспечивает адекватное понимание решения проблем планирования, которые возникают в более сложных и реалистичных системах. Поэтому эвристика предпочтительнее для решения вопросов оперативно-календарного планирования [3]. ГА считается наиболее известным методом оптимизации для класса комбинаторных задач [4, 5]. Генетические алгоритмы (ГА), введенные Холандом [6], являются алгоритмами поиска на основе эволюционного процесса. ГА хорошо известны для решения задач оптимизации теоретической информатики. В ГА, решение в популяции соответствующим образом кодируется и подражая процессу ГА, оно обладает способностью соотносить решения с проблемами реального мира [7]. Анализ ГА начался давно, чтобы понять работу генетических алгоритмов и как их использовать для получения наилучшего решения [8]. При применении ГА к проблеме необходимо разработать подходящее представление (кодирование) для данной проблемы. Также необходима фитнесс-функция, которая используется для выбора индивидуальных решений от общей популяции. Во время работы алгоритма выбранные решения проходят через кроссовер (воспроизведение) и мутацию для создания новых потомков. Основная идея здесь в том, что потомки будут лучше, чем их родители.

Первый метод, основанный на ГА для задачи планирования, был предложен Дэвисом [9] в 1985 году. После этого ГА часто использовались для решения задач оперативно-календарного планирования. В этом исследовании мы представили ГА для решения оперативно-календарного планирования.

Статья разделена на три основных раздела. В разделе 2 обзор литературы в области проблемы ГА и теории расписаний. В разделе 3 предлагается генетический алгоритм, который представлен путем детального описания стратегий схемы кодирования, фитнесс-функции, критериев выбора, операторов кроссовера и мутаций, выбранных для генерации потомков.Эксперименты выполняются в разделе 4, чтобы показать эффективность предлагаемого ГА, а выводы приводятся в разделе 5

2. Обзор литературы

В литературе для решения проблем оперативно-календарного планирования были использованы различные подходы ГА. Эти подходы отличаются друг от друга на основе схемы представления хромосом, обработки ограничений и преследуемых целей. Тем не менее, все подходы имеют одну общую вещь: они стремятся создать оптимальное расписание для обработки рабочих мест. В 1985 году Дэвис [9] впервые использовал ГА для решения проблемы оперативно-календарного планирования. Джейн и Миран [10] предоставляют всесторонний обзор методов, которые используются для решения проблемы оперативно-календарного планирования. Они пришли к выводу, что среди различных методов решения проблемы оперативно-календарного планирования метаэвристическая техника лучше всего подходит для этого. Совместное использование эвристики и ГА называется метаэвристикой. С ростом популярности ГА в середине 1980-х годов различные исследователи использовали ГА для решения проблемы оперативно-календарного планирования.

Двухуровневая структура хромосом была предложена Ли и Ченом [11], которая основана на рабочем порядке процедур и распределении машин для минимизации времени работы в проблеме оперативно-календарного планирования. Lee et al. [12] предложил структуру, которая использует ГА вместе с машинным обучением и эвристикой, чтобы найти последовательность заказов на выпуск задания и последовательность для отправки заданий на каждой отдельной машине. Согласно Onwubolu и Davendra [13], ГА – лучший метод, который используется для оптимизации проблемы оперативно-календарного планирования. В то время как некоторые исследователи, Bierwirth et al. [14], Meeran и Morshed [15] считают, что модифицированный ГА для оптимизации проблемы оперативно-календарного планирования намного лучше, чем стандартный ГА. Для решения проблемы на практике также используются методы, отличные от ГА, такие как перечислительная техника, приближенный подход и искусственные нейронные сети. Уильямсон и др. [16] демонстрируют, что решение о наличии расписания с тремя вариантами может быть осуществлено в полиномиальное время, пока совокупное время подготовки, необходимое для всех операций на каждой из машин, близко к трем. Фундаментальное среднее среди перечисленных методологий для расписания – это метод ветвей и границ. Для практического применения стандартный ГА может быть недостаточно гибким, и это становится все более очевидным, когда проблема усложняется. Кроме того, Uckun et al. [18] пришел к выводу, что генетические алгоритмы быстро склоняются к возможным решениям.

3. Предлагаемый генетический алгоритм

Общая структура нашей предлагаемой ГА описывается в следующих шагах:

  1. Представление: каждая хромосома (решение) в популяции представлена в формате, в котором будут применяться другие операторы ГА;
  2. Отбор: выбор решений для популяции для репродукции;
  3. Создание потомков: новые решения получаются путем изменения последовательности операций (порядковый кроссовер) и путем изменения назначения машин на операции (единый кроссовер);
  4. Мутация: случайным образом меняются некоторые биты в расписании;
  5. Фитнесс-функция: вычисляется время работы для каждого расписания, полученного после шага 4;
  6. Критерий останова: Достигнуто фиксированное количество поколений. Когда критерий останова достигается, ГА возвращает наилучшее расписание вместе с соответствующим временем работы в качестве вывода. Ниже описаны следующие шесть шагов, которые мы использовали для решения проблемы оперативно-календарного планирования.

3.1 Схема кодирования

Кодирование является ключевым и жизненно важным элементом генетического алгоритма. Поиск оптимального решения проблемы с использованием ГА в значительной степени зависит от схемы кодирования. ГА обычно обрабатывает популяции строк. Первоначальная популяция генерируется случайным образом. Каждая хромосома представляет собой решение (расписание) для задачи оперативно-календарного планирования. Назначения необходимых операций станкам в расписаниях описываются генами хромосом, а порядок операций, который появляется в хромосоме, представляет собой последовательность операций. В нашей предлагаемой ГА мы использовали трехуровневую структуру для представления хромосомы (расписания).
На рисунке 1 показана трехуровневая структура хромосомы.

Рисунок 1 – Схема кодирования

На рисунке 1 первая строка представляет операции работ. Например, O31 подразумевает операцию 1 из работы 3 (J3), O21 подразумевает операцию 1 из работы 2 (J2), O33 подразумевает операцию 3 из работы 3(J3), O43 подразумевает операцию 3 из работы 4(J4) и так далее. Вторая строка представляет собой распределение станка для каждой операции. 3 подразумевает, что операция O31 перейдет к 3 станку для обработки, 1 означает, что станок 1 назначена для операции O21 и т. д. Третья строка показывает зависимости операций от выполняемых операций. Здесь 0 означает, что для выполнения O31 нет ограничений приоритета. То же самое относится и к первой работе других рабочих мест. O31 подразумевает, что обработка операции O32 начнется при обработке операции O31.

3.2. Выбор родителя

После представления хромосомы следующий шаг – выбор расписаний из популяции. Выбранные расписания называются родительскими хромосомами (расписаниями). Для выбора родительских хромосом используются разные методы. Чтобы избежать преждевременной сходимости, мы произвольно выбираем два расписания из популяции. Это означает, что все индивидуумы (расписания) в населении имеют одинаковые шансы на отбор в качестве родителей.

3.3. Оператор кроссовера

Оператор кроссовер ГА используется для обмена операциями заданий и назначения конкретной операции станку в двух выбранных родителях, чтобы минимизировать время работы. В нашем предлагаемом алгоритме мы использовали кроссинговер для операций, меняя их между двумя родительскими расписаниями. Принимая во внимание, что единый кроссовера используется только для перетасовки присвоения машин операциям.

3.3.1 Порядковый кроссовер

Мы использовали порядковый кроссовер [19], чтобы отделить дочерние расписания от родительских. Мы наложили 2 ограничения на порядковый кроссовер для соответствия ограничениям приоритета. Эти ограничения следующие:

3.3.2 Единый кроссовер

В задаче составления расписаний, назначение станка для конкретной операции задания известно заранее. Мы использовали единый кроссовер для изменения назначения станка между операциями заданий, чтобы минимизировать время работы и простоя. В едином кроссовере, в случае когда одна и та же необходимая операция в двух расписаниях имеет разное назначение станкам, перетасовывайте номер машины среди них. Ниже приведен пример работы единого кроссовера для перетасовки станков. Пусть два расписания, полученные после операции порядкового кроссовера:


После единого кроссовера новое назначение станка для каждой операции в расписаниях S1 и S2 будет:

3.4 Оператор мутации

Lee et al. [20] использовал приоритет, сохраняющий оператор мутации сдвига в их предложенном генетическом алгоритме. Мы также использовали оператор мутации сдвига, однако с небольшими изменениями. Последующие шаги показывают, как работает наш модифицированный оператор мутации сдвига, и как мутируют расписания, полученные после работы оператора единого кроссовера.

Предположим, что операция по индексу 16 выбрана в качестве операции сдвига. Для него po это операция, находящаяся по индексу 9.

Новое расписание, полученное после модифицированного оператора мутации сдвига,

3.5 Фитнесс-функция

Основная задача теории расписаний заключается в том, чтобы найти такое расписание с наименьшим значением времени обработки и простоя. Его можно рассчитать благодаря информации о последовательности обработки операций на каждом станке и времени начала обработки операции. Мы выбрали время работы как функцию фитнеса. Так как мы хотим получить расписания, которые имеют более низкие значения времени обработки, то генетическая эволюция предпочтет расписания с более низкими значениями фитнесс-функции. В течении каждого поколения оцениваются все выбранные расписания, и выбирается лучшее.

4. Результаты и обсуждения

Мы применили предложенную ГА к решению проблемы составления расписания 4 × 4 для проверки применимости и эффективности принятой методологии. Операционная последовательность обработки каждого задания и время обработки для каждой операции приведены в таблице 1.

Таблица 1. Назначение операций станкам и время, необходимое для выполнения каждой операции.

Исходная популяция, которую мы рассмотрели, составляет 50, и мы запускаем ГА 30 раз при условии, что коэффициент кроссовера равен 0,8, а мутации 0,2. Результат в таблице 2 показывает, что предложенная нами ГА дает результат так же хорошо, как и другие методы. Также из таблицы 2 видно, что последнее выполненное задание – O44 на машине 4. Следовательно, значение времени работы для этого расписания составляет 26,5. Результат в Таблице 2 также содержит информацию о последовательности заданий для каждого станка, начальное и конечное время каждой операции. Например, на станке1 O21 запускается в момент времени 0 и заканчивается в 5.5. Затем операция O41 запускается в момент 5.5 и заканчивается в момент 14 и так далее. На рисунке 2 приведена диаграмма Гантта. Полученные значения времени после каждой эпохи показаны на рисунке 3. Из рисунка 3 видно, что оптимальное значение времени обнаружено в поколении 12.


Рисунок 2. Диаграмма Гантта.


Рисунок 3. Результат, полученный с использованием случайно сгенерированных расписаний в качестве начальной популяции.

Таблица 2. Полученное распределение станков по операциям и время начала и окончания каждой операции

5. Вывод

В этой статье представлен генетический алгоритм (ГА) для задачи планирования расписания. Вычислительные результаты показывают, что предложенная ГА является эффективной. ГА и теория расписаний представляют собой основу для эволюционных вычислений и понимания проблем комбинаторной оптимизации. Хотя у ГА есть слабость, для достижения лучшего решения требуется много времени, но она предлагает гибкую основу для эволюционных вычислений. В будущем мы хотели бы видеть, как предлагаемая ГА будет применяться к решениям более сложных проблем, чтобы увидеть ее производительность в них.

Список литературы

  1. Phanden, R. K., Jain, A. and Verma, R., “A genetic algorithm based approach for job shop scheduling.” Journal of Manufacturing Technology, 23(7): 937-946 (2012).
  2. Garey, M. R., Johnson, D. S. and Sethi R., “The complexity of flow shop and job shop scheduling.” Mathematical Operational Research, 1(2): 117–129 (1976)
  3. Maccarthy, B. L. and Liu, J., “Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling.” International Journal of Production Research, 31(1): 5979 (1993).
  4. Jia, H. Z., Fuh, J. Y., Nee, A. Y. C. and Zhang, Y. F., “Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems.” Computers & Industrial Engineering, 53(2): 313-320 (2007)
  5. Bancila, D. and Buzatu, C., “A hybrid algorithm for job shop scheduling.” In: Proceedings of 6th International DAAAM Baltic Conference, Industrial Engineering, pp. 1-6 (2008).
  6. Holland, J. H., “Adaptation in Natural and Artificial Systems.” University of Michigan Press, Ann Arbor, MI, USA (1975).
  7. Mathew, T. V., “Genetic algorithm.” Indian Institute of Technology, Mumbai (2012).
  8. Nawaz M. S., Lali M. I. and Pasha M. A., “Formal verification of crossover operator in genetic algorithms using Prototype Verification System (PVS)”, In: Proceedings of 9th IEEE International Conference on Emerging Technologies, pp. 1-6 (2013).
  9. Davis, L., “Job shop scheduling with genetic algorithms.’ In: Proceedings of International Conference on Genetic Algorithms and their Applications, Vol. 140 (1985).
  10. Jain, A. S. and Meeran, S., “Deterministic job-shop scheduling: past, present and future.” European Journal of Operational Research, 113(2): 390–434 (1999)
  11. Li, Y. and Chen, Y., “A genetic algorithm for job-shop scheduling.” Journal of Software, 5(3): 269-274 (2010).
  12. Lee, C. Y., Piramuthu, S. and Tsai, Y. K., “Job shop scheduling with a genetic algorithm and machine learning.” International Journal of Production Research, 35(4): 1171-1191 (1997)
  13. Onwubolu, S. and Davendra, D., “Scheduling flow shops using differential evolution algorithm.” European Journal of Operational Research, 171(2): 674-692 (2006).
  14. Bierwirth, C., Kopfer H., Mattfeld D. C. and Rixen I., “Genetic algorithm based scheduling in a dynamic manufacturing environment.” In: proceedings of International Conference on Evolutionary Computation, Vol. 1, pp. 439 (1995).
  15. Meeran, S. and Morshed, M. S., “A hybrid genetic tabu search algorithm for solving job shop scheduling problems. A case study.” Journal of Intelligent Manufacturing, 23 (4): 1063-1078 (2012).
  16. Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast'Janov, S. V. and Shmoys, D. B., “Short shop schedules.” Operational Research, 45 (2): 288-294 (1997)
  17. Lageweg, B. J., Lenstra, J. K. and Rinnooy Kan, A. H. G., “Job-shop scheduling by implicit enumeration.” Management Science, 24 (4): 441-450 (1997).
  18. Uckun, S., Bagchi. S., Kawamura, K. and Miyabe, Y., “Managing genetic search in job shop scheduling.” IEEE Expert, 8 (5): 15-24 (1993).
  19. Davis, L., “Applying adaptive algorithms to Epistatic domains.” In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 162-164 (1985).
  20. Lee, K. M., Yamakawa. T. and Lee. K. M. “A genetic algorithm for general machine scheduling problems.” In: Proceedings of 2nd International Conference on Knowledge-Based Intelligent Electronic Systems, pp. 60–66 (1998).