Systems and Means of Informatics
2023, Volume 33, Issue 4, pp 50-59
ALGORITHM FOR GLOBAL OPTIMIZATION OF TIME-RELATED STATIONARY CHARACTERISTICS OF JOBS IN NONOBSERVABLE PARALLEL QUEUES
- M. G. Konovalov
- R. V. Razumchik
Abstract
Consideration is given to the model of a stochastic system comprised of a finite number of parallel independently running queues with heterogeneous servers, a single flow of independent jobs, and a single dispatcher which possesses full a priori information about the system's parameters and its initial state. At any moment, the dispatcher does not have any feedback from the queues but can memorize its previous routing decisions and time instants at which the decisions were made. Under quite general assumptions about the jobs' interarrival and jobs' size distributions and queues' scheduling, the (policy gradient) algorithm is proposed which allows one to locate the global optimum of the job's stationary mean sojourn or waiting time. The algorithm is based on the assumption that one can reach the neighborhood of the global optimum by applying the dispatching policy with a finite memory.
[+] References (11)
- Mengistu, T. M., and D. Che. 2019. Survey and taxonomy of volunteer computing. ACM Comput. Surv. 52(3):59. 35 p. doi: 10.1145/3320073.
- Konovalov, M., and R. Razumchik. 2023. Dispetcherizatsiya v chastichno nablyudaemykh stokhasticheskikh sistemakh konechnoy emkosti s parallel'nym obsluzhivaniem [Dispatching in nonobservable parallel queues with finite capacities]. Sistemy i Sredstva Informatiki - Systems and Means of Informatics 33(3):29-47. doi: 10.14357/08696527230303. EDN: XUVVNH.
- Albertian, A., I. Kurochkin, and E. Vatutin. 2022. Improving the heterogeneous computing node performance of the desktop grid when searching for orthogonal diagonal latin squares. High-performance computing systems and technologies in scientific research, automation of control and production. Eds. V. Jordan, I. Tarasov, and V. Faerman. Communications in computer and information science ser. Cham: Springer. 1526:161-173. doi: 10.1007/978-3-030-94141-3.13.
- Lakshmi, L. 2022. Resource and history-aware IoT task scheduling in volunteer assisted Fog computing. Conference (International) on Smart Applications, Communications and Networking Proceedings. Piscataway, NJ: IEEE. Art. 9993995. 6 p. doi: 10.1109/SmartNets55823.2022.9993995.
- Gonzalo, S., J. Marques, A. Garcia-Villoria, J. Panadero, and L. Calvet. 2022. CLARA: A novel clustering-based resource-allocation mechanism for exploiting low- availability complementarities of voluntarily contributed nodes. Future Gener. Comp. Sy. 128:248-264. doi: 10.1016/j.future.2021.10.002.
- Hordijk, W., A. Hordijk, and B. Heidergott. 2015. A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information. Asia Pac. J. Oper. Res. 32(3):1550015. 20 p. doi: 10.1142/S0217595915500153.
- Konovalov, M. G. 2007. Metody adaptivnoy obrabotki informatsii i ikh prilozheniya [Methods of adaptive information processing and their applications]. Moscow: IPI RAN. 212 p.
- Konovalov, M., and R. Razumchik. 2021. Dispetcherizatsiya v sisteme s parallel'nym obsluzhivaniem s pomoshch'yu raspredelennogo gradientnogo upravleniya markovskoy tsep'yu [Routing jobs to heterogeneous parallel queues using distributed policy gradient algorithm]. Informatika i ee Primeneniya - Inform. Appl. 15(3):41-50. doi: 10.14357/19922264210306.
- Hordijk, A., and D.A. van der Laan. 2004. Periodic routing to parallel queues and billiard sequences. Math. Method. Oper. Res. 59(2): 173-192. doi: 10.1007/s001860300322.
- Konovalov, M., and R. Razumchik. 2021. Minimizing mean response time in batch- arrival non-observable systems with single-server FIFO queues operating in parallel. Communications ECMS 35(1):272-278. doi: 10.7148/2021-0272.
- Konovalov, M., and R. Razumchik. 2018. Improving routing decisions in parallel nonobservable queues. Computing 100(10): 1059-1079. doi: 10.1007/s00607-018-0598-5.
[+] About this article
Title
ALGORITHM FOR GLOBAL OPTIMIZATION OF TIME-RELATED STATIONARY CHARACTERISTICS OF JOBS IN NONOBSERVABLE PARALLEL QUEUES
Journal
Systems and Means of Informatics
Volume 33, Issue 4, pp 50-59
Cover Date
2023-12-10
DOI
10.14357/08696527230405
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
parallel service systems; dispatching; control under incomplete observations; program control
Authors
M. G. Konovalov  and R. V. Razumchik
Author Affiliations
Federal Research Center "Computer Science and Control", Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|