基于智能优化算法的网格任务调度策略研究
|
摘要
任务分配问题,一般是NP完全问题。存在许多任务调度问题的具体实例的启发式算法,但多数情况下效率都不高。本文主要探索了几种智能优化算法及其改进策略在任务调度中的应用,主要包括均场退火算法、微正则均场退火算法、模糊动态遗传算法等。
首先将均场退火算法(MFA)应用到网格任务调度中,构造了满足各种约束条件的能量函数和状态更新函数等,并进行了仿真实验,验证了均场退火算法的有效性。
接着本文对微正则退火算法作了改进,并将其应用到任务调度中。首先提出了分段的能量奖励策略和混合能量补偿策略。其次,在基本微正则退火算法的基础上,提出了微正则均场退火算法(MMFA),采用均场退火算法的能量函数形式和新状态产生方法,保证新状态都是向能量降低的方向转移,从而加快搜索速度,提高算法性能。
最后针对网格任务调度的动态特性,提出并实现了一种改进的遗传算法—模糊动态遗传算法FDGA,重新对遗传算法编码机制、适应度函数确定、选择算子、交叉算子、变异算子等进行了设计,在编码阶段考虑了网格的动态性,适应度函数采用基于模糊数学的模糊评价机制,综合考虑到总的完成时间、主机的空闲时间和任务的deadline要求等性能指标,根据网格系统各服务节点的计算能力、负载等状态进行动态调度,从而向用户提供较优性能。同时,在OPNET环境中构建了一个可扩展的局部网格仿真平台,对所提出的算法进行了仿真实验,结果表明模糊动态遗传算法具有很好的优化能力,提供了较好的服务质量。
The problem of scheduling tasks onto resources, otherwise known as the task allocation problem, is an NP-hard problem for the general case. Many heuristic algorithms exist for specific instances of the task scheduling problem, but are inefficient for a more general case. We have investigated some intelligent optimization algorithms, such as Mean Field Annealing Algorithm (MFA), Microcanonical Annealing Algorithm (MA), Genetic Algorithm (GA), etc. And we have applied these algorithms to task scheduling in grid.
Firstly, Mean Field Annealing algorithm is applied to the grid task scheduling. We construct the energy function and status-updating function, which meet a variety of restrictive conditions. And simulation experiments show the good ability of optimization.
Then we improve the Microcanonical Annealing Algorithm, and applied to the task scheduling. Two strategies are proposed, which are energy incentives strategy with subsection and hybrid energy compensation strategy. And we adopt the he energy function and status-updating function of MFA algorithm in the MA algorithm, which formed a new algorithm---Microcanonical Mean Field Annealing Algorithm (MMFA). This new algorithm ensures that the energy of new state is reduced, so speeds up the search speed and improves performance of the algorithm.
Finally, Fuzzy Dynamic Genetic Algorithm (FDGA) is proposed for grid task scheduling. In FDGA, we develop a new coding system considering the dynamics of the grid, and design new operators of selection, crossover and mutation. The fitness function is constructed based on fuzzy evaluation mechanisms, taking into account the makespan, the idle time of hosts and the deadline requirements of tasks. According to the computing power of hosts and load states of network, dynamic scheduling algorithm is carried out to provide users with optimum performance. A local grid simulation model is constructed by OPNET. We realize the FDGA algorithm in this simulation, and compare with other grid task scheduling algorithms (such as Min-min, Max-min, etc.). The simulation results show that the FDGA scheduling algorithm has good ability of optimization, and provide good quality of service.
首先将均场退火算法(MFA)应用到网格任务调度中,构造了满足各种约束条件的能量函数和状态更新函数等,并进行了仿真实验,验证了均场退火算法的有效性。
接着本文对微正则退火算法作了改进,并将其应用到任务调度中。首先提出了分段的能量奖励策略和混合能量补偿策略。其次,在基本微正则退火算法的基础上,提出了微正则均场退火算法(MMFA),采用均场退火算法的能量函数形式和新状态产生方法,保证新状态都是向能量降低的方向转移,从而加快搜索速度,提高算法性能。
最后针对网格任务调度的动态特性,提出并实现了一种改进的遗传算法—模糊动态遗传算法FDGA,重新对遗传算法编码机制、适应度函数确定、选择算子、交叉算子、变异算子等进行了设计,在编码阶段考虑了网格的动态性,适应度函数采用基于模糊数学的模糊评价机制,综合考虑到总的完成时间、主机的空闲时间和任务的deadline要求等性能指标,根据网格系统各服务节点的计算能力、负载等状态进行动态调度,从而向用户提供较优性能。同时,在OPNET环境中构建了一个可扩展的局部网格仿真平台,对所提出的算法进行了仿真实验,结果表明模糊动态遗传算法具有很好的优化能力,提供了较好的服务质量。
The problem of scheduling tasks onto resources, otherwise known as the task allocation problem, is an NP-hard problem for the general case. Many heuristic algorithms exist for specific instances of the task scheduling problem, but are inefficient for a more general case. We have investigated some intelligent optimization algorithms, such as Mean Field Annealing Algorithm (MFA), Microcanonical Annealing Algorithm (MA), Genetic Algorithm (GA), etc. And we have applied these algorithms to task scheduling in grid.
Firstly, Mean Field Annealing algorithm is applied to the grid task scheduling. We construct the energy function and status-updating function, which meet a variety of restrictive conditions. And simulation experiments show the good ability of optimization.
Then we improve the Microcanonical Annealing Algorithm, and applied to the task scheduling. Two strategies are proposed, which are energy incentives strategy with subsection and hybrid energy compensation strategy. And we adopt the he energy function and status-updating function of MFA algorithm in the MA algorithm, which formed a new algorithm---Microcanonical Mean Field Annealing Algorithm (MMFA). This new algorithm ensures that the energy of new state is reduced, so speeds up the search speed and improves performance of the algorithm.
Finally, Fuzzy Dynamic Genetic Algorithm (FDGA) is proposed for grid task scheduling. In FDGA, we develop a new coding system considering the dynamics of the grid, and design new operators of selection, crossover and mutation. The fitness function is constructed based on fuzzy evaluation mechanisms, taking into account the makespan, the idle time of hosts and the deadline requirements of tasks. According to the computing power of hosts and load states of network, dynamic scheduling algorithm is carried out to provide users with optimum performance. A local grid simulation model is constructed by OPNET. We realize the FDGA algorithm in this simulation, and compare with other grid task scheduling algorithms (such as Min-min, Max-min, etc.). The simulation results show that the FDGA scheduling algorithm has good ability of optimization, and provide good quality of service.
引文
[1] I. Foster, C. Kesselman, and S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. Int. J. of Supercomputing Applications, 2001
[2]朱福喜,何炎祥,并行分布计算中的调度算法理论与设计,武汉:武汉大学出版社,2003
[3] Buyya R., Abramson D., Giddy J. Nimrod/G: An architecture for a resource management and scheduling system in a global computational grid. In: Proc. of the High Performance Computing in the Asia-Pacific Region. 2000
[4] Figueira, M., Hayes, J., Obertelli, G., etc. Adaptive Computing on the Grid Using AppLeS. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(4): 369-382
[5] Frey, J., Tannenbaum, T., Livny, M., Foster, I., Tuecke, S. Condor-G: a computation management agent for multi-institutional grids. High Performance Distributed Computing, 2001: 55-63
[6] http://www.globus.org
[7] http://legion.virginia.edu
[8] H. EI-Rewini, T. Lewis, H. Ali. Task Scheduling in Parallel and Distributed Systems. Prentice Hall, Englewood Cliffs, New Jersey, 1994
[9] S. S. Fatima, M. Wooldridge. Adaptive Task and Resource Allocation in Multi-Agent Systems. In Agents 2001: Proceedings of the Fifth International Conference on Autonomous Agents Montreal, 2001
[10]林成江,李三立.一种可适应的分市式动态负载平衡策略及其仿真.计算机学报,1995,18(10):721-727
[11]田新民,王鼎兴,沈美明,等.并行任务动态派生的积极惰性化控制方法.软件学报,1994.2,5(2)
[12]王怀民,吴泉源,高洪奎等.基于Agent的分布计算环境.计算机学报,1996.3,19(3)
[13]周笑波,汲化,谢立.一个基于PVM的异构型智能分布式任务调度系统.计算机科学,1996.11,23(6):3-33
[14]刘大有,陈建中,钟绍春.多Agent系统中的一对一协商谈判过程.软件学报,863高技术项目智能机主题专刊(1996):159-165
[15]翁楚良.基于经济机制的网格资源管理与调度策略的研究:[博士学位论文].上海:上海交通大学,2004
[16] R. Armstrong, D. Hensgen, T. Kidd. The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions. In: Proceedings of the 7th IEEE Heterogeneous Computing Workshop, Orlando, Florida, IEEE Computer Society, March 1998. 79-87
[17] R. Freund, M. Gherrity, S. Ambrosius, etc. Scheduling Resources in Multi-user, Heterogeneous, Computing Environments with SmartNet. In: Proceedings of the 7th IEEE Heterogeneous Computing Workshop, Orlando, Florida, IEEE Computer Society, March 1998. 184-199
[18] R. Freund, H. Siegel. Heterogeneous Processing. IEEE Computer. 1993, 26(6): 13-17
[19] M. Maheswaran, S. Ali, H. Siegel, etc. Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. Journal of Parallel and Distributed Computing. 1999, 59(2): 107-131
[20] I. Foster, A. Roy, V. Sander. A Quality of Service Architecture that Combines Resource Reservation and Application Adaptation. In: Proceeding of the 8th International Workship on Quality of Service, Pittsburgh, PA, June 2000. 181-188
[21] H. Singh, A. Youssef. Mapping and Scheduling Heterogeneous Task Graphs Using Genetic Algo rithms. In: Proceedings of the 5th IEEE Heterogeneous Computing Workshop, Honolulu, Hawai, IEEE Computer Society, April 1996. 86-97
[22] M. Srinivas, L. Patnaik. Genetic Algorithms: A Survey. IEEE Computer. 1994, 27(6): 17-26
[23] L. Wang, H. Siegel, V. Roychowdhury, A. Maciejewski. Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach. Journal of Parallel and Distributed Computing. 1997, 47(1): 8-22
[24] M. Coli, P. Palazzari. Real Time Pipelined System Design Through Simulated Annealing. Journal of Systems Architecture, 1996, 42(6-7): 465-475
[25] A. Zomaya, R. Kazman. Simulated Annealing Techniques, In: M. Atallah (editor), Algorithms and Theory of Computation Handbook, CRC Press, 1999
[26] H. Chen, N. Flann, D. Watson. Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(2): 126-136
[27] P. Shroff, D. Watson, N. Flann, etc. Genetic Simulated Annealing for Scheduling Datadependent Tasks in Heterogeneous Environments. In: Proceedings of the 5th IEEE Heterogeneous Computing Workshop, Honolulu, Hawai, IEEE Computer Society, April 1996. 98-104
[28] M. Kafil, I. Ahmad. Optimal Task Assignment in Heterogeneous Distributed Computing Systems. IEEE Concurrency, 1998, 6(3): 42-51
[29] C. Shen, W. Tsai. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing System Using a Minimax Criterion. IEEE Transactions on Computers. 1985, 34(3): 197-203
[30] H. Casanova, D. Zagorodnov, F. Berman, etc. Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. In: Proceedings of the 9th Heterogeneous Computing Workshop, Cancun, Mexico, IEEE Computer Society, May 2000. 349-363
[31] Q. Ding, G. Chen. A Benefit Function Mapping Heuristic for a Class of Meta-tasks in Grid Environment. In: Proceedings of the 1st IEEE/ACM International Symposium on Cluster Computing and the Grid, Brisbane, Australia, IEEE Computer Society, May 2001. 654-659
[32] A. Yarkihan, J. Dongarra. Experiments with Scheduling Using Simulated Annealing in a Grid Environment. In: Proceedings of the 3rd International Workshop on Grid Computing, Baltimore, MD, LNCS, November 2002, Vol. 2536: 232-242
[33] V. Subramani, R. Kettimuthu, S. Srinivasan, etc. Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests. In: Proceedings of 11th IEEE International Symposium on High Performance Distributed Computing, Edinburgh, Scotland, IEEE Computer Society, July 2002. 359-367
[34] H. Chen, M. Maheswaran. Distributed Dynamic Scheduling of Composite Tasks on Grid Computing System. In Proceedings of the International Parallel and Distributed Processing Symposium: IPDPS 2002 Workshops (CDROM), April 2002, Fort Lauderdale, Florida
[35] A. Takefusa, H. Casanova, S. Matsuoka, etc. A Study of Deadline Scheduling for Client/server Systems on the Computational Grid. In: Proceedings of 10th IEEE International Symposium on High Performance Distributed Computing, San Francisco, CA, IEEE Computer Society, August 2001. 406-415
[36] E. Heymann, M. Senar, E. Luque, etc. Adaptive Scheduling for Master-Worker Applications on the Computational Grid. In: Proceedings of the 1st IEEE/ACM International Workshop on Grid Computing, Bangalore, India, December 2000, LNCS, Vol. 1971: 214-227
[37] J. Hollingsworth, S. Maneewongvatana. Imprecise Calendars: an Approach to Scheduling Computational Grids. In: Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, TX, IEEE Computer Society, May 1999. 352-359
[38] C. Ernemann, V. Hamscher, U. Schwiegelshohn, etc. On Advantages of Grid Computing for Parallel Job Scheduling. In: Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, May 2002, Berlin, Germany, IEEE Computer Society, 2002. 39-46
[39] V. Di Martino, M. Mililotti. Scheduling in a Grid Computing Environment Using Genetic Algorithms. In: Proceedings of the International Parallel and Distributed Processing Symposium, Fort Lauderdale, Florida, IEEE Computer Society, April 2002. 235-239
[40] V. Hamscher, U. Schwiegelshohn, A. Streit, etc. Evaluation of Job-scheduling Strategies for Grid Computing. In: Proceedings of the 1st IEEE/ACM International Workshop on Grid Computing, December 2000, Bangalore, India, LNCS, Vol. 1971: 191-202
[41] http://www.zurich.ibm.com/grideconomics
[42] http://www.gridbus.org/ecogrid
[43]王凌,智能优化算法及其应用,北京:清华大学出版社,2001
[44] I. Foster, C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Fransisco, CA, 1999
[45] http://www.w3.org/2002/ws
[46] I. Foster, C. Kesselman, J. Nick, etc. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. http://www.globus.org/research/papers/ogsa.pdf, June 2002
[47] K. Czajkowski, D.F. Ferguson, I. Foster, etc. The WS-Resource Framework Version 1.0, http://www-106.ibm.com/developerworks/library/ws-resource/ws-wsrf.pdf, March 2004
[48] Guojie Li, Zhiwei Xu, Yuan Wang, Wei Li. The Vega Grid and autonomous decentralized systems. Autonomous Decentralized System, 2002. The 2nd International Workshop on, 6-7 Nov. 2002. 2-7
[49] http://people.cs.uchicago.edu/~krangana/ChicSim.html
[50] W. E. Johnston, D. Gannon, B. Nitzberg. Grids as Production Computing Environments: The Engineering Aspects of NASA's Information Power Grid. Eighth IEEE International Symposium on High Performance Distributed Computing, Redondo Beach, CA, Aug. 1999
[51] R.Buyya, H.Stockinger. Economic models for resource management andscheduling in Grid computing. The Journal of Concurrency and Computation: Practice and Experience (CCPE) Special issue on Grid computing environments, 2002
[52] K. Nowinski, B. Lesyng, M. Niezgódka, P. Bala. Project EUROGRID (abstract). PIONIER 2001 Conference Proceedings, pp. 187-191, Poznan 2001, ISBN 83-913639-2-9
[53] John P. Stenbit. Moving Power to the Edge. CHIPS - The Department of the Navy Information Technology Magazine, Summer 2003, 21(3)
[54] Catlett C. The philosophy of TeraGrid: building an open, extensible, distributed TeraScale facility. Cluster Computing and the Grid 2nd IEEE/ACM International Symposium CCGRID2002, May 2002. 5-8
[55] http://www.d-grid.de/
[56] Depei Q. CNGrid: a test-bed for Grid technologies in China. Distributed Computing Systems, 2004. FTDCS 2004. Proceedings. 10th IEEE International Workshop on Future Trends of, May 2004. 135–139
[57] Maozhen Li著,王相林等译.网格计算核心计术,北京:清华大学出版社,2006
[58] Hamscher V., Schwiegelshohn U., Streit A., etc. Evaluation of job-scheduling strategies for grid computing. In: Proc. of the Grid Computing (Grid 2000) at 7th Int'l Conf. on High Performance Computing (HiPC 2000). LNCS 1971, Berlin: Springer-Verlag, 2004. 191-202
[59] http://www.cs.wisc.edu/condor/
[60] http://www.sun.com/software/gridware/
[61] http://www.openpbs.org/
[62] http://www.platform.com/products/LSF/
[63] http://nws.cs.ucsb.edu/
[64] A. Gerasoulis, J. Jiao. Rescheduling Support for Mapping Dynamic Scientific Computation onto Distributed Memory Multiprocessors. Proceedings of the Euro-Pa’97, Lecture Notes in Computer Science, Springer-Verlag. August 1997, Passau, Germany
[65] http://www.cactuscode.org/
[66] S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi. Optimization by simulated annealing, Science, 1983, 220: 671-680
[67] Nirwan Ansari, Edwin Hou著,李军,边肇祺译.用于最优化的计算智能,北京:清华大学出版社,1999
[68]阎平凡,张长水,人工神经网络与模拟进化计算,北京:清华大学出版社,2000
[69]杨建刚,人工神经网络实用教程,杭州:浙江大学出版社,2001
[70] Computer Dictionary Online , http://www.computer-dictionary-online.org/index.asp?q=simulated+annealing
[71] L. Ingber. Simulated Annealing: Practice Versus Theory. Mathematical and Computer Modelling, 1993,18: 29-57
[72] L. Ingber, B. Rosen. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison. Mathematical and Computer Modelling, 1992,16: 87-100
[73]汪千山,遗传算法和模拟退火算法的改进和应用:[硕士学位论文],上海;上海交通大学,2001
[74] S. Johnson, R. Aragon, A. McGeoch. Optimization by Simulated Annealing: An Experimental Ebaluation; Part II, Graph Coloring and Number Partitioning, Operations Research, 1991, 39: 378-406
[75] A. Corana, M. Marchesi. Minimizing multimodal functions of continuous variables with the“Simulated Annealing”algorithm, ACM Transactions on Mathematical Software (TOMS), 1987, 13: 262-280
[76] Glauber,R.J. Time-dependent statistics of the Ising model, Journal of Mathematical Physics, 1963, 4: 294-307
[77] D.J. Thouless, P.W. Anderson and R.G. Palmer. Solution of solvable model of a spin glass, Philosophical Magazine, 1977, 35(3): 593-601
[78] C. Peterson, J. R. Anderson. A mean field theory learning algorithm for neural networks, Complex Systems, 1987, 1: 995-1019
[79] C. Peterson, J. R. Anderson. Neural networks and NP-complete optimization problems: a performance study on the graph bisection problem,”Complex Systems, 1988, 2: 59-89
[80] C. Peterson, J. R. Anderson. Applications of mean field theory neural networks, Dept, of Theoretical Physics, Technical Report CS-1153, Univ. of Lund, August 1989. 1-27
[81] C. Peterson, E. Hartman. Explorations of the mean field theory learning algorithm, Neural Networks, August 1989,2: 475-494
[82] C. Peterson, B. Soderberg. A new method for mapping optimization problems onto neural networks, International Journal of Neural Systems, 1989, 1(1): 3-22
[83] N. Ansari, E. S. H. Hou, Y. Yu. A new method to optimize the satellite broadcasting schedules using the mean field annealing of a hopfield neural network, IEEE Transactions on Neural Network, March 1995, 6(2): 470-483
[84] G. L. Bilbro, W. E. Snyder , J. W. Gault. Mean field annealing: aformalism for constructing GNC-like algorithms, IEEE Transactions on Neural Network, 1992, 3(1): 131-138
[85] J. Cook. The mean-field theory of a Q-state neural network model, Journal of Physics A, June 21, 1989, 22(12): 2057-2058
[86] R. A. Nobakht, S. H. Ardalan, D. E. Van den Bout. Adaptive filtering of nonlinear systems with memory by quantized mean field annealing, IEEE Trans. On Signal Processing, February 1993, 41(2): 913-925
[87] D. E. Van den Bout, T. K. Miller. Graph partitioning using annealed networks, IEEE Trans. On Neural Networks, 1990, 1(2): 192-203
[88] Wang, G. and N. Ansari. Maximizing data throughput in an integrated TDMA communication system using mean field annealing, Proc. 1994 IEEE Conference on Global Telecommunications, San Francisco, CA, November 28-December 2, 1994. 329-333
[89] J. Zerubia, R. Chellappa. Mean field annealing using compound Gauss-Markov random fields for edge detection and image estimation, IEEE Trans. On Neural Networks, July 1993, 4(4): 703-709
[90] Grava, C., Buzuloiu, V., Augereau, B., etc. A multi-resolution mean mield annealing algorithm for motion estimation in medical CT image sequences, IEEE International Symposium on Signals, Circuits and Systems, 2007 (ISSCS 2007), July 2007, 1: 1-4
[91]胡卫明,徐俊华,何志均. k-着色问题及其均场退火求解算法,软件学报, 2000, 11(2):256-259
[92]刘海颖,王惠南.平均场退火算法在GPS姿态确定中的应用,中国航空学报(英文版),2004,17(3):165-169
[93]张吉林,陈明,朱能翰.均场退火神经网络算法实现多用户检测,空军雷达学院学报,2004,18(2):56-58
[94]徐宁,何松柏,虞厥邦.通道布线的神经网络优化算法,计算机辅助设计与图形学学报,2002,14(1):1-3
[95]胡卫明. BBL布局的均场退火方法,计算机辅助设计与图形学学报, 2000, 12(1):39-42
[96] Lee, N.J., Louri, A. Microcanonical mean field annealing: a new algorithm for increasing the convergence speed of mean field annealing. 1991 IEEE International Joint Conference on Neural Networks (Cat. No.91CH3065-0), 1991, 2: 941-946
[97] Cattaneo, G., Cesa-Bianchi, N. Microcanonical annealing on neural networks, Neural Networks, SUPPL, 1988, 1(1): 81
[98]徐俊杰.元启发式优化算法理论与应用研究:[博士学位论文],北京邮电大学,2007:62-84
[99]徐俊杰,忻展红.基于微正则退火的频率分配方法,北京邮电大学学报,2007,30(2): 67-70
[100] Barnard S. T. Stereo matching by hierarchical, microcanonical annealing. Proc. of the Tenth International Joint Conference on Artificial Intelligence. 1987. 832-835
[101] Bhandarkar Suchendra M., Zhang Hui. Image segmentation using evolutionary computation. IEEE Transactions on Evolutionary Computation, 1999, 3(1): 1-21
[102] Laurent Herault, Radu Horaud. Figure-ground discrimination: A combinatorial optimization approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. 15(9): 889-914
[103] Duque-Anton M, Kunz D, Ruber B. Channel assignment for cellular radio using simulated annealing. IEEE Transactions on Vehicular Technology, 1993, 42(1): 14-21
[104] Creutz M. Microcanonical Monte Carlo Simulation. Physical Review Letters, 1983, 50(19):1411-1414
[105] J. Huang, H. Liu. Stereo vision using a microcanonical mean field annealing neural network, Network: Computation in Neural Systems, Feb. 1997, 8(1): 87-104
[106] http://ai.ia.ac.cn/chinese/publication/dong/dga.htm
[107]苑希民,李鸿雁,刘树坤等.神经网络和遗传算法在水科学领域的应用,北京:中国水利水电出版社,2002
[108]王小平,曹立明.遗传算法——理论、应用与软件实现,西安:西安交通大学出版社,2002
[109] S.Ali,S.M.Sait, and M.S.T.Benton, GSA: Scheduling and Allocation Using Genetic Algorithm, Proc. EURO-DAC '94, 1994. 84-89
[110] Sekhar Darbha, Dharma P. Agrawal. A task duplication based scalable scheduling algorithm for distributed memory systems, Journal of Parallel and Distributed Computing, Oct.10, 1997, 46(1): 15-27
[111] E.S.H.Hou, N.Ansari, H.Ren. A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, February 1994, 5(2): 113-120
[112] Imtiaz Ahmad, Muhammad K. Dhodhi. Multiprocessor scheduling in a genetic paradigm, Parallel Computing, March 1996, 22(3): 395-406
[113] Yu-Kwong Kwok , Ishfaq Ahmad. Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, Nov. 25, 1997, 47(1):58-77
[114]谢季坚,刘承平.模糊数学方法及其应用(第2版),武汉:华中科技大学出版,2004
[115] Lowen R. Mathematics and fuzziness, PartⅡ, Fuzzy set and Systems, 1989, 30(1): 1-3,49-53
[116]刘普寅,吴孟达.模糊理论及其应用,长沙:国防科技大学出版社,1998
[117] OPNET Technologies. OPNET Modeler Documention, 2002
[2]朱福喜,何炎祥,并行分布计算中的调度算法理论与设计,武汉:武汉大学出版社,2003
[3] Buyya R., Abramson D., Giddy J. Nimrod/G: An architecture for a resource management and scheduling system in a global computational grid. In: Proc. of the High Performance Computing in the Asia-Pacific Region. 2000
[4] Figueira, M., Hayes, J., Obertelli, G., etc. Adaptive Computing on the Grid Using AppLeS. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(4): 369-382
[5] Frey, J., Tannenbaum, T., Livny, M., Foster, I., Tuecke, S. Condor-G: a computation management agent for multi-institutional grids. High Performance Distributed Computing, 2001: 55-63
[6] http://www.globus.org
[7] http://legion.virginia.edu
[8] H. EI-Rewini, T. Lewis, H. Ali. Task Scheduling in Parallel and Distributed Systems. Prentice Hall, Englewood Cliffs, New Jersey, 1994
[9] S. S. Fatima, M. Wooldridge. Adaptive Task and Resource Allocation in Multi-Agent Systems. In Agents 2001: Proceedings of the Fifth International Conference on Autonomous Agents Montreal, 2001
[10]林成江,李三立.一种可适应的分市式动态负载平衡策略及其仿真.计算机学报,1995,18(10):721-727
[11]田新民,王鼎兴,沈美明,等.并行任务动态派生的积极惰性化控制方法.软件学报,1994.2,5(2)
[12]王怀民,吴泉源,高洪奎等.基于Agent的分布计算环境.计算机学报,1996.3,19(3)
[13]周笑波,汲化,谢立.一个基于PVM的异构型智能分布式任务调度系统.计算机科学,1996.11,23(6):3-33
[14]刘大有,陈建中,钟绍春.多Agent系统中的一对一协商谈判过程.软件学报,863高技术项目智能机主题专刊(1996):159-165
[15]翁楚良.基于经济机制的网格资源管理与调度策略的研究:[博士学位论文].上海:上海交通大学,2004
[16] R. Armstrong, D. Hensgen, T. Kidd. The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions. In: Proceedings of the 7th IEEE Heterogeneous Computing Workshop, Orlando, Florida, IEEE Computer Society, March 1998. 79-87
[17] R. Freund, M. Gherrity, S. Ambrosius, etc. Scheduling Resources in Multi-user, Heterogeneous, Computing Environments with SmartNet. In: Proceedings of the 7th IEEE Heterogeneous Computing Workshop, Orlando, Florida, IEEE Computer Society, March 1998. 184-199
[18] R. Freund, H. Siegel. Heterogeneous Processing. IEEE Computer. 1993, 26(6): 13-17
[19] M. Maheswaran, S. Ali, H. Siegel, etc. Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. Journal of Parallel and Distributed Computing. 1999, 59(2): 107-131
[20] I. Foster, A. Roy, V. Sander. A Quality of Service Architecture that Combines Resource Reservation and Application Adaptation. In: Proceeding of the 8th International Workship on Quality of Service, Pittsburgh, PA, June 2000. 181-188
[21] H. Singh, A. Youssef. Mapping and Scheduling Heterogeneous Task Graphs Using Genetic Algo rithms. In: Proceedings of the 5th IEEE Heterogeneous Computing Workshop, Honolulu, Hawai, IEEE Computer Society, April 1996. 86-97
[22] M. Srinivas, L. Patnaik. Genetic Algorithms: A Survey. IEEE Computer. 1994, 27(6): 17-26
[23] L. Wang, H. Siegel, V. Roychowdhury, A. Maciejewski. Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach. Journal of Parallel and Distributed Computing. 1997, 47(1): 8-22
[24] M. Coli, P. Palazzari. Real Time Pipelined System Design Through Simulated Annealing. Journal of Systems Architecture, 1996, 42(6-7): 465-475
[25] A. Zomaya, R. Kazman. Simulated Annealing Techniques, In: M. Atallah (editor), Algorithms and Theory of Computation Handbook, CRC Press, 1999
[26] H. Chen, N. Flann, D. Watson. Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(2): 126-136
[27] P. Shroff, D. Watson, N. Flann, etc. Genetic Simulated Annealing for Scheduling Datadependent Tasks in Heterogeneous Environments. In: Proceedings of the 5th IEEE Heterogeneous Computing Workshop, Honolulu, Hawai, IEEE Computer Society, April 1996. 98-104
[28] M. Kafil, I. Ahmad. Optimal Task Assignment in Heterogeneous Distributed Computing Systems. IEEE Concurrency, 1998, 6(3): 42-51
[29] C. Shen, W. Tsai. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing System Using a Minimax Criterion. IEEE Transactions on Computers. 1985, 34(3): 197-203
[30] H. Casanova, D. Zagorodnov, F. Berman, etc. Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. In: Proceedings of the 9th Heterogeneous Computing Workshop, Cancun, Mexico, IEEE Computer Society, May 2000. 349-363
[31] Q. Ding, G. Chen. A Benefit Function Mapping Heuristic for a Class of Meta-tasks in Grid Environment. In: Proceedings of the 1st IEEE/ACM International Symposium on Cluster Computing and the Grid, Brisbane, Australia, IEEE Computer Society, May 2001. 654-659
[32] A. Yarkihan, J. Dongarra. Experiments with Scheduling Using Simulated Annealing in a Grid Environment. In: Proceedings of the 3rd International Workshop on Grid Computing, Baltimore, MD, LNCS, November 2002, Vol. 2536: 232-242
[33] V. Subramani, R. Kettimuthu, S. Srinivasan, etc. Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests. In: Proceedings of 11th IEEE International Symposium on High Performance Distributed Computing, Edinburgh, Scotland, IEEE Computer Society, July 2002. 359-367
[34] H. Chen, M. Maheswaran. Distributed Dynamic Scheduling of Composite Tasks on Grid Computing System. In Proceedings of the International Parallel and Distributed Processing Symposium: IPDPS 2002 Workshops (CDROM), April 2002, Fort Lauderdale, Florida
[35] A. Takefusa, H. Casanova, S. Matsuoka, etc. A Study of Deadline Scheduling for Client/server Systems on the Computational Grid. In: Proceedings of 10th IEEE International Symposium on High Performance Distributed Computing, San Francisco, CA, IEEE Computer Society, August 2001. 406-415
[36] E. Heymann, M. Senar, E. Luque, etc. Adaptive Scheduling for Master-Worker Applications on the Computational Grid. In: Proceedings of the 1st IEEE/ACM International Workshop on Grid Computing, Bangalore, India, December 2000, LNCS, Vol. 1971: 214-227
[37] J. Hollingsworth, S. Maneewongvatana. Imprecise Calendars: an Approach to Scheduling Computational Grids. In: Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, TX, IEEE Computer Society, May 1999. 352-359
[38] C. Ernemann, V. Hamscher, U. Schwiegelshohn, etc. On Advantages of Grid Computing for Parallel Job Scheduling. In: Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, May 2002, Berlin, Germany, IEEE Computer Society, 2002. 39-46
[39] V. Di Martino, M. Mililotti. Scheduling in a Grid Computing Environment Using Genetic Algorithms. In: Proceedings of the International Parallel and Distributed Processing Symposium, Fort Lauderdale, Florida, IEEE Computer Society, April 2002. 235-239
[40] V. Hamscher, U. Schwiegelshohn, A. Streit, etc. Evaluation of Job-scheduling Strategies for Grid Computing. In: Proceedings of the 1st IEEE/ACM International Workshop on Grid Computing, December 2000, Bangalore, India, LNCS, Vol. 1971: 191-202
[41] http://www.zurich.ibm.com/grideconomics
[42] http://www.gridbus.org/ecogrid
[43]王凌,智能优化算法及其应用,北京:清华大学出版社,2001
[44] I. Foster, C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Fransisco, CA, 1999
[45] http://www.w3.org/2002/ws
[46] I. Foster, C. Kesselman, J. Nick, etc. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. http://www.globus.org/research/papers/ogsa.pdf, June 2002
[47] K. Czajkowski, D.F. Ferguson, I. Foster, etc. The WS-Resource Framework Version 1.0, http://www-106.ibm.com/developerworks/library/ws-resource/ws-wsrf.pdf, March 2004
[48] Guojie Li, Zhiwei Xu, Yuan Wang, Wei Li. The Vega Grid and autonomous decentralized systems. Autonomous Decentralized System, 2002. The 2nd International Workshop on, 6-7 Nov. 2002. 2-7
[49] http://people.cs.uchicago.edu/~krangana/ChicSim.html
[50] W. E. Johnston, D. Gannon, B. Nitzberg. Grids as Production Computing Environments: The Engineering Aspects of NASA's Information Power Grid. Eighth IEEE International Symposium on High Performance Distributed Computing, Redondo Beach, CA, Aug. 1999
[51] R.Buyya, H.Stockinger. Economic models for resource management andscheduling in Grid computing. The Journal of Concurrency and Computation: Practice and Experience (CCPE) Special issue on Grid computing environments, 2002
[52] K. Nowinski, B. Lesyng, M. Niezgódka, P. Bala. Project EUROGRID (abstract). PIONIER 2001 Conference Proceedings, pp. 187-191, Poznan 2001, ISBN 83-913639-2-9
[53] John P. Stenbit. Moving Power to the Edge. CHIPS - The Department of the Navy Information Technology Magazine, Summer 2003, 21(3)
[54] Catlett C. The philosophy of TeraGrid: building an open, extensible, distributed TeraScale facility. Cluster Computing and the Grid 2nd IEEE/ACM International Symposium CCGRID2002, May 2002. 5-8
[55] http://www.d-grid.de/
[56] Depei Q. CNGrid: a test-bed for Grid technologies in China. Distributed Computing Systems, 2004. FTDCS 2004. Proceedings. 10th IEEE International Workshop on Future Trends of, May 2004. 135–139
[57] Maozhen Li著,王相林等译.网格计算核心计术,北京:清华大学出版社,2006
[58] Hamscher V., Schwiegelshohn U., Streit A., etc. Evaluation of job-scheduling strategies for grid computing. In: Proc. of the Grid Computing (Grid 2000) at 7th Int'l Conf. on High Performance Computing (HiPC 2000). LNCS 1971, Berlin: Springer-Verlag, 2004. 191-202
[59] http://www.cs.wisc.edu/condor/
[60] http://www.sun.com/software/gridware/
[61] http://www.openpbs.org/
[62] http://www.platform.com/products/LSF/
[63] http://nws.cs.ucsb.edu/
[64] A. Gerasoulis, J. Jiao. Rescheduling Support for Mapping Dynamic Scientific Computation onto Distributed Memory Multiprocessors. Proceedings of the Euro-Pa’97, Lecture Notes in Computer Science, Springer-Verlag. August 1997, Passau, Germany
[65] http://www.cactuscode.org/
[66] S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi. Optimization by simulated annealing, Science, 1983, 220: 671-680
[67] Nirwan Ansari, Edwin Hou著,李军,边肇祺译.用于最优化的计算智能,北京:清华大学出版社,1999
[68]阎平凡,张长水,人工神经网络与模拟进化计算,北京:清华大学出版社,2000
[69]杨建刚,人工神经网络实用教程,杭州:浙江大学出版社,2001
[70] Computer Dictionary Online , http://www.computer-dictionary-online.org/index.asp?q=simulated+annealing
[71] L. Ingber. Simulated Annealing: Practice Versus Theory. Mathematical and Computer Modelling, 1993,18: 29-57
[72] L. Ingber, B. Rosen. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison. Mathematical and Computer Modelling, 1992,16: 87-100
[73]汪千山,遗传算法和模拟退火算法的改进和应用:[硕士学位论文],上海;上海交通大学,2001
[74] S. Johnson, R. Aragon, A. McGeoch. Optimization by Simulated Annealing: An Experimental Ebaluation; Part II, Graph Coloring and Number Partitioning, Operations Research, 1991, 39: 378-406
[75] A. Corana, M. Marchesi. Minimizing multimodal functions of continuous variables with the“Simulated Annealing”algorithm, ACM Transactions on Mathematical Software (TOMS), 1987, 13: 262-280
[76] Glauber,R.J. Time-dependent statistics of the Ising model, Journal of Mathematical Physics, 1963, 4: 294-307
[77] D.J. Thouless, P.W. Anderson and R.G. Palmer. Solution of solvable model of a spin glass, Philosophical Magazine, 1977, 35(3): 593-601
[78] C. Peterson, J. R. Anderson. A mean field theory learning algorithm for neural networks, Complex Systems, 1987, 1: 995-1019
[79] C. Peterson, J. R. Anderson. Neural networks and NP-complete optimization problems: a performance study on the graph bisection problem,”Complex Systems, 1988, 2: 59-89
[80] C. Peterson, J. R. Anderson. Applications of mean field theory neural networks, Dept, of Theoretical Physics, Technical Report CS-1153, Univ. of Lund, August 1989. 1-27
[81] C. Peterson, E. Hartman. Explorations of the mean field theory learning algorithm, Neural Networks, August 1989,2: 475-494
[82] C. Peterson, B. Soderberg. A new method for mapping optimization problems onto neural networks, International Journal of Neural Systems, 1989, 1(1): 3-22
[83] N. Ansari, E. S. H. Hou, Y. Yu. A new method to optimize the satellite broadcasting schedules using the mean field annealing of a hopfield neural network, IEEE Transactions on Neural Network, March 1995, 6(2): 470-483
[84] G. L. Bilbro, W. E. Snyder , J. W. Gault. Mean field annealing: aformalism for constructing GNC-like algorithms, IEEE Transactions on Neural Network, 1992, 3(1): 131-138
[85] J. Cook. The mean-field theory of a Q-state neural network model, Journal of Physics A, June 21, 1989, 22(12): 2057-2058
[86] R. A. Nobakht, S. H. Ardalan, D. E. Van den Bout. Adaptive filtering of nonlinear systems with memory by quantized mean field annealing, IEEE Trans. On Signal Processing, February 1993, 41(2): 913-925
[87] D. E. Van den Bout, T. K. Miller. Graph partitioning using annealed networks, IEEE Trans. On Neural Networks, 1990, 1(2): 192-203
[88] Wang, G. and N. Ansari. Maximizing data throughput in an integrated TDMA communication system using mean field annealing, Proc. 1994 IEEE Conference on Global Telecommunications, San Francisco, CA, November 28-December 2, 1994. 329-333
[89] J. Zerubia, R. Chellappa. Mean field annealing using compound Gauss-Markov random fields for edge detection and image estimation, IEEE Trans. On Neural Networks, July 1993, 4(4): 703-709
[90] Grava, C., Buzuloiu, V., Augereau, B., etc. A multi-resolution mean mield annealing algorithm for motion estimation in medical CT image sequences, IEEE International Symposium on Signals, Circuits and Systems, 2007 (ISSCS 2007), July 2007, 1: 1-4
[91]胡卫明,徐俊华,何志均. k-着色问题及其均场退火求解算法,软件学报, 2000, 11(2):256-259
[92]刘海颖,王惠南.平均场退火算法在GPS姿态确定中的应用,中国航空学报(英文版),2004,17(3):165-169
[93]张吉林,陈明,朱能翰.均场退火神经网络算法实现多用户检测,空军雷达学院学报,2004,18(2):56-58
[94]徐宁,何松柏,虞厥邦.通道布线的神经网络优化算法,计算机辅助设计与图形学学报,2002,14(1):1-3
[95]胡卫明. BBL布局的均场退火方法,计算机辅助设计与图形学学报, 2000, 12(1):39-42
[96] Lee, N.J., Louri, A. Microcanonical mean field annealing: a new algorithm for increasing the convergence speed of mean field annealing. 1991 IEEE International Joint Conference on Neural Networks (Cat. No.91CH3065-0), 1991, 2: 941-946
[97] Cattaneo, G., Cesa-Bianchi, N. Microcanonical annealing on neural networks, Neural Networks, SUPPL, 1988, 1(1): 81
[98]徐俊杰.元启发式优化算法理论与应用研究:[博士学位论文],北京邮电大学,2007:62-84
[99]徐俊杰,忻展红.基于微正则退火的频率分配方法,北京邮电大学学报,2007,30(2): 67-70
[100] Barnard S. T. Stereo matching by hierarchical, microcanonical annealing. Proc. of the Tenth International Joint Conference on Artificial Intelligence. 1987. 832-835
[101] Bhandarkar Suchendra M., Zhang Hui. Image segmentation using evolutionary computation. IEEE Transactions on Evolutionary Computation, 1999, 3(1): 1-21
[102] Laurent Herault, Radu Horaud. Figure-ground discrimination: A combinatorial optimization approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. 15(9): 889-914
[103] Duque-Anton M, Kunz D, Ruber B. Channel assignment for cellular radio using simulated annealing. IEEE Transactions on Vehicular Technology, 1993, 42(1): 14-21
[104] Creutz M. Microcanonical Monte Carlo Simulation. Physical Review Letters, 1983, 50(19):1411-1414
[105] J. Huang, H. Liu. Stereo vision using a microcanonical mean field annealing neural network, Network: Computation in Neural Systems, Feb. 1997, 8(1): 87-104
[106] http://ai.ia.ac.cn/chinese/publication/dong/dga.htm
[107]苑希民,李鸿雁,刘树坤等.神经网络和遗传算法在水科学领域的应用,北京:中国水利水电出版社,2002
[108]王小平,曹立明.遗传算法——理论、应用与软件实现,西安:西安交通大学出版社,2002
[109] S.Ali,S.M.Sait, and M.S.T.Benton, GSA: Scheduling and Allocation Using Genetic Algorithm, Proc. EURO-DAC '94, 1994. 84-89
[110] Sekhar Darbha, Dharma P. Agrawal. A task duplication based scalable scheduling algorithm for distributed memory systems, Journal of Parallel and Distributed Computing, Oct.10, 1997, 46(1): 15-27
[111] E.S.H.Hou, N.Ansari, H.Ren. A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, February 1994, 5(2): 113-120
[112] Imtiaz Ahmad, Muhammad K. Dhodhi. Multiprocessor scheduling in a genetic paradigm, Parallel Computing, March 1996, 22(3): 395-406
[113] Yu-Kwong Kwok , Ishfaq Ahmad. Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, Nov. 25, 1997, 47(1):58-77
[114]谢季坚,刘承平.模糊数学方法及其应用(第2版),武汉:华中科技大学出版,2004
[115] Lowen R. Mathematics and fuzziness, PartⅡ, Fuzzy set and Systems, 1989, 30(1): 1-3,49-53
[116]刘普寅,吴孟达.模糊理论及其应用,长沙:国防科技大学出版社,1998
[117] OPNET Technologies. OPNET Modeler Documention, 2002
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |