Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting

ЗаголовокPolynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting
Тип публікаціїJournal Article
Рік публікації2016
АвториIemets, OO, Leonova, MV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.15407/dopovidi2016.03.026
Номер видання3
РозділInformation Science and Cybernetics
Нумерація сторінок26-31
Дата публікації3/2016
МоваUkrainian
Анотація
The article is devoted to the development of a classification of tasks $Z=(P,R,W,F)$ of finding the timetable of one device with the given parameters. Each of the tasks has a positive weight $w_{i} \in W$, processing time $p_{i} \in P$, and waiting time $r_{i} \in R$, if it is not available for the service, and a given criterion F of optimal schedule. The possibility of a scheduling polynomial in the time for these tasks is shown. It is proved that the optimal solution of the tasks of scheduling a device is the nondecreasing ordering $\sigma =(i_{1},\ldots,i_{k} )$ of the elements of permutations $X=(r_{i_{1}},\ldots,r_{i_{k}})\in E_{kn} (R)$, $R$ is a multiset of waiting times of tasks.
Ключові словаpolynomial algorithm, task of scheduling for a single device
Посилання: 
  1. Konvey R. V., Maksvell V. L., Miller L. V. Scheduling theory. Moscow, Nauka, 1975 (in Russian).
  2. Koffman E. G. Computers and job-shop scheduling theory. Moscow, Nauka, 1984 (in Russian).
  3. Tanaev V. S., Shkurba V. V. Introduction to the theory of schedules, Moscow, Nauka, 1975 (in Russian).
  4. Zgurovskiy M. Z., Pavlov A. A. Decision making in network systems with limited resources: Monograph. Kiev, Nauk. dumka, 2010 (in Russian).
  5. Shereshik N.Yu. Polyhedral properties maintenance task of different requirements with one device. (Theses of reports XVI Baikal International School-Seminar "Optimization methods and their applications"). Irkutsk, ISEM SO RAN, 2014 (in Russian).
  6. Brucker P., Knust S. Complexity Results for Scheduling Problems. Available at: www//mathematik.uniosnabrueck.de/research/OR/class.
  7. Stoyan Yu. G., Emets O. O. Theory and methods of Euclidean combinatorial optimization. Kiev, Research Institute of Education, 1993 (in Ukrainian).
  8. Lazarev A. A. J. of Numerical Math. and Math. Phys., 2007: 1087–1098 (in Russian).
  9. Knut D. Art of Computer Programming, Volume 3: Sorting and searching, Moscow, "Vilyams", 2000 (in Russian).