生产调度问题及其优化算法
生产调度问题及其优化算法
<采用遗传算法与MATLAB编程）
信息014 孙卓明
二零零三年八月十四日
生产调度问题及其优化算法
背景及摘要
这是一个典型的Job-
Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-
Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含种排列。因为问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。
一．问题重述
某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其
工序产品
1 2 3 4 5 6 7 8
S T S T S T S T S T S T S T S T
1 C 8 A
2 B 4 C 24 D 6
2 A 4 D 5 B
3 C 4
3 C 3 D 7 A 15 B 20 A 8
4 B 7 C 6 D 21 A 1 D 16 C 3
5 D 10 B 4 C 8 D 4 A 12 C
6 D 1
6 A 1 B 4 A
7 C 3 D 5 A 2 C 5 A 8
条件：1、每件产品必须按规定的工序加工，不得颠倒；
2、每台设备在同一时间只能担任一项任务。
<每件产品的每个工序为一个任务）
问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。
要求：给出每台设备承担任务的时间表。
注：在上面，机器A，B，C，D即为机器1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D
二．模型假设
1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断；
2．所有机器均同时开工，且工件从机器I 到机器J 的转移过程时间损耗不计；
3．各工件必须按工艺路线以指定的次序在机器上加工多次；
4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。
三．符号说明及初始数据表达分析
- 第i个工件 - 机器顺序阵表示i工件的第 j个操作的机器号 - 第j台机器 - 工件排列阵表示i机器上第j次加工的工件号 - 加工时间阵为i工件的第 j个操作的时间周期 - 整个任务完成时间 整理数据后得到： =[ C A B C D 0 0 0 ] = [ 8 2 4 24 6 0 0 0 ] [ A D B C 0 0 0 0 ] [ 4 5 3 4 0 0 0 0 ] [ C D A B A 0 0 0 ] [ 3 7 15 20 8 0 0 0 ] [ B C D A D C 0 0 ] [ 7 6 21 1 16 3 0 0 ] [ D B C D A C D 0 ] [ 10 4 8 4 12 6 1 0 ] [ A B A C D A C A ] [ 1 4 7 3 5 2 5 8 ] 上述二阵直接从题目得出，而则是我们要求的。 产品/工件 加工工序总数<个） 5 4 5 6 7 8 35 机器/设备(j>: A B C D 总计 总净加工时间60 42 70 75 247 加工操作次数10 6 10 9 35 因为各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总计为247，那么总时间 C 介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。 希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D 不间断工作,直至全部加工任务完成。四．贪婪法快速求解 如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则: 1.优先选择总剩余时间或总剩余操作较多的工件。<如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。 2.机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D 不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。首先按照最优化时间为75的设想避免D 出现等待，排序后得到升以下具体排列顺序。 各机器承担任务表为(其中粗体字为对应工件产品号，括号内为对应时间周期 (1037 178 4421 6448 4 25 375242015163166 1 5 124 2^^^ ^ 38 8 010 20 30 40 50 60 70 80 D 机器 C 机器B 机器A 机器^ (图一> 上图为加工周期图<甘特图），标注数字为相应操作的周期，完工时间为第75周期。 五．计算机随机模拟<编程） 1．编码： 随机产生生产的工序操作优先顺序，进行编码，如：K=[ 4 35 6 6 2 3 1 4 1 6 3 5 4 53 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 6 5]<注：同时作为下文的染色体之用）意思为：工件4优先被考虑进行第一次操作，然后3进行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次进行。如果前后互相不冲突，则可同时在不同机器上操作。 通过排列组合得出，总共有类似K的排列序列 2多种！ 当然，这其中只对应解[75，247]，意味着有大量排列序列对应同一加工方案，而大量加工方案又对应同一时间解。 2．解码： 即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作<记为<2，i），且在机器A上进行）被安排在工件3第j步操作<记为JM<3,j））后面进行，那么如果安排好 <3,j）后，只要<2，i）在工件2已经排序好的操作之后进行，那么操作<2，i）可插入到机器A处最前可安置的时间段进行。 在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。 3．编程： 通过一组随机编码产生一生产加工优先序列，通过解码过程产生相应加工方案及其总耗费时间C . N次模拟后即可得出解C的概率密度分布情况以及相对最优解 4．计算机模拟所得数据分析 a. 进行100次模拟得出最优解情况：(共运行10次> 82，83，82，84，78，80，81，83，87，82 平均值 82.2，每回耗时约3秒b. 进行1000次模拟得出最优解情况：(共运行10次> 80，79，78，78，79，79，76，80，77，78 平均值 78.4 , 每回耗时25秒 c. 进行10000次模拟得出最优解情况：(共运行10次> 76，77，77，75，76，76，77，76，76，77 平均值 76.3, 每回耗时4分钟 d. 模拟1000000次得到的解C的概率密度分布情况为：<如图二所示） ( 图二 > <注：75处为17次<概率为17/1000000=1/58823），76处为40次，77处167次） 结论：如果想将2中排序序列以平均出现一次的可能性进行模拟，即运行2次，计算机需运行将近150万亿年！当然，我们没有这个必要，因为我们只需要运行数万次，就很可能得到最优解75，<在随机 模拟1000000次后出现17次75，那么意味着概率大约17/1000000=1/58823 ，另外76处为40次，77处167次）。 六．遗传算法模型建立和步骤解法 遗传算法 Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。 本文根据实际情况采取了1-6整数编码。数字1，2，3，4，5，6分别代表6件待加工产品。 本文遗传算法基本流程: 通过编码，解码程序随机产生N个<有一定数量,如50或100）个体构成初始种群 a)从初始中群中选取2个具有最优染色体<最有排序方案）的个体作为临时个体<父 代）； 如果此2个体中有一个个体通过解码操作能够实现最优排序<即使总时间为75周 期），那么结束此算法，得到最优解； 对2个临时个体以一定方式(循环交叉>执行染色体交叉变换和变异选择<小概率,互换操作），产生2个新的个体； d)对父代和子代共4个个体进行选择，从中选出最佳的2个个体，做为下一代的父代； e)重复执行第二步(b>操作； f)如果执行完M步后仍然未得出答案75，那么将目前的最优解作为本算法的最优解答 案。 1．编码和解码 <同上） 2．交叉变换(crossover> 对2个父代临时个体进行染色体交叉变换，采用循环交叉方法 :[3 2 5 4 1 6 7 8 9],:[9 4 6 8 7 3 5 2 1],实现交叉变换。 3．变异选择 采用互换操作 :[3 2 5 4 1 6 7 8 9] 。随机产生变换位置号，如产生随机数3和5，那么交换数字后得到染色体：[3 2 1 4 5 6 7 8 9]，变异概率取0.1 。 4．选择操作 对父代2个体f1,f2和子代2个体f3,f4进行选择，通过编码操作确定具有最优解的2个个体，成为新一代f1和f2 。 如此，通过多次编码和解码随机产生一定数量的个体，选取2个最佳个体进行交叉变换操作，产生2个新个体，然后对4个个体进行选择，产生下一代，如果某时刻通过解码操作得出最优解<所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最终最优解。 七．遗传算法模拟<采用MATLAB工具编程） 主程序如下：<子程序见略） % 本程序为主程序，调用以下各分支程序 task= 'Welcome! Wait a moment please! --- Writer: 孙卓明 ,信息 014', f1=zeros(1,35>。f2=zeros(1,35>。 while f1==f2。 % 此步避免初始染色体 f1,f2 相同，导致以下死循环 [minminmax1,s1]=chushijie(N>。 % 种群初始化；基于操作的编码策略；活动化解码算法。 chushijie(N> 参数 N 为初始种群数 f1=s1 。 minminmax1, % 选取的第一个初始个体 [minminmax2,s2]=chushijie(N>。 % 再次种群初始化 f2=s2 。 minminmax2, % 选取的第二个初始个体 end。 for e=1:M。 % e=1:M 进行 M 次遗传操作<交叉-变异-选择> [D]=jiaocha(f1,f2>。 % 交叉变化<循环交叉操作，cycle crossover CX）,选取 f1。 f2。“染色体”无需变动部分基因 [f3,f4]=jiaocha_bianyi(f1,f2,D>。 % 生成交叉后的“染色体”,并进行变异选择 f3。 f4。 [f1,f2]=xuanze(f1,f2,f3,f4>。 % 选择：对父代f1,f2和子代f3,f4进行解码，得出2个f1。 f2。较优个体，成为下一代的父代 [minmaxf1,a1,b1]=tongbujinzhan(f1>。 % 求该时刻个体f1的最优时间(因为f1优于f2> if minmaxf1==75。 f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, task='Finish! Successful! Best answer! Congratulation! ' , return 。 end。end。 f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, if minminmax_last>=90。 task='Finish! Action again please!',end。 if minminmax_last>=80&&minminmax_last<90。 task='Finish!' , end。 if minminmax_last<80。 task='Finish! Successful!', end。 八．遗传算法模拟结果 首先给出最优方案: 在进行某次n=100,m=200的操作后得到模拟最优结果75周期时间： minminmax1 =83minminmax2 =78<二个初始较优个体解） f1 =[4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5 6 4 6 6 4 3 2 2 5 1 1] a1 = 5 35 39 64 0 0 0 0 0 15 24 0 0 0 0 0 0 0 17 53 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b1 =11 38 42 65 0 0 0 0 0 20 35 0 0 0 0 0 0 0 18 54 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 minminmax =75 <最终最优解） 其中机器A空闲时间段为:5-11,35-38,39-42,64-65。机器B则为:15-20,24-35。机器C为:17-18,53-54,65-68。机器D无空闲。 100时得到的100*2个随机解中的最优解,78为经过M=10000代的遗传(交叉变异选择>后得到的最终最优解。 明显地发现: M 的增大所产生的优化效果明显好于N增大产生的优化效果 M 从1-10-100-1000-10000的变化使最优解有从9*--8*--7* 的变化规律， N 的1-10-100的变化则不明显。 因此相对于随机取解, 经过遗传算法优化之后效果是显著的。 由上表看来,虽然在均值方面相差不显著,但是时间上采用遗传算法之后节约了约三分之二的运行时间,效率显而易见。 九．模型优缺点及改进 模型优点，采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。 缺点，采用遗传算法还不全面，只是一个简单模型，未考虑收敛性,适配值等，对参数设置与最优解关系研究还不够深入。 模型本身还具有漏动，仍需改进，较好设想为采用和模拟退火算法的混合遗传算法，因为时间紧迫，在此就不再深入给出模型及分析了。 [参考文献]： 1．车间调度与遗传算法王凌清华大学出版社 2．数值计算的算法与分析张可村赵英良科学出版社 3．Permutation Based GAs and Ordered GreedPeter G. Anderson, 4．MATLAB6.0 与科学计算王沫然电子工业出版社 5．C程序设计<第二版）潭浩强清华大学出版社 信息014孙卓明 2003年8月14日 本文网上下载地址(个人主页>: 附录： 子程序一：(种群初始化，得较优个体> function [minminmax,ss]=chushijie(n> % 种群初始化,以下为编码和解码过程，同时对n次选取最优化个体 Jm=[3 1 2 3 4 0 0 0 。1 4 2 3 0 0 0 0 。3 4 1 2 1 0 0 0 。2 3 4 1 4 3 0 0 。4 2 3 4 1 3 4 0 。1 2 1 3 4 1 3 1 ]。 minminmax=200。 for d=1:n。 s=0。 % 编码程序：基于操作的编码策略 k=1。 for t=1:35 。 I=randint(1,1,[1,6]>。 while Jm(I,1>==0。 I=randint(1,1,[1,6]>。 end。 s(k>=I。 k=k+1。 x=1。 while x<=7。 Jm(I,x>=Jm(I,x+1>。 x=x+1。 end。 Jm(I,8>=0。 end。 Jm=[3 1 2 3 4 0 0 0 。1 4 2 3 0 0 0 0 。3 4 1 2 1 0 0 0 。2 3 4 1 4 3 0 0 。4 2 3 4 1 3 4 0 。1 2 1 3 4 1 3 1 ]。 T=[8 2 4 24 6 0 0 0。4 5 3 4 0 0 0 0。3 7 15 20 8 0 0 0。7 6 21 1 16 3 0 0。10 4 8 4 12 6 1 0。 1 4 7 3 5 2 5 8 ]。 % 解码程序：活动化解码算法 for i=1:6。 k(i>=1。 end 。 for q=1:4。 for x=1:9。 a(q,x>=0。b(q,x>=0。flag_(q>=0。 end。 end。 for p=1:6。 flag(p>=0。 end。 for i=1:35。 q=Jm(s(i>,k(s(i>>>。t=T(s(i>,k(s(i>>>。z=0。 v=0。 for x=1:9。 if max(flag(s(i>>,a(q,x>>+t<=b(q,x>&&z==0 。 if flag(s(i>><=a(q,x>&&a(q,x>+t==b(q,x>。 flag(s(i>>=b(q,x>。for y=x:8。 a(q,y>=a(q,y+1>。b(q,y>=b(q,y+1>。 end。z=1 。 elseif flag(s(i>><=a(q,x>&&a(q,x>+t elseif flag(s(i>>>a(q,x>&&a(q,x>+t==b(q,x> 。flag(s(i>>=b(q,x>。b(q,x>=b(q,x>-t。z=1。 elseif flag(s(i>>>a(q,x>&&a(q,x>+t for y=8:x+2。 a(q,y>=a(q,y-1>。b(q,y>=b(q,y-1>。 end。 b(q,x+1>=b(q,x>。b(q,x>=flag(s(i>>。a(q,x+1>=flag(s(i>>+t。flag(s(i>>=a(q,x+1>。z=1。 end。 end。 end。 if z==0。 if flag(s(i>><=flag_(q>。 flag(s(i>>=flag_(q>+t。 flag_(q>=flag_(q>+t。 elseif flag(s(i>>>flag_(q>。 for x=1:9。 if a(q,x>==0&&v==0。 a(q,x>=flag_(q>。b(q,x>=flag(s(i>>。v=1。 end。end。flag(s(i>>=flag(s(i>>+t。 flag_(q>=flag(s(i>>。 end。 end。 k(s(i>>=k(s(i>>+1。 end。 minmax=0。 for q=1:4。 if minmax minmax=flag_(q>。 end。 end。 if minminmax>minmax 。% 得出初始最优解 minminmax=minmax 。ss=s 。 end 。 end。 子程序二：<父代交叉变换） function [D]=jiaocha(f1,f2> % 交叉变化<循环交叉操作，CX）,选取“染色体”无需变动部分基因 s=randint(1,1,[1,35]>。 while f1(s>==f2(s>。 s=randint(1,1,[1,35]>。 end。 for p=1:34。 D(p>=0。 end。 z=0。j=1。D(j>=s。j=j+1。 for i=1:35。 if f1(i>==f2(s>&&z==0 。 D(j>=i。j=j+1。z=1。 end。 end。 if f2(D(j-1>>==f1(s>。 return。 end。 for m=1:34。 z=0。 for i=1:35。 if f1(i>==f2(D(j-1>> && z==0 。 w=0。 for t=3:j。 if (i-D(t-1>>>0||(i-D(t-1>><0。 w=w+1。 end。 end。 if w==j-2。 D(j>=i。 j=j+1。z=1。 end 。 end 。 end。 if f2(D(j-1>>==f1(s>&&z==1。 return。 end。 end。 end。 子程序三：<变异选择，形成子代）function [f3,f4]=jiaocha_bianyi(f1,f2,D> % 生成交叉后的“染色体”,并进行变异选择 g2=f1。g1=f2。 for i=1:34。 if D(i>>0。 g1(D(i>>=f1(D(i>>。g2(D(i>>=f2(D(i>>。 end。 end。 f3=g1。f4=g2。 c=randint(1,1,[1,100]>。 if c==1 。 d1=randint(1,1,[1,35]>。 d2=randint(1,1,[1,35]>。 while d1==d2。 d2=randint(1,1,[1,35]>。 end。 m=f3(d1>。f3(d1>=f3(d2>。f3(d2>=m。 elseif c==2。 d1=randint(1,1,[1,35]>。 d2=randint(1,1,[1,35]>。 while d1==d2。 d2=randint(1,1,[1,35]>。 end。 m=f4(d1>。f4(d1>=f4(d2>。f4(d2>=m。end。 子程序四：<四者中选取最优二个体） function [f1,f2]=xuanze(f1,f2,f3,f4> % 对父代f1,f2和子代f3,f4进行解码，得出2个 较优个体，成为下一代的父代 min1=0。min2=0。min3=0。min4=0。h=0。g=0。[min1]=tongbujinzhan(f1>。 [min2]=tongbujinzhan(f2>。 [min3]=tongbujinzhan(f3>。 [min4]=tongbujinzhan(f4>。 if min1<=min2&&min1<=min3&&min1<=min4 。 h=f1 。if min2<=min3&&min2<=min4。 g=f2。 elseif min3<=min2&&min3<=min4。 g=f3。 elseif min4<=min2&&min4<=min3。 g=f4。 end。 elseif min2<=min1&&min2<=min3&&min2<=min4 。 h=f2。if min1<=min3&&min1<=min4 。 g=f1。 elseif min3<=min1&&min3<=min4 。 g=f3。 elseif min4<=min1&&min4<=min3 。 g=f4。 end。 elseif min3<=min1&&min3<=min2&&min3<=min4 。 h=f3。if min1<=min2&&min1<=min4 。 g=f1。 elseif min2<=min1&&min2<=min4 。 g=f2。 elseif min4<=min1&&min4<=min2 。 g=f4。 end。 elseif min4<=min1&&min4<=min2&&min4<=min3 。 h=f4。if min1<=min2&&min1<=min3 。 g=f1。 elseif min2<=min1&&min2<=min3 。 g=f2。 elseif min3<=min1&&min3<=min2 。 g=f3。 end。 end。 end。 f1=h。f2=g。 while f1==f2。 [minminmax3,s1]=chushijie(30>。 f2=s1。 end。 子程序五：<循环之中，同步求解）function [minmaxf1,a1,b1]=tongbujinzhan(f1> % 求该时刻个体f1的最优时间 Jm=[3 1 2 3 4 0 0 0 。1 4 2 3 0 0 0 0 。3 4 1 2 1 0 0 0 。2 3 4 1 4 3 0 0 。4 2 3 4 1 3 4 0 。1 2 1 3 4 1 3 1 ]。 T=[8 2 4 24 6 0 0 0。4 5 3 4 0 0 0 0。3 7 15 20 8 0 0 0。7 6 21 1 16 3 0 0。10 4 8 4 12 6 1 0。1 4 7 3 5 2 5 8 ]。 s=f1 。 % 解码程序：活动化解码算法 for i=1:6。 k(i>=1。 end 。 for q=1:4。 for x=1:9。 a(q,x>=0。b(q,x>=0。flag_(q>=0。 end。 end。 for p=1:6。 flag(p>=0。 end。 for i=1:35。 q=Jm(s(i>,k(s(i>>>。t=T(s(i>,k(s(i>>>。 z=0。 v=0。 for x=1:9。 if max(flag(s(i>>,a(q,x>>+t<=b(q,x>&&z==0 。 if flag(s(i>><=a(q,x>&&a(q,x>+t==b(q,x>。 flag(s(i>>=b(q,x>。 for y=x:8。a(q,y>=a(q,y+1>。b(q,y>=b(q,y+1>。 end。 z=1 。 elseif flag(s(i>><=a(q,x>&&a(q,x>+t flag(s(i>>>a(q,x>&&a(q,x>+t==b(q,x> 。flag(s(i>>=b(q,x>。b(q,x>=b(q,x>-t。z=1 。 elseif flag(s(i>>>a(q,x>&&a(q,x>+t for y=8:x+2。 a(q,y>=a(q,y-1>。b(q,y>=b(q,y-1>。 end。 b(q,x+1>=b(q,x>。b(q,x>=flag(s(i>>。a(q,x+1>=flag(s(i>>+t。flag(s(i>>=a(q,x+1>。z=1。 end。 end。 end。 if z==0。 if flag(s(i>><=flag_(q>。 flag(s(i>>=flag_(q>+t。 flag_(q>=flag_(q>+t。 elseif flag(s(i>>>flag_(q>。 for x=1:9。 ifa(q,x>==0&&v==0。a(q,x>=flag_(q>。b(q,x>=flag(s(i>>。v=1。 end。end。flag(s(i>>=flag(s(i>>+t。flag_(q>=flag(s(i>>。 end。 end。 k(s(i>>=k(s(i>>+1。 end。 minmaxf1=0。 for q=1:4。 if minmaxf1 minmaxf1=flag_(q>。 end。 end。 a1=a。 b1=b。 申明： 所有资料为本人收集整理，仅限个人学习使用，勿做商业用 途。 《操作系统原理》实验报告 实验名称：Linux随机进程调度算法实现 班级： 学号： 姓名： 日期： 2012/12/31 一、实验名称 Linux随机进程调度算法实现 二、所属课程名称 《操作系统原理》 三、实验原理 linux 0.11内核目录linux/kernel中的sched.c函数是内核中进程调度管理的程序，其中schedule()函数负责选择系统中下一个要运行的进程。 schedule()函数首先对所有任务（进程）进行检测，唤醒任何一个已经得到信号的进程。具体方法是任务数组中的每个进程，检查其报警定时值alarm。如果进程的alarm时间已经过期（alarm NR_TASKS：系统能容纳的最大进程数(64个)； task[]：任务（进程）数组； 更改代码如下：（linux 0.11内核目录下linux/kernel/sched.c 源文件的scheduling（）函数while（1）循环）while (1) { //定义c用来判断系统中是否可运行的任务（进程）存在; c=-1; //c初值设为-1，默认不存在可运行进程; next = 0;//next记录下一个即将运行的进程; i=jiffies % NR_TASKS+1; //i的值是随机产生的; p=&task[i];//p指向在task表中下标为i的进程； while (--i) { //遍历task[]； if(!*--p)continue; //如果task[i]不包含进程，跳过； //如果task[i]包含进程且该进程处于就绪状态，记录 //该任务（进程）序号，跳出无限循环while(1),转向 //switch_to()函数执行该任务（进程）； if ((*p)->state == TASK_RUNNING) { next = i; c=i; break; } } if (c) break;//如果没有任何任务(进程)要执行，则跳出， //转向switch_to()，执行0号进程(idle)。 } 2018年8月电工技术学报Vol.33 No. 15 第33卷第15期TRANSACTIONS OF CHINA ELECTROTECHNICAL SOCIETY Aug. 2018 DOI：10.19595/https://www.wendangku.net/doc/ea567585.html,ki.1000-6753.tces.170871 基于动态调度优先级的主动配电网 多目标优化调度 黄伟1熊伟鹏1华亮亮2刘立夫1刘自发1 （1. 华北电力大学电气与电子工程学院北京 102206 2. 蒙东通辽供电公司通辽 028000） 摘要供需互动的主动配电网调度技术为应对可再生能源的高比例接入提供了新的思路。在多种不确定性的环境下，本文建立了需求侧资源（如柔性负荷、电动汽车等）和供给侧资源（如 储能装置、可控分布式电源等）互动调度机制，综合考虑可调度资源的实时状态和历史数据信息， 建立可调度资源动态调度优先级（DSP）评估体系。在此基础上，根据DSP评估结果对各类可调 度资源进行协调控制，以达到调度成本最小、可再生能源利用率最大以及用户满意度最高的主动 配电网优化目标。最后结合某11节点配电网络，通过改进粒子群算法对调度模型求解，验证了调 度模型和求解算法的有效性和可行性。 关键词：主动配电网可调度资源动态调度优先级多目标优化 中图分类号：TM734 Multi-Objective Optimization Dispatch of Active Distribution Network Based on Dynamic Schedule Priority Huang Wei1 Xiong Weipeng1 Hua Liangliang2 Liu Lifu1 Liu Zifa1 (1. School of Electrical and Electric Engineering North China Electric Power University Beijing 102206 China 2. State Grid of Tongliao Inner Mongolia Tongliao 028000 China) Abstract The dispatch technology of active distribution network which involves the interaction between supply side and demand side has provided a new idea to cope with the access of high proportion of renewable energy resources. Under the circumstance of various uncertainties, a interact dispatch mechanism is established in this paper, which considered the demand side resources (such as flexible load, electric vehicle) and supply side resources (such as energy storage system, controllable distribution generator). The dynamic schedule priority evaluation system is also proposed, which take the real-state status information and historical date of schedulable resources into account. Based on the evaluation results, all kinds of schedulable resources are controlled to achieve the optimization dispatch goal, which is minimizing the dispatch costs, maximizing the utilization of renewable energy resources, and promoting the consumer satisfaction level. Finally, improved particle swarm optimization is applied in this paper to solve the dispatch model, and numerical simulations on a 11-bus distribution network illustrate the effectiveness and feasibility of the dispatch model and the optimal algorithm. Keywords：Active distribution network, schedulable resources, dynamic schedule priority, multi-objective optimization 国家自然科学基金资助项目（51577058）。 收稿日期 2017-06-19 改稿日期 2017-08-17 万方数据 Abstract An intelligent bus dispatching system can better meet people's travel needs.The optimized algorithm takes advantage of advanced technology and equipments.However,in recent years the development of Chinese intelligent bus dispatching systems is not satisfactory with an.excessive attention to advanced technology but less to practicality.Dynamic scheduling has yet to be fully exploited.In this paper,intelligent transportation scheduling systems and scheduling characteristics are analyzed. The information about dynamic transportation and vehicle locations is acquired and merged.An optimization model for intelligent dispatching of buses is proposed on basis of real data.This model is under the support of GPS positioning,communications,computers and other technologies,where intelligent algorithms are used in bus operation and dispatching and both passengers satisfaction and company profit are considered.The method of collecting data automatically and the algorithm of this model are presented.This model is shown to be able to significantly improve the rate of bus full loading,shorten the waiting time of passengers,and reduce the total vehicle trips,with an evident effect of optimized dispatching. Keywords intelligent transportation;optional model;dynamic dispatching;intelligent bus;Matlab software 0引言 伴随经济社会的发展，中国城市交通问题日益突出。交 通问题的出现，严重影响了城市的生产生活，而且从长远来看，影响了城市功能的发挥，制约了城市的健康发展。国际上城市交通发展的经验证明，解决城市交通问题，关键是要树立城市公共交通在城市交通体系中的主导地位，大力优先发展公共交通，建立先进的公共交通系统APTS （Advanced Public Traffic System ）[1]，实现公交调度智能化，提高道路通行 能力和公交运营管理水平。 近年来，由于科学技术的进步和政府对公交投入力度的加大，中国智能公共交通调度系统初现端倪，已经有杭州、上海、北京等地安装了电子站牌，车载GPS 定位设备，实现了车辆的实时跟踪、定位，公交车与调度室的双向通讯，以及电子站牌上实时显示下班车位置信息等功能。青岛、贵阳、石家庄等城市在实现公交系统智能化管理方面，已经有了一系列有益的探索[2]。但是，这些系统普遍存在先进的系统与静态、原始的调度方法共存现象，未能充分利用智能系统提供的动态 智能公交动态调度优化模型 摘要 利用先进的技术和设备实现公交的优化调度，充分满足人们的出行需要，是智能公交系统发展的目标。然而近年来中国智 能公交发展在一定程度上出现过于追求先进性、忽略实用性、运营效果不理想、动态调度尚待充分开发等问题。结合中国智能公交系统现状，通过对智能公交调度系统和调度特点深入分析，在GPS 定位、通信、计算机等技术的支持下，将动态交通状态信息与车辆定位信息有效融合，将智能化算法引入到公交运营调度中，建立了基于实时动态数据，兼顾乘客满意度和企业效益的动态调度优化模型。并且阐述了模型数据的自动采集方法、模型Matlab 程式化的解法。结果表明，该模型可以显著提高公交车辆满载率、缩短乘客等车时间和减少车辆总班次，优化调度效果明显。 关键词智能交通；优化模型；动态调度；智能公交；Matlab 软件 中图分类号U494.22，TP29文献标识码A 文章编号1000-7857（2009）17-0069-04 李志强，周建立，张毅 河南科技大学车辆和动力工程学院，河南洛阳471003 An Optimization Model for Dynamic Intelligent Dispatching of Buses 收稿日期：2009-05-11 基金项目：河南教育厅自然科学基金项目（200510464028）；河南科技大学科研基金项目（2004ZY030，2006ZY027）作者简介：李志强，经济师，研究方向为智能交通，电子信箱：liqiangsqjt@https://www.wendangku.net/doc/ea567585.html, LI Zhiqiang,ZHOU Jianli,ZHANG Yi Vehicle &Motive Power Engineering College,Henan University of Science and Technology,Luoyang 471003,Henan Province,China 1．概述 1.1 调度问题的提出 敏捷制造作为21世纪企业的先进制造模式，综合了JIT、并行工程、精良制造等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有效实用的调度方法和优化技术的研究与应用已成为先进制造技术实践的基础。 调度问题主要集中在车间的计划与调度方面，许多学者作了大量研究，出了不少的研究成果。制造系统的生产调度是针对一项可分解的工作（如产品制造），探讨在在尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分（操作）使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问题常被称为排序问题或资源分配问题。 1.2 调度问题的分类 生产调度系统的分类方法很多，主要有以下几种： (1) 根据加工系统的复杂度，可分为单机、多台并行机、flow shop和job shop。 单机调度问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队问题，对于单机调度比较有代表性的请见文[9][10][l1]；多台并行机的调度问题更复杂，因而优化问题更突出，文[8][11]][13]研究了多台并行机的调度；flow shop型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序，文[12][13][14]研究了flow shop问题；job shop是最一般的调度类型、并不限制作业的操作的加工设备，并允许一个作业加工具有不同的加工路径。对于job shop型问题的研究，文献很多，综述文章可参见Lawler等[15]。 (2) 根据性能指标，分为基于调度费用和调度性能的指标两大类。 (3) 根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。 (4) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的工作均处于待加工状态，因而进行—次调度后、各作业的加工被确定、在以后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的损坏等。因此动态调度要根据系统中作业、设备等的状况，不断地进行调度。实际调度的类型往往是job shop型，且是动态的。 1.3 生产调度的环境特征 一般的调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和 操作系统实验报告（二） 实验题目：进程调度算法 实验环境：C++ 实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较 各种算法的性能优劣。 实验内容：编程实现如下算法： 1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。 设计分析： 程序流程图： 1.先来先服务算法 开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法 3.时间片轮转调度算法 实验代码： 1.先来先服务算法 #include int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main() { int amount,i,j,diao,huan; fcs f[n]; cout<<"请输入进程个数:"< 题目：设计一个按优先数调度算法实现处理器调度的程序 提示： (1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为： 进程名、指针、要求运行时间、优先数、状态。 进程名——P1~P5。 指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。 要求运行时间——假设进程需要运行的单位时间数。 优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态——假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。 (2) 每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。 (3) 处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先 数减1，要求运行时间减1。 (4) 进程运行一次后，若要求运行时间不等于0，则将它加入队列，否则，将状态改为“结 束”，退出队列。 (5) 若就绪队列为空，结束，否则，重复(3)。 2．程序中使用的数据结构及符号说明： #define num 5//假定系统中进程个数为5 struct PCB{ char ID;//进程名 int runtime;//要求运行时间 int pri;//优先数 char state; //状态，R-就绪，F-结束 }; struct PCB pcblist[num];//定义进程控制块数组 3．流程图： (1)主程序流程图： (2)子程序init()流程图： (3) 子程序max_pri_process()流程图： (4)子程序show()流程图： (5)子程序run()流程图： 水库调度研究现状及发展趋势 摘要：实施梯级水电站群联合优化运行是统筹流域上下游各电站流量、水头间的关系，从而实现科学利用水能资源的重要手段，符合建设资源节约型、环境友好型社会的要求，是实现节能减排目标的重要途径，对贯彻落实科学发展观，促进流域又好又快发展具有重要意义。本文拟介绍水库调度研究现状及发展趋势，对工程实际具有重要的理论意义。 关键词：水库;优化调度;研究形状;发展趋势 随着水电发展的规划推进落实，大型流域梯级水库群将逐步形成，其联合调度运行必将获得巨大的电力补偿效益和水文补偿效益，同时在实际工程中也会不断涌现新的现象和问题。在新形势下综合考虑梯级上下游电站之间复杂的水力、电力联系，开展梯级水库群联合调度新的优化理论与方法应用研究，统筹协调梯级水库群上下游电站各部门的利益及用水需求，结合工程实际探索梯级水库群联合优化调度的多目标优化及决策方法，实现流域水能资源的高效利用、提高流域梯级水库群的联合运行管理水平乃至达到流域梯级整体综合效益的最大化，对缓解能源短缺、落实科学发展观、贯彻国家“节能 减排”战略以及履行减排承诺均具有重要的理论指导意义和工程实用价值[1]。 1 水库调度研究现状 水库调度研究，按其采用的基本理论性质划分，可分为常规调度(或传统方法)和优 化调度[2]。常规调度，一般指采用时历法和统计法进行水库调度;优化调度则是一种以 一定的最优准则为依据，以水库电站为中心建立目标函数，结合系统实际，考虑其应满足的各种约束条件，然后用最优化方法求解由目标函数和约束条件组成的系统方程组， 使目标函数取得极值的水库控制运用方式 [3]。 常规调度 常规调度主要是利用径流调节理论和水能计算方法来确定满足水库既定任务的蓄泄过程，制定调度图或调度规则，以指导水库运行。它以实测资料为依据，方法比较简单直观，可以汇入调度和决策人员的经验和判断能力等，所以是目前水库电站规划设计阶段以及中小水库运行调度中通常采用的方法。但常规方法只能从事先拟定的极其有限的方案中选择较好的方案，调度结果一般只是可行解，而不是最优解，且该方法难以处理多目标、多约束和复杂水利系统的调度问题。 优化调度 为了充分利用有限的水资源，国内外从上世纪50年代起兴起了水库优化调度研究。其核心有两点:一是根据某种准则建立优化调度模型，二是寻找求解模型的优化方法。 1946年美国学者Masse最早引入优化概念解决水库调度问题。1955年美国人Little[4]采 生产调度问题及其优化算法（采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日 生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M ( N)! 种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工， 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 （每件产品的每个工序为一个任务） 问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。 要求：给出每台设备承担任务的时间表。 注：在上面，机器 A，B，C，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D 一．课程概述 1.1.设计构想 程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。 1.2.需求分析 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。 1.3.理论依据 为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(Process Control Block),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB 而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。 1.4.课程任务 一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多 种算法实现对进程的模拟调度。 二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多 级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。 三、实现用户界面的开发 毕业设计说明书中文摘要 刘杰：电力市场下电力系统优化调度研究毕业设计说明书外文摘要 刘杰：电力市场下电力系统优化调度研究 目录 1 引言 (4) 1.1课题研究的目的与意义 (4) 1.2电力系统的现状 (5) 2 电力系统油画调度算法 (5) 2.1优化算法 (5) 2.2优化调度遗传算法 (7) 2.3优化调度动态规划法 (11) 3 电力系统优化调度 (12) 3.1水电厂优化调度思路 (12) 3.2水电厂优化调度建模 (12) 3.3水电厂优化调度运行 (15) 3.3.1优化调度检修优化 (17) 3.3.2最小风险度模型 (18) 4优化结果比较 (19) 4.1计算结果分析比较 (19) 4.2两种算法比较 (21) 5结论与展望。 (23) 5.1结论 (23) 5.2展望 (23) 参考文献 (23) 致谢 (23) 刘杰：电力系统优化调度研究 电力系统优化调度研究 1 引言 1.1课题研究的目的与意义 电力工业的根本任务是以安全为中心，在充分合理地利用能源和运行设备能力的条件下，保证安全经济发、供电，以满足国民经济各部门的电能需求。电力系统供应着现代化社会生产和生活的大部分能量，相应地，也消耗着大量的一次能源——煤、石油等。对于电力这样重要的能源转换系统，提高其运行效率、实现其运行优化的必要性是显而易见的。对于一个大的电力系统而言，在保证供电的前提下减少燃料消耗，提高运行的效率，就意味着每年能够节约数以万吨计的燃料。因此，电力系统的优化问题长期以来一直是电力系统工程技术人员和学者研究的重点。尤其是近几年来，随着我国国民经济的快速发展和人民生活水平快速提高，全社会用电量急速增长，全国都面临着电力严重短缺的局面。在如此严峻的形势下，深入研究电力系统的优化及经济运行问题更具有十分现实的社会意义。 电力系统优化是电力系统分析的一个分支，它所研究的问题主要是在满足负荷需求的前提下，如何优化地配置系统资源以及调度系统内设备的运行工况，从而使系统发电所需的总费用或所消耗的总能源耗量达到最小这样一个运筹决策问题。现代电力系统优化是电力系统潮流分析、数学优化理论、运筹学以及系统工程等多学科交叉的一个研究领域，它所包含的内容是十分广泛的。本文从能耗及环境方面等角度研究现代电网优化问题，根据现代电力系统的特点建立合适的数学模型，结合数学优化理论、运筹学知识以及优化算法，对研究水电厂实用化可提供一定的解决方案。 总之，对电力系统优化调度的研究有助于发展和丰富电力系统分析和优化运行理论，有益于提高电力系统经济效益，促进电力市场的健康发展，同时也是提高电力系统自动化水平的迫切要求，因此本课题研究电力系统的优化调度具有深远的理论意义，也具有重大的实际价值。 1.2电力系统的现状 作者姓名：翟桥柱 论文题目：电力系统优化调度模型与算法研究 作者简介：翟桥柱，男，1972年6月出生，1999年9月师从于西安交通大学系统工程研究所管晓宏教授，于2005年12月获博士学位。 中文摘要 电力系统优化调度是有巨大潜在经济效益的一类优化问题。它的主要目标是在确保电力正常供应的前提下合理利用发电资源，减少能源消耗和环境污染，降低发电总成本，提高发电厂在电力市场中的竞争力。随着主要发电用燃料——煤、石油和天然气等资源的日渐消耗和世界范围内电力市场化改革的推进，如何进一步提高电力系统优化调度水平成为迫切需要研究的一个课题。 Lagrange松弛法是目前公认的求解电力系统优化调度问题最有效的方法之一。本文主要研究了Lagrange松弛法框架下一些多年遗留问题以及电力市场环境下与调度有关的一些新问题。具体包括以下几个方面： 对电力系统优化调度问题进行了概述，特别分析了电力市场环境下对调度问题的新要求，介绍了我国电力系统优化调度现状。 Lagrange松弛框架下的同构振荡是一个多年未获解决的难题，同构振荡是指在松弛法框架下，乘子每次修正后，相同机组对应的子问题的解始终保持同步变化。虽然从对偶问题角度看，同构振荡是自然的，但由于受系统负载需求的制约，在可行解和最优解中相同机组的开关状态及生产情况一般不同，所以同构振荡会使构造可行解变得异常困难。本文通过分析同构振荡产生的根源，指出只有通过合理的途径将对偶优化中的相同子问题化为不同才能从根本上消除同构振荡。由于正是系统负载需求约束导致相同机组的解可能不同，所以本文提出采用增广Lagrange函数引入对负载需求约束的惩罚项，且在解子问题时提出了序贯求解算法以克服可分性被破坏后给求解带来的困难，理论分析和实例测试均表明这是一种能彻底克服同构振荡的有效算法，同时这种方法还可以解决相同机组市场竞标中的公平性问题。(参见：Qiaozhu Zhai, Xiaohong Guan, Jian Cui. Unit Commitment with Identical Units: Successive Subproblems Solving Method Based on Lagrangian Relaxation [J]. IEEE Transactions on Power Systems, Vol.17, No. 4, pp.1250-1257. 2002. X.H. Guan, Q.Z. Zhai, F. Lai. New Lagrangian Relaxation Based Algorithm for Resource Scheduling with Homogeneous Subproblems[J]. Journal of Optimization Theory and Applications, Vol. 113, No.1, pp.65-82, 2002.) 电力系统优化调度中机组的爬升约束会给求解带来极大困难，引起困难的根本原因在于离散量与连续量的密切耦合，本文通过深入分析提出了一种新的状态定义及阶段划分方法，基于新的状态定义实现了离散量与连续量的解耦，以此为基础设计了一种双动态规划算法，在低层用连续动态规划求解最优的连续决策，在高层用离散动态规划求解最优的离散决策，其中离散决策费用与低层的最优连续决策有关。双动态规划法可以迅速获得具有爬升约束机组子问题的最优解，理论分析及数值计算均表明了算法的有效性，从而彻底改变了长期以来 生产调度管理办法 一、总则 ㈠为加强生产调度系统的管理，搞好公司的产销优化，确保生产组织秩序的正常开展和年度生产目标的完成，特制定本办法。 ㈡办法所称的生产调度是指为保障公司生产系统正常、安全、稳定高效、优质、经济运行，对生产所进行的组织、指挥和协调。 ㈢公司生产系统实行统一调度管理原则。 ㈣公司生产系统的基本纪律和要求：必须遵循下级服从上级的组织原则，做到有令必行、有禁必止，提高执行力，确保政令畅通。 二、生产调度系统管辖范围 ㈠生产调度系统的管理 1、在总经理领导下，分管生产的副总经理负责公司生产组织的全面统一指挥，行使生产调度指挥权。 2、公司生产安全处是公司生产管理的主管部门，在分管生产的副总经理领导下，具体负责公司的调度系统管理。 3、公司生产调度指挥系统示意图： ㈡生产调度系统执行机构 1、公司生产调度室是公司生产日常指挥与协调、统筹与控制的常设机构。 2、各厂、维修中心的生产、维修工作受公司生产调度室的指挥、协调，生产过程中出现影响产量、质量、消耗、安全、环保的问题时应及时向生产调度室报告，并受当班调度员指挥、安排。 3、生产调度员必须熟悉制盐、热电、井矿、化工、供用电线路负荷量及天然气的生产和各产品生产工艺流程。 4、生产调度员的考核办法由生产安全处按公司绩效考核办法确定。 ㈢生产调度室的管辖范围及任务 生产调度室在生产安全处处长（副处长）的直接领导下，负责贯彻执行公司指令和调度会决议，按照公司生产计划和产品销售计划，对公司日常生产活动进行控制和调节，其主 要工作： 1、发布公司生产调度令。负责公司日常生产管理、协调、平衡，协调好各产品生产及原燃材料的平衡供给，重点做好固体盐和液体盐的生产调度工作。 2、全面掌握公司生产运行变化动态，收集、汇总公司生产运行情况，处理亟待解决的生产问题。 3、建立生产监控模型，实施生产监控，在规定时间内向集团公司调度中心传送生产日报表，及时向有关领导发送主要产品产量完成情况信息，合理组织生产，提高生产过程的连续性、均衡性，生产品种的合理性，重点抓好固体盐、液体盐的优化效益生产，并做好盐的品种生产安排，及时与大英县电力公司调度室衔接，做好外购电的日常供给，根据各用电线路的负荷状况，合理调整外购电量与自发电量，确保公司生产用电的优化平衡，负责天然气供气系统的调节，按照效益优先的原则调整各单位及对外供的用气量。 4、做好矿山采卤、输卤、卤水的净化及周转、澄清、兑卤等环节的调度工作，确保制盐及金仓用卤所需。 5、做好天然气采集、输送协调工作，按照优先公司用气、兼顾外售原则，做好天然气分配使用的调度指挥工作。 6、供用电调度指挥：⑴、按照效益优先、多生产自发电、少购外电原则，负责6KV、10KV供用电线路的负荷调节； ⑵、负责6KV、10KV供用电线路的停、供电指挥，对上述线 1 处理机调度 1.1 实验内容及要求 实验内容：按优先数调度算法实现处理器调度。 实验要求：能接受键盘输入的进程数、进程标识、进程优先数及要求运行时间，能显示每次进程调度的情况：运行进程、就绪进程和就绪进程的排列情况。 1.2 实验目的 本实验模拟在单处理器环境下的处理器调度，加深了解处理器调度工作。 1.3 实验环境 本实验的设计基于Windows7操作系统DevC++5.11环境，用C语言实现编程。 1.4 实验思路 (1) 每个进程用一个PCB来代表。PCB的结构为： 进程名——作为进程标识。 优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 要求运行时间——假设进程需要运行的单位时间数。 状态——假设两种状态：就绪和结束，用R表示就绪，用E表示结束。 初始状态都为就绪状态。 指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。 (2) 开始运行之前，为每个进程确定它的“优先数”和“要求运行时间”。通过键盘输入这些参数。 (3) 处理器总是选择队首进程运行。采用动态改变优先数的办法，进程每运 行1次，优先数减1，要求运行时间减1。 (4) 进程运行一次后，若要求运行时间不等于0，则将它加入就绪队列，否则，将状态改为“结束”，退出就绪队列。 (5) 若就绪队列为空，结束，否则转到(3)重复。 1.5 数据结构与全局变量 typedef struct pcb{ int pname;//进程名 int priority;//优先级 int runTime;//所需时间 int state;//状态 struct pcb* next;//下一个进程控制块 }PCB; //进程控制块 int num;//存储进程数 PCB readyHead;//头结点，不存储进程 PCB *readyEnd;//指向尾结点的指针 1.6 函数说明 （1）主函数main() 输入进程数并调createProcess()初始化进程；若有进程，则依次调用sortProcess()、runProcess()、printProcessLink()和printProcessInfo()。（2）进程创建函数createProcess() 输入进程标识、优先级和运行时间进行初始化。 （3）进程排序函数sortProcess() 用冒泡排序算法根据进程的优先级进行降序排序，每次排序之后优先级最高的进程放在就绪队列首。 （4）进程运行函数runProcess() 将数组首的进程优先级和所需时间减1； 若剩余所需时间为0，则PCB状态标记为E（结束）。 matlab生产调度问题及其优化算法 生产调度问题及其优化算法（采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日 生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M N)! (种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加 工序产品 1 2 3 4 5 6 7 8 S T S T S T S T S T S T S T S T 1 C 8 A 2 B 4 C 24 D 6 2 A 4 D 5 B 3 C 4 3 C 3 D 7 A 15 B 20 A 8 4 B 7 C 6 D 21 A 1 D 16 C 3 5 D 10 B 4 C 8 D 4 A 12 C 6 D 1 6 A 1 B 4 A 7 C 3 D 5 A 2 C 5 A 8 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 （每件产品的每个工序为一个任务） 操作系统 ——项目文档报告 进程调度算法 专业： 班级： 指导教师： 姓名： 学号： 一、核心算法思想 1.先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 2.短作业（进程）优先调度算法 短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。 3.高响应比优先调度算法 在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的运行得不到保证。如果我们能为每个作业引人动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为: 优先权=（等待时间+要求服务时间）/要求服务时间 即优先权=响应时间/要求服务时间 如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利于短作业。 当要球服务的时间相同时，作业的优先权决定于其等待时间，等待时间越长，优先权越高，因而它实现的是先来先服务 对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时，其优先级便可以升到很高，从而也可获得处理机。 4.时间片轮转算法 在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。 二、核心算法流程图随机进程调度算法
基于动态调度优先级的主动配电网多目标优化调度
智能公交动态调度优化模型
优化调度概述
进程调度算法实验报告
设计一个按优先数调度算法实现处理器调度的程序
水库优化调度
matlab生产调度问题及其优化算法
进程模拟调度算法课程设计
电力系统优化调度研究
电力系统优化调度模型与算法研究
生产调度管理办法
处理器调度之动态优先数调度算法
matlab生产调度问题及其优化算法
操作系统模拟进程调度算法