Informatics and Applications
2019, Volume 13, Issue 4, pp 54-59
MIXED POLICIES FOR ONLINE JOB ALLOCATION IN ONE CLASS OF SYSTEMS WITH PARALLEL SERVICE
- M. G. Konovalov
- R. V. Razumchik
Abstract
Consideration is given to the problem of efficient job allocation in the class of systems with parallel service on independently working single-server stations each equipped with the infinite capacity queue. There is one dispatcher which routes jobs, arriving one by one, to servers. The dispatcher does not have a queue to store the jobs and, thus, the routing decision must be made on the fly. No jockeying between servers is allowed and jobs cannot be rejected. For a job, there is the soft deadline (maximum waiting time in the queue). If the deadline is violated, a fixed cost is incurred and the job remains in the system and must be served. The goal is to find the job allocation policy which minimizes both the job's stationary response time and probability of job's deadline violation. Based on simulation results, it is demonstrated that the goal may be achieved (to some extent) by adopting a mixed policy,
i. e. a proper dispatching rule and the service discipline in the server.
[+] References (10)
- Kleinrock, L., and R. R. Muntz. 1972. Processor sharing queueing models of mixed scheduling disciplines for time shared system. J. ACM 19(3):464-482.
- Aalto, S., andU. Ayesta. 2008. Optimal scheduling ofjobs with a DHR tail in the M/G/1 queue. 3rd Conference (International) on Performance Evaluation Methodologies and Tools Proceedings. Brussels, Belgium. doi: 10.4108/ ICST.VALUETOOLS2008.4335.
- Wu, R., andD. G. Down. Scheduling multi-server systems using foreground-background processing. Available at: http://www.cas.mcmaster.ca/~downd/fbpspaper5.pdf (accessed October 3, 2019).
- Hyytia, E., and R. Righter. 2016. Routing jobs with dead-lines to heterogeneous parallel servers. Operations Research Lett. 44(4):507-513.
- Avi-Itzhak, B., and S. Halfin. 1989. Expected response times in a non-symmetric time sharing queue with a limited number of service positions. 12th Teletraffic Congress (International) Proceedings. Torino. Art. ID: 5.4B.2. 7 p.
- Schroeder, B., M. Harchol-Balter, A. Iyengar, E. Nahum, and A. Wierman. 2006. How to determine a good multi-programming level for external scheduling. 22nd Con
ference (International) on Data Engineering Proceedings. Atlanta, GA. 60.
- Konovalov, M. G. 2007. Metody adaptivnoy obrabotki in- formatsii i ikh prilozheniya [Methods of adaptive information processing and their applications]. Moscow: IPI RAN. 212 p.
- Konovalov, M. G., and R.V. Razumchik. 2015. Obzor modeley i algoritmov razmeshcheniya zadaniy v sis- temakh s parallel'nym obsluzhivaniem [Methods and al-gorithms for j ob scheduling in systems with parallel service: A survey]. Informatika i ee Primeneniya - Inform. Appl. 9(4):56-67.
- Konovalov, M. G., and R. V. Razumchik. 2019. Minimizatsiya srednego vremeni prebyvaniya v nenablyudaemykh sistemakh s parallel'nym obsluzhivaniem i distsiplinoy spravedlivogo razdeleniya protsessora v serverakh [Mini-mizing mean response time in non-observable distributed processing systems with nodes, operating under egalitarian processor sharing policy]. Informatsionnye protsessy [Information Processes] 19(3):327-338.
- Konovalov, M.G., and R.V. Razumchik. 2019. Minimizing mean response time in non-observable distributed systems with processor sharing nodes. Commun. ECMS 33(1):456-461.
[+] About this article
Title
MIXED POLICIES FOR ONLINE JOB ALLOCATION IN ONE CLASS OF SYSTEMS WITH PARALLEL SERVICE
Journal
Informatics and Applications
2019, Volume 13, Issue 4, pp 54-59
Cover Date
2019-12-30
DOI
10.14357/19922264190409
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
parallel service; dispatching policy; service discipline; sojourn time; deadline violation
Authors
M. G. Konovalov  and R. V. Razumchik , 
Author Affiliations
Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
|