CN4321258/TP ISSN10072130X 计算机工程与科学
COMPU TER EN GIN EERIN G&SCIENCE
2009年第31卷第8期
Vol131,No18,2009
文章编号:10072130X(2009)0820052205
基于多目标粒子群算法的混合流水车间调度方法研究3
A Hybrid Flow2Shop Scheduling Approach Based on Multi2Objective Particle Swarm Optimization
欧 微,邹逢兴,高 政,徐晓红
OU Wei,Z OU Feng2xing,G AO Zheng,XU Xiao2hong
(国防科技大学机电工程与自动化学院,湖南长沙410073)
(School of Mechatronics E ngineering and Autom ation,N ational U niversity of Defense T echnology,Ch angsha410073,China)
摘 要:混合流水车间调度问题HFSP是一种具有很强应用背景的生产调度问题。本文给出了一种HFSP多目标调度模型,提出了一种针对该类问题的多目标粒子群算法。该算法采用基于Pareto支配关系的极值更新策略;采取对自适应惯性权重递减和对种群变异的方法以保持种群多样性;设置Pareto解池保存计算中出现的Pareto最优解,并提出了一种基于适应度拥挤度的聚类算法优化解的分布特性。实验结果表明,本文算法是求解HFSP问题的一种有效方法。
Abstract:The hybrid flow2shop scheduling problem(HFSP)is a scheduling problem with strong application background.
A multi2objective scheduling model of HFSP is put forward in this paper,and a multi2objective particle swarm optimization (MOPSO)algorithm is proposed.This algorithm adopts an updating strategy based on the Pareto dominance relationship, and introduces a self2adaptive inertia weight and mutation approach to keep the diversity of the population,the also designs a Pareto optimal set pool to preserve the dominance solutions found in the evolution process.Then a clustering algorithm based on the fitness crowd degree is presented.Finally,the effectiveness of MOPSO is demonstrated by numerous simula2 tion experiments.
关键词:生产调度;混合流水车间;多目标优化;粒子群算法;Pareto最优解;进化计算
K ey w ords:production scheduling;hybrid flow2shop scheduling;multi2objective optimization;particle swarm optimiza2 tion;Pareto optimum solution;evolutionary algorithm
中图分类号:TP273文献标识码:A
1 引言
生产调度问题是指在一定的时间内,进行可共享资源的分配和生产任务的排序,以满足某些指定的性能指标。混合流水车间调度问题(Hybrid Flow2Shop Scheduling Problem,简称HFSP)在冶金、石化和国防工业等领域有很强的应用背景,是一般流水车间调度问题和并行机调度问题的推广,具有多约束、多阶段、多目标和高度的非线性等特点[1]。
文献[2]证明,即使是单目标两阶段中只有一个阶段有并行机的HFSP问题也属于NP2hard问题。鉴于问题的复杂性,很难用一般的数学规划方法进行求解。科学的调度方法一直是研究的重点,近年来,启发式方法[3]、遗传算法(G e2 netic Algorithm,简称G A)[4]和粒子群算法(Particle Swarm Optimization,简称PSO)[5]等智能算法在求解单目标HFSP 问题时表现出了较好的性能。但是,对于实际问题,HFSP 往往需要综合考虑生产成本、资源能耗和产品周期等多个因素,而且各因素之间往往会存在冲突,属于多目标优化问题(Multi2Objective Optimization Problem,简称MOP)。
粒子群算法是一种新兴的基于群集智能的进化算法,已在神经网络训练、模糊系统控制和多目标函数优化[6]等领域取得了广泛的应用。与遗传算法相比,PSO和GA都具有强大的隐并行搜索性能。由于PSO基于单个粒子与
3收稿日期:2008204209;修订日期:2008209212
基金项目:国家自然科学基金资助项目(60634020)
作者简介:欧微(19832),男,湖南邵阳人,硕士生,研究方向为粒子群算法与优化调度;邹逢兴,教授,研究方向为控制理论与控制工程、检测技术与自动化装置、智能算法与优化调度等;高政,副教授,研究方向为图像处理与模式识别、数据挖掘与智能算法等;徐晓红,高级实验师。
通讯地址:410073湖南省长沙市国防科技大学机电工程与自动化学院;Tel:139********;E2mail:ouweiwlmq@https://www.doczj.com/doc/38149306.html,
Address:School of Mechatronics Engineering and Automation,National University of Defense Technology,Changsha,Hunan 410073,P.R.China
优秀个体间的信息共享,优秀个体直接指导粒子下一代的进化方向,而GA 是基于种群所有个体间的信息共享,向最优解的方向缓慢进化,所以PSO 比GA 具有更高的搜索效率。因此,研究基于多目标PSO 算法(Multi 2objective PSO ,MOPSO )的HFSP 问题的调度方法具有重要的理论意义和工程应用价值。
2 问题描述
2.1 多目标优化问题
MOP 问题可以描述为[7]:寻找一组既满足约束条件又
使总目标函数最优化的决策变量的取值,总目标函数的元素是子目标函数。若MOP 问题的目标函数为:
Max x ∈R n
F (x )={f 1(x ),f 2(x ),…,f Q (x )}
(1)
其中,R n 称为决策向量可行空间,R Q 称为目标向量空间。
定义1 一个向量u =(u 1,u 2,…,u Q )支配向量v =
(v 1,v 2,…,v Q ),当且仅当对任意i ∈{1,2,…,Q},u i ≥v i ,且?i ∈{1,2,…,Q},使得u i >v i 。
定义2 一个解x u ∈R n 称为问题的Pareto 最优解,当且仅当不存在x v ∈R n ,使得F (x v )支配F (x u )。
定义3 所有Pareto 最优解的集合称为Pareto 最优集,相应的目标向量的图形称为Pareto 最优前沿。
2.2 混合流水车间调度问题
HFSP 问题可以描述为:N 个工件在流水线上进行S
道工序的加工,每个工序有M j (M j ≥1)台并行机,每个工件各道工序都可以在相应阶段上的任意一台机器上加工,要求确定并行机器的分配情况和同一机器上工件的加工顺序,使得多个调度目标得以优化[4]。
缩短生产周期、优化资源配置和降低产品的次品率是生产系统的三个最重要的调度目标。缩短生产周期可以提高系统的生产能力,并能增加系统的柔性;减少设备空转时间可以减少资源浪费,提高设备的使用寿命,降低单位产品的生产成本和能源消耗;降低产品的次品率可以减少次品返厂加工的人力、原料和能源消耗。因此,对调度目标描述如下:
(1)缩短生产周期。即最小化最大流程时间:
Minmize (Max N
i =1(C iS ))
(2)
其中,C iS 表示工件i 的第S 道工序(最后一道工序)的完工时间。式(2)表示调度目标为使得所有工件中的最大完工时间最小化。
(2)减少设备空转时间。一般情况下,考虑到开启和停止设备带来的消耗,设备一旦开启,则在所有加工任务完成之前不再关闭,因此对减少设备空转时间描述为:
Minmize (
∑S
j =1∑
M j
k =1
ΔT jk )(3)
其中,ΔT jk 表示加工第j 道工序的机器k 在加工流程中存
在的空转时间。式(3)表示调度目标为整个加工流程所有机器空闲时间的总和最小化。
(3)降低产品次品率。产品的次品率受多种因素影响,对于生产调度而言,选择生产产品次品率低的品质较优的
机器进行加工是降低产品次品率的有效方法:
Maxmize (
∑S
j =1∑M j
k =1
N
kj
E jk )(4)
其中,N kj 表示加工第j 道工序的第k 台机器加工工件的个数,E jk 表示该机器的品质属性。式(4)表示调度目标为最大化品质较优机器的加工任务。
3 求解HFSP 的MOPSO 算法
3.1 标准PSO 算法
SPSO (Standard PSO ,简称SPSO )将每个个体看作是D 维搜索空间中一个没有体积质量的粒子,在搜索空间中
以一定的速度飞行,粒子通过跟踪两个极值来更新自己:一
是粒子本身所找到的最优解,即个体极值rbest ;另一个是整个种群目前找到的最优解,即全局极值gbest 。若用v id 表示粒子i 在第d 维空间的速度,x id 表示其在第d 维空间的位置,w 表示惯性权重,c 1和c 2分别表示认知系数和社会系数,rand 1()、rand 2()为区间[0,1]内均匀分布的随机数,则粒子按式(5)和式(6)更新当前速度和位置。v id (t +1)=wv id (t )+c 1rand 1()(rbest id -x id (t ))+
c 2ran
d 2()(gbest d -x id (t ))
(5)x id (t +1)=x id (t )+v id (t +1)
(6)式(5)和式(6)表明粒子下一步飞行速度由三部分组成:第一部分由粒子先前速度的惯性引起,表示粒子对当前自身运动状态的信任,即依据自身的速度进行惯性运动;第二部分为“认知(Cognition )”部分,表示粒子本身的思考,即粒子本身的信息对自己下一步行为的影响;第三部分为“社会(Social )”部分,表示粒子间的信息共享和相互合作,即群体信息对粒子下一步行为的影响。
3.2 粒子编码与计算方法[4,5]
借鉴遗传算法的矩阵编码方法对粒子进行编码,编码矩阵如式(7)所示:
P N ×S =
p 11
p 12…p 1
S p 21
p 22
…
p 2S
…
…
…p N 1
p N 2
…p NS
(7)
矩阵P N ×S 是所有工件所有工序的完全编码,其每一列
对应一道工序,每一行对应一个工件。矩阵元素p ij 是区间
(1,M j +1)内的一个实数,其整数部分代表机器编号,小数
部分代表工件的优先权值。
解码时,对矩阵P N ×S 的每一个元素向下取整,得到该编码矩阵对应的机器分配情况,记为矩阵Q N ×S ,元素q ij 为区间[1,M j ]内的正整数,表示工件i 的第j 道工序在第q ij 台机器上加工。显然,可能会出现q ij =q kj 的情况,这表明有多个工件使用同一机器加工同一个工序。此时,如果是第一道工序,则按照p ij 的大小降序排列加工顺序;否则,按照各工件前一道工序完工时间的先后来排序,若前一道工序的完工时间相同,则仍按照p ij 值的降序排列加工顺序。计算时,不再单独考虑粒子在各维空间的信息,而是将编码矩阵P N ×S 整体作为搜索空间中的一个粒子,直接更新
粒子的速度和位置的整体信息。用V N ×S 、P rbest N ×S 、P gbest N ×S 分
别表示粒子的速度、局部极值和全局极值,则HFSP问题的速度和位置按式(8)和式(9)进行更新:
V N×S(t+1)=wV N×S(t)+c1rand1()(P rbest N×S-P N×S(t))+
c2rand2()(P gbest
N×S
-P N×S(t))(8) P N×S(t+1)=P N×S(t)+V N×S(t+1)(9) 在计算完成后进行一次修正,若矩阵元素p ij<1,则p ij=1.1;若p ij>M j+1,则p ij=M j+0.9,即可保证粒子的合法性。对于单个粒子而言,只需要一次数值迭代运算就可以更新完成其所有信息,能够充分利用PSO算法并行搜索能力。
3.3 多目标进化策略
通常进化算法用于多目标优化必须考虑两个问题[7]: (1)如何保证算法朝Pareto最优集的方向搜索;(2)为了避免未成熟收敛和获得均匀分布且范围最广的最优解,如何保持种群的多样性。
PSO算法基于所有粒子与全局最优粒子的信息共享,若采用多目标遗传算法的可变目标权重聚合策略分配适应度值,PSO算法容易收敛于非劣最优的局部区域。为了使算法朝各个目标最优解方向进化,采用基于Pareto支配关系的极值更新策略,实现向Pareto前沿高效搜索;同时,采用自适应递减惯性权重和对种群变异的方法来保持种群多样性。
3.3.1 极值更新策略
(1)局部极值的更新:第一代种群中的各粒子分别初始化其局部极值;在以后的每一代进化中,根据各目标方向上的适应度值Pareto支配关系来更新局部极值,若更新后的粒子支配其局部极值,则更新局部极值为该粒子的当前位置,否则其局部极值保持不变。
(2)全局极值更新:在每一代各粒子的局部极值更新完成后,计算每一个局部极值支配其它局部极值的数目,将支配其它局部极值最多的一个置为全局最优极值。
(3)各目标方向上最大适应度值更新:为了得到下文所提到的算法性能分析时的理想点Z3,需保存并更新各目标方向上出现的最大适应度值。更新方法为:在每一代各粒子适应度值更新完成后,若某个粒子i在目标方向q上的适应度值f q i大于f q max,则令f q max等于该值;否则,f q max保持不变。其中,Z3=(f1max,f2max,…,f Q max)。
3.3.2 种群多样性保持
为了避免算法早熟,收敛陷入局部最优,保证搜索到搜索空间中最广的Pareto最优解,在进化后期需增加个体差异。因此,本文采用自适应递减的方法动态调整惯性权重,并引入遗传算法中的变异算子,对SPSO算法进行改进。
惯性权重按照式(10)实现自适应递减动态调整:
w=w o-(g/gen)×k(10)其中,w o为初始惯性权重,g为当前进化代数,gen为最大进化代数,k为递减系数。
种群变异的实现方法如下:
变异规则:随机选择参与变异粒子的两行进行交换。
变异步骤:(1)判断粒子是否参与变异,若粒子适应度值同时满足式(11)和式(12)则参与变异,否则该粒子不参与变异;(2)对满足变异条件的粒子按照变异规则进行变异,用变异后的粒子替代变异前的粒子,更新种群。
f q i≤f q min+(f q max-f q min)/Mf(11)
F i≤F min+(F max-F min)/M F(12)其中,Mf和M F为变异因子,用于调整种群中参与变异的粒子的各目标方向和总的适应度值取值范围,根据不同问题设置为不同的数值。
3.4 Pareto最优解保留策略
3.4.1 Pareto最优解池更新策略
为了防止优化过程中的随机因素导致优秀个体的丢失,采取最优个体保留策略。为保留Pareto最优解,设置Pareto最优解池(简称Pareto解池),用于保存迭代中出现的Pareto最优解。实现方法如图1所示
。
图1 Pareto解池更新策略
在每一代粒子更新完成后,计算单个粒子在各个目标上的适应度值,更新Pareto解池。其更新原则为:(1)若该粒子支配Pareto解池中的某些粒子,则删除被支配的粒子,将该粒子加入解池;(2)若Pareto解池中有粒子支配该粒子,则忽略;(3)若该粒子与解池中的各个粒子互不支配,则将该粒子加入Pareto解池。
3.4.2 基于适应度拥挤度的聚类算法
对于复杂的多目标优化问题,若保留进化过程中出现的所有的Pareto最优解,会导致解池中出现大量的相似解,不仅影响解的分布性能,同时也会增加求解的内存开销和时间复杂性。为了保证Pareto解集的分布性能,同时降低算法的复杂性,根据HFSP的编码特性,本文提出了一种针对该类问题的聚类算法。设解池最大规模为Pnum,算法实现如下:
(1)若解池规模u>Pnum,以各目标方向上的适应度值作为空间坐标计算Pareto解池中两两粒子间的欧氏距离,记录在一个对角线元素全为0的下三角矩阵DS中。
(2)选择矩阵中数值最小的非0元素对应的两个点,在解池中删除其中的任意一个,调整解池大小,并将该元素在DS中所对应的行和列的所有元素均赋值为0。
(3)若解池规模u>Pnum转(2);否则,结束。
下三角矩阵如式(13)所示:
DS=
00 0
d210 (00)
d31d32 (00)
…………
d u1d u2…d uu0
(13)
其中,元素d ij表示粒子i与粒子j之间的距离。
该聚类算法避免了一般的聚类算法每合并两类都要计算一次所有两对类之间距离的缺陷,每一次调用该聚类算法,只需要计算一次解池中粒子两两间的距离,即可删除所有超出解池规模的拥挤粒子,降低了求解的复杂性。
3.5 算法流程
综上所述,基于HFSP问题的MOPSO算法的主要流
程如下:
Step1(设置初始参数) 初始惯性权重w o ,递减系数k ,认知系数c 1,社会系数c 2,进化代数gen ;目标维数Q ,种群规模popsize ,变异因子Mf 、M F ,解池规模Pnum ,机器品质矩阵E ,适应度系数k 0、k 1、k 2;种群初始化。
Step2(计算适应度值) 分别计算种群中所有粒子在各个目标方向上的适应度值;更新在各目标方向上的最大适应度值。
Step3(更新种群信息) (1)Pareto 解池信息更新:计算粒子间相互支配关系;调用聚类算法删除拥挤粒子;(2)更新全局极值和
各粒子的局部极值。
Step4(生成新种群) (1)分别更新种群中所有粒子的速度和位置;(2)读取种群中各粒子在各目标方向上的适应度值,根据变异规则对种群中的部分粒子进行变异;(3)根据(1)和(2)更新后的粒子生成下一代种群。
Step5(停止准则) 判断是否达到最大进化代数,若是,退出流程,输出Pareto 解池(最优解集);否则,转Step2。
3.6 适应度函数设计
算法在三个目标方向上的适应度函数分别设置如式(14)、式(15)和式(16)所示:
f 1=1/Max N
i =1(C iS )
(14)f 2=k 0-k 1(
∑S
j =1∑
M j k =1ΔT jk )(15)f 3=k 2(
∑S
j =1∑M j
k =1
N
kj
E jk )
(16)
其中
,f 1、f 2和f 3分别对应最小化流程时间、
最小化机器空闲时间和最大化高品质属性机器加工任务所对应的适应度函数;k 0、k 1和k 2为调节系数,用来调整三个目标方向上的适应度值在一个数量级,以便于度量Pareto 解池中个体间的距离。
3.7 算法性能分析
在有限进化代数内,得到的Pareto 最优解集不一定能和理论上的Pareto 最优解集重合。记第t 代Pareto 最优解集为E current (t ),理论Pareto 最优解集为E true 。为了度量算法的收敛速度,Veldhuizen 和Lamont 定义了多目标算法相对收敛进程指标[8]:
R P =ln
G 1/G t
(17)
其中,G 1表示E current (1)与E true 之间的距离,G t 表示E current (t )与E true 之间的距离,由于难以确定最终Pareto 最优解集E true ,因此采用理想点Z 3进行代替。
4 实验结果分析
为了验证本文MOPSO 算法求解HFSP 的有效性,选取文献[4]的汽车发动机厂调度实例(文献[4,5]研究了该实例以最小化最大完工时间为目标函数的单目标调度问题),结合本文的HFSP 多目标模型(记为P 1),在MA T 2
L AB 7.0下编写代码,进行仿真研究。
参数设置如下:w o =3.2,c 1=1.8,c 2=1.6,gen
=200,popsize =40,Mf =M F =2.0,Pnum =10,
Q =3,k =2.6,k 0=0.05,k 1=0.0005,k 2=0.001。
假定经过统计机器运转的历史数据,得到机器品质属性系数,如表1所示。
为验证算法性能,进行了大量实验,得到一组在算法进化终止时Pareto 解池中保留的粒子在各目标方向上的适应度值,如表2所示。
表1 机器品质属性系数表机器
品质
M 1
M 2M 3M 4M 5M 6M 7M 8M 9
0.80.20.80.90.50.10.90.80.3
表2 Pareto 解池粒子适应度值
粒子
目标1
目标2
目标3
10.03850.04750.047620.03700.04400.048230.03570.05000.048440.03450.04450.049750.03330.04950.051460.03030.04850.053070.02940.05000.054880.02440.04550.056990.02130.04850.055010
0.0208
0.0340
0.0582
从表2可以看出,目标方向1的适应度最大值达到0.0385,对应的最小流程时间为26,优于文献[4]的最小值29,达到了文献[5]的最小值26;目标2方向上的最大适应度值为0.05,对应的机器空转时间为0,也达到了最优值;目标方向3上的最大适应度值也取得了较优值。同时可以看出,Pareto 解池中的粒子间的距离比较均匀,较好地满足了分布性能,能有效地收敛于Pareto 最优前沿。
为了分析本文算法的收敛进程,选择多目标遗传算法(Multi 2Objective G enetic Algorithm ,MO GA )[7]对P 1进行比较实验,所得到的RP 值曲线分别如图2所示。
图2 相对收敛进程RP 值曲线
由图2可以看出,MOPSO 算法的收敛速度和收敛能力相比MO G A 算法有了较大的提高,尤其是在进化后期,由于有效地保持了种群多样性,其寻优能力有了明显的改善。
对于决策者来说,在很多时候需要均衡考虑各个目标,在Pareto 解池中选择一个满足偏好或折中的最优解来指导生产。对于汽车发动机厂调度实例,一个折衷考虑生产周期、设备空转时间和机器品质属性的Pareto 最优解(表3中的粒子5)所对应的问题的甘特图如图3所示。
由图3可见,该Pareto 最优解对应的最大流程时间仅为30;给品质属性系数较低的M 2和M 6分配了较轻的加工任务,而给M 4和M 7分配了较重的加工任务;同时,机器空闲的总时间仅为1个单位时间。虽然对单个目标而言,该Pareto 最优解并不是最好的解,但它使多个目标同
时得以优化,对于决策者来说是一个较为理想的解
。
图3 单个Pareto 最优解的调度甘特图
5 结束语
本文将缩短加工周期、减少设备空转时间和降低产品
次品率作为调度的目标函数,建立了HFSP 的多目标模型,并设计了求解多目标HFSP 问题的MOPSO 算法。仿真结果表明,本文的MOPSO 算法能够有效地向Pareto 最优前沿进化,求得的Pareto 最优解集满足良好的分布性能,算法具有较优的收敛能力,得到的解是符合实际应用问题的合理解。本文的模型和算法对于实际生产调度问题具有一定的理论价值和指导意义。
参考文献:
[1] 王万良,吴启迪.生产调度智能算法及其应用[M ].北京:科
学出版社,2007.
[2] Gupta J N D.Two 2Stage Hybrid Flow Shop Scheduling
Problem [J ].Asia 2Pacific Journal of Operational Research ,1988,39(4):3592364.
[3] Hentous H ,Benhammadi F.Heuristics Resolution of A Con 2
strained Hybrid Flow Shop Problem [C ]∥Proc of t he 11t h IEEE Symp on Computers and Communications ,2006:5322
535.
[4] 王万良,姚明海,吴云高,等.基于遗传算法的混合Flow 2
shop 调度方法[J ].系统仿真学报.2002,14(7):8632869.[5] 欧微,邹逢兴,高政.基于混合粒子群算法的柔性Flow 2
shop 调度方法研究[C ]∥第28届中国控制与决策会议,2008:9462951.
[6] Zhang L B ,Zhou C G ,Liu X H.Solving Multi 2Objective
Optimization Problems Using Particle Swarm Optimization [C]∥Proc of t he 2003Congress on Evolutionary Computa 2tion ,2003:240022405.
[7] 崔逊学.多目标进化算法及其应用[M ].北京:国防工业出
版社,2006.[8] Veldhuizen V ,Lamont G B.Evolutionary Computation and
Convergence to a Pareto Front [C ]∥Proc of Late Breaking Papers at t he Genetic Programming ,1998:2212228.
(上接第9页)
5 结束语
本文在阐述SHOIQ (D )的语法语义和Tableau 演算原
理的基础上,引入相关优化技术提高本体一致性检测推理效率,并给出评测。还进一步给出一致性检测的核心引擎算法并实现了一致性检测推理机。今后要实现对检测到的逻辑冲突自动给出诊断,进一步完善推理机。
参考文献:
[1] Borst W N.Construction of Engineering Ontologies for
Knowledge Sharing and Reuse :[Ph D Thesis][D ].Univer 2sity of Twente ,1997:11212.
[2] Baader F ,Horrocks I ,Sattler U.Description logics as On 2
tology Languages for t he Semantic Web[C]∥Fest schrift in Honor of J rg Siekmann ,2003:1292135.
[3] Horrocks I ,Patel 2Schneider P F.Reducing OWL Entailment
to Description Logic Satisfiability [C ]∥Proc of t he 2003Int ’l Semantic Web Conf ,2003:17229.
[4] Lutz C ,Sattler U ,Tendera L.The Complexity of Finite
Model Reasoning in Description Logics[J ].Information and Computation ,2005,199(122):1322171.
[5] Schmidt S ,Smolka.Atrributive Concept Descriptions wit h
Complement s[J Artificial Intelligence ,1991,48(1):1226.
[6] Kazakov Y ,Sattler U ,Zolin Z.How Many Legs Do I Have ?
[C]∥Non 2Simple Roles in Number Restrictions Revisited.L PAR ’07,2007:15219.
[7] Horrocks I ,Sattler U ,Tobies S.A PSPACE 2Algorit hm for
Deciding ALCNI R +Satisfiability [R ].Technical Report 98208,LuFg Theoretical Computer Science ,RW T H Aachen ,Germany ,1998:62273.
[8] Ding Y ,Haarslev V.Tableau Caching for Description Logics
wit h Inverse and Transitive Roles[C]∥Proc of Int ’l Work 2shop on Description Logics ,2006:1432149.
[9] Horrocks I ,Sattler U.A Description Logic wit h Transitive
and Inverse Roles and Role Hierarchies[J ].Journal of Logic and Computation ,1999,9(3):3852410.
[10] G limm B ,Horrocks I ,Lutz C ,et al.Conjunctive Query
Answering for t he Description Logic SHIQ[C]∥Proc of IJ 2CA I ’07,2007:3992404.
[11] Tsarkov D ,Horrocks I.FaCT ++Description Logic Rea 2
soner :System Description [C]∥Proc of IJ CAR ’06,2006:2922297.
[12] Horrocks I ,Sattler U.A Tableau Decision Procedure for
SHOIQ[J ].Automated Reasoning ,2007,39(3):2492176.
[13] Baader F ,Sert kaya B ,Turhan A https://www.doczj.com/doc/38149306.html,puting t he Least
Common Subsumer w.r.t.a Background Terminology[J ].Journal of Applied Logic ,2007,5(3):3922420.
[14] Hustadt U ,Motik B ,Sattler U.Data Complexity of Rea 2
soning in Very Expressive Description Logics[C ]∥Proc of I J CAI ’05,2005:4662471.
[15] Gardiner T ,Horrocks I ,Tsarkov D.Automated Bench 2
marking of Description Logic Reasoners [C ]∥Proc of t he PIWDL ’06,2006:1672174.
基本粒子群算法的原理和matlab程序 作者——niewei120（nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy和Eberhart提出，是一种通用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i ，p i=(p i1,p i2,....,p iQ)，i=1,2,3,....,n。所有粒子搜索到的最优值p g，p g=(p g1,p g2,....,p gQ)，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1]区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为1 。
学号： 姓名： 班级： 实验时间： 2011-10-10 实验编号 002 实验名称 作业调度算法 实验目的和 要求 通过对作业调度算法的模拟加深对作业概念和作业调度算法的理解 实验内容 （1） 模拟FCFS 算法实现作业调度 （2） 模拟短作业优先算法实现作业调度 模拟最高相应比优先算法实现作业调度 一、 实验题目 输入：作业流文件，其中存储的是一系列要执行的作业， 每个作业包括三个数据项： 作业号、作业进入系统的时间（用一小数表示，如10：10，表示成10.10）、估计执行时间（单位小时，以十进制表示） 参数用空格隔开，下面是示例： 1 8.00 0.5 2 8.15 0.3 3 8.30 0.25 4 8.35 0.20 5 8.45 0.15 6 9.00 0.10 7 9.20 0.05 其中调度时刻为最后一个作业到达系统的时间！ 输出：作业号 进入内存的时间，每行输出一个作业信息。 并输出每一种调度算法的平均周转时间和平均带权周转时间。 二、 算法设计思路 首先用一个switch 函数做界面选择进入哪一种算法。用一个内来定义作业 float s;//提交时间 float j;//执行时间 float k;//开始时间 float w;//完成时间 float z;//周转时间 float d;//带权周转时间 1， 先来先服务，首先计算第一个作业的完成时间，周转时间，带权周转时间。再用for 循 环来计算剩下每一个作业的完成时间，周转时间，带权周转时间。然后再算出平均周转时间和平均带权周转时间。 2， 短作业有优先，首先计算第一个作业的完成时间，周转时间，带权周转时间。再用来计 算其他作业的。其中在for 循环中嵌套while 函数，在每一次计算前判断处于等待状态 计算机操作系统 实验报告
处理器调度 选择题 当CPU执行操作系统代码时，则处理机处于( )。 A．执行态 B．目态 C．管态 D．就绪态 ( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 A．系统调用 B．操作系统 C．内核 D．特权指令 操作系统提供给程序员的接口是( )。 A．进程 B．系统调用 C．库函数 D．B和C 用户程序向系统提出使用外设的请求方式是( )。 A．作业申请 B．原语 C．系统调用 D．I／O指令 当作业正常完成进入完成状态时，操作系统( )。 A．将输出该作业的结果并删除内存中的作业 B．将收回该作业的所占资源并输出结果 C．将收回该作业的所占资源及输出结果，并删除该作业 D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 B．作业是比进程低一级的概念。 C．一个作业至少由一个进程组成。 D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B．响应时间C．等待调度时间D．运行时间 设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 A．T1+T2+T3 B．1／3(T1+T2+T3) C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A．中断时间 B．等待时间 C．周转时间 D．响应时间 设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 A．1 h B．5 h C．2．5 h D．8 h FCFS调度算法有利于( )。 A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A．对于长作业(进程)不利 B．未考虑作业(进程)的紧迫程度 C．不能有效降低作业(进程)的平均等待时间 D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 A．先来先服务调度算法B．短进程优先调度算法 C．优先权调度算法D．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
主函数源程序（main.m） %------基本粒子群优化算法（Particle Swarm Optimization）-----------%------名称：基本粒子群优化算法（PSO） %------作用：求解优化问题 %------说明：全局性，并行性，高效的群体智能算法 %------初始格式化--------------------------------------------------clear all; clc; format long; %------给定初始化条件---------------------------------------------- c1=1.4962;%学习因子1 c2=1.4962;%学习因子2 w=0.7298;%惯性权重 MaxDT=1000;%最大迭代次数 D=10;%搜索空间维数（未知数个数） N=40;%初始化群体个体数目 eps=10^(-6);%设置精度(在已知最小值时候用) %------初始化种群的个体(可以在这里限定位置和速度的范围)------------for i=1:N for j=1:D x(i,j)=randn;%随机初始化位置 v(i,j)=randn;%随机初始化速度 end end %------先计算各个粒子的适应度，并初始化Pi和Pg----------------------for i=1:N p(i)=fitness(x(i,:),D); y(i,:)=x(i,:); end pg=x(1,:);%Pg为全局最优 for i=2:N if fitness(x(i,:),D)
《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037
一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法
高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include
第二讲作业调度算法主讲教师：张新彩
3.2 作业调度算法 3.2.1 先来先服务算法 3.2.2 短作业 / 进程优先算法 3.2.3 优先级调度算法 3.2.4 高响应比优先调度算法
3.2.1 先来先服务算法 ?适用于作业调度 ?从后备作业队列中选择一个或多个最先进入的作业，将 它们调入内存，为它们分配资源、创建进程，然后放入 就绪队列。 ?适用于进程调度 ?从就绪进程队列中选择一个最先进入的进程，为之分配 处理机，使之投入运行；直到运行完成或阻塞，才会让 出处理机。
3.2.1 先来先服务算法 4 平均周转时间为（4+6+10+11+14）/5=9 作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。请用先来先服务算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。 作业 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间 A 4 B 1 3 C 2 5 D 3 2 E 4 4 4 7 12 14 1 2 2 5.5 0 4 7 12 4 6 10 11 18 3.5 14 14 简单易实现，有利于长作业，不利于短作业
3.2.2 短作业 / 进程优先算法 ?短作业优先（SJF） ?从后备队列中选择一个或多个估计运行时间最短的作业 调入内存。 ?短进程优先（SPF） ?从就绪队列中选出一个估计运行时间最短的进程，将处 理机分配给它，使它立即执行。
3.2.2 短作业 / 进程优先算法 6 平均周转时间为（4+3+8+9+16）/5=8 作业 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间 作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。请用短作业优先算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。 4 1 0 4 6 1. 5 4 3 9 8/3 6 8 13 9/4 9 9 18 16/5 13 16 D 3 2 B 1 3 E 4 4 C 2 5 A 0 4
粒子群算法程序 tic D=10;%粒子群中粒子的个数 %w=0.729;%w为惯性因子 wmin=1.2; wmax=1.4; c1=1.49445;%正常数，成为加速因子 c2=1.49445;%正常数，成为加速因子 Loop_max=50;%最大迭代次数 %初始化粒子群 for i=1:D X(i)=rand(1)*(-5-7)+7; V(i)=1; f1(i)=X(i)^2; f2(i)=(X(i)-2)^2; end Loop=1;%迭代计数器 while Loop<=Loop_max%循环终止条件 %对粒子群中的每个粒子进行评价 for i=1:D k1=find(1==Xv(i,:));%找出第一辆车配送的城市编号 nb1=size(k1,2);%计算第一辆车配送城市的个数 if nb1>0%判断第一辆车配送城市个数是否大于0，如果大于0则 a1=[Xr(i,k1(:))];%找出第一辆车配送城市顺序号 b1=sort(a1);%对找出第一辆车的顺序号进行排序 G1(i)=0;%初始化第一辆车的配送量 k51=[]; am=[]; for j1=1:nb1 am=find(b1(j1)==Xr(i,:)); k51(j1)=intersect(k1,am);%计算第一辆车配送城市的顺序号 G1(i)=G1(i)+g(k51(j1)+1);%计算第一辆车的配送量 end k61=[]; k61=[0,k51,0];%定义第一辆车的配送路径 L1(i)=0;%初始化第一辆车的配送路径长度 for k11=1:nb1+1 L1(i)=L1(i)+Distance(k61(k11)+1,k61(k11+1)+1);%计算第一辆车的配送路径长度end else%如果第一辆车配送的城市个数不大于0则 G1(i)=0;%第一辆车的配送量设为0 L1(i)=0;%第一辆车的配送路径长度设为0 end
基本粒子群算法的原理和matlab 程序 作者—— niewei120 （nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy 和 Eberhart 提出，是一种通 用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远， 那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i，p i=(p i1 ,p i2 ,....,p iQ )， i=1,2,3,....,n 。所有粒子搜索到的最优值p g， p g=(p g1 ,p g2,....,p gQ )，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为 2 。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1] 区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为 1 。
课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期：
目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13)
摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。
一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列
处理器调度习题
处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法
制造业车间作业计划与调度研究 车间作业计划（Production Activity Control，PAC）是依据主生产计划（MPS）而编制的具体执行工作方案，它把车间的生产任务落实到每个人、每台设备上，是车间组织生产的依据，也是企业管理中最重要的部分。PAC的实施贯穿于生产系统的各道工序，受很多因素的制约。随着生产规模的扩大和复杂程度的提高，PAC的实施与调度也出现了一些问题。本文应用车间作业调度方法，针对当前PAC与调度中存在的问题进行研究，为企业提供优化的生产作业排序和车间作业调度策略，从实践与理论方面提升PAC及其调度水平，以提高制造系统的运行效率，增强企业的市场竞争力。 PAC与车间调度的内涵与特点 PAC系统是一个高度复杂的系统，它有效地综合了机械、信息、网络等资源。制定PAC是为了使生产设备、物料、人员和信息四者匹配，实现车间均衡、协调、持续生产。在PAC生产执行过程中，决策部门需要根据车间的生产能力及其它资源的使用等反馈情况不断地调整PAC，而调整计划贯穿于企业生产活动的全过程。因此，要最大限度地发挥生产系统的柔性潜力，满足市场需求。 1.1 PAC与车间调度的界定与内涵 PAC的编制包括确定操作顺序、分配资源和制定期量标准等。PAC与车间调度问题是一个典型的任务集，包括资源集、约束条件集、性能指标集。其中，资源集包括人员、设备、工具和材料等，而每台设备可以完成一种或多种作业，不同设备能完成的作业集可能相同也可能不同；约束条件集用以规定生产过程中需要的条件，如任务的优先级、每个作业要求完成的时间、资源的能力、生产工艺、质量标准等；性能指标集用以规定生产过程中需要优化的目标，如生产周期、在制品量、订单交货期、资源利用率和生产成本等。每一个任务都包含一组需要执行的作业序列（工序），而这些作业序列需要占用系统的机器、工具等资源，并且必须按照一定的工艺顺序执行。 调度的目标是为作业合理分配资源，为每一个加工对象合理安排具体的加工顺序、路径、时间、制造设备资源和操作等，使内部和外部约束条件被满足，其中内部约束主要为企业的资源约束、能力约束和生产过程中的技术约束等；外部约束主要为订单规定的时间要求和品质要求等，同时使大部分生产性能指标得到优化。在有限产能、库存容量及资源的约束下，通过优化配置生产资源来提高PAC的可实施性以及生产过程的可计划性、可控性。而车间作业调度与控制则是实现生产高效率、高柔性和高可靠性的关键环节。 1.2 编制PAC的特点 在编制PAC过程中应考虑其如下特点： （1）实用性。以在制品加工进度为基础编制工序能力计划，使PAC紧跟生产现场，达到计划编制与生产节拍的和谐统一。PAC计划期短、计划内容具体、计划单位小等，具有可操作性强。 （2）合理性。综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素，通过合理地排程方法，达到满足交付和有效利用资源的目的。
操作系统》实验一实验报告 【实验题目】：先来先服务FCFS 和短作业优先SJF进程调度算法【实验目的】 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 【实验内容】 问题描述： 设计程序模拟进程的先来先服务FCFS 和短作业优先SJF 调度过程。假设有n个进程分别在T1, ?,T n时刻到达系统，它们需要的服务时间分别为S1, ?,S n。分别采用先来先服务FCFS和短作业优先SJF 进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n 个进程的平均周转时间和平均带权周转时间。 程序要求如下： 1）进程个数n；每个进程的到达时间T1, ?,T n 和服务时间S1, ?,S n；选择算法1-FCFS，2-SJF。 2）要求采用先来先服务FCFS 和短作业优先SJF分别调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间； 3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程 B 开始运行”等等；
4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间， 所有进程的平均周转时间，带权平均周转时间 【实验过程】 #include 粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置 第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。 粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。 . 题目先来先服务FCFS和短作业优先SJF进程调度算法 姓名： 学号： 专业： 学院： 指导教师：林若宁 二零一八年十一月 一、实验目的 模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法，以加深对进程的概念及进程调度算法的理解． 二、实验内容 1. 短作业优先调度算法原理 短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理 先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 三、程序设计 1.概要设计 程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；主函数流程：输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果 2.算法流程 SJF算法流程图： 3.详细设计 （1）定义一个结构体 typedef struct PCB { char job_id[10]; //作业ID float Arr_time; //到达时刻 float Fun_time; //估计运行时间 float Wait_time; //等待时间 float Start_time; //开始时刻 float Fin_time; //完成时刻 float Tur_time; //周转时间 float WTur_time; //带权周转时间 int Order; //优先标记 }list; （2）先来先服务算法函数 void fcfs(list *p,int count) //先来先服务算法{ list temp; //临时结构体变量int i; int j; //粒子群PSO算法 #include 操作系统上机测试作业调度算法算法 一、实验目的和要求（供参考） 1.掌握作业调度功能和调度程序常用算法。 2.掌握利用C语言设计实现不同调度策略的作业调度算法。 3.验证不同作业调度算法对性能的影响。 二、实验环境（供参考） 1.知识准备：学过进程管理、作业管理、处理机调度等章节的内容。 2.开发环境与工具： 硬件平台——个人计算机。 软件平台——C语言开发环境。 三、实验内容 用“先来先服务（FCFS）”算法和“最短作业优先（SJF）”算法模拟作业调度。 要求：按作业的到达顺序输入各作业需要的运行时间，按算法调度输出平均周转时间。 例如(FCFS)，输入：8（到达时间0），5（到达时间2），7（到达时间3），1（到达时间6）J1 J2 J3 J4 0 8 13 20 21 输出：aver=(8+(13-2)+(20-3)+(21-6))/4=51/4 例如(SJF)，输入：8（到达时间0），5（到达时间2），7（到达时间3），1（到达时间6）J1 J4 J2 J3 0 8 9 14 21 输出：aver=(8+(9-6)+(14-2)+(21-3))/4=42/4 注：输入的格式任意，只要输出平均周转时间即可。 四、代码（带注释） 1、先来先服务 实验结果（截图呈现） 代码： #include 实验二作业调度实验 一. 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。 二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 调度算法的流程图如下图所示。 三 . 实习题： 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 3、编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 可以参考课本中的例子自行设计。 三 . 实验过程： 1、编写并调试一个单道处理系统的作业等待模拟程序。 先来先服务（FCFS）： main.cpp: /* **先来先服作业调度算法模拟 */ #include 粒子群优化算法介绍及matlab程序
操作系统实验 FCFS和短作业优先SJF调度算法模拟
c语言实现的粒子群算法代码及解释
操作系统作业调度算法
各类作业调度算法
相关主题
文本预览