Title  Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting 
Publication Type  Journal Article 
Year of Publication  2016 
Authors  Iemets, OO, Leonova, MV 
Abbreviated Key Title  Dopov. Nac. akad. nauk Ukr. 
DOI  10.15407/dopovidi2016.03.026 
Issue  3 
Section  Information Science and Cybernetics 
Pagination  2631 
Date Published  3/2016 
Language  Ukrainian 
Abstract  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 
References:
 Konvey R. V., Maksvell V. L., Miller L. V. Scheduling theory. Moscow, Nauka, 1975 (in Russian).
 Koffman E. G. Computers and jobshop scheduling theory. Moscow, Nauka, 1984 (in Russian).
 Tanaev V. S., Shkurba V. V. Introduction to the theory of schedules, Moscow, Nauka, 1975 (in Russian).
 Zgurovskiy M. Z., Pavlov A. A. Decision making in network systems with limited resources: Monograph. Kiev, Nauk. dumka, 2010 (in Russian).
 Shereshik N.Yu. Polyhedral properties maintenance task of different requirements with one device. (Theses of reports XVI Baikal International SchoolSeminar "Optimization methods and their applications"). Irkutsk, ISEM SO RAN, 2014 (in Russian).
 Brucker P., Knust S. Complexity Results for Scheduling Problems. Available at: www//mathematik.uniosnabrueck.de/research/OR/class.
 Stoyan Yu. G., Emets O. O. Theory and methods of Euclidean combinatorial optimization. Kiev, Research Institute of Education, 1993 (in Ukrainian).
 Lazarev A. A. J. of Numerical Math. and Math. Phys., 2007: 1087–1098 (in Russian).
 Knut D. Art of Computer Programming, Volume 3: Sorting and searching, Moscow, "Vilyams", 2000 (in Russian).