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


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

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

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

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

Выпуск № 1 (62) Январь - Март 2016
Авторы:

Ю.А. МЕЗЕНЦЕВ
DOI: http://dx.doi.org/10.17212/1814-1196-2016-1-49-73
Аннотация
Сформулированы прикладные задачи оптимизации управления объектами добывающей промышленности. Представлены формальные постановки задач календарного планирования строительства скважин нефтегазоконденсатного месторождения, основанные на разработанных автором моделях синтеза приближенных к оптимальным по быстродействию расписаний одностадийных параллельных систем с задержками начала обслуживания. Предложен набор из четырех взаимосвязанных алгоритмов оптимизации, позволяющих широко варьировать трудоемкость (быстродействие) и степени точности решений задач смешанного программирования, в которые трансформируются содержательные постановки рассматриваемых прикладных задач оптимизации. Приведен иллюстративный пример синтеза оптимальных по быстродействию календарных графиков бурения скважин нефтегазоконденсатного месторождения. Пример иллюстрирует построение оптимального расписания бурения семи кустов скважин двумя буровыми установками с заданными задержками начала бурения. Интерпретированы и детализированы получаемые результаты вплоть до построения графиков Гантта синтезируемых оптимальных по быстродействию расписаний. Примеры подробно иллюстрируют предложенные алгоритмы дискретной оптимизации. Приведены результаты модельных расчетов сгенерированных тестовых примеров на размерностях, приближенных к реальным; проведено сравнение программных реализаций двух представленных алгоритмов. Экспериментально доказана эффективность алгоритма, основанного на процедуре динамического программирования с отсевом части вариантов на каждом шаге, что позволяет обеспечить приемлемое быстродействие и близость к оптимумам. Кроме этого, определены перспективы развития темы для обеспечения большей точности решений и быстродействия программных реализаций. Показана непосредственная применимость разработанных алгоритмов и программ в проектировании и планировании деятельности крупных предприятий добывающей промышленности
Ключевые слова: управление, оптимизация управления, оптимальность по быстродействию, оптимальные расписания, дискретная оптимизация, параллельные приборы, задержки начала обслуживания, одностадийные системы, релаксация, декомпозиция, динамическое программирование, отсев вариантов, гибридный алгоритм, нефтегазоконденсатные месторождения, графики бурения

Список литературы
1. Мезенцев Ю.А. Эффективные вычислительные методы решения дискретных задач оптимизации управления производственными процессами. – Новосибирск: Изд-во НГТУ, 2015. – 275 с.

2. Мезенцев Ю.А. Оптимизация расписаний параллельно-последовательных систем в календарном планировании // Информационные технологии. – 2009. – № 6. – С. 35–41.

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

4. Avdeenko T.V., Mezentsev Yu.A. Efficient hybrid algorithm for optimal scheduling of unrelated parallel machines // The 10th International Forum on Strategic Technology (IFOST 2015): proceedings, Indonesia, Bali, 3–5 June 2015. – Yogyakarta, 2015. – P. 66.

5. 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.

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

7. Bank J., Verner F. Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties // Mathematical and Computer Modelling. – 2001. – Vol. 33 (4–5). – P. 363–383.

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

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

10. Kaabi J., Harrath Y. A survey of parallel machine scheduling under availability con-straints // International Journal of Computer and Information Technology. – 2014. – Vol. 03, iss. 02. – P. 238–245.

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

12. 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, no. 3–4. – P. 328–334.

13. 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.

14. 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, UK, 30 June – 2 July 2010. – London, 2010. – Vol. 3.

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