基于提前预留的backfill并行调度优化模型和算法研究
|
摘要
网格计算环境为实现各种资源的共享提供了条件。提前预留是网格资源预留机制的重要组成部分。通过采用提前预留方法,可以使作业在未来某个时间段内获得协定的资源和服务质量。随着高性能计算技术的不断发展,单处理机由于受到自身计算速度的限制,已经无法满足那些对计算速度有较高要求的应用问题,对于比较复杂的大型工程计算问题和实时性上有较高要求的应用问题,必须在并行处理机上通过并行算法才能求解,所以并行调度显得越来越重要。
本文在现有支持预留的网格资源管理和调度技术的基础上,研究了并行调度过程中常用的Easy backfill算法和Conservative backfill算法,并提出新的backfill策略和backfill预留策略,建立了相应的调度优化模型一二维装箱模型。
无论是Easy backfill算法还是Conservative backfill算法,都包括backfill策略和backfill预留策略。现有的backfill策略每次只选择一个作业进行回填,没有考虑多个作业的组合,也没有考虑回填作业与当前可用资源的匹配情况。针对以上backfill策略的不足,本文中提出了新的backfill策略—JCO策略,该策略每次选择多个作业进行回填,并根据当前空闲区域的大小来选择回填作业。原有的backfill预留策略都是选择作业能够开始执行的最早时间预留资源,这样的预留策略没有考虑预留作业对空闲资源的影响,会产生很多资源碎片,导致系统的利用率很低。针对以上backfill预留策略的不足,本文提出了新的backfill预留策略—OSTP策略,该策略充分考虑了backfill预留作业对空闲资源的影响,总是选择最佳的时间点预留作业。
通过实验仿真验证了backfill策略的可行性,分析了不同预留深度对资源平均利用率、作业平均等待时间和作业平均减缓的影响,比较了各种backfill策略在不同性能参数下的差异。
Grid resource management plays an important role while enabling the sharing and coordinating of resources in Grid computing environments. Advance reservation is an important part of grid resource reservation mechanism. An advance reservation is a scheduling object which reserves a group of resources for a particular timeframe for access only by a specified entity or group of entities. With the development of high performance of computing, signal processor, due to the limit of computing speed, cannot meet the requirement of applications with higher computing speed. Nothing but parallel processors can provide service for applications such as large-scale computing projects and real-time required applications, which highlighted the importance of parallel scheduling.
Based on the existing grid resource management and scheduling technologies, I studied scheduling algorithms, Easy backfill and Conservative backfill, which are massively used in parallel scheduling.In this paper, new backfill algorithm and backfill reservation algorithm are proposed, and an optimization model, two-dimensional packing model, is raised correspondingly.
Both Easy Backfill and Conservative Backfill algorithms include backfill strategy and backfill reservation method. Existing backfill strategies only consider one job for every backfill,never considered the combination of multiple jobs, and did not consider the current available resources match with the backfill jobs.In this paper, for the inadequate of existing backfill algorithms, a newly designed backfill algorithm, JCO, is proposed. This backfill algorithm selects multiple jobs for every backfill, and selects jobs for resources based on the size of current free resource. The existing backfill reservation policy chose the earliest time to execute jobs which will fragment resources greatly and reduce system utilization rate. To change this situation, a new backfill reservation algorithm, OSTP, is proposed which take full account of backfill operation on free resources and always choose the best time to reserve resources for jobs.
Experiments proved the feasibility of backfill algorithms, and show the impacts of reservation depth on resource utilization, average waiting time and average slowdown of jobs. We can compare the difference of different backfill strategies in different performance parameters.
本文在现有支持预留的网格资源管理和调度技术的基础上,研究了并行调度过程中常用的Easy backfill算法和Conservative backfill算法,并提出新的backfill策略和backfill预留策略,建立了相应的调度优化模型一二维装箱模型。
无论是Easy backfill算法还是Conservative backfill算法,都包括backfill策略和backfill预留策略。现有的backfill策略每次只选择一个作业进行回填,没有考虑多个作业的组合,也没有考虑回填作业与当前可用资源的匹配情况。针对以上backfill策略的不足,本文中提出了新的backfill策略—JCO策略,该策略每次选择多个作业进行回填,并根据当前空闲区域的大小来选择回填作业。原有的backfill预留策略都是选择作业能够开始执行的最早时间预留资源,这样的预留策略没有考虑预留作业对空闲资源的影响,会产生很多资源碎片,导致系统的利用率很低。针对以上backfill预留策略的不足,本文提出了新的backfill预留策略—OSTP策略,该策略充分考虑了backfill预留作业对空闲资源的影响,总是选择最佳的时间点预留作业。
通过实验仿真验证了backfill策略的可行性,分析了不同预留深度对资源平均利用率、作业平均等待时间和作业平均减缓的影响,比较了各种backfill策略在不同性能参数下的差异。
Grid resource management plays an important role while enabling the sharing and coordinating of resources in Grid computing environments. Advance reservation is an important part of grid resource reservation mechanism. An advance reservation is a scheduling object which reserves a group of resources for a particular timeframe for access only by a specified entity or group of entities. With the development of high performance of computing, signal processor, due to the limit of computing speed, cannot meet the requirement of applications with higher computing speed. Nothing but parallel processors can provide service for applications such as large-scale computing projects and real-time required applications, which highlighted the importance of parallel scheduling.
Based on the existing grid resource management and scheduling technologies, I studied scheduling algorithms, Easy backfill and Conservative backfill, which are massively used in parallel scheduling.In this paper, new backfill algorithm and backfill reservation algorithm are proposed, and an optimization model, two-dimensional packing model, is raised correspondingly.
Both Easy Backfill and Conservative Backfill algorithms include backfill strategy and backfill reservation method. Existing backfill strategies only consider one job for every backfill,never considered the combination of multiple jobs, and did not consider the current available resources match with the backfill jobs.In this paper, for the inadequate of existing backfill algorithms, a newly designed backfill algorithm, JCO, is proposed. This backfill algorithm selects multiple jobs for every backfill, and selects jobs for resources based on the size of current free resource. The existing backfill reservation policy chose the earliest time to execute jobs which will fragment resources greatly and reduce system utilization rate. To change this situation, a new backfill reservation algorithm, OSTP, is proposed which take full account of backfill operation on free resources and always choose the best time to reserve resources for jobs.
Experiments proved the feasibility of backfill algorithms, and show the impacts of reservation depth on resource utilization, average waiting time and average slowdown of jobs. We can compare the difference of different backfill strategies in different performance parameters.
引文
[1]FOSTER I, KESSELMAN C, M N J. The physiology of the grid:An open grid services architecture for distributed systems integration [J]. In:Berman F, Fox G, Hey A, edsGrid computing:Making the global infrastructure a reality,2002:Chichester:Wiley):217-250.
[2]FOSTER I, KESSELMAN C S T. The anatomy of the grid:Enabling scalable virtual organizations[J]. International Journal of High-performance Computing Application,2001: 15(3):200-222.
[3]Thain D, Tannenbaum T L M. Condor and the grid.In:Berman F,Hey A,Fox G,eds. Grid computing-making the global infrastructure a reality,2003. Chichester:Wiley:p. 299-337.
[4]Foster I K C. The globus project:A status report[J]. Future Generation Computer Systems, 1999:15(5-6):607-621.
[5]http://eu_datagrid.web.cern.ch/eu_datagrid.
[6]陈国良.并行算法研究进展.(http://www.ccf.org.cn).
[7]张季平,曾国荪,吴豪.高性能网格并行计算[J].计算机工程,2004.30(001):1-3.
[8]李波.支持网格资源预留的作业调度算法研究[D].武汉：华中科技大学,2005.
[9]Castillo C,Rouskas G N,Harfoush K. On the design of online schedulingalgorithms for advance reservations and QoS in grids[J].2007:IEEE.
[10]Schwiegelshohn U, Yahyapour R. Analysis of first-come-first-serve parallel job scheduling[J]. 1998:Society for Industrial and Applied Mathematics.
[11]Lifka D. The anl/ibm sp scheduling system.In:Feitelson D QRudolph L,eds.Job scheduling strategies for parallel processing[J]. in Lecture Notes in Computer Science 949.1995: Springer.
[12]Chiang S H, Fu C. Re-evaluating reservation policies for backfill scheduling on parallel systems[J]. in In Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems.2004:Citeseer:ACTA Press.
[13]Chiang S H A, Arpaci-Dusseau, Vernon M. The impact of more accurate requested runtimes on production job scheduling performance[J].2002:Springer.
[14]Srinivasan S, et al. Selective reservation strategies for backfill job scheduling[J].2002: Springer.
[15]Jackson D, Snell Q,Clement M. Core algorithms of the Maui scheduler[J]. in Job scheduling strategies for parallel processing.2001. Lecture Notes in Computer Science 2221:Springer.
[16]Ward W, Mahood C,West J. Scheduling jobs on parallel systems using a relaxed backfill strategy[J]. in Job scheduling strategies for parallel processing,Lecture Notes in Computer Science 2537.2002:Springer.
[17]Lawson B, Smirni E. Multiple-queue backfilling scheduling with priorities and reservations for parallel systems[J].2002:Springer.
[18]Shmueli E. and D. Feitelson. Backfilling with lookahead to optimize the performance of parallel job scheduling[J].2003:Springer.
[19]Snell Q, Clement M,Jackson D. Preemption based backfill. in Job scheduling strategies for parallel processing[J].Lecture Notes in Computer Science 2537.2002:Berlin:Springer.
[20]Kettimuthu R, et al. Selective preemption strategies for parallel job scheduling[J]. International Journal of High Performance Computing and Networking,2005.3(2):122-152.
[21]Karatza H D. Performance of gang scheduling strategies in a parallel system[J]. Simulation Modelling Practice and Theory,2009.17(2):430-441.
[22]Sulistio A, Buyya R. A grid simulation infrastructure supporting advance reservation[J].2004: Citeseer.
[23]Heine F,et al. On the impact of reservations from the grid on planning-based resource management[J]. Computational Science CICCS 2005,2005:155-162.
[24]Xing J, et al. Flexible advance reservation for grid computing[J]. Grid and Cooperative Computing CGCC 2004,2004:241-248.
[25]胡春明,怀进鹏,沃天宇.一种基于松弛时间的服务网格资源能力预留机制[J].计算机研究与发展,2007.44(001)：20-28.
[26]Xiao P. Relaxed resource advance reservation policy in grid computing[J]. The Journal of China Universities of Posts and Telecommunications,2009.16(2):108-113.
[27]陈珺,李波,赵东风.支持网格资源预留的松弛时间单机在线调度算法研究[C].第六届全国信息获取与处理学术会议论文集.2008:8-9.
[28]Sulistio A.Advance reservation and revenue-based resource management for grid systems[J]. 2008.
[29]Chen Y, Lee K. A flexible service model for advance reservation[J]. Computer Networks, 2001.37(3-4):251-262.
[30]Rblitz T, Schintke F,Wendler J. Elastic Grid reservations with user-defined optimization policies[J],2004:Citeseer.
[31]张萌.一种基于网格服务质量的柔性预留机制[J].大连理工大学学报,2005.45(z):280-283.
[32]Rblitz T,Schintke F,Reinefeld A. Resource reservations with fuzzy requests[J]. Concurrency and Computation:Practice and Experience,2006.18(13):1681-1703.
[33]谢晓兰,周德俭,李春泉.SLA的制造网格模糊资源预留技术研究[J].中国机械工程,2008.19(001)：64-68.
[34]Majumdar S,Eager D L,Bunt R B. Scheduling in multiprogrammed parallel systems[J]. ACM SIGMETRICS Performance Evaluation Review,1988.16(1):104-113.
[35]Mu'alem A W, Feitelson D G. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[J]. Parallel and Distributed Systems, IEEE Transactions on,2001.12(6):529-543.
[36]李波.支持网格作业提前预留的Backfill算法性能研究[J].2005.
[37]Paull A.Linear programming:A key to optimum newsprint production[J]. Pulp and Paper Magazine of Canada,1956.57(1):85-90.
[38]Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem[J]. Operations research,1961.9(6):849-859.
[39]Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems[J]. Operations research,1977.25(1):30-44.
[40]Cung V. Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm[J]. International Transactions in Operational Research,2000.7(3):185-210.
[41]Baker B S, Coffman Jr E G, Rivest R L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing,1980.9:846.
[42]Chazelle B. The bottomn-left bin-packing heuristic:An efficient implementation[J]. IEEE Transactions on Computers,1983:697-707.
[43]Coffman Jr E G,et al. Performance bounds for level-oriented two-dimensional packing algorithms[J]. SIAM Journal on Computing,1980.9:808.
[44]Lodi A, Martello S,Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems[J]. INFORMS Journal on Computing,1999. 11(4):345-357.
[45]Lodi A, Martello S, Vigo D. Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem[J]. in Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization.1999. Kluwer Academic Publishers, Boston.
[46]Berkey J, Wang P. Two-dimensional finite bin-packing algorithms[J]. The Journal of the Operational Research Society,1987.38(5):423-429.
[47]Frenk J B G, Galambos G. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem[J]. Computing,1987.39(3):201-217.
[48]Liu D, Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles 1[J]. European Journal of Operational Research,1999.112(2):413-420.
[49]Zhang D, Kang Y, Deng A.A new heuristic recursive algorithm for the strip rectangular packing problem[J]. Computers & Operations Research,2006.33(8):2209-2217.
[50]Huang W, Chen D. An efficient heuristic algorithm for rectangle-packing problem[J]. Simulation Modelling Practice and Theory,2007.15(10):1356-1365.
[51]Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-completeness[J].1979:WH Freeman & Co. New York, NY, USA.
[52]Hochbaum D S,Shmoys D B. Using dual approximation algorithms for scheduling problems theoretical and practical results[J]. Journal of the ACM (JACM),1987.34(1):144-162.
[53]Corcoran A L, Wainwright R L. A parallel island model genetic algorithm for the multiprocessor scheduling problem[J].1994:ACM.
[54]Alvim A C F, Ribeiro C C.A hybrid improvement heuristic for the bin-packing problem and its application to the multiprocessor scheduling problem[J].
[55]Caramia M, Giordani S. Data management policies and scheduling in grid computing[J]. 2006:World Scientific and Engineering Academy and Society (WSEAS).
[56]Boyar J, Favrholdt L. Scheduling jobs on grid processors[J]. Algorithm Theory "CSWAT 2006, 2006:17-28.
[57]Sun K, Li H. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines[J]. International Journal of Production Economics, 2010.124(1):151-158.
[58]Beitollahi H, Deconinck G. Fault-tolerant partitioning scheduling algorithms in real-time multiprocessor systems[J]. Katholieke Universiteit Leuven, Electrical Engineering, Kasteelpark Arenberg 10, Leuven, Belgium,2006.
[59]Xian C, Lu Y H, Li Z.Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time[J].2007:ACM.
[60]Yu G, Zhang G. Scheduling with a minimum number of machines [J]. Operations Research Letters,2009.37(2):97-101.
[61]Coffman Jr E,Garey M,Johnson D. An application of bin-packing to multiprocessor scheduling[J].SIAM Journal on Computing,1978.7:1.
[62]Woodside C M, Monforton G G. Fast allocation of processes in distributed and parallel systems[J]. Parallel and Distributed Systems, IEEE Transactions on,1993.4(2):164-174.
[63]Chao S,Chinneck J M, Goubran R A. Assigning service requests in voice-over-internet gateway multiprocessors [J]. Computers & Operations Research,2004.31(14):2419-2437.
[64]Liu C, Baskiyar S. Scheduling mixed tasks with deadlines in grids using bin packing[J].2008: IEEE.
[65]王二飞.计算网格中截止时间约束的提前预留作业调度算法研究[D].昆明：云南大学,2010.
[66]李波,赵东风.支持资源预留的网格计算仿真平台[J].系统仿真学报,2006.18(z2):373-376.
[67]Kreutzer W, Hopkins J, Van Mierlo M. SimJAVA-a framework for modeling queueing networks in Java. in In Proceedings of the 1997 Winter Simulation Conference[J].1997: IEEE Computer Society.
[2]FOSTER I, KESSELMAN C S T. The anatomy of the grid:Enabling scalable virtual organizations[J]. International Journal of High-performance Computing Application,2001: 15(3):200-222.
[3]Thain D, Tannenbaum T L M. Condor and the grid.In:Berman F,Hey A,Fox G,eds. Grid computing-making the global infrastructure a reality,2003. Chichester:Wiley:p. 299-337.
[4]Foster I K C. The globus project:A status report[J]. Future Generation Computer Systems, 1999:15(5-6):607-621.
[5]http://eu_datagrid.web.cern.ch/eu_datagrid.
[6]陈国良.并行算法研究进展.(http://www.ccf.org.cn).
[7]张季平,曾国荪,吴豪.高性能网格并行计算[J].计算机工程,2004.30(001):1-3.
[8]李波.支持网格资源预留的作业调度算法研究[D].武汉：华中科技大学,2005.
[9]Castillo C,Rouskas G N,Harfoush K. On the design of online schedulingalgorithms for advance reservations and QoS in grids[J].2007:IEEE.
[10]Schwiegelshohn U, Yahyapour R. Analysis of first-come-first-serve parallel job scheduling[J]. 1998:Society for Industrial and Applied Mathematics.
[11]Lifka D. The anl/ibm sp scheduling system.In:Feitelson D QRudolph L,eds.Job scheduling strategies for parallel processing[J]. in Lecture Notes in Computer Science 949.1995: Springer.
[12]Chiang S H, Fu C. Re-evaluating reservation policies for backfill scheduling on parallel systems[J]. in In Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems.2004:Citeseer:ACTA Press.
[13]Chiang S H A, Arpaci-Dusseau, Vernon M. The impact of more accurate requested runtimes on production job scheduling performance[J].2002:Springer.
[14]Srinivasan S, et al. Selective reservation strategies for backfill job scheduling[J].2002: Springer.
[15]Jackson D, Snell Q,Clement M. Core algorithms of the Maui scheduler[J]. in Job scheduling strategies for parallel processing.2001. Lecture Notes in Computer Science 2221:Springer.
[16]Ward W, Mahood C,West J. Scheduling jobs on parallel systems using a relaxed backfill strategy[J]. in Job scheduling strategies for parallel processing,Lecture Notes in Computer Science 2537.2002:Springer.
[17]Lawson B, Smirni E. Multiple-queue backfilling scheduling with priorities and reservations for parallel systems[J].2002:Springer.
[18]Shmueli E. and D. Feitelson. Backfilling with lookahead to optimize the performance of parallel job scheduling[J].2003:Springer.
[19]Snell Q, Clement M,Jackson D. Preemption based backfill. in Job scheduling strategies for parallel processing[J].Lecture Notes in Computer Science 2537.2002:Berlin:Springer.
[20]Kettimuthu R, et al. Selective preemption strategies for parallel job scheduling[J]. International Journal of High Performance Computing and Networking,2005.3(2):122-152.
[21]Karatza H D. Performance of gang scheduling strategies in a parallel system[J]. Simulation Modelling Practice and Theory,2009.17(2):430-441.
[22]Sulistio A, Buyya R. A grid simulation infrastructure supporting advance reservation[J].2004: Citeseer.
[23]Heine F,et al. On the impact of reservations from the grid on planning-based resource management[J]. Computational Science CICCS 2005,2005:155-162.
[24]Xing J, et al. Flexible advance reservation for grid computing[J]. Grid and Cooperative Computing CGCC 2004,2004:241-248.
[25]胡春明,怀进鹏,沃天宇.一种基于松弛时间的服务网格资源能力预留机制[J].计算机研究与发展,2007.44(001)：20-28.
[26]Xiao P. Relaxed resource advance reservation policy in grid computing[J]. The Journal of China Universities of Posts and Telecommunications,2009.16(2):108-113.
[27]陈珺,李波,赵东风.支持网格资源预留的松弛时间单机在线调度算法研究[C].第六届全国信息获取与处理学术会议论文集.2008:8-9.
[28]Sulistio A.Advance reservation and revenue-based resource management for grid systems[J]. 2008.
[29]Chen Y, Lee K. A flexible service model for advance reservation[J]. Computer Networks, 2001.37(3-4):251-262.
[30]Rblitz T, Schintke F,Wendler J. Elastic Grid reservations with user-defined optimization policies[J],2004:Citeseer.
[31]张萌.一种基于网格服务质量的柔性预留机制[J].大连理工大学学报,2005.45(z):280-283.
[32]Rblitz T,Schintke F,Reinefeld A. Resource reservations with fuzzy requests[J]. Concurrency and Computation:Practice and Experience,2006.18(13):1681-1703.
[33]谢晓兰,周德俭,李春泉.SLA的制造网格模糊资源预留技术研究[J].中国机械工程,2008.19(001)：64-68.
[34]Majumdar S,Eager D L,Bunt R B. Scheduling in multiprogrammed parallel systems[J]. ACM SIGMETRICS Performance Evaluation Review,1988.16(1):104-113.
[35]Mu'alem A W, Feitelson D G. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[J]. Parallel and Distributed Systems, IEEE Transactions on,2001.12(6):529-543.
[36]李波.支持网格作业提前预留的Backfill算法性能研究[J].2005.
[37]Paull A.Linear programming:A key to optimum newsprint production[J]. Pulp and Paper Magazine of Canada,1956.57(1):85-90.
[38]Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem[J]. Operations research,1961.9(6):849-859.
[39]Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems[J]. Operations research,1977.25(1):30-44.
[40]Cung V. Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm[J]. International Transactions in Operational Research,2000.7(3):185-210.
[41]Baker B S, Coffman Jr E G, Rivest R L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing,1980.9:846.
[42]Chazelle B. The bottomn-left bin-packing heuristic:An efficient implementation[J]. IEEE Transactions on Computers,1983:697-707.
[43]Coffman Jr E G,et al. Performance bounds for level-oriented two-dimensional packing algorithms[J]. SIAM Journal on Computing,1980.9:808.
[44]Lodi A, Martello S,Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems[J]. INFORMS Journal on Computing,1999. 11(4):345-357.
[45]Lodi A, Martello S, Vigo D. Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem[J]. in Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization.1999. Kluwer Academic Publishers, Boston.
[46]Berkey J, Wang P. Two-dimensional finite bin-packing algorithms[J]. The Journal of the Operational Research Society,1987.38(5):423-429.
[47]Frenk J B G, Galambos G. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem[J]. Computing,1987.39(3):201-217.
[48]Liu D, Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles 1[J]. European Journal of Operational Research,1999.112(2):413-420.
[49]Zhang D, Kang Y, Deng A.A new heuristic recursive algorithm for the strip rectangular packing problem[J]. Computers & Operations Research,2006.33(8):2209-2217.
[50]Huang W, Chen D. An efficient heuristic algorithm for rectangle-packing problem[J]. Simulation Modelling Practice and Theory,2007.15(10):1356-1365.
[51]Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-completeness[J].1979:WH Freeman & Co. New York, NY, USA.
[52]Hochbaum D S,Shmoys D B. Using dual approximation algorithms for scheduling problems theoretical and practical results[J]. Journal of the ACM (JACM),1987.34(1):144-162.
[53]Corcoran A L, Wainwright R L. A parallel island model genetic algorithm for the multiprocessor scheduling problem[J].1994:ACM.
[54]Alvim A C F, Ribeiro C C.A hybrid improvement heuristic for the bin-packing problem and its application to the multiprocessor scheduling problem[J].
[55]Caramia M, Giordani S. Data management policies and scheduling in grid computing[J]. 2006:World Scientific and Engineering Academy and Society (WSEAS).
[56]Boyar J, Favrholdt L. Scheduling jobs on grid processors[J]. Algorithm Theory "CSWAT 2006, 2006:17-28.
[57]Sun K, Li H. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines[J]. International Journal of Production Economics, 2010.124(1):151-158.
[58]Beitollahi H, Deconinck G. Fault-tolerant partitioning scheduling algorithms in real-time multiprocessor systems[J]. Katholieke Universiteit Leuven, Electrical Engineering, Kasteelpark Arenberg 10, Leuven, Belgium,2006.
[59]Xian C, Lu Y H, Li Z.Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time[J].2007:ACM.
[60]Yu G, Zhang G. Scheduling with a minimum number of machines [J]. Operations Research Letters,2009.37(2):97-101.
[61]Coffman Jr E,Garey M,Johnson D. An application of bin-packing to multiprocessor scheduling[J].SIAM Journal on Computing,1978.7:1.
[62]Woodside C M, Monforton G G. Fast allocation of processes in distributed and parallel systems[J]. Parallel and Distributed Systems, IEEE Transactions on,1993.4(2):164-174.
[63]Chao S,Chinneck J M, Goubran R A. Assigning service requests in voice-over-internet gateway multiprocessors [J]. Computers & Operations Research,2004.31(14):2419-2437.
[64]Liu C, Baskiyar S. Scheduling mixed tasks with deadlines in grids using bin packing[J].2008: IEEE.
[65]王二飞.计算网格中截止时间约束的提前预留作业调度算法研究[D].昆明：云南大学,2010.
[66]李波,赵东风.支持资源预留的网格计算仿真平台[J].系统仿真学报,2006.18(z2):373-376.
[67]Kreutzer W, Hopkins J, Van Mierlo M. SimJAVA-a framework for modeling queueing networks in Java. in In Proceedings of the 1997 Winter Simulation Conference[J].1997: IEEE Computer Society.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |