Задачи упорядочения носят самый общий характер. Они возникают повсюду, где существует возможность выбора той или иной очередности выполнения работ: при составлении расписания приземления самолетов, прибытии поездов, обслуживании клиентов, распределении работ на предприятии, формировании очередности выполнения программ вычислительным центром и организации отдыха.[1.2, с. 11]
Методы решения разнообразных актуальных задач управления системами физико-технической, организационно-экономической и другой природы стали особенно актуальными в 20-м веке. Именно в это время сформировалась новая область математики - исследование операций, а также смежные с ней дисциплины - теория массового обслуживания, теория оптимального управления, теория автоматического управления, теория многокритериального принятия решений, теория расписаний.
Задачи теории расписаний связаны с построением расписаний, т.е. с упорядочиванием некоторых работ (операций, требований) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения работ, возникающие вследствие технологических или маркетинговых условий, и ограничения, связанные с исполнителями. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, а лучше - нахождение оптимального допустимого расписания по критерию оптимальности. Например, построение оптимального расписания в задаче распределения (поиск оптимального распределения работ по исполнителям), расписания по быстродействию (т.е. с минимизацией общего времени выполнения всех работ), расписания с минимальными финансовыми затратами и т.п. [1.3, с 7]
В обществе, на бытовом уровне составление расписаний происходит интуитивно. Но даже здесь человек определяет алгоритмы, выбирая максимально эффективные для каждой отдельно взятой ситуации, пусть даже не осознавая этого. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно.
Однако, использование улучшенных расписаний, построенных по специально выверенным алгоритмам, в масштабах производства может значительно сэкономить ресурсы предприятия. И поэтому стремительно развивающаяся автоматизация производства ставит перед научным сообществом все более и более трудные задачи составления расписаний. Решение этих задач усложняется тем фактом, что, реализованные на ЭВМ они могут требовать неприемлемо много времени для решения практических задач даже небольшой размерности. [1.3, с.7]
Одной из таких задач является задача минимизации максимального штрафа. Важным компонентом для исследования является математическая модель, сформулированная в терминах обслуживания требований в системе, состоящей из обслуживающих приборов. Каждому требованию или задаче может быть поставлено в соответствие: продолжительность обслуживания; момент готовности к обслуживанию или момент поступления; директивный срок, к которому желательно (или необходимо) завершить процесс обслуживания; весовой коэффициент, который может характеризовать уровень важности требования или степень срочности его обслуживания. Обслуживание требования прибором может происходить непрерывно или с прерываниями.
В данной работе исследования направлены на определение точности приближенных алгоритмов решения задачи минимизации максимального штрафа. В основе наших экспериментов будут такие алгоритмы, как метод ветвей и границ и два приближенных метода, использующий расписание алгоритма с прерываниями и строящий расписание с конца, где на каждом шаге на последнее место выбирается требование с минимальным значением функции штрафа. Из выводов, сделанных в данной работе, можно определить оценку точности и эффективности работы приближенных алгоритмов. Трудоемкости приближенных алгоритмов много меньше трудоемкости точного алгоритма, и именно поэтому их так необходимо сравнить, чтобы оценить вероятность экономических или производственных потерь на предприятиях, где приоритетом является не только точность решения задачи, но и скорость.
В задачах теории расписаний решения представляют собой конечное множество, которые теоретически можно перебрать и выбрать наилучший вариант. На практике такое часто бывает неосуществимо даже для задач небольшой размерности.
Метод ветвей и границ, который по существу является вариацией полного перебора с отсевом подмножеств допустимых решений, уже однозначно не содержащих оптимальных расписаний [II.4], позволяет решить задачу за время 0(n!), поэтому является одним из самых трудозатратных методов и требует большого объема памяти и мощного процессора. И даже с такими параметрами компьютер будет получать результат не сразу. Именно поэтому стремление использовать алгоритмы, которые решают задачу быстрее и получают результат не хуже, всегда являлось приоритетом в данной области.
Приближенные методы, изученные в данной работе, определяют оптимальные расписания, но с некоторой погрешностью, так как не рассматривают всевозможные переборы, а строят расписание исходя из предположения, что выбранные наборы будут давать хороший результат - достаточный для решения поставленной задачи.
В ходе исследования для изучения задачи минимизации максимального штрафа и предложенных алгоритмов был реализован удобный интерфейс, позволяющий быстро получить необходимые результаты исследования и проанализировать их.
Приближенный метод, строящий расписание с конца, где на каждом шаге на последнее место выбирается требование с минимальным значением функции штрафа, строит расписание за время 0(n ). Нельзя утверждать, что алгоритм является точным, однако, как показали исследования, получает неплохие результаты, не зависит от входных параметров требований и строит близкие к оптимальным расписания, в целом отличающие на 10-20%.
Второй приближенный метод, строящий расписание на основе алгоритма с разрешением прерываний, также определяет расписание за время 0(n ), однако часто строит расписания, зависящие от входных параметров требований и их количества.
Результаты, полученные только на небольших объемах данных, дают значения, достаточно точные для использования в дальнейших исследованиях. Однако было выявлено, что с увеличением количества требований значения штрафных функций приближенных методов все больше отличаются от значений, полученных методом ветвей и границ. А при большом количестве требований первый метод сильно уступает второму, причем, даже когда требований становится всего лишь больше 10, целевая функция второго метода всегда больше целевой функции первого.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
