Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting - Iemets, O. O.; Leonova, M. V. (Reports of the National Academy of Sciences of Ukraine, 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 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.