考虑处理机释放时间的可分任务调度优化模型

doi:10.3969/j.issn.1001-2400.2016.01.009

Abstract

Abstract:

Divisible-load scheduling has become an increasingly hot subject in the research on information technologies in recent years. Most existing divisible-load scheduling models assume that all processors are idle at the beginning of workload assignment. In fact, many processors may still in the busy state when a new workload arrives. Processors may have different waiting times from the busy state to the idle, that is, processors have different release times. This paper proposes a new release time aware divisible-load scheduling model with hybrid time constraints and designs an effective global optimization genetic algorithm to solve it. Finally, experimental results show the effectiveness of the proposed model and the efficiency of the proposed algorithm.

Key words: divisible-load scheduling, release time, hybrid time constraints, genetic algorithm

WANG Xiaoli;WANG Yuping;MENG Kun. Release time aware divisible-load scheduling optimization model[J].J4, 2016, 43(1): 47-53.

References

［1］ BHARADWAJ V, GHOSE D, MANI V, et al. Scheduling Divisible Loads in Parallel and Distributed Systems ［M］. Los Alamitos: IEEE Computer Society Press, 1996.
［2］ BHARADWAJ V, GHOSE D, ROBERTAZZI T G. Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems ［J］. Cluster Computing, 2003, 6(1): 7-18.
［3］ ROBERTAZZI T G. Ten Reasons to Use Divisible Load Theory ［J］. Computer, 2003, 36: 63-68.
［4］ MANI V, GHOSE D. Distributed Computation in Linear Networks: Closed Form Solutions ［J］. IEEE Transactions on Aerospace and Electronic Systems, 1994, 30: 471-483.
［5］ BATAINEH S, ROBERTAZZI T G. Ultimate Performance Limits for Networks of Load Sharing Processors ［C］//Proceedings of the Conference on Information Sciences and Systems. New York: Princeton University, 1992: 794-799.
［6］ GHOSE D, MANI V. Distributed Computation with Communication Delays: Asymptotic Performance Analysis ［J］. Journal of Parallel and Distributed Computing, 1994, 23: 293-305.
［7］ BHARADWAJ V, GHOSE D, MANI V. Optimal Sequencing and Arrangement in Distributed Single-Level Networks with Communication Delays ［J］. IEEE Transactions on Parallel and Distributed Systems, 1994, 5: 968-976.
［8］ KIM H J, JEE G I, LEE J G. Optimal Load Distribution for Tree Network Processors ［J］. IEEE Transactions on Aerospace and Electronic Systems, 1996, 32(2): 607-612.
［9］ SURESH S, MANI V, OMKAR S N. The Effect of Start-up Delays in Scheduling Divisible Load on Bus Networks: an Alternate Approach ［J］. Journal of Computational and Applied Mathematics, 2003, 46(10/11): 1545-1557.
［10］ BHARADWAJ V, LI X L, CHUNG C K. On the Influence of Start-up Costs in Scheduling Divisible Load on Bus Networks ［J］. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(12): 1288-1305.
［11］ SOHN J, ROBERTAZZI T G. Optimal Load Sharing for a Divisible Job on a Bus Network ［J］. IEEE Transactions on Aerospace and Electronic Systems, 1996, 32(1): 34-40.
［12］ SHANG M S. Optimal Algorithm for Scheduling Large Divisible Workload on Heterogeneous System ［J］. Applied Mathematical Modeling, 2008, 32: 1682-1695.
［13］ MURUGESAN G, CHELLAPPAN C. Multi-source Task Scheduling in Grid Computing Environment Using Linear Programming ［J］. International Journal of Computer Science and Engineering, 2014, 9(1): 80-85.
［14］ IYER G N, VEERAVALLI B, KRISHNAMOORTHY S G. On Handling Large-scale Polynomial Multiplication in Compute Cloud Environments using Divisible Load Paradigm ［J］. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(1): 820-831.
［15］ LIN W, LIANG C, WANG J Z, et al. Bandwidth-aware Divisible Task Scheduling for Cloud Computing ［J］. Software: Practice and Experience, 2014, 44(2): 163-174.
［16］ SHI H Y, WANG W L, KWOK N M, et al. Adaptive Indexed Divisible Load Theory for Wireless Sensor Network Workload Allocation ［J］. International Journal of Distributed Sensor Networks, 2013, 2013: 484796.
［17］ MAMAT A, LU Y, DEOGUN J, et al. Efficient Real-time Divisible Load Scheduling ［J］. Journal of Parallel and Distributed Computing, 2012, 72(12): 1603-1616.
［18］ HU M, VEERAVALLI B. Dynamic Scheduling of Hybrid Real-time Tasks on Clusters ［J］. IEEE Transactions on Computers, 2013, 99: 1.
［19］ HU M, VEERAVALLI B. Requirement-aware Strategies for Scheduling Real-time Divisible Loads on Clusters ［J］. Journal of Parallel and Distributed Computing, 2013, 73(8): 1083-1091.
［20］ CHOI K, ROBERTAZZI T G. An Exhaustive Approach to Release Time Aware Divisible Load Scheduling ［J］. International Journal of Internet and Distributed Computing Systems, 2011, 1(2): 40-50.
［21］ COSTA A, CAPPADONNA F A, FICHERA S. A Novel Genetic Algorithm for the Hybrid Flow Shop Scheduling with Parallel Batching and Eligibility Constraints［J］. The International Journal of Advanced Manufacturing Technology, 2014, 75(5-8): 833-847.

