下载文档原格式
蒙特卡洛算法组员李小兵周立冯俊李继华艾海提李日浩算法简介蒙特·卡洛方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。
是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。
蒙特·卡洛方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。
与它对应的是确定性算法。
蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。
背景知识1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。
它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算列?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。
在这里我们要假定豆子都在一个平面上，相互之间没有重叠。
蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。
生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。
算法描述以概率和统计理论方法为基础的一种计算方法。
将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。
比如，给定x=a，和x=b，你要求某一曲线f和这两竖线，及x轴围成的面积，你可以起定y轴一横线 y=c 其中c>=f(x)max，很简单的，你可以求出 y=c,x=a,x=b,及 x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：doteUpCount,nodeDownCount,然后所要求的面积可以近似为doteDownCounts所占比例*矩形面积。
多级调度算法什么是多级调度算法？多级调度算法（Multi-Level Feedback Queue，MLFQ）是一种操作系统中的进程调度算法。
它将进程队列分成多个级别，每个级别都有不同的时间片大小和优先级。
当一个进程被加入队列时，它被放置在最高优先级的队列中，如果它在该队列中运行了一段时间后仍未完成，则被降低到较低优先级的队列中继续运行。
这样可以使长时间运行的进程获得更多的CPU时间，并且能够保证短时间运行的进程能够快速响应用户请求。
多级调度算法的特点1. 多个队列：多级调度算法将进程队列分成多个级别，每个级别都有不同的时间片大小和优先级。
2. 时间片轮转：每个队列使用时间片轮转方式进行调度。
3. 优先级：每个队列都有自己的优先级，高优先级的队列会被更频繁地执行。
4. 抢占式：如果一个高优先级进程加入了队列，则当前正在执行的低优先级进程会被抢占。
5. 动态变化：根据当前系统负载情况动态改变各个队列之间切换所需的时间片大小。
多级调度算法的实现步骤1. 初始化队列：将所有进程按照优先级放入不同的队列中，每个队列都有自己的时间片大小。
2. 运行进程：从最高优先级队列开始运行进程，如果该进程在时间片内完成，则被移出队列，否则被降低到较低优先级的队列中继续运行。
3. 抢占式调度：如果一个高优先级进程加入了队列，则当前正在执行的低优先级进程会被抢占。
4. 动态变化：根据当前系统负载情况动态改变各个队列之间切换所需的时间片大小。
5. 结束进程：当一个进程完成或被杀死时，从相应的队列中移出该进程。
多级调度算法存在的问题1. 饥饿问题：如果系统中有大量长时间运行的高优先级进程，则低优先级进程可能会一直等待，导致饥饿问题。
2. 时间片大小选择问题：选择合适的时间片大小非常重要，如果时间片过小，则会导致频繁切换而浪费CPU资源；如果时间片过大，则会导致响应速度变慢。
3. 进程数目过多：当系统中存在大量进程时，多级调度算法的效率会降低。
处理机调度算法的模拟在计算机操作系统中，处理机调度算法决定了在多个进程或任务同时存在的情况下，哪个任务将获得处理机的使用权，以及在多个任务之间如何切换。
处理机调度算法可以按照多个指标进行优化，例如响应时间、吞吐量、周转时间和等待时间等。
以下是几种常见的处理机调度算法：1.先来先服务（FCFS）：先来先服务是最简单的调度算法之一，它按照任务到达的先后顺序分配处理机资源。
这种算法的优点是简单易实现，但是当存在长作业（任务）时，会导致其他短作业的等待时间过长。
2.短作业优先（SJF）：短作业优先调度算法根据任务的估计执行时间来进行调度，优先执行估计执行时间短的任务。
这种算法可以减少任务的等待时间，但对于长作业来说，可能会导致饥饿现象。
3.优先级调度：优先级调度算法根据任务的优先级进行调度，优先级高的任务先获得处理机的使用权。
这种算法可以根据不同任务的紧急性和重要性来确保任务得到适当的优先级处理。
但是，如果优先级设置不合理，可能会导致一些任务永远得不到执行。
4.时间片轮转调度：时间片轮转调度算法是一种公平的调度算法，它将处理机的使用权按照时间片划分给不同的任务，每个任务只能执行一个时间片的任务。
如果任务在时间片结束之前没有完成，它将被放回到任务队列的末尾继续等待。
这种算法可以确保每个任务都有机会获得处理机的使用权，但是可能会存在上下文切换的开销。
以上只是几种常见的处理机调度算法，实际上还有许多其他算法以及它们的变体，例如最短剩余时间优先（SRTF）、多级反馈队列调度（MFQ）等。
每种调度算法都有不同的优缺点，选择适合的调度算法取决于系统的需求和资源限制。
为了模拟处理机调度算法，可以使用计算机模拟软件或编写自己的模拟程序。
模拟程序可以模拟任务的到达和执行过程，按照指定的调度算法进行任务的分配和切换，并统计不同指标（如响应时间、吞吐量等）来评估算法的性能。
在模拟处理机调度算法时，需要考虑以下几个方面：1.任务的到达过程：任务可以按照随机分布的方式到达，模拟任务的到达时间和资源需求。
处理机调度的常用算法包括以下几种：
1. 先来先服务调度算法（FCFS，First Come First Service）：这是一种最简单的调度算法，按先后顺序进行调度。
既可用于作业调度，也可用于进程调度。
2. 短作业优先调度算法（SJF/SPF，Shortest Job First）：该算法根据作业长短进行调度，有利于短作业（进程）的完成。
3. 高响应比优先调度算法（HRRN，Highest Response Raito Next）：该算法综合考虑了作业长短和等待时间，能够适用于短作业较多的批处理系统中，但长作业的运行可能得不到保证。
4. 基于时间片的轮转调度算法（RR，Round Robin）：该算法将系统中所有的就绪进程按照FCFS原则，排成一个队列。
每次调度时将CPU 分派给队首进程，让其执行一个时间片。
时间片的长度从几个ms到几百ms。
在一个时间片结束时，发生时钟中断。
调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。
进程阻塞情况发生时，未用完时间片也要出让CPU。
这些算法各有优缺点，需要根据实际应用场景选择合适的算法。
多级调度算法简介多级调度算法是操作系统中的一种调度算法，用于管理和分配系统中的各个任务和进程资源。
它根据任务的优先级不同，将系统中的任务划分为多个不同的队列，并分配不同的调度策略给每个队列。
多级调度算法可以更加有效地利用系统资源，提高系统的性能和响应速度。
基本原则多级调度算法通常包含以下的基本原则：1.任务分类：将系统中的任务按照不同的优先级划分为多个队列，通常包括高优先级队列、中优先级队列和低优先级队列等。
2.调度策略：为每个队列分配不同的调度策略，以满足不同优先级任务的特点和需求。
常见的调度策略包括先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（RR）等。
3.优先级继承：当一个任务需要等待一个优先级较低的任务执行完成时，可以将其临时提升到较高的优先级队列中执行，以避免优先级反转（PriorityInversion）问题。
4.任务迁移：根据系统中任务的负载情况，可以将任务从一个队列迁移到另一个队列，以实现负载均衡和资源利用的最大化。
常见的多级调度算法先来先服务（FCFS）先来先服务是一种最简单的调度策略，按照任务到达的顺序进行处理。
当一个任务到达系统时，被放入对应优先级队列的末尾。
如果当前正在执行任务，则新到达的任务必须等待前面的任务执行完毕后才能执行。
优点：实现简单，公平性好。
缺点：对长作业不利，容易产生饥饿现象。
最短作业优先（SJF）最短作业优先是根据任务的执行时间进行调度的策略。
具有最短执行时间的任务将被先执行，以减少平均等待时间。
优点：平均等待时间最短。
缺点：无法预测任务执行时间，不利于实时任务。
时间片轮转（RR）时间片轮转是一种基于时间片的调度策略。
每个任务分配一个固定长度的时间片，当时间片用完后，任务被暂停，放回队列尾部，并执行下一个任务。
通过轮转的方式，实现公平地分配每个任务的CPU时间。
优点：响应时间快，公平性好。
缺点：时间片长度的选择会影响系统的性能。
多级反馈队列（MLFQ）多级反馈队列是一种综合性的多级调度算法。
算法之多机调度问题用贪心法解决多机调度问题(1)问题的描述设有n个独立的作业｛1,乙…,n｝,由m台相同的机器｛Ml, M乙…,Mm｝进行加工处理，作业i所需的处理时间为ti (l<i<n),每个作业均可在任何一台机器上加工处理，但不可间断、拆分。
多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
(2)算法设计思想解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。
(3)数据及解题过程设7个独立作业｛匕2, 3, 4, 5, 6, 7｝由3台机器｛M2, M2, M3｝加工处理,各作业所需的处理时间分别为｛2, 14, 4,16, 6, 5, 3｝。
贪心法产生的作业调度如下：(4)程序使用C++运行测试(5)代码如下：#include <iostream>#inelude vconio.h>using namespace std;〃冒泡法对作业时间t降序排列，作业编号P的顺序也随t的顺序改变而改变，这点很重要！void Dsc_Order_By_t(int t[],int p[],int n) 〃注意：数组元素下标从1 开始｛〃你的代码int i,j;for (i=l;i<=n;i++)for (j=l;j<=n-i;j++){{int b=t[j+l];t[j+i]=tU];tU)=b；int g=p[j+l]; P D+I]=P U]; P U]=S; }}}for (i=l;i<=n;i++){cout«t[i]«,,\t n;}cout«e ndl;for (i=l;i<=n;i++)cout«e ndl;}void Processing(int p[],int t[],int n’int s[],int d[],int m){ 〃你的代码，根据书中伪代码编写，P154,算法7.9〃其中s[i]={p[i]}ffl位集合表示，代码^:s[i]|=(l«(p[i]-l))〃s[j]=s[j]+{p[i]}实际代码是：s[j]|=(l«(p[i]-l))^懂问我，把它搞清楚！int i; intj; for(i=l;i<=m;i++){s[i]|=(l«(p[i]-D);d[i]=t[i];}for(i=m+l;i<=n;i++){for(int k=l;k<m;k++){int o=d[k];if (o>d[k+l])o=d[k+l];j=k+l;}}sU]|=(l«(p[i]-D)；d[j]二d[j]+t[i];}}void Output(int *p,int n,int *sjnt *d,int m) 〃阅读并理解这个函数{int max=0,k=l;cout«endl«"作业在各台机器上的安排如下："«endl;for(int i=l;i<=m;i++){cout«K机器,,«i«n：for(intj=l;j<=n;j++) if((s[i]»(p[j]-l))&l) cout«*作业*«p0]«" ”; 〃理解位值运算！cout«"总耗时：”《d[i]vvendl;if(max<d[i]) {max=d[i]; k=i;}coutvv“\n“vvnvv”个作业在” vvmvv”台机器上执行完毕最少需要时间H«d[k]«endl;}int main()intp[]={0,l, 2,3, 4,5,6,7}, 〃作业编号，p[0]不用t[]={0,2,14,4,16,6,5,3}, 〃对应作业时间，t[0]不用s[]={0,0,0,0}, 〃机器处理的作业集合，女口：s⑴存放机器处理过的作业号，s[0]不用d[]二{0,000}; 〃机器处理作业的总时间，女口：d[2]存放机器处理过的作业的总时间，d[0]不用int n=sizeof(p)/sizeof(int)-l,m=sizeof(s)/sizeof(int)-l; //n-作业总数，m••机器台数Dsc_Order_By_t(t,p,n); 〃对作业根据运行时间t进行降序排列Processing(p,t,n,s,d,m); 〃用最长运行时间优先算法处理作业Output(p,n,s,d,m); 〃输出结果_getch();return 0;}运行结果图:。
多机调度问题一、 问题描述设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。
作业i所需的处理时间为t i。
现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理，任何作业不能拆分成更小的子作业。
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
二、 问题分析这是一个NP完全问题，到目前为止还没有有效的解法。
本报告根据教材指导及实践经验，采用贪心算法进行分析求解，并进行简单评估。
使用贪心算法，能避免许多复杂的子问题分析，便于直观地剖析主要问题。
在选择贪心算法的基础上，进一步地，我们采用最长处理时间作业优先的贪心选择策略，以求设计出解多机调度问题的较好的近似算法。
预期效果：根据最长处理时间作业优先的原则，理应能够得出直观下比较高效的输出结果。
三、算法设计与分析1．算法输入和输出输入：作业数n，机器数m，作业i对应的处理时间t i（t i在测试时用一个一维数组time表示）输出：总耗费时间2．算法说明最长处理时间作业优先的贪心算法，顾名思义，就是将目前还未被处理的且需要处理时间最长的作业，分配给最先空闲的机器，直到分配完所有的作业为止。
3．算法描述（1）（处理1）：当n≤m时，只要将机器i的[0,t i]时间区间分配给作业i即可。
（2）（处理2）：当n＞m时：i.先将耗时最长的m个作业依次分配给m个机器ii.沿着时间轴，寻找最先得到空闲的机器。
将还未被处理且需要处理时间最长的那个作业分配给此机器iii.重复上一步直到所有作业都被处理完毕4．算法分析当n≤m时，算法需要O(1)时间。
当n＞m时，算法需要O(nlogn)时间。
四、算法流程图输入是否n≤m处理1 处理2输出图4-1 多机调度算法流程图五、测试数据及其结果分析1．测试数据当输入n=7, m=3, time={2,14,4,16,6,5,3}时（教材示例），经历处理2，输出结果为17 当输入n=7, m=3, time={4,5,13,9,4,11,2}时，经历处理2，输出结果为20当输入n=18, m=3, time={1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}时，经历处理2，输出结果为33当输入n=3, m=3, time={2,3,5}时，经历处理1，输出结果为52．结果分析观察可知，贪心算法解此问题，比直观感受要更高效。
云计算中的多任务调度算法研究与优化随着云计算的迅速发展，越来越多的人开始认识到多任务调度算法对于云计算平台的重要性。
多任务调度算法是云计算系统中的关键技术之一，它能够在满足各种约束条件的情况下，有效地将多个任务分配给云计算资源，提高资源利用率和运行效率。
本文将对云计算中的多任务调度算法进行研究与优化。
首先，我们来介绍云计算中的多任务调度算法。
多任务调度算法是指将不同的任务分配给云计算平台上的多个资源节点，以实现任务的高效执行。
常见的多任务调度算法包括作业优先级调度算法、最短作业优先调度算法、时间片轮转调度算法等。
这些算法通过考虑任务的优先级、执行时间和资源需求等因素，确定任务的执行顺序和分配方式，以提高系统的效率和性能。
然而，传统的多任务调度算法在应对复杂的云计算环境时存在一些不足之处。
首先，资源利用率不高。
传统算法往往只考虑任务的执行时间和优先级等因素，而忽视了资源的动态变化。
云计算平台中的资源分配是动态的，随着时间的推移和任务的变化，资源的利用率往往不高。
其次，执行时间长的作业可能会影响整个系统的运行效率。
如果没有合理地分配资源，执行时间长的作业可能会阻塞其他任务的执行，导致整个系统的运行效率下降。
为了解决这些问题，研究人员提出了一些优化的多任务调度算法。
这些算法使用了更加复杂的调度策略，考虑了更多的因素，以提高系统的性能和效率。
例如，最佳适应算法可以根据任务的资源需求和执行时间，动态地分配资源，以最大化系统的利用率。
进化算法通过模拟生物进化过程，自适应地调整任务的执行顺序和分配方式，优化整个系统的性能。
此外，还有一些基于机器学习和人工智能的算法，可以根据历史数据和预测模型，预测任务的资源需求和执行时间，从而实现更加精确的任务调度。
除了算法本身的优化，还可以通过优化云计算平台的资源管理策略，来提高多任务调度算法的效果。
例如，可以使用虚拟机迁移技术，将正在执行的任务迁移到其他资源节点，以实现负载均衡和优化资源利用率。
蒙特卡洛方法在中子输运中的应用《中子输运理论与数值方法》课程作业——蒙特卡洛方法目录1.前言 (4)2. 蒙特卡洛方法概述 (4)2.1 蒙特卡洛方法的基本思想 (5)2.2 蒙特卡洛方法的收敛性、误差 (5)2.2.1 蒙特卡洛方法的收敛性 (5)2.2.2 蒙特卡洛方法的误差 (6)2.3 蒙特卡洛方法的特点 (7)2.4 蒙特卡洛方法的主要应用范围 (8)3. 随机数 (9)3.1 线性乘同余方法 (10)3.2 伪随机数序列的均匀性和独立性 (10)3.2.1 伪随机数的均匀性 (10)3.2.2 伪随机数的独立性 (11)4. 蒙特卡洛方法在粒子输运上的应用 (11)4.1 屏蔽问题模型 (11)4.2 直接模拟方法 (12)4.2.1 状态参数与状态序列 (12)4.2.2 模拟运动过程 (13)4.2.3 记录结果 (16)4.3 蒙特卡洛方法的效率 (17)5. 蒙特卡洛方法应用程序—MCNP (18)5.1 MCNP简述 (18)5.2 MCNP误差的估计 (19)5.3 MCNP效率因素 (20)6. 结论 (20)参考文献 (21)1.前言半个多世纪以来，由于科学技术的发展和电子计算机的发明，蒙特卡洛(Monte Carlo)方法作为一种独立的方法被提出来，并首先在核武器的试验与研制中得到了应用。
蒙特卡洛方法是一种计算方法，但与一般数值计算方法有很大区别。
它是以概率统计理论为基础的一种方法。
由于蒙特卡洛方法能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题，因而该方法的应用领域日趋广泛。
蒙特卡洛模拟计算是解决中子在介质中输运较为成熟、有效的方法，对于原子能、辐射防护、剂量学和辐射生物物理学等研究领域实际问题的计算，都可以利用蒙特卡洛方法予以实现。
粒子输运过程可以用玻耳兹曼方程加以描述，然而，以此基础上发展起来的近似数值方法如扩散近似法、离散坐标方法在处理截面与能量相关以及散射各向异性介质、复杂几何条件问题时碰到了较大困难。
同类机环境下不同尺寸工件的分批调度问题李小林;杜冰;许瑞;陈华平【摘要】为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。
由于该问题是NP难解的,给出了一个下界以衡量近似算法的性能,并证明了该下界的有效性。
提出了批的隐性加工时间的概念,并以此为基础给出了一种新的局部优化算法,对最大最小蚁群算法进行了改进。
使用启发式算法最终对同类机环境下分批调度问题进行求解。
通过仿真实验将该蚁群算法与遗传算法、微粒群优化算法及BFLPT等进行比较和性能分析。
%To improve the production efficiency by using batch processor effectively,a batch scheduling problem with non-identical job size on uniform parallel machines was proposed and solved.This problem was proved to be NP-hard,thus a lower bound was presented to evaluate the performance of approximation algorithms,and the validity of this lower bound was proved.On the basis of recessive processing time concept,a new local optimization algorithm was proposed to improve the max-min ant algorithm.A heuristic algorithm named Longest Processing Time for Uniform Machines（LPTUM） was used to solve the problem.Through simulation experiment,the proposed algorithm was compared to genetic algorithm,particle swam optimization and BFLPT,as well as the performance was analyzed.【期刊名称】《计算机集成制造系统》【年(卷),期】2012(018)001【总页数】9页(P102-110)【关键词】同类机;批调度;蚁群优化算法;组合优化;启发式算法【作者】李小林;杜冰;许瑞;陈华平【作者单位】中国科学技术大学管理学院,安徽合肥230026;中国科学技术大学管理学院,安徽合肥230026;中国科学技术大学管理学院,安徽合肥230026;中国科学技术大学管理学院,安徽合肥230026【正文语种】中文【中图分类】TP3010 引言批调度问题是将一组工件使用批处理机分批进行加工的问题，是现实生活中典型的组合优化问题，在社会生产的许多领域有广泛的应用，如金属加工业中的热处理操作、集成电路板生产时进行的环境应力筛选（environmental stress－screening）等。
1997年7月 烟台大学学报(自然科学与工程版) July1997第10卷第3期 Journal of Yantai U niversity(N atural Science and Eng ineering) Vol.10No.3多处理机调度问题的一种近似算法程建纲(烟台大学数学与信息科学系,烟台264005) 秦成林(上海大学数学系,上海201800)摘要 对多处理机调度问题P C max,给出一种近似算法.大量实例的计算结果表明,本文的算法是非常有效的.关键词 组合优化 排序 近似算法 随机算法中图分类号 O224多处理机调度问题P C max考虑有n个独立的工件和m台相同的机器,每一工件在并且仅在一台机器上加工一次,同时在加工时不允许中断加工的情形,所讨论的问题为:确定工件在各机器上的分配方案,使得从第一个被加工工件开始加工时刻起到全部工件加工完毕时刻止的时间跨度取极小.由于它在许多领域中都有广泛的应用,同时又是一个NP-C 问题,故其近似算法的研究受到广泛重视[1,2].本文对此问题通过随机迭代来给出一种近似算法,并通过大量的计算实例来表明对通常的P C max问题,本文的算法能够获得精度很高的近似解,而且在许多情况下也能获得问题的精确解.下面首先给出本文中对此问题的数学描述形式.设m,n是正整数,R n+表示分量全为正数的n维向量的全体,同时为了方便起见,在本文中,对任意的向量,其分量始终用括号的形式表示,例如对l R n+,其相应的n个分量为l(1),l(2),!,l(n),另外对j所满足的条件组 ,以∀{l(j)|条件组 }表示对所有j满足条件组 的分量l(j)做累加,以M表示由{1,2,!,n}到{1,2,!,m}的映象全体所构成的空间,此时l R n+表示n个工件的工件组,其中第j个工件的加工时间为l(j),q M表示对工组的一个分配方案,它将第j个工件分配给第q(j)号机器,进而P C max问题为:对给定的l R n+,极小化问题min max1#i#m∀{l(j)|q(j)=i} s.t q M(P)为了便于描述本文对此问题的算法,再引进以下一些记号,以R m表示通常的m维空间, [0,h]n表示R n中所有分量都不超过h的n维非负向量的全体,以S n表示{1,2,!,n}上的全体置换所构成的n次对称群,对l R n+, S n,l 表示向量(l( (1)),l( (2)),!, l( (n))),映象A:R n+∃M%R n+的定义为A(l,q)的第n个分量A(l,q)(j)=∀{l(k)|q(k)=q(j),k&j},映象D:R n+%S n的定义为:对y R n+,D(y)由以下两条件唯一确定:(1)y (D(y )(1))&y (D (y )(2))&!&y (D (y )(n ));(2)若j <k,y (j )=y (k ),则[D(y )]-1(j )<[D (y )]-1(k ),即向量yD(y )是y 经非增序重排后所得到的新向量,映象B :R n +%M 的定义为:对lR n +,B (l)通过如下的方式对j 从1到n 依次给出:B (l)(j )=min {k |b(k ,j )=min 1#i #m b(i,j )},其中b(i,j )=∀{l(j ∋)|B (l)(j ∋)=i,j ∋<j },即B(l)是按l 的分量顺序,用首先完工准则所得到的分配方案.在以上记号下,本文对问题(P)的算法为:算法P:取正整数T 为算法中止的迭代次数,正数 h 为给定的步长,以q * M 存放到当前为止的最好解,f *存放其相应的目标值,即f *=max 1#i #m ∀{l (j )|q *(j )=i},qM 存放当前解,另外t 为当前的迭代次数,变量f ,g,h R ,!, S n ,z R n .Step0:(初始化)任选一个q M 做为问题的初始解,初始化t =0;h =0;q *=q ;f *=max 1#i #m ∀{l (j )|q *(j )=i};f =∀m i=1[∀{l(j )|q (j )=i}]2.Step1:(构造新解)置g =f .当h >0时,以均匀分布的方式在[0,h ]n 中随机选取向量z ,当h =0时,取z 为零向量.以均匀分布的方式在S n 中随机选取 ,置!=D(A (l ,q ) -1+z -1),q =B(l !)!-1,f =∀m i=1[∀{l(j )|q (j )=i}]2.Step2:(改变h)如果f =g ,则置h =h + h,否则置h =0.Step3:(比较f *)如果max 1#i #m∀{l(j )|q (j )=i}<f *,则置f *=m ax 1#i #m ∀{l(j )|q (j )=i},q *=qStep4:(流程控制)如果t <T ,则置t =t +1,转Step1,否则输出q *及f*做为问题(P )的近似解及相应的目标值.注1:!=D (A (l ,q ) -1+z -1)可通过如下的过程给出,取变量y R n ,x R m .(0)初始化j =n ,x (i)=0,i =1,2,!,m ;(1)置x (q (j ))=x (q (j ))+l (j ),y (j )=x (q (j ))+z (j );(2)如果j =1,则取!=D (y ),否则置j =j -1,转(1).注2:q =B (l !)!-1及f =∀mi=1[∀{l(j )|q (j )=i }]2可通过如下过程给出:取变量x R m .(0)初始化j =1,x (i)=0,i =1,2,!,m ;(1)置q (!(j ))=min {k |x (k )=min 1#i #m x (i)};(2)置x (q (!(j )))=x (q (!(j )))+l(!(j ));(3)如果j =n ,则转(4),否则置j =j +1,转(1);(4)置f =∀m i=1[x (i )]2,结束过程.注3:算法在实现时,随机量 和z 的选取可通过伪随机近似的产生,例如伪随机数用乘同余法∀(k )(23∃∀(k -1)(mod (108+1)),给出,当取∀(0)=∀0=47594118时,它具有比较好的性质[3].在算法P 开始时,初始化∀(0)=∀0,然后每次在S n 中随机选取 都用如下的方式进行.13)166)烟台大学学报(自然科学与工程版) 第10卷(2)置∀(0)=∀(n ).当h >0时,每次在[0,h]n 中随机选取z 都用如下的方式进行(1)取z (k )=h ∃∀(j )/(108+1),k =1,2,!,n;(2)置∀(0)=∀(n ).由以上的注可知当用注3的方式实现算法P 时,其计算复杂性不超过O(T (n 2+m 2)),对此算法的理论分析将在另文给出,下面通过大量的实例来表明算法P 具有非常好的性质.现在来构造问题P 的一些实例,首先对注3中的乘同余法初始化∀(0)=∀0,然后对每组给定的m ,n (n <256),通过如下的方式做出问题(P )的一千个实例E(m ,n ),其中第k 个实例的向量l 的分量取值为 l(j )=int (100∃∀(256∃(k -1)+j )/(108+1))+1,j =1,2,!,n.其中函数int 表示取整数部分,由此l 的分量的取值范围在1到100之间,并且E (m ,n)中第k 个实列的l 分量的取值与E (m ,n +1)中第k 个实例的l 分量的前n 个分量相同,例如E (3,16)中的第1个实例为:m =3,n =16,l =(95,78,78,86,66,99,74,89,42,52,80,29,66,10,14,4),E (3,11)中的第1个实例为:m =3,n =16,l =(95,78,78,86,66,99,74,89,42,52,80),另外E (m ,n)与E (m +1,n)中相应实例的l 向量是相同的.由于以上所有的实例中,l 的分量是正整数,因此 f ∋=int ((m -1+∀n j=1l(j ))/m ),是问题的最优目标值的下界.下面给出对部分实例组E (m ,n )的计算结果,对每个实例都用注3的方式使用算法P ,初始解都取q(j )=1,j =1,!,n.对输出值f *,记d *=f *-f ∋,t *为迭代过程中首次取到输出值f *时的t 值.运算结果:取T =300, h =1.0,对以下12个算例组E (6,22),E (12,44),E(18,66),E (24,88),E (30,110),E (36,132),E (42,154),E (48,176),E(3,11),E (3,13),E (3,15),E (3,17)中的所有实例分别进行运算,其d *与t *的分布情况由表1与表2给出,另外表3给出LPT 算法[4]相应于表1的结果,即d LPT =max 1#i #m ∀{l(j )|q LPT (j )=i}-f ∋的分布情况,其中q LPT =B(lD(l ))[D (l)]-1,所有表中的数字都表示相应的实例数.表1 d *的分布统计表123&4E (6,22)91385011E(12,44)91639E(18,66)97327E(24,88)97723E(30,110)98713E(36,132)97822E(42,154)98218)167)第3期 程建纲等:多处理机调度问题的一种近似算法续表10123&4E (3,11)56132875828E (3,13)9177841E (3,15)9928E (3,17)1000表2 t *的分布统计表0~4950~99100~149150~199&200E (6,22)720142623046E(12,44)84281322124E(18,66)88951222513E(24,88)9135120106E(30,110)94039777E(36,132)9284091013E(42,154)942351166E(48,176)937351765E (3,11)906572593E (3,13)853********E (3,15)920551294E (3,17)95442310表3 d LPT 的分布统计表012345&6E(6,22)6508311912493525E (12,44)12870110142134515E (18,66)11471118144125527E (24,88)01564148156166451E (30,110)01184157162159427E (36,132)01786164165172396E (42,154)11077159206190357E (48,176)0772192223170336E(3,11)461041201119886435E(3,13)4914715711712381326E(3,15)7316117312510696266)168)烟台大学学报(自然科学与工程版) 第10卷以上统计结果表明对所选实例组中的绝大多数实列,算法P 都能用较少的迭代次数得到问题的最优解,同时表1表明其绝对精度有以下两个趋势:(1)对固定的k ,当n =k m 时,随着m 的增大,绝对精度有提高的趋势;(2)对固定的m ,随着n 的增大,绝对精度有提高的趋势.因此算法P 对大规模多处理机调度问题具有明显的优点,而不同于LPT 算法,表3表明当n =km 时,随着m 的增大,LPT 算法的绝对精度有降低的趋势.最后关于算法P 中参数 h 的作用,在Step1产生新解时,如果h =0,则由文献[5]中结论可知新解的目标值一定不超过原来解的目标值,但随着h 的增大,新解目标值的随机性将变大,而倾向性将变小,另外对大量实例的计算结果表明在迭代到一定的次数后,目标值会出现涨落现象,而其均值与涨落次数都明显的依赖于参数 h 的选取,随着 h 的增大,目标值的均值与目标值的涨落次数同时具有增大的趋势,因此当T 比较大, h 在一定的范围内变化时,解的性能不会有明显的改变.参 考 文 献1 孙世杰.排序问题的简短历史和国外发展动态.运筹学杂志,1991,10(1):22~382 唐国春.排序问题的定义、分类和在国内的某些研究进展.运筹学杂志,1990,9(2):65~743 徐钟济.蒙特卡罗方法.上海:上海科学技术出版社,19854 Graham R L.Bounds on mult iprocessing timing ano malies.SIAM J A ppl M ath,1969,17:416~4295 程建纲.同型号平行机器排序问题中近似解的一种改进方法.烟台大学学报(自),1996(1):29~33An Approximation Algorithm forthe Problem of Multiprocessor SchedulingCheng Jiang ang(Department of M athematics and Information S cience,Yantai U niversity,Yantai 264005)Qin Cheng lin(Department of M athematics,S hanghai Universi ty,S hanghai 201800)Abstract For the problem P C m a x of multiprocessor scheduling,an approximate algorithm is g iven in this paper.The calculated results from many ex amples show that this alg orithm is very effective.Key words combinatorial optimization,scheduling ,approximate algorithm,random ized algo rithm(责任编辑 苏晓东))169)第3期 程建纲等:多处理机调度问题的一种近似算法。
