Рolynomial component PDС-algorithm tasks solving the scheduling theory

Authors

  • Олександр Анатолійович Павлов National Technical University of Ukraine "Kiev Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056, Ukraine
  • Олена Григорівна Жданова National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056, Ukraine
  • Олена Борисівна Місюра National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056, Ukraine
  • Майя Олегівна Сперкач National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056, Ukraine

DOI:

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

Keywords:

shop scheduling, schedule, parallel devices, PDС-algorithm, max, starting moment

Abstract

This article discusses the usage of the operating shop scheduling in the production management. Some results of the investigation in the sphere are presented in the article. The problem of shop scheduling fulfillment over general due date with identical parallel devices is considered on purpose to maximize a starting moment of devices on condition that all tasks have not been detached. The main goal of the investigation is to determine the latest starting moment of tasks fulfillment with parallel devices over due date in permissible schedule.

The article observes the task properties of shop scheduling of tasks fulfillment over general due date with identical parallel devices. According to the method of construction for difficult problems of combinatorial optimization polynomial component is developed PDС-algorithm structure tasks solving. It has been proposed algorithm of initial schedule structure. It has been determined the set of transpositions that allows to improve in succession the significance of the criterion. This set transpositions form the basis of the developed algorithm tasks solving. The results of the investigation could be put into practice of operative shop scheduling of production.

Author Biographies

Олександр Анатолійович Павлов, National Technical University of Ukraine "Kiev Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056

Doctor of technical sciences, professor, head of Department of Computer-Aided Management and Data Processing Systems

Winner of two State Prizes of Ukraine in Science and Technology

Олена Григорівна Жданова, National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056

Ph.D., Associate Professor of Department of Computer-Aided Management and Data Processing Systems

Олена Борисівна Місюра, National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056

Ph.D., Senior Researcher in Department of Computer-Aided Management and Data Processing Systems of the Laboratory of combinatorial optimization

Майя Олегівна Сперкач, National Technical University of Ukraine "Kyiv Polytechnic Institute" 37, Avenue Роbede, Kiev, Ukraine, 03056

Assistant of Department of Computer-Aided Management and Data Processing Systems

References

  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.

Downloads

Published

2013-12-23

How to Cite

Павлов, О. А., Жданова, О. Г., Місюра, О. Б., & Сперкач, М. О. (2013). Рolynomial component PDС-algorithm tasks solving the scheduling theory. Technology Audit and Production Reserves, 6(3(14), 47–51. https://doi.org/10.15587/2312-8372.2013.19550

Issue

Vol. 6 No. 3(14) (2013): Economy of enterprise. Management systems and processes

Section

Systems and Control Processes

License

Copyright (c) 2016 Олександр Анатолійович Павлов, Олена Григорівна Жданова, Олена Борисівна Місюра, Майя Олегівна Сперкач

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.