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

TitlePolynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting
Publication TypeJournal Article
Year of Publication2016
AuthorsIemets, OO, Leonova, MV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
SectionInformation Science and Cybernetics
Date Published3/2016
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.
Keywordspolynomial 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).