СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

В статье предложен параметрический полиномиально трудоемкий алгоритм оптимизации расписаний параллельной системы с задержками на входе, который дополнен улучшающим обменным алгоритмом. Критерием эффективности в рассматриваемой постановке является максимальное быстродействие системы (С_max), что обеспечивает равномерную загрузку приборов. Наличие этого критерия, а также задержек начала обслуживания поступающих заявок делает задачу труднорешаемой с априорной оценкой любого аппроксимационного алгоритма, равной двум. Предложенный параметрический алгоритм основан на схеме динамического программирования модифицированной адаптивным сужением области поиска, что обеспечивает его вычислительную эффективность. Сформулированные задачи синтеза и предложенный алгоритм оптимизации расписаний параллельных обслуживающих систем ориентированы на практическое применение в календарном планировании и оперативном регулировании производственных процессов с дискретным характером. Оценена трудоемкость синтеза точных и приближенных к оптимальным по быстродействию расписаниям. Приведен иллюстративный пример использования представленных формальных постановок и алгоритма для синтеза оптимальных расписаний параллельной системы рассматриваемого типа. Проведенные вычислительные эксперименты на специально сгенерированных реализациях задачи больших размерностей показали хорошие практические результаты. Приведена итоговая сравнительная статистика точности и времени счета посредством программных реализаций параметрического и обменного алгоритмов с результатами альтернативных инструментов, показывающая неоспоримое преимущество представленных в статье алгоритмов. Экспериментально доказана вычислительная эффективность связки алгоритма, основанного на процедуре динамического программирования с отсевом части вариантов на каждом шаге и обменного алгоритма, что позволяет обеспечить приемлемое быстродействие и близость к оптимумам. Апостериорная оценка близости к оптимумам получаемых решений на доступных для оценки тестах не превысила 5%.

1. Brucker P. Scheduling algorithms. – 5^th ed. – Berlin; New York: Springer, 2007. – 372 p.

2. Pinedo M. Scheduling theory, algorithms, and systems – 3^rd ed. – New York; London: Springer, 2008. – 672 p.

3. Multiprocessor scheduling: theory and applications / ed. by E. Levner. – Vienna, Austria: I-Tech Education and Publishing, 2007. – 436 p.

4. Мезенцев Ю.А. Прикладные задачи и алгоритмы оптимизации расписаний параллельных обслуживающих систем // Научный вестник НГТУ. – 2016. – № 1 (62). – С. 49–73.

5. Мезенцев Ю.А. Оптимизация расписаний параллельных динамических систем в календарном планировании // Информационные технологии. – 2008. – № 2. – С. 16–23.

6. Santos F.C., Vilarinho P.M. The problem of scheduling in parallel machines: a case study // Proceedings of the World Congress on Engineering WCE 2010. – London, 2010. – Vol. 3. – P. 2443–2448.

7. Kaabi J., Harrath Y. A survey of parallel machine scheduling under availability constraints // International Journal of Computer and Information Technology. – 2014. – Vol. 3, iss. 2. – P. 238–245.

8. Lin Y.K., Hsieh H.T., Hsieh F.Y. Unrelated parallel machine scheduling problem using an ant colony optimization approach // World Academy of Science, Engineering and Technology. – 2012. – Vol. 6. – P. 1798–1803.

9. Lin Y.K. Particle swarm optimization algorithm for unrelated parallel machine scheduling with release dates // Mathematical Problems in Engineering. – 2013. – Vol. 2013. – Art. 409486. – P. 1–9.

10. Lee W.C., Wu C.C., Chen P. A simulated annealing approach to makespan minimization on identical parallel machines // International Journal of Advanced Manufacturing Technology. – 2006. – Vol. 31, N 3–4. – P. 328–334.

11. Gharbi A., Haouari M. Minimizing makespan on parallel machines subject to release dates and delivery times // Journal of Scheduling. – 2002. – Vol. 5, N 4. – P. 329–355.

12. Vazirani V. Approximation algorithms. – Berlin; New York: Springer, 2001. – 375 p.

13. Kashan A.H., Karimi B. A discrete particle swarm optimization algorithm for scheduling parallel machines // Computers and Industrial Engineering. – 2009. – Vol. 56, N 1. – P. 216–223.

14. Мезенцев Ю.А. Метод бинарных отсечений и ветвлений целочисленного программирования // Доклады Академии наук высшей школы РФ. – 2011. – № 1 (16). – С. 12–25.

15. Mezentsev Yu.A. Binary cut-and-branch method for solving mixed integer programming problems // 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA): Proceedings. – St. Petersburg, 2017. – P. 210–212.