Поліноміальна складова ПДС-алгоритму розв’язання однієї задачі теорії розкладів

Автор(и)

  • Олександр Анатолійович Павлов Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056, Україна
  • Олена Григорівна Жданова Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056, Україна
  • Олена Борисівна Місюра Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056, Україна
  • Майя Олегівна Сперкач Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056, Україна

DOI:

https://doi.org/10.15587/2312-8372.2013.19550

Ключові слова:

календарне планування, розклад, паралельні прилади, ПДС-алгоритм, максимізація моменту запуску

Анотація

Розглянуто властивості задачі календарного планування виконання завдань із загальним директивним терміном ідентичними паралельними приладами за критерієм максимізації моменту запуску приладів за умови, що усі завдання не запізнюються. Застосовуючи методологію побудови ПДС-алгоритмів на основі ознак оптимальності розкладів визначена множина перестановок, що дозволяють послідовно покращувати значення критерію. Ці перестановки покладені в основу розробленої ПДС-складової алгоритму розв'язання задачі.

Біографії авторів

Олександр Анатолійович Павлов, Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056

Доктор технічних наук, професор, завідуючий кафедри

Кафедра автоматизованих систем обробки інформації та управління

Лауреат двох державних премій України в області науки і техніки

Олена Григорівна Жданова, Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056

Кандидат технічних наук, доцент

Кафедра автоматизованих систем обробки інформації та управління

Олена Борисівна Місюра, Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056

Кандидат технічних наук, старший науковий співробітник

Кафедра автоматизованих систем обробки інформації та управління, співробітник лабораторії комбінаторної оптимізації

Майя Олегівна Сперкач, Національний технічний університет України "Київський політехнічний інститут" просп. Перемоги, 37, м. Київ, Україна, 03056

Асистент

Кафедра автоматизованих систем обробки інформації та управління

Посилання

  1. Конвей, Р. В. Теория расписаний [Текст]/ Р. В. Конвей, В. Л. Максвел, Л. В. Миллер. – М.: Физматгиз, Наука, 1975. – 359 с.
  2. Танаев, В. С. Введение в теорию расписаний [Текст]/ В. С. Танаев, В. В. Шкуба. – М.: Физматгиз, Наука, – 1975.– 236 с.
  3. Шкуба, В. В. Задачи календарного планирования и методы их решения [Текст]/ В. В.Шкуба. – К.: Наукова думка, – 1966.– 155 с.
  4. Domschke, W. Produktionsplanung. Ablauforganisatorische Aspekte [Text]/ W. Domschke, A. Scholl, S. Vob. – Berlin, Heidelberg: Springer Verlag. – 2005. – 456 р.
  5. Згуровский, М. З. Принятие решений в сетевых системах с ограниченными ресурсами [Текст]: монография / М. З. Згуровский, А. А. Павлов. – К.: Наукова думка, 2010.– 573 с.
  6. Павлов, А. А. Исследование свойств задачи календарного планирования выполнения заданий с общим директивным сроком параллельными приборами по разным критериям оптимальности [Текст]/ А. А. Павлов, Е.Б. Мисюра, М. О. Сперкач // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2012. – №57. – С. 15–17.
  7. Pavlov, A. A. About one subclass of polynomially solvable problems from class “Sequencing jobs to minimize total weighted completion time subject to precedence constraints”[Text]/ A. A. Pavlov, L. A. Pavlova. – Uzhhorod: “Karpatskij region”, 1998. – № 15. – 320 p.
  8. Павлов, А. А. Субоптимальный полиномиальный алгоритм решения одного класса многоэтапных сетевых задач календарного планирования [Текст]/ А. А. Павлов, М. О. Сперкач, Е. А. Халус // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2012. – №57. – С. 51–55.
  9. Павлов, А. А. Результирующая формализация первого уровня трехуровневой модели оперативного планирования и принятия решений по критерию минимизации суммарного опережения директивных сроков [Текст]/ А. А. Павлов, Е. Б. Мисюра, Е. А. Халус, М. О. Сперкач, Г. А. Аракелян // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2012. – №56.– С. 56–57.
  10. Павлов, А. А. Четырехуровневая модель планирования, принятия решений и оперативного управления в сетевых системах с ограниченными ресурсами [Текст] / А. А. Павлов, Е. Б. Мисюра, Т. Н. Лисецький, Е. А. Халус, М. О. Сперкач // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2013. – №58.– С. 15-20.
  11. Павлов, А. А. Признаки оптимальности допустимых решений труднорешаемых задач комбинаторной оптимизации [Текст]/ А. А. Павлов// Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2013. – №59.
  12. Conway, R. W., Maxwell, W. L., Miller, L. V. (1975). Scheduling theory. Moscow: Nauka, 359.
  13. Tanayev, V. S., Shkuba, V. V. (1975). Introduction to the theory of schedules. Moscow: Nauka, 236.
  14. Shkuba, V. V. (1996). Scheduling problem and solution methods. Kyiv: Naukova Dumka, 155.
  15. Domschke, W., Scholl, A., Vob, S. (2005). Production planning. Expiration Organisational aspects. Berlin, Heidelberg: Springer Verlag, 456.
  16. Zgurovsky, M. Z., Pavlov, A. A. (2010) Decision-making in network systems with limited resources: Monograph. Kyiv: Naukova Dumka, 573.
  17. Pavlov, A. A., Misura, E. B., Sperkach, M. O. (2012). Research of the properties of the scheduling problem of the tasks execution with common due date for parallel machines by different criteria of optimality. Vestnik NTUU (KPI), 57, 15–17.
  18. Pavlov, A., Pavlova, L. (1998). About one subclass of polynomially solvable problems from class “Sequencing jobs to minimize total weighted completion time subject to precedence constraints”. Uzhhorod: “Karpatskij region”, 320.
  19. Pavlov, A. A., Sperkach, M. O., Khalus, E. A. (2012). Suboptimal polynomial algorithm for solving a multistage network scheduling problem of a single class. Vestnik NTUU (KPI), 57,51-55.
  20. Pavlov, A. A., Misyura, E. B., Khalus, E. A., Sperkach, M. O., Arakelyan, G. A. (2012). The resulting formalization of first-level three-level model of operational planning and decision-making by minimizing the total timing deadlines. Vestnik NTUU (KPI), 56, 56–57.
  21. Pavlov, A. A., Misyura, E .B., Lisetsky, T. N., Khalus, E. A., Sperkach, M. O. (2013). The four-level model of planning, decision making and operational control in the network systems with limited resources. Vestnik NTUU (KPI), 58, 15-20.
  22. Pavlov, А. А. (2013). The optimality symptoms of feasible solutions of intractable combinatorial optimization problems. Vestnik NTUU (KPI), 59.

##submission.downloads##

Опубліковано

2013-12-23

Як цитувати

Павлов, О. А., Жданова, О. Г., Місюра, О. Б., & Сперкач, М. О. (2013). Поліноміальна складова ПДС-алгоритму розв’язання однієї задачі теорії розкладів. Technology Audit and Production Reserves, 6(3(14), 47–51. https://doi.org/10.15587/2312-8372.2013.19550

Номер

Том 6 № 3(14) (2013): Економіка підприємства. Системи і процеси управління

Розділ

Системи та процеси керування

Ліцензія

Авторське право (c) 2016 Технологічний аудит та резерви виробництва

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.