Cat Swarm Optimization Task Scheduling Algorithm Based on Double Arbitration Mechanism and Taguchi Orthogonal Method

Xingming ZHANG; Congyue YIN; Shuai WEI; Shengzhao YE; Ping LÜ

doi:10.11999/JEIT180215

Volume 40 Issue 10

Sep. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(10): 2521-2528

Xingming ZHANG, Congyue YIN, Shuai WEI, Shengzhao YE, Ping LÜ. Cat Swarm Optimization Task Scheduling Algorithm Based on Double Arbitration Mechanism and Taguchi Orthogonal Method[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2521-2528. doi: 10.11999/JEIT180215

Citation:

Xingming ZHANG, Congyue YIN, Shuai WEI, Shengzhao YE, Ping LÜ. Cat Swarm Optimization Task Scheduling Algorithm Based on Double Arbitration Mechanism and Taguchi Orthogonal Method[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2521-2528. doi: 10.11999/JEIT180215

Citation:

Xingming ZHANG, Congyue YIN, Shuai WEI, Shengzhao YE, Ping LÜ. Cat Swarm Optimization Task Scheduling Algorithm Based on Double Arbitration Mechanism and Taguchi Orthogonal Method[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2521-2528. doi: 10.11999/JEIT180215

PDF( 2497 KB)

Cat Swarm Optimization Task Scheduling Algorithm Based on Double Arbitration Mechanism and Taguchi Orthogonal Method

doi: 10.11999/JEIT180215

National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China

Funds: The National Science Technology Major Project (2016ZX01012101), The National Natural Science Foundation of China (61572520, 61521003)

Received Date: 2018-03-07
Rev Recd Date: 2018-07-25

Available Online: 2018-08-02

Publish Date: 2018-10-01

Abstract

Abstract

To solve communication conflicts and algorithm running time problem in task scheduling process of heterogeneous computing system, a cat swarm optimization task scheduling algorithm is proposed based on double arbitration mechanism and Taguchi orthogonal method. Firstly, the double arbitration mechanism is used to manage the task resources, and the task assignment is dynamically decided to avoid effectively communication conflicts. Then, the Taguchi orthogonal method is applied to the tracking mode of the cat swarm optimization process to reduce the algorithm running time and improve the quality of the solution. Experimental results show that the algorithm runs at a rate of at least about 10% faster than other algorithms. The algorithm performs best in parallelism when dealing with a large number of tasks and has considerable advantages in heterogeneous environments.
- Heterogeneous computing,
- Task scheduling,
- Cat swarm optimization,
- Double arbitration,
- Taguchi orthogonal method

FullText(HTML)

References(22)

References

KHOKHAR A A, PRASANNA V K, SHAABAN M E, et al. Heterogeneous computing: Challenges and opportunities[J].Computer, 1993, 26(6): 18–27 doi: 10.1109/2.214439

朱晓敏, 贺川, 王建江,等. 异构计算系统中弹性节能调度策略研究[J]. 计算机学报, 2012, 35(6): 1313–1326 doi: 10.3724/SP.J.1016.2012.01313

ZHU Xiaomin, HE Chuan, WANG Jianjiang, et al. An elastic energy-aware scheduling strategy for heterogeneous computing systems[J]. Journal of Computer, 2012, 35(6): 1313–1326 doi: 10.3724/SP.J.1016.2012.01313

MACHOVEC D, PASRICHA S, MACIELEWSKI A A, et al. Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system[C]. IEEE, Parallel and Distributed Processing Symposium Workshops, Lake Buena Vista, USA, 2017: 54–64.

DAOUD M I and KHARMA N. A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks[J]. Journal of Parallel&Distributed Computing, 2011, 71(11): 1518–1531 doi: 10.1016/j.jpdc.2011.05.005

DING Shan, WU Jinhui, XIE Guoqi, et al. A hybrid heuristic-genetic algorithm with adaptive parameters for static task scheduling in heterogeneous computing system[C]. The 14th IEEE International Conference on Embedded Software And Systems, Sydney, Australia, 2017: 761–766.

MORTEZA M and HADI S S. An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph[J]. Applied Intelligence, 2016, 45(3): 695–712 doi: 10.1007/s10489-016-0782-2

JING Chao. Ant-colony optimization based algorithm for energy-efficient scheduling on dynamically reconfigurable systems[C]. The Ninth IEEE International Conference on Frontier of Computer Science and Technology, Sydney, Australia, 2015: 127–134.

KIANPISHEH S, CHARKARI N M, and KARGAHI M. Ant colony based constrained workflow scheduling for heterogeneous computing systems[J]. Cluster Computing, 2016, 19(3): 1–18 doi: 10.1007/s10586-016-0575-8

KUMAR N and VIDVARTHI D P. A novel hybrid PSO–GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems[J]. Engineering with Computers, 2016, 32(1): 35–47 doi: 10.1007/s00366-015-0396-z

WANG Hui, WU Zhij, RAHNAMAVAN S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699–4714 doi: 10.1016/j.ins.2011.03.016

KUMAR Y and SAHOO G. An improved cat swarm optimization algorithm based on opposition-based learning and Cauchy operator for clustering[J]. Journal of Information Processing Systems, 2017, 13(4): 1000–1013 doi: 10.3745/JIPS.02.0022

JIANG Yunlian, SUN Guangzhong, WU Wentao, et al. Efficient communication contention aware scheduling in heterogeneous system[J]. Journal of University of Science&Technology of China, 2006, 8(8): 875–881 doi: 10.3969/j.issn.0253-2778.2006.08.015

BEAUMONT O, BOUDET V, and ROBERT Y. A realistic model and an efficient heuristic for scheduling with heterogeneous processors[C]. Proceeding 16th International Parallel and Distributed Processing Symposium, Ft.Lauderdale, USA, 2002: 1–14.

WANG Yan, LI Kenli, and LI Keqin. Partition scheduling on heterogeneous multicore processors for multi-dimensional loops applications[J]. International Journal of Parallel Programming, 2016, 45(4): 1–26 doi: 10.1007/s10766-016-0445-2

LE D V, GO B S, SONG M G, et al. Mathematical design of a pulsed power induction coilgun system using the taguchi method[C]. IEEE 21st International Conference on Pulsed Power (PPC), Brighton, UK, 2017: 1–5.

TSAI J T, FANG J C, and CHOU J H. Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm[J]. Computers&Operations Research, 2013, 40(12): 3045–3055 doi: 10.1016/j.cor.2013.06.012

SAMARAWEERA L, THALAGALA S, GAMAGE P, et al. Optimization of green sand casting parameters using taguchi method to improve the surface quality of white cast iron grinding plates—A case study[C]. IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, 2017: 1723–1727.

KUMAR B, KALRA M, and SINGH P. Discrete binary cat swarm optimization for scheduling workflow applications in cloud systems[C]. IEEE International Conference on Computational Intelligence & Communication Technology, Ghaziabad, India, 2017: 1–6.

GABI D, ISMAIL A S, ZAINAL A, et al. Cloud scalable multi-objective task scheduling algorithm for cloud computing using cat swarm optimization and simulated annealing[C]. International Conference on Information Technology, Amman, Jordan, 2017: 1007–1012.

SUTER F and HUNOLD D S. A synthetic task graph generator[OL]. https://github.com/frs69wq/daggen.2017.4.

TOPCUOGLU H, HARIRI S, and WU Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260–274 doi: 10.1109/71.993206

ARABNELAD H and BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel&Distributed Systems, 2014, 25(3): 682–694 doi: 10.1109/TPDS.2013.57

Relative Articles

Supplements(0)

Cited By

Proportional views