一种求解柔性作业车间调度问题的混合智能算法_武福
第5期2013年5月
组合机床与自动化加工技术
Modular Machine Tool ＆Automatic Manufacturing Technique
No．5May 2013
文章编号：1001－2265（2013）05－0130－04
收稿日期：2012－10－25
*基金项目：甘肃省自然科学基金（1112RJZA045）
作者简介：武福（1973—），男，甘肃人，兰州交通大学机电工程学院副教授，主要从事制造系统建模与优化调度的研究，
（E －mail ）wufu@mail．lzjtu．cn 。
一种求解柔性作业车间调度问题的混合智能算法
*
武
福1，2
张治娟
2
（1．甘肃省轨道交通装备系统动力学与可靠性重点实验室，兰州
730070；2．兰州交通大学机电工
程学院，兰州730070）
摘要：提出了一种将蚁群算法、遗传算法和粒子群算法优化融合的混合智能算法，并将其应用于解决多目标柔性作业车间调度问题。采用蚁群算法寻径生成初始群体，利用遗传算法进行调度路径的优化，利用粒子群算法对蚁群算法中的信息素进行优化，优势互补。最后通过仿真实例验证了该算法的可行性和有效性。
关键词：蚁群算法；多目标优化；柔性作业车间调度中图分类号：TH165；TG65文献标识码：A Research on Multi-objective Flexible Job-shop Scheduling Problem Based
on Hybrid Intelligence Algorithm
WU Fu 1，2
，ZHANG Zhi-juan 2
（1．Key-lab of System Dynamics and Reliability of Rail Transportation Equipment of Gansu Province ，
Lanzhou 730070，China ；2．Institute of Mech-Electronic Technology ，Lanzhou Jiaotong University ，
Lanzhou 730070，China ）
Abstract ：This paper proposed a hybrid intelligence algorithm to solve multi-objective flexible job-shop
scheduling that was based on the combination of ant colony algorithm ，genetic algorithm and particle swarm optimization．First ，it adopted ant colony algorithm to get a new population by routing．Second it made use of genetic algorithm to optimize the path ，the PSO algorithm to optimize the pheromone in ant colony algorithm．Finally ，it developed enough advantage of the three algorithms．The simulation results show that the algorithm is feasible and effective．Key words ：ant colony algorithm ；multi-objective optimization ；flexible job-shop scheduling
0引言
蚁群算法（Ant Colony Algorithm ）是意大利学者M．Dorigo 等人通过模拟自然界蚂蚁寻径的行为提的一种应用于组合优化问题的启发式搜索算法，它充分利用蚁群行为中所体现的正反馈机制进行求解，同时，利用分布并行计算方式在全局的多点进行解
的搜索［1］
。
遗传算法（GA ）是模拟自然界生物遗传机制的随机搜索算法，通过选择、交叉、变异等优化过程设计人工寻优方法，其特点在于容易与其他智能算法
相结合，形成更好的优化算法［2］
。
粒子群算法（PSO ）是由美国的Kennedy 和Eber-har 于1995年提出的基于群智能的进化类算法。该算法通过粒子在解空间追随最优粒子进行搜索，操
作简单，易于实现［3］
。
柔性调度问题是车间调度问题和并行机调度问
题的综合与推广，是强NP-hard 问题，其特征是某些
加性以及多目标性更能反映实际生产过程，其理论和方法具有更高的应用价值，目前柔性调度问题已经成调度研究得热点，受到了许多研究者的关注，取得了不少的研究成果。国内外许多学者曾用蚁群算法（ACO ）、遗传算法（GA ）、禁忌搜索算法（TS ）、粒子群算法（PSO ）等求解柔性作业车间调度问题，取得了
很好的效果
［1-4］
。目前国内对多目标柔性调度的研究相对较少，吴秀丽等［5］
进行了基于混合遗传算法的多目标优化方法的研究，遗传算法具有大范围的
全局搜索能力，
但对反馈信息利用不足，当解到一定程度时往往做大量无用的冗余迭代；蚁群算法具有反馈机制但收敛速度慢；PSO 算法收敛速度快，但不能保证得到最优解。针对以上各算法的优缺点，为
了使各种算法取长补短，提高算法寻优的效率，本文提出了将蚁群算法、遗传算法、PSO算法进行融合的混合智能算法，并将其应用于解决多目标柔性作业车间调度问题（flexible job-shop scheduling problem，FJSP）的求解。
1问题描述和模型的建立
FJSP问题可描述如下：假定一个加工系统有
m｛M
1，M
2
，…，Mm｝台机器和n｛J
1
，J
2
，…，Jn｝个工
件，每个工件包含K
i ｛K
i
=1，2，…，m｝道工序，记为
J i =｛O
i1
，O
i2
，…，O
iKi
｝。工件的加工顺序是确定的，
每道工序O
iKi
可以在多台不同的机床上加工。调度目标是合理地将每道工序安排到机器上，并对每台机器要加工的工序进行有效的排序，使加工系统的某些性能指标取得最优值（如最小制造周期、最大交货满意度、最低生产成本等）。
为了简化问题，我们先从完工时间、交货期、两个机床总负荷、最大负荷几个方面进行评价并建立如下的优化目标函数：
min f
1=min［max C
j
］（1）
min f
2=min［max|C
j
－d
j
|］（2）
min f
3
=min∑m
k=1∑n
j=1
∑n j
i=1
P
ijk
X
ijk
（3）
min f
4
=min max∑n
j=1∑n j
i=1
P
ijk
X
[]
ijk
（4）
其中，j=1，2，…，n；k=1，2，…，m；C
j 为工件J
i
的
完成时间；d
j 为工件J
i
的交货期；P
ijk
为工件的第i道
工序在第k台机器上加工所需要的时间；X
ijk
为决策
变量，表示工件J
i
的第i道工序是否在第k台机器上
加工；X
ijk =0表示未选中，X
ijk
=1表示选中。
同时根据调度模型给出的如下假设（约束）：①不考虑机床故障，工件运输时间计算在加工时间内；②每台机床每次只能处理一道工序；③工序一旦进入加工状态就必须完成，不可以中断；④不同工件的工序间没有先后顺序要求；⑤各工序在不同机床上的加工时间是预先给定的［5-12］。
2混合智能算法的优化原理
将车间作业调度问题描述为一个有向图［7］，图中边的属性（比如长度）代表该工序的加工时间，这样可将该加工时间的问题转化为路径规划问题。因此，为了提高收敛速度，本文提出了一种混合智能算法。首先利用蚁群算法寻找满足min｛C
max
｝的初始路径，然后利用遗传算法进行调度路径的优化，利用粒子群算法对蚁群算法中的信息素进行更新和调整，其中蚁群算法中下一节点选择及信息素调整是该算法的关键［1，4］。
2.1节点的选择
假设第i只蚂蚁在节点r，则按照下述规则选取下一个节点s：
s=
argmax｛［τ（r，u）］α?［η（r，u）］β｝u∈allowed
i
，
if q≥q
0 {S otherwise
（1）其中，τ（r，u）表示节点r到节点u间的信息素之量；η（r，s）表示节点r到节点s间的启发式因子；α、β分别表示加工路径上的信息量和启发式因子的权重；q
是［0 1］之间的单位分布的随机数；q
是满足0≤
q
≤1的常数；allowed i=｛0，1，2，…，n－1｝表示蚂蚁i允许选择的下一个所有节点。否则，按（2）式选择下一个节点。
P i（r，s）=
τ（r，s）α?η（r，s）β
∑
u∈allowed i
［τ（r，u）α?η（r，u）β］
s∈allowed
i
0{otherwise（2）2.2信息素的调整
2.2.1信息素的全局更新
每次迭代后，对全局最优加工路径按式（4）进行信息素调整，其余按式（5）进行调整。
τ（r，s）←（1－e）τ（r，s）+e?f k（4）
τ（r，s）←（1－e）τ（r，s）（5）其中，e表示信息素挥发程度，e∈（0，1）。
2.2．2利用PSO算法进行信息素的局部更新
为了进一步提高优化效果，在信息素更新中引入PSO算法［4］。如果第i只蚂蚁找到的路径满足目标函数的要求，则对该路径上的信息素进行局部调整，否则不调整。若没有局部更新，所有蚂蚁将在前一次最好加工路径的有限相邻区域内搜索。POS算法的作用是用来局部更新各蚂蚁所寻路径上的信息素，使较优路径上的信息素增加；最终使后续蚂蚁寻径时收敛于该路径。常见的惯性权值：
v
i
=w?v
i
+c
1
?random（）?（p
i
－x
i
）+
c
2
?random（）?（g－x
i
）（6）
x
i
=x
i
+v
i
（7）
其中，x
i
表示位置；v
i
表示速度；random（）为（0，1）之
间的随机数；c
1
，c
2
为学习因子，一般取c
1
=c
2
=2；w
为惯性权值，在0.7 0.9之间时算法性能最佳；p
i
表示个体最优粒子；g表示全局最优粒子。
2.3遗传算法的参数设置
2.3.1编码与适应度函数
遗传算法的一个显著特点是交替地在编码空间和解空间中工作，它在编码空间中对染色体进行遗传算法，在解空间进行评估和选择。
考虑到受工序的加工路线的约束，本算法中选择了基于工序的编码方式［5］，将调度编码为工序的序列，每个基因代表一道工序，给所有统一工件的工序制定相同的符号，然后根据它们在给定染色体中出现的顺序加以解释。
在该调度算法中，采用权重系数法计算个体的适应度，由于寻径有多种方案，而每种方案对各指标的满
·
131
·
2013年5月武福，等：一种求解柔性作业车间调度问题的混合智能算法
足程度不同，分别为每一种方案的各指标赋予随机权重，
然后线性相加，即为该方案的适应度函数。多目标柔性调度的适应度函数的计算过程如下［6］
：
u j （f （x ））=
∑t
i =1w i f i
（x ）
u （f （x ））=max t j =1
u j （f （x ））（8）
其中，
w i 为权重系数，t 为目标个数。2.3.2初始群体与染色体的选择
采用按改进后的蚁群算法搜索到的x 条路径，作
为初始群体，x 为群体规模，根据交叉、变异的概率。
采用轮盘赌法作为选择方法，选择准备交配的染色体。
2.3.3交叉和变异操作
由于该混合算法用染色体确定工序的优先权，然后用一次通过优先分配启发式算法产生活动调度，因此不要求双亲和后代中部分调度的工序顺序一致，故采用简单的单断点交叉法，随机产生一个断点，交换双亲上断点的右端，最后调整染色体，删除多余的基因，添加丢失的基因使产生的后代合法化。
变异采用基于邻域［6］
搜索的机理设计，以便产生改进的后代。具体操作方法为：首先随机产生3个不同
位置点，3个基因的全排列共生成6个新染色体，调用
评价函数评价染色体，用具有最高适应值个体取代群体中适应值较低的染色体。
3混合智能算法的实现
针对柔性作业车间调度多约束性、动态性以及
多目标性的特点，结合蚁群算法、遗传算法、
PSO 算法各自的优缺点，试图提出一种将以上三种算法进行融合的混合智能算法。该算法的流程图如下
：
图1混合智能算法流程图
4算例验证与分析
算法运行环境为Pentium 4，CPU 主频2.6GHz ，
256GB 内存，Windows XP 操作系统，并采用Visual Basic6.0编写。为验证本文算法的性能，分别采用两组仿真实验验证了算法的性能。4.1
仿真实验1
为了便于比较本算法的性能，首先选用文献［
2］中的算例进行研究。该算例为8个工件，6台机床，每
个工件的工序1 4个不等，共20个工序的柔性作业
车间调度。
参数设置为：循环次数1000，种群大小为100，蚂蚁数100，交叉概率0.05，α=4，β=2，c 1=c 2=2，w =0.8，w 1=0.4，w 2=0.5，运行10次，平均运
行时间为43.4（s ）。运行结果如表1所示（其中，
A ，
B ，
C 分别表示生产周期，最大负荷，机床总负荷）。表1中可以看出，本算法的生产周期目标A 的最优解为22，最优解平均值为23．9，其均优于文献［2］的24和248。
表1
算法运行结果
运行次数12345678910平均解目标值
A 2422242323242524252523.9B
22
23
23
22
24
23
22
22
21
23
20.1
C 112110108107104108109114110112109.4
4.2仿真实验2
为了进一步验证算法的有效性，采用混合智能
算法（ACO +GA +PSO ）对表2所示的三个标准测试
用例（8?8，10?10，15?10）进行求解，对每个测试
用例运行15次，
9次得到最优解．并与一些典型的优化算法求解结果进行对比，
比较结果如图2所示。进行比较的优化算法包括：混合粒子群算法（PSO +
SA ）［3，11］、改进遗传算法（IGA ）［4，11］
、粒子群禁忌搜
索算法（PSO +TS ）
［5，12］
。ACO +GA +PSO 算法（本文算法）主要参数：种群大小为100，
蚂蚁数为50，交叉概率为0.05，迭代次数为2000，α=4，β=2，
c 1=c 2=2，w =0.8，w 1=0.4，w 2=0.5。
表2
求解结果比较
算法问题（A /B /C ）8?810?1015?10IGA 14/77/127/43/612/91/11PSO +SA 15/75/127/44/612/91/11PSO +TS 14/77/127/43/611/93/11本文算法
13/78/12
6/45/5
9/97/9
从表中可以看出，对于每个标准用例，最小生产周
期目标比文献［3 5］中最好的结果降低了1 2个单
位，相应的性能也提高了约7% 18%；最大负荷目标
在8?8用例中和文献［3，4，6］中最好的结果持平，而
在其它两个用例中也分别降低了1 2个单位，性能也得到了相应的提高；但各用例的总负荷目标略微有所下降，比最好的指标高了3 6个单位，性能下降了约4% 6%。由此可见，提出的新的混合智能算法对求解多目标优化问题取得了良好的效果。
·
231·组合机床与自动化加工技术
第5期
5结论
本研究在蚁群算法的基础上提出了新的求解多目标柔性job-shop调度问题的混合智能算法。FJSP 与JSP的不同在于增加了机器选择这一环节，使得求解更加复杂，采用蚁群算法寻径生成初始群体，利用遗传算法进行调度的路径优化，利用粒子群算法对蚁群算法中的信息素进行优化，使算法能够快速跳出局部收敛，达到全局最优。经仿真比较，证明该算法是有效、可行的。这种将不同算法优势相结合的策略对于类似FJSP的组合优化问题，具有较好的求解效果，这也是未来发展和研究的方向之一。
［参考文献］
［1］刘志勇，吕文阁，谢庆华，等．应用改进蚁群算法求解柔性作业车间调度问题［J］．工业工程与管理，2010，15
（3）：115－119．
［2］白俊杰，王宁生，唐敦兵．一种求解多目标柔性作业车间调度的改进粒子群算法［J］．南京航空航天大学学报，2010，42（4）：447－453．
［3］袁坤，朱剑英．一种求解多目标柔性Job Shop调度的改进遗传算法［J］．中国机械工程，2007，18（2）：156－160．［4］吴秀丽，孙树栋，余建军，等．多目标柔性作业车间调度优化研究［J］．计算机集成制造系统，2006，12（5）：731－736．［5］ZHANG Guohui，SHAO Xinyu，LI Peigen，et al．An Effec-tive Hybrid Particle Swarm Optimization Algorithm for Multi-objective Flexible Job-shop Scheduling problem［J］．Com-puters and Industrial Engineering，2009，56（4）：1309－1318．［6］宋晓宇，朱云龙，尹朝万，等．应用混合蚁群算法求解模糊作业车间调度问题［J］．计算机集成制造系统，2007，13（1）：105－109，125．
［7］刘晓霞，谢里阳，陶泽，等．柔性作业车间多目标优化研究［J］．东北大学学报，2008，29（3）：362－365，382．［8］余琦玮，赵亮，潘双夏．基于遗传算法的柔性作业车间调度优化［J］．组合机床与自动化加工技术，2004（4）：34－
36．
［9］XIA Weijun，WU Zhiming．An Effective Hybrid Optimiza-tion Approach for Multi-objective Flexible Job-shop Schedu-ling Problems［J］．Computers and Industrial Engineering，2005，48（2）：409－425．
［10］ZHANG Guohui，SHAO Xinyu，LI Peigen，et al．An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-ob-
jective Flexible Job-shop Scheduling problem［J］．Comput-
ers and Industrial Engineering，2009，56（4）：1309－1318．［11］雷德明．现代制造系统智能调度技术及其应用［M］．北京：中国电力出版社，2011．
［12］刘民，吴澄．制造过程智能优化调度算法及其应用［M］．北京：国防工业出版社，2008．（编辑李秀敏）
（上接第127页
）
图5叶身数控加工刀路
表2叶身数控加工策略
工序工序名称加工策略Powermill主要参数设置
1
粗加工
叶身
偏置区域清除
模型
2
半精加
工叶身
偏置区域清除
模型
类型：初加工；转速1600r/
min；进给率：1200mm/min；
下切进给率：500mm/min；
行距：15mm；下切步距：1mm
4
精加工
叶身
曲面投影精加
工
5
精加工叶
身连接处
曲面精加工
类型：精加工；转速3000r/
min；进给率：800mm/min；下
切进给率：200mm/min；行
距：0.6mm；
（3）刀具路径过切、碰撞检查和自动加工仿真。
利用PowerMll的刀具路径“检查”功能对刀具路径进
行过切、碰撞检查。没有问题后，打开“Viewmill”工
具条进行加工仿真。
（4）生成叶身加工程序。对前面生成的刀具路
径选择机床系统文件进行后置处理，完成叶身自动
加工程序生成。
4结论
本文针对汽轮机叶片设计与加工中的难点，研
究提出了叶片设计与加工中CAD和CAM技术系统
化流程，给出了面向CAM技术的叶片数控加工工艺
和刀具轨迹生成策略，本文研究已运用于企业实际
生产，实现了产品设计和制造过程一体化，提高了叶
片设计制造精度，缩短了产品开发和制造时间，使汽
轮机叶片设计与加工技术迈上了一个新的台阶。
［参考文献］
［1］韩庆瑶，朱长月，乐英．基于Pro/E的汽轮机叶片造型及
数控编程研究［J］．汽轮机技术，2009，51（4）：312－314．
［2］邢健，付大鹏，郝德成．基于逆向工程的汽轮机叶片型面
CAD建模方法的研究［J］．机械设计与制造，2011（5）：
223－224．
［3］席光，吴广宽，郑健生．基于半径和角偏置的直纹面五坐
标加工刀位生成算法［J］．机械工程学报，2008，44（4）：
92－96．
［4］于源，贠敏，王小椿．汽轮机叶片五轴数控加工的一种实用
方法［J］．小型微型计算机系统，2002，23（10）：1278－1280．
［5］陈光明，张旭阳．汽轮机叶片的结构特点与数控加工技
术研究［J］．制造业自动化，2011，33（9）：93－98．
［6］洪如瑾．UG NX6CAD快速入门指导［M］．北京：清华大
学出版社，2009．
［7］朱克忆．PowerMILL数控加工自动编程经典实例［M］．
北京：机械工业出版社，2011．（编辑赵蓉）
·
331
·2013年5月武福，等：一种求解柔性作业车间调度问题的混合智能算法
(完整版)智能算法在柔性车间调度中的应用
智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。
柔性工作车间调度问题的多目标优化方法研究
第15卷第8期计算机集成制造系统 Vol.15No.82009年8月 Computer Integrated Manufacturing Systems Aug.2009 文章编号:1006-5911(2009)08-1592-07 收稿日期:2008207208;修订日期:2008209201。Received 08J uly 2008;accepted 01Sep.2008. 基金项目:国家863/CIMS 主题资助项目(2007AA04Z190,2008AA042301);国家自然科学基金资助项目(50835008,50875237)。Found ation i 2 tems :Project supported by t he National High 2Tech.R &D Program for CIMS ,China (No.2007AA04Z190,2008AA042301),and t he National Natural Science Foundation ,China (No.50835008,50875237). 作者简介:魏 巍(1982-),男,辽宁沈阳人,浙江大学CAD &CG 国家重点实验室博士研究生,主要从事产品配置优化、产品信息建模、多目标 优化和先进制造技术等研究。E 2mail :boyweiwei @https://www.wendangku.net/doc/ec11378790.html, ;+通信作者E 2mail :fyxtv @https://www.wendangku.net/doc/ec11378790.html, 。 柔性工作车间调度问题的多目标优化方法研究 魏 巍1,谭建荣1,冯毅雄+1,张 蕊2 (1.浙江大学流体传动及控制国家重点实验室,浙江 杭州 310027; 2.华晨金杯汽车有限公司,辽宁 沈阳 110044) 摘 要:针对各工件目标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多目标优化数学模型。针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto 进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto 综合最优解。最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题。 关键词:柔性车间调度;多目标优化;遗传算法;强度Pareto 进化算法中图分类号:TP278 文献标识码:A Multi 2objective optimization method research on flexible job shop scheduling problem W EI Wei 1 ,TA N J ian 2rong 1 ,F EN G Yi 2x iong +1 ,Z HA N G Rui 2 (1.State K ey Laboratory of Fluid Power T ransmission &C ontrol ,Zhejiang University ,Hangzhou 310027,China ; 2.Shenyang Brilliance J INB EI Automotive Corporation Limited.,Shenyang 110044,China ) Abstract :To solve the multi 2objective optimization problem in flexible job shop scheduling ,the multi 2objective sched 2uling optimization model ,namely the cost 、quality and term ,was constructed.While the traditional genetic algo 2rithm which combined random weigh could not solve the multi 2objective scheduling optimization problem commend 2ably.An improved strength Pareto evolutionary algorithm was employed to optimize the multi 2objective optimization model parallelly.As a result ,the optimal schema of flexible job shop scheduling was presented in the form of Pareto optimal sets.At last ,an instance related with the project in the air separation equip industry was given to prove that the proposed method could solve multi 2objective optimization problem in flexible job shop scheduling effectively.K ey w ords :flexible job shop scheduling ;multi 2objective optimization ;genetic algorithm ;SPEA2 0 引言 柔性作业车间调度问题(Flexible Job Shop Scheduling Problem ,FJ SP )是指带有机器可选柔性的车间调度问题。相对经典作业车间调度问题,FJ SP 突破了资源唯一性限制,每个工序可由多个不 同的机器完成,更加符合实际的生产环境。因此,研 究FJ SP 具有重要的理论价值和应用意义。 在处理FJ SP 问题上,文献[1]提出分布法,其基本思想是将机器分配问题和调度问题分开考虑,以降低FJ SP 问题的复杂性。文献[2]～文献[4]分别采用贪婪法、模拟退火算法和禁忌搜索法对FJ SP 问题进行优化求解。文献[5]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标
作业调度算法C++实现
学号： 姓名： 班级： 实验时间： 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 函数，在每一次计算前判断处于等待状态 计算机操作系统 实验报告
流水车间调度问题的研究-周杭超
流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品
混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==L L 。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。
作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
作业调度算法(先来先服务算法,短作业算法)
《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037
一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法
高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include
置换流水车间调度问题的MATLAB求解
物流运筹实务课程设计 题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解
目录 一、前言 (5) 二、问题描述 (6) 三、算法设计 (7) 四、实验结果 (15)
摘要 自从Johnson 1954年发表第一篇关于流水车间调度问题的文章以来．流水车间调度问题引起了许多学者的关注。安排合理有效的生产调度是生产活动能井然有序开展，生产资源得到最佳配置，运作过程简明流畅的有力保证。流水车间调度问题是许多实际流水线生产调度问题的简化模型。它无论是在离散制造工业还是在流程工业中都具有广泛的应用。因此，对进行研究具有重要的理论意义和工程价值。流水线调度问题中一个非常典型的问题，而置换流水线调度问题作为FSP问题的子问题，是一个著名的组合优化问题。该问题是一个典型的NP难问题，也是生产管理的核心内容。随着生产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此对其研究具有重要的
理论和现实意义。 关键字：流水车间，单件小批量生产，jsp模型，Matlab 前言 企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中,所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。车间生产计划与控制的核心理论是调度理论。车间调度问题是一类重要的组合优化问题。为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念。在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率。因此,研究成组技术下车间调度问题是很有必要的。生产调度，即对生产过程进行作业计划，是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心。置换流水车间调度问题是许多实际生产调度问题的简化模型。生产计划与调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。调度问题是组合优化问题，属于NP问题，难以用常规力一法求解。随着制造业的快速发展，大规模定制生产、全球化制造等思想的提出，使车间调度问题呈现出以下的新特点:约束条件多，时间复杂度高，空问复杂度高。这将导致在许多情况下，求解所建立的数学模型的快速性无法满
基于文化遗传算法求解柔性作业车间调度问题
第16卷第4期计算机集成制造系统 Vol.16No.42010年4月 Computer Integrated Manufacturing Systems Apr.2010 文章编号:1006-5911(2010)04-0861-06 收稿日期:2009204220;修订日期:2009209216。Received 20Apr.2009;accepted 16Sep.2009. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Found ation item :Project supported by t he National Natural Science Foundation , China (No.70771008,70371057). 作者简介:李铁克(1958-),男,吉林长春人,北京科技大学经济管理学院教授,博士生导师,主要从事先进制造管理、生产计划与调度、智能算 法等的研究。E 2mail :tiekeli @https://www.wendangku.net/doc/ec11378790.html, 。 基于文化遗传算法求解柔性作业车间调度问题 李铁克,王伟玲,张文学 (北京科技大学经济管理学院,北京 100083) 摘 要:在分析柔性作业车间调度问题特性的基础上,提出了一种采用主群体空间和信仰空间的双层进化结构的调度算法。该算法采用优良调度方案的知识信息构成信仰空间;提出一种二维矩阵的集成编码;基于工序顺序编码和基于机器分配编码的两种交叉和变异算子在主群体空间进行传统的遗传操作;通过具有自学习特点的相似性选择算子,使子代更好地继承父代的优良特征。通过典型算例的计算实验,表明算法在计算效率和求解质量上均具有较好的效果。 关键词:柔性作业车间调度;文化算法;遗传算法;选择算子中图分类号:TP301.6 文献标志码:A Solving flexible Job Shop scheduling problem based on cultural genetic algorithm L I Tie 2ke ,W A N G Wei 2ling ,Z HA N G Wen 2x ue (School of Economics &Management ,University of Science &Technology Beijing ,Beijing 100083,China )Abstract :Based on the analysis of the characteristics of Flexible Job Shop Scheduling (FJ SP )problem ,the double 2layer evolution scheduling algorithm with f rame population space and belief space to solve FJ SP was proposed.This algorithm adopted usef ul knowledge of excellent scheduling schemes to form belief space.A two 2dimensional matrix integrated coding was put forward.Traditional genetic operations were conducted in f rame population space among two effective crossover operators and mutation operators ,which were designed on the basis of the integration of ma 2chine assignment and operation sequence for the genetic algorithm.By selection operators with similar self 2learning char 2acteristics ,son 2generations inherited excellent characteristics from parent 2generations.Experimental results indicated that the proposed algorithm outperformed the current approaches in computation efficiency and solution quality.K ey w ords :flexible Job Shop scheduling ;cultural algorithm ;genetic algorithm ;selection operator 0 引言 柔性作业车间调度问题(Flexible Job 2shop Scheduling Problem ,FJ SP )是经典作业车间调度问题(Job 2shop Scheduling Problem ,J SP )的扩展[1]。在J SP 中,仅考虑工件具有唯一确定的加工工艺路线的情况。而在FJ SP 中,每道工序可以在多台机器上加工,工件具有可选择的加工路线,并且在不同机器上加工所需的时间不同,因此FJ SP 比J SP 更 接近实际制造环境,是实际生产中亟需解决的一类调度问题。 FJ SP 不仅需要确定工件的加工顺序,还要确定某道工序由哪台机器加工。因此,FJ SP 是比J SP 更为复杂的N P 2hard 问题,一般不存在有效的多项式算法[2]。现有的研究方法主要分为精确算法、启发式规则[3]和元启发式算法(如模拟退火、遗传算法(Genetic Algorit hm ,GA )等)[4]。其中精确算法无法对大规模FJ SP 进行有效求解;启发式规则求解
操作系统短作业优先调度算法
课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期：
目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13)
摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。
一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列
基于深度强化学习的柔性车间调度问题现代研究
基于深度强化学习的柔性车间调度问题现代研究 摘要本文针对多目标柔性作业车间调度问题进行研究，分别以机器总负荷和设备利用率为性能指标，建立了多目标柔性作业车间调度模型。由于传统的企业调度算法忽略了历史数据的价值，在实时事件发生后不能快速响应支持，同时为了迎合“智慧工厂”的趋势，提出了一种适用于柔性作业车间调度的深度强化学习方法，实现了从状态输入到行为输出的直接控制。最后，通过实验案例验证了该方法在解决多目标柔性作业车间调度问题的可行性和有效性。 关键词柔性作业车间调度；深度强化学习；状态编码；多智能体 前言 近年来，市场中定制化服务已经成为一种普遍需求，“随需应变”的理念得到了企业管理者的高度重视。柔性生产是指通过先进制造设备来实现多品种、小批量的生产方式，其主要优点是增强了制造企业的灵活性和应变能力，提高了设备利用率。柔性作业车间调度问题（Flexible job-shop problem，FJSP）是传统作业车间调度问题的重要扩展，是目前车间调度问题的研究热点。 与传统的作业车间调度问题相比，柔性作业车间调度问题减少了机器能力约束，是更为复杂的NP-hard问题。目前的相关研究主要集中在算法效率改进[1-3]、问题实际化[4-7]、优化目标扩展[8-10]三个方面。在柔性作业车间调度问题上一般采用两种方法求解：启发式方法和集成方法[11]。问题实际化的研究主要通过加入更多生产相关约束，使得问题模型更加贴近实际生产。许多学者在上述三个方面进行了深入的研究，但是他们对于企業过去的生产调度历史数据并没有进行关注，忽略了其价值。 随着“中国制造2025”的提出，智能制造成为推进该项战略的重要举措。智能制造包括了智能制造技术和智能制造系统。深度强化学习作为一种端对端的感知与控制系统，为构建智能化的生产调度系统提供了重要指导和有效支持。 本文针对柔性作业车间调度问题，以最小化机器总负荷和最大化设备利用率为目标。通过对生产状态的编码，将每个工件构建为一个智能体。采用多智能体Actor-Critic算法，使得工件智能体学习彼此协作，为求解多目标柔性作业车间调度问题提供一种智能化的方法。 1 多目标柔性作业车间优化建模 1.1 问题描述 nm的FJSP问题可以描述为：一个拥有m台机器的加工系统，加工处理n 个工件。其中每个工件包含一道或者多道工序，每道工序可以在一台或者多台机器上进行加工处理，且相对应的加工时间取决于所分配的机器能力。对于该类问
先来先服务和短作业优先调度算法
操作系统》实验一实验报告 【实验题目】：先来先服务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 . 题目先来先服务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; 流水车间调度问题的研究-周杭超 流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品 混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。 操作系统上机测试作业调度算法算法 一、实验目的和要求（供参考） 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 流水车间调度问题的研究 机械工程学院2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品 混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。操作系统实验 FCFS和短作业优先SJF调度算法模拟
流水车间调度问题的研究-周杭超
操作系统作业调度算法
流水车间调度问题的研究周杭超