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

Authors

  • O. O. Iemets V. G. Korolenko Poltava National Pedagogical University
  • M. V. Leonova V. G. Korolenko Poltava National Pedagogical University

DOI:

https://doi.org/10.15407/dopovidi2016.03.026

Keywords:

polynomial algorithm, task of scheduling for a single device

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 wi∈W, processing time pi∈P, and waiting time ri∈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 σ=(i1,…,ik) of the elements of permutations X=(ri1,…,rik)∈Ekn(R), R is a multiset of waiting times of tasks.

Downloads

Download data is not yet available.

References

Konvey R. V., Maksvell V. L., Miller L. V. Scheduling theory. Moscow, Nauka, 1975 (in Russian).

Koffman E. G. Computers and job-shop 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 School-Seminar "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).

Downloads

Published

10.10.2024

How to Cite

Iemets, O. O., & Leonova, M. V. (2024). Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting . Reports of the National Academy of Sciences of Ukraine, (3), 26–31. https://doi.org/10.15407/dopovidi2016.03.026

Issue

No. 3 (2016): Reports of the National Academy of Sciences of Ukraine

Section

Information Science and Cybernetics

License

Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine

Creative Commons License

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