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

1Iemets, OO
2Leonova, MV
1Poltava University of Economics and Trade
2V.G. Korolenko Poltava National Pedagogical University
Dopov. Nac. akad. nauk Ukr. 2016, 3:26-31
Section: Information Science and Cybernetics
Language: 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.
Keywords: 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).