НАУЧНЫЙ ВЕСТНИК


НОВОСИБИРСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

ISSN (печатн.): 1814-1196          ISSN (онлайн): 2658-3275
English | Русский

Последний выпуск
№3(72) Июль - Сентябрь 2018

Эффективный параметрический алгоритм оптимизации расписаний параллельных систем с заданным расписанием начала обслуживания

Выпуск № 3 (72) Июль - Сентябрь 2018
Авторы:

Мезенцев Юрий Анатольевич,
Эстрайх Игорь Викторович
DOI: http://dx.doi.org/10.17212/1814-1196-2018-3-87-106
Аннотация

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


Ключевые слова: оптимальное расписание, параллельные производственные системы, несвязанные параллельные системы, задержки начала обслуживания, критерий быстродействия, дискретная оптимизация, эффективный параметрический алгоритм, обменный улучшающий алгоритм

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

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



2. Pinedo M. Scheduling theory, algorithms, and systems – 3rd 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.

Для цитирования:

Мезенцев Ю.А., Эстрайх И.В. Эффективный параметрический алгоритм оптимизации расписаний параллельных систем с заданным расписанием начала обслуживания // Научный вестник НГТУ. – 2018. – № 3 (72). – С. 87–106. – doi: 10.17212/1814-1196-2018-3-87-106.

 

For citation:

Mezentsev Yu., Estraykh I. Effektivnyi parametricheskii algoritm optimizatsii raspisanii parallel'nykh sistem s zadannym raspisaniem nachala obsluzhivaniya [An efficient parametric algorithm for optimal scheduling of unrelated parallel machines with release dates]. Nauchnyi vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta – Science bulletin of the Novosibirsk state technical university, 2018, no. 3 (72), pp. 87–106. doi: 10.17212/1814-1196-2018-3-87-106.

Просмотров: 53