[1]	SUN Qian,ZHANG Jiarui,GAO Ling,WANG Yuxiang,YANG Jianfeng. Health prediction algorithm for edge layer nodes [J]. Journal of Xidian University, 2020, 47(3): 32-39.
[2]	XIE Fan,FENG Lifang. Visible light assisted relay communication system and a power allocation scheme [J]. Journal of Xidian University, 2020, 47(1): 95-103.
[3]	YANG Yajun,CHEN Zhang. Hardware trojan attack methods and security analysis under split manufacturing [J]. Journal of Xidian University, 2019, 46(4): 167-175.
[4]	GUO Pengcheng;WANG Xing;CHENG Siyi;WANG Feng. Non-linear frequency modulated signal decomposition based on the improved chirplet time-frequency atom [J]. Journal of Xidian University, 2018, 45(1): 123-128.
[5]	YUAN Haobo;WU Zhengguo;HOU Jianqiang;DANG Xiaojie. Accurate optimization algorithm for the antenna phase center [J]. Journal of Xidian University, 2017, 44(5): 64-68.
[6]	REN Yanqing;LU Zhiyu;BA Bin;WANG Daming. Fast direct position determination method based on the sharpening function genetic algorithm [J]. Journal of Xidian University, 2017, 44(4): 144-150.
[7]	GONG Changmei;SHAO Xiaopeng;WU Tengfei;DAI Weijia;LIU Jietao;ZHANG Jianqi. Focusing of random scattering light by global optimization amplitude modulation [J]. J4, 2016, 43(1): 99-104.
[8]	WU Kai;SU Tao. Design and application of the allpass fractional delay filter [J]. J4, 2015, 42(4): 8-13.
[9]	GE Lin;JI Xinsheng;JIANG Tao. Situation prediction of network information content security incidents using E-IGA-RBF [J]. J4, 2015, 42(4): 107-113.
[10]	FENG Xueyong;YANG Lin;GONG Shuxi;WANG Jianxiao. Design of a plane-wave generator for base station antenna measurements [J]. J4, 2015, 42(3): 33-37.
[11]	WANG Ershen;ZHANG Shufang;CAI Ming;PANG Tao. GPS receiver autonomous integrity monitoring algorithm using the genetic particle filter [J]. J4, 2015, 42(1): 136-141.
[12]	CHEN Lihua;WANG Shicheng;LIU Zhiguo;SUN Yuan. Low cost geomagnetic matching navigation method [J]. J4, 2013, 40(1): 118-122+188.
[13]	Renqingdaoerji;WANG Yuping. Schema theorem based on limited character set encoding and its proof [J]. J4, 2012, 39(6): 99-103.
[14]	ZHANG Yan;FENG Dazheng;QU Xiaoning. A Hybrid Phase Unwrapping Algorithm Combining Branch-Cut and Surface-Fitting for InSAR [J]. J4, 2012, 39(5): 47-53.
[15]	MIAO Zhuang;CHENG Yongmei;PAN Quan;HOU Jun. Research on the approximation algorithm of the evidential thoeory [J]. J4, 2011, 38(2): 187-193.

Release time aware divisible-load scheduling optimization model

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10