|
Article information
2016 , Volume 21, ¹ 5, p.77-94
Krotov K.V., Krotova T.Y.
Gradient method for construction dynamic data processing schedules in a conveyor system with various data arrival time and different priorities
Nowadays the task of handling of pipelined data using various priority programs is an actual task. High priority data is received for processing by the system at later time points. It interrupts the processing of the previously received low priority data on the conveyor segments. As the disturbance, it violates the planned course of the computational process. Reducing the effect of these disturbances is possible by building dynamic scheduling that accounts for entering the high-data system. The model of the computer data processing with different priorities, type of endpoint of generated dynamic scheduling, as well as a method of constructing dynamic scheduling along with the search for locally optimal solutions within the neighbourhood with a variety of metrics are executed for the task. The formulated method for constructing dynamic scheduling is based on the conditions that allow the determination the important data in the sequences on each segment of the pipeline. The order in these sequences can be changed, and the data order may be not. For data, for which the order of the processing sequences can be changed, a dynamic schedule based on the received high-priority data is arranged. Comparison of the results based on the dynamic scheduling that uses this method and the results of the build schedules, which use the heuristic rules is completed. The heuristic rules take into account the priorities for organizing data in a sequence of processing them on the conveyor segments. Studies have shown that this method for construction of the dynamic scheduling is 25-40 % more efficient then the procedure that uses heuristic rules that take into account these priorities.
[full text]
Keywords: conveyor system, data processing, programs execution schedule, greedy algorithm, dynamic scheduling, priorities
Author(s):
Krotov Kirill Victorovich
PhD. , Associate Professor
Position: Associate Professor
Office: Sevastopol State University
Address: 290053, Russia, Sevastopol, Universitetskaya street, 33
Phone Office: (8692)435-364
E-mail: krotov_k1@mail.ru
Krotova Tatiana Yurievna
Position: Senior Fellow
Office: Sevastopol State University
Address: 290053, Russia, Sevastopol, Universitetskaya street, 33
Phone Office: (8692)435-100
E-mail: sevas_tan@mail.ru
References:
Ñïèñîê ëèòåðàòóðû / References
[1] Krotov, K.V. Gradient Method of making a static schedules for conveyor systems based on greedy strategies. Novosibirsk State University Journal of Information Technologies. 2015; 13(1):55–73. (In Russ.)
[2] Toporkov, V.V. Modeli raspredelennykh vychisleniy [Models of distibuted computing]. Moscow: FIZMATLIT; 2004: 320. (In Russ.)
[3] Morton, T.E., Pentico, D.W. Heuristic scheduling systems: with applications to production systems and project management. Wiley series in engineering & technology management. John Wiley & Sons; 1993: 720.
[4]Jakobovic´, D, Budin, L Dynamic scheduling with genetic programming. Genetic Programming, 9th European Conference, EuroGP2006. Lecture Notes in Computer Science, LNCS 3905, pp. 238–249.
[5] Barbosa da Silva, E., Costa, G. M., Fatima de Souza da Silva, M., Pereira, F. H. Simulition study of dispatching rules in stochastic job shop dynamic scheduling. World Journal of Modelling and Simulation. 2014; 10(3):231–240.
[6] Frachtenberg, E., Feitelson, D.G., Ferrandez, Ju., Petrini, F. Parrallel job scheduling under dynamic workloads. 9th Workshop in Job Scheduling Strategies for Parallel Processing. JSSPP2003. Seattle, WA, USA. 24 June. 2003.
[7] Lee, S., Kim, H., Lee, J. A Soft aperiodic task scheduling algorithm in dynamic priority system. 2nd International Workshop on Real-Time Computing Systems and Applications. October 25 – 27, 1995. Japan, Tokyo; 1995:68–72.
[8] Cosnard, M., Jeannot, Å., Rougent, L. Low Memory Cost Dynamic Scheduling of Large Coarse Grain Task Graphs. International Parallel Processing Symposium. Symposium on Parallel and Distributed Processing (IPPS/SPDP’98). USA, Florida: Orlando; 1998:524-530. Available at: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5485&punumber%3D5485%26filter%3DAND%28p_IS_Number%3A14764%29%26pageNumber%3D3&pageNumber=4
[9] Dahal, K., Hossain, A., Varghese, B., Abraham, A., Xhafa, F., Daradoumis, A. Scheduling in multiprocessor system using genetic algoritm. 7th International Conference on Computer Information System and Industrial Management Application. Czech Republic, Ostrava; 2008: 281–286.
[10] Lin, S.-C., Goodman, E.D., Punch, W.F. A genetic algorithm approach to dynamic job shop scheduling problems. 7th International Conference on Genetic Algoritm. East Lansing. USA. July 19-23. 1997: 481–488.
[11] Kochetov, Yu.A., Mladenovich, N., Khansen, P. Local search with alternating neighborhoods. Diskretnyi Analiz i Issledovanie Operatsii. Series 2. 2003; 10(1):11-43. (In Russ.)
[12] Kononova, P.A. Lower and upper bounds for the optimal makespan in the multimedia problem. Diskretnyi Analiz i Issledovanie Operatsii. 2012; 19(1):59-73. (In Russ.)
[13] Kononova, P.A., Kochetov, Yu.A Variable neighborhood search for two machine flowshop problem with a passive prefetch. Diskretnyi Analiz i Issledovanie Operatsii. 2012; 10(5):63-82. (In Russ.)
[14] Kononova, P.A. Lokal'nyy poisk s chereduyushchimisya okrestnostyami dlya zadachi Dzhon-sona s passivnym buferom [Local search with alternating neighborhoods for the Johnson problem with passive buffer]. Dissertatsionnaya rabota kandidata fiz. -mat. nauk. Novosibirsk: Sobolev Institute of Mathematics; 2012. 106 p. (In Russ.)
[15] Kovalev, M.M. Matroidy v diskretnoy optimizatsii [Matroids in discrete optimization]. Moscow: Editorial URSS; 2003: 224. (In Russ.)
Bibliography link:
Krotov K.V., Krotova T.Y. Gradient method for construction dynamic data processing schedules in a conveyor system with various data arrival time and different priorities // Computational technologies. 2016. V. 21. ¹ 5. P. 77-94
|
