求解作业车间调度问题的一种改进遗传算法
第10卷第8期计算机集成制造系统
Vol.10No.82004年8月Computer Integrated Manufacturing Systems Aug.2004
文章编号:1006-5911(2004)08-0966-05
求解作业车间调度问题的一种改进遗传算法
张超勇,饶运清,李培根,刘向军
收稿日期:2003-07-15;修订日期:2003-12-08。
基金项目:国家自然科学基金资助项目(50105006;50305008)。
作者简介:张超勇(1972-),男,江苏海门人,华中科技大学博士研究生,主要从事智能调度算法、网络化制造、敏捷供应链等研究。
E -mail:s uperbrave_2002@https://www.wendangku.net/doc/0116273798.html, 。
(华中科技大学机械科学与工程学院,湖北 武汉 430074)
摘 要:为克服传统遗传算法解决车间作业调度问题的局限性,综合遗传算法和局部搜索的优点,提出一种改进的遗传算法。为基于工序的编码提出了一种新的PO X 交叉算子。同时,为克服传统遗传算法在求解车间作业调度问题时的早熟收敛,设计了一种子代交替模式的交叉方式,并运用局部搜索改善交叉和变异后得到的调度解,将提出的改进遗传算法应用于M uth and T hompson 基准问题的实验运行,显示了该算法的有效性。
关键词:车间作业调度;遗传算法;交叉算子;局部搜索中图分类号:T P278 文献标识码:A
0 引言
为适应用户多样化和个性化的要求,现代生产方式也由大批量向中小批量和多品种生产转变,调度在这种生产方式中的作用显得更加重要。一般典型的Job -Shop 调度问题可描述为:假设n 个工件在m 台机器上加工,由于工件加工工艺的要求,每个工件使用机器的顺序及每道工序所花的时间给定,且1不同工件的工序之间没有顺序约束;o某一工序一旦开始加工就不能中断,每个机器在同一时刻只能加工一个工序;?机器不发生故障。调度的目标就是确定每个机器上工序的加工顺序和每个工序的开工时间,使完成所有工序所需的时间(makespan)最小。
Job -Shop 调度问题是NP -难组合优化问题[1],其研究的方向有两大类:精确算法和近似算法[2,3]
。精确算法主要包括分支定界法、基于析取图模型的枚举方法、混合整数规划模型和拉格朗日松弛法等。近似算法包括优先权规则调度算法、瓶颈转移启发式算法、邻域搜索算法和人工智能方法等。精确算法虽能保证得到全局最优解,但只能解
决小规模的调度问题,无法实际应用。近年来,用邻域搜索算法,如模拟退火算法(simulated anneal-ing)[4]、禁忌搜索算法(tabu search)[5]和遗传算法(Genetic Algorithms,GA)[6]等解决Job -Shop 调度
问题,亦倍受关注[7,8]。遗传算法具有全局搜索能力,但易早熟收敛,而局部搜索善于微调,但常陷于局部最优。本文提出的改进遗传算法,综合了遗传算法和局部搜索的优点,将遗传算法用于完成全局搜索和跳离局部最优,而将局部搜索用于微调。遗传算法中交叉算子是最重要的算子,它决定着遗传算法的全局收敛性,本文提出的基于工序编码的POX(precedence operation crossover)交叉,并将它与其他基于工序编码的交叉进行比较,证明该交叉方法的子代能较好地继承父代的优良特征。笔者在深入分析Job -Shop 问题的基础上,设计了一种子代交替模式的遗传算法,取得了良好的效果,其原理同样适用于其他组合优化问题。
1 改进遗传算法的实现
111 调度问题遗传编码
本文采用M ITS UO Gen 等人提出的基于工序
DOI ：10.13196/j.cims.2004.08.97.zhangchy.019
的编码方法,它具有解码和置换染色体后总能得到可行调度的优点[9,10],可完全避免不可行解。这种编码方法中每个工件的工序都用相应的工件序号表示,并根据在染色体中出现的次序加以编译。对于一个n个工件在m台机器加工的调度问题,其染色体由n@m个基因组成,每个工件序号只能在染色体中出现m次,从左到右扫描染色体,对于第k次出现的工件序号,表示该工件的第k道工序。
表13@3Job-Shop调度问题
工件
机器顺序加工时间
工序1工序2工序3工序1工序2工序3 j1123456
j2312564
j3231465
表23@3Jo b-Shop调度解
机器号工件顺序
m1123
m2132
m3213
例如,表1为一个3@3Job-Shop问题,设它的一个染色体为[211312332],其中1表示工件j1,2和3意义类似。染色体中的3个1表示工件j1的3个工序,此染色体对应的机器分配为[31 2231312],每台机器上的工件加工顺序(简称机器码)如表2。本文解码过程的算法是应用插入式贪婪解码算法[11],此算法是从第1道工序开始,按顺序将每道工序插入到对应机器上最早的空闲时段安排加工,以此方式,直到序列上所有工序都安排在最佳可行的地方。以上的解码过程能保证生成主动调度。基于工序编码的染色体与机器码可互相转换[12],虽然工序编码方法置换染色体后总能得到可行调度,但不同染色体可能对应同一机器码,即可能对应相同的调度解。本文用机器码可以转化对应的一种主动调度染色体,用于交叉和变异。基于工序编码方法的状态空间容量为(m@n)!/(n!)m。112遗传交叉算子的设计
交叉是遗传算法最关键的操作,决定遗传算法的全局搜索能力。遗传算法假定一个个体的适应度较好,那么基因链码中的某些相邻关系片段是好的,并且由这些链码所构成的其他个体的适应度也较好。在表现型(phenoty pe)空间显示的特征在基因型(的研究中发现:如果机床m上加工相邻工件i和j所得到的解的指标比较好,那么包含这一顺序i和j的其他很多解的指标也比较好。
为了在Job-Shop调度问题中成功地应用GA,设计交叉算子时最重要的就是子代对父代优良特征的继承性和子代的可行性。在其他编码方案中,曾有研究人员提出许多较好的交叉算子,如JOX[13] (the Job-based order crossover)、SXX[14](subse-quence exchange crossover)、PPX[15](precedence preservation crossover)、SPX[10](set-partition crossover)、GT crossover[16]、M ulti-Step Crossover[17]和LOX[18]等,其中基于机器编码的交叉算子JOX能很好地继承父代特征,但其产生的子代可能为不可行调度。虽然基于工序编码的交叉具有子代都是可行的这一优点,但在Job-Shop问题上的特性是每台机器上工序的次序,而基于工序的编码相邻染色体没有表现出此特性,于是许多文献[9~11]设计的基于工序编码的交叉很难继承父代的特征。通过研究JOX、SXX、SPX、PPX等交叉算子,本文提出一种运用于基于工序编码的新的交叉算子POX,它能够很好地继承父代优良特征并且子代总是可行的。在相同条件下,交叉算子POX能够得到比其他基于工序编码交叉算子更好的结果(见实验运行)。设父代m@n染色体Parent1和Par-ent2,POX产生Children1和Children2,POX交叉的具体流程如下:
步骤1随机划分工件集{1,2,3,,,n}为两个非空的子集J1和J2。
步骤2复制Parent1包含在J1的工件到Chil-dren1,Parent2包含在J1的工件到Children2,保留它们的位置。
步骤3复制Parent2包含在J2的工件到Chil-dren1,Parent1包含在J2的工件到Children2,保留它们的顺序。
图1说明了3@3调度问题的两个父代交叉过程。两个父代Parent1、Parent2交叉生成Children1染色体基因为[122213133],Children2染色体基因为[33122123]。可以看出经过POX交叉保留了工件2在机器上的位置,使子代继承父代每台机器上的工件次序。不同于JOX交叉,由于POX 交叉是基于工序编码,生成子代染色体无需运用GT方法将不可行调度强制转化为可行调度。
967
第8期张超勇等:求解作业车间调度问题的一种改进遗传算法
113 遗传变异算子的设计
本文采用一种基于邻域搜索的新型变异算子,它在局部范围内搜索改善子代的性能,具体结构如下[19]:
步骤1 设i =0。
步骤2 判断i [popsize @p m 是否成立(popsize 为种群规模,p m 为变异概率),如果成立,转步骤3,否则转步骤6。
步骤3 取变异染色体上K 个不同的基因,生成其排序的所有领域。
步骤4 评价所有领域的调度适应值,取其中的最佳个体。
步骤5 i =i +1。步骤6 结束。114 局部邻域搜索
局部邻域搜索是对遗传算法中经交叉和变异后的染色体进行微调,以改善解的质量,并将改善的特性传递到下一代中,加快遗传算法的收敛速度。本文运用的是基于关键路径邻域的局部搜索。关键路径是指从起点到终点最长的、加工中没有时间空闲的一条路径。在关键路径上,由从属于同一加工机床的最大数目的贴邻工序组成,且所含工序数不少于两个的工序序列叫工序块。若关键路径上的工序顺序没有改变,则Job -Shop 调度问题的目标makespan 不会减少,原因是原有关键路径仍然存在[4]。通过移动搜索缩短关键路径的方法有多种[2~20],本文采用的是基于工序块的快速邻域搜索
方式[5]
,其邻域结构如图2所示。局部邻域搜索的流程如下:
步骤1 确定目前解的关键路径和全部工序块,并设Updated=False 。
步骤2 对于关键路径的首尾工序块,仅交换块中最后(前)的两个工序,对中间块仅交换块中最前和最后的两个工序。如果移动改善了目标
makespan,则交换被接受,并设Updated=True,回步骤3 直到Updated=False 停止,取最好机器码,并将机器码转化为基于工序的编码。
115 Jo b -Shop 调度问题改进遗传算法的设计
本文提出的改进遗传算法的流程图如图3所示,改进遗传算法采用子代交替模式的交叉方式,两父代交叉n 次产生2n 个后代,选择父代中最优的一个和所有2n 个后代中最优的两染色体作为下一代,这样既能将最优染色体保留到下一代,又能保证子代的多样性。实验证明,与传统的遗传算法比较,应用子代交替模式的遗传算法所得到的调度解在收敛速度和质量上都有较大提高,并用局部邻域搜索进一步改善交叉和变异产生的子代解的质量。求解Job -Shop 调度问题的改进遗传算法流程如下:
步骤1 初始化产生P 个可行解,P 为种群规模。
步骤2 计算个体适应度,评价个体适应度值。步骤3 判断是否达到终止条件,若符合取最优个体为问题的解,结束算法运行;否则转步骤4。
步骤4 按赌轮选择策略选择下一代种群P 。步骤5a 按交叉概率p c 和POX 交叉n 次,从最优父代和所有后代中选择最优两染色体作为下一代。
步骤5b 按变异概率p m 和基于邻域搜索的新型变异算子,生成新子代个体。
步骤6 把交叉和变异子代进行局部搜索,产生新一代的种群,返回到步骤2。
2 计算实验结果
应用著名的Muth and Thompson .s(M T)基准问题[21]来测试改进的遗传算法。实验测试分两部分:第一部分检测POX 交叉的性能,通过比较POX 与其他基于工序编码交叉的结果来验证;第二部分通过与其他文献刊登的用遗传算法解(M T)基准问题结果的比较,验证本文所述遗传算法的有效性。实验采用Visual C++编写算法程序,运行计算机内存256M B,处理器为P4CPU1.6G 。
968计算机集成制造系统第10卷
为了检测POX 的性能,将交叉算子POX 与其他基于工序编码的交叉算子SPX [10]、PPX [15]、LOX 比较,除了交叉方式以外,其他条件都是相同的。采用子代交替模式的遗传算法,种群规模设为500,交叉次数为n =4,进化500代,交叉概率为0.8,实验为检验交叉性能排除了变异和局部搜索,故变异概率设为0。由于M T10@10比较典型和难度大,且已知其最优m akespan 是930,本文以M T10@10为测试数据来比较这三种交叉,每种交叉运行20次,具体结果如表3所示。从表3可以看出,POX 交叉最优解和平均解均优于其他三种交叉,这证明POX 比其他三种交叉更好地继承了父代的特征。
表3 几种交叉的比较结果
交叉方式最优解平均解平均时间/s
POX 942965.083SPX 962980.272PPX 9921006.785LOX
994
1011.2
78
为验证本文设计的遗传算法的有效性,与其他文献用遗传算法测试(M T)的结果进行了比较,这些方法包括GA /GT [22]、GA /MSX [17]等。具体遗传参数如下:交叉概率p c =0.8,交叉次数n =3次,变异概率p m =0.1,K =3,种群规模P =400,最大代数800,实验结果如表4所示。
表4 本文算法与其他算法性能的比较
对于较简单的M T 6@6问题,本文算法都在十几代以内收敛到最优解,而对于难度较大的M T10@10和M T20@5本文算法也得到最优解。从表4可以看出,本算法所得最优解比Gen 算法、P -GA 和GA /GT 要好,与著名的GA /MSX 算法解的质量相当。图4为算法MT10@10的收敛曲线,从图中可以看出,本文设计的改进遗传算法有较快的收敛速度。通过以上交叉和遗传算法实验结果不难看出,本文算法有更强的搜索能力。
3 结论
本文通过深入分析Job -Shop 调度问题的特性,为基于工序的编码提出了一种有效的POX 交叉算子,由于传统遗传算法在解Job -Shop 调度问题时不是很成功,笔者为Job -Shop 调度问题设计了一种子代交替模式的遗传算法,该算法能更好地继承父代的优良特征,其原理同样适用于其他组合优化问题,并运用局部搜索改善交叉和变异后的解。最后,将本文设计的改进遗传算法应用于Muth and Thompson .s 基准问题的实验运行,得到了较好的效果。参考文献:
[1] LENST R A J K,RINNOOY,KAN A H G,BRUCKER https://www.wendangku.net/doc/0116273798.html,-pl exity of machine scheduling problem [J ].Ann.Discr.M ath.,1997,(1):343-362.
[2] BLAZEWICZ J,DOM SCHKE W,PESCH E.The Job shop
scheduling probl em:conventional and new s olution techniques[J].of Research,1996,93(1):1-33.
M EERAN S.Deterministic Job -shop scheduling:
and futu re [J ].European Jou rnal of R esearch,2):390-434.
Van P,AARTS E,LENS TRA J K.Job shop
by s imul ated annealing [J ].Operations R esearch,1):113-125.
969
第8期张超勇等:求解作业车间调度问题的一种改进遗传算法
[5] NOWICKI E,SM UTNICKI C.A fast taboo search algorithm for
the Job shop probl em [J ].M anagement Science,1996,42(6):797-813.
[6] CARLIE R J,PINSON F.An algorithm for solving the Job -shop
probl em [J ].M anagement Science,1989,35(2):164-176.[7] R ODAM M ER F A,WHITE K P.A recent survey of production
schedul ing [J ].IEE E T rans.S M C,1988,18(6):841-851.[8] WANG Ling.Intelligent optimization algorithm s w ith appl ication
[M ].Beijing:T s inghua University Press ,2001(in Chinese).[王 凌.智能优化算法及其应用[M ].北京:清华大学出版社,2001.]
[9] M I TSOU G,YASUHIRO T,ERIKA K.Solving Job -shop
schedul ing problems by genetic algorithm [A].Proceedings of the 1995IEEE International Conference on System s ,M an,and Cy-bernetics [C ].Vancouver:Institute of Electrical and Electronics Engineers,1995.1577-1582.
[10] GUOYONG S ,HITOSHI IIM A,NOBUO S.A new encoding
s cheme for Job Shop p roblems by Genetic Al gorithm [A ].Pro-ceedings of the 35th Conference on Decision and Control [C ].Kobe,Japan,1996.4395-4400.
[11] CHEN Xiong,KONG Qingsheng,W U Qidi.Hybird algorithm
for Job -shop s cheduling problem [A ].Procceding of the 4th Congress on Intelligent Control and Automation[C ].S hanghai:East China Univ.of S&T Press,2002.1739-1743.
[12] BAKER K R.Introduction to sequencing and scheduling [M ].
New York:Wisely,1974.
[13] ISAO O,M AS AYUKI Y,SHIGENOBU K.A genetic al go-rithm for Job -shop scheduling problem s us ing Job -based order crossover[A ].Proc.of ICEC .96[C ].Japan:Nagoya Univ.,1996.547-552.
[14] KOBAYASHI S,ONO I,YAM AM URA M .An efficient genetic
algorithm for Job shop scheduling problems [EB /OL ].h ttp://w ww -ono.is .tokushima -u.ac.jp /member /isao /PDFs /ic-ga95.pdf,1995.
[15] BIERWI RTH C,M ATTFELDAND D,KOPFE R H.On per-mutation representations for scheduling problems [A ].In 4th PPS N[C ].Berlin:Springer,1996.156-160.
[16] YAM ADA T ,NAKANO R.A genetic algorithm appl icable to
large -scal e Job -shop problems [A ].In 2nd PPSN [C ].Am s -terdam:North Holland,1992.281-290.
[17] TAKESHI Y,RYOHEI N.A genetic algorithm with multi -step crossover for Job -s hop scheduling problems [A ].First IEE /IEEE In ternational Conference on Genetic Algorithms in Engineering Systems:Innovations and Applications (GALESIA .95)[C ].S heffield,UK:Inst.of Electrical Engineers,1995.146-151.
[18] FALKENNUER E.BOUFFOIX S.A genetic algorithm for Job
shop[A ].Proceedings of the 1991IEEE International Confer-ence on Robotics and Automation [C ].Sacramento,CA:IEEE Service Cen ter,1992.824-829.
[19] CHENG R.A study on genetic algorithm s -based optimal
scheduling tech niques [D ].PhD thesis,Tokyo Institute of Technol ogy,1997.
[20] VAESS ENS R J M ,AARTS E H L,LENST RA J K.Job shop
scheduling by local search [J ].INFOR M S Journal on Comput-ing,1996,8(3):302-317.
[21] M UTH J F,THOM PSON G L.Industrial schedul ing [M ].NJ :
Prentice -Hall,Englew ood Cliffs,1963.
[22] DAVIDOR Y,YAM ADA T,NAKANO R.The ecological
framew ork ii:Im proving GA performance at virtual ly zero cost [A ].In 5th ICGA [C ].Tokyo:Inst.of Electrical Engineers,1993.171-176.
An improved genetic algorithm for Job -Shop scheduling
ZHA NG Cha o -yong,RAO Y un -qing,L I Pei -g en,LIU Xiang -j un
(Sch.of Mechanical Sci.&Eng.,Huazhong Univ.of S &T,Wuhan 430074,China)
Received 15Jul.2003;accepted 08Dec.2003.
Found ation item:Proj ect sup ported b y the Nation al Natural Science Found ation,China (No.50105006,50305008).
A bstract:To overcome the limitations of traditio nal Genetic Alg orithm (GA)w hen solving the problem of job -shop scheduling,an improved GA was proposed by taking advantages of traditional GA and local search.A new crossover operator,Precedenc e Operation Crossover (POX),for operation -based representation w as created.To avoid premature convergence,which appeared in the course of solving job -shop scheduling by apply ing con-ventional GA.The concept of an improved generation alteration model w as introduced.After a schedule w as ob-tained,a local search heuristic was applied to improve the solution.Its efficiency was validated by applying im-proved GA to M uth and Thompson .s benchm ark problem.
Key words:job -shop scheduling;genetic algo rithm;crossover operator;local search
970计算机集成制造系统第10卷
基于遗传算法的车间调度算法
得分：_______ 南京林业大学 研究生课程论文 2011～2012学年第一学期 课程号：73327 课程名称：Matlab语言 论文题目：基于遗传算法的车间调度算法 学科专业：交通运输工程 学号：8113102 姓名：闫盖 任课教师：王一雄 二○一一年十二月
基于遗传算法的车间调度算法 【摘要】车间调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年，各种演化计算方法逐渐被引入到生产调度中，特别是遗传算法的应用。本文主要介绍了企业车间调度问题的遗传算法实现，通过Matlab 实现对遗传算法的编程，其仿真调度结果验证了遗传算法用于求解车间调度问题的可行性和有效性。 【关键词】遗传算法 车间调度 Matlab Flow-Shop scheduling based on genetic algorithm Abstract ：The Flow-Shop scheduling problem has the property of modeling complexity, computational complexity, dynamic multi-constraint and multi-targeted. In recent years a variety of evolutionary computation methods, in particular, the application of genetic algorithms has been gradually introduced into the production scheduling problem. This paper puts forward a method to design Flow-Shop by using genetic algorithm. Program about genetic algorithm designs by using Matlab, Simulation results of our experiment show the feasibility and effectiveness of genetic algorithm for solving Flow-Shop scheduling. Key words ：Genetic algorithm Flow-Shop scheduling Matlab 引言 生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。研究和解决好调度问题，能极大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年Johnson 发表第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法。其中，以遗传算法、模拟退火、禁忌搜索以及人工神经网络为代表的智能化优化技术迅速发展，用来解决流水车间调度问题，受到人们的普遍关注。遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，很多启发式混合方法都是在此基础上发展起来的。本文采用遗传算法进行求解。 1车间调度问题描述 车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源，提高企业经济效益的目的。车间调度问题从数学上可以描述为有n 个代加工的零件在m 台机器上加工，车间调度的数学模型如下： （1） 机器集},,{21m m m m M ，?=，j m 表示第j 台机器，j=1,2,…,m 。 （2） 零件集},,{21n p p p P ，?=，i p 表示第i 个零件，i=1,2,…,n 。 （3） 工序序列集},,{21n op op op OP ，?=，},,{21ik i i i op op op op ，?=表示零件i p 加工工序序列。 （4） 可选机器集},,{21ik i i op op op OPM ，?=,},,{21ijk ij ij ij op op op op ，?=表示零件 i p 加工工序j 可以选择的加工机器。
柔性工作车间调度问题的多目标优化方法研究
第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/0116273798.html, ;+通信作者E 2mail :fyxtv @https://www.wendangku.net/doc/0116273798.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]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标
数学建模--车间作业调度问题
一、二维背包问题 一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。 它的状态变量有两个因素:一个是重量，一个是体积。 二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。 模型： 11 1 max . ,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑
例题 码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表: 现求如何装载这四种货物使价值量最大。 1 1 1 max .,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 可用动态规划来解决 1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量， 2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段） 3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。 状态转移方程： 11k k k k k k k k S S a x R R b x ++=-=- ()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装 入前j 中货品的价值。（j=1,2,3,4）
流水线车间生产调度的遗传算法MATLAB源代码
流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand; end end
作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
基于文化遗传算法求解柔性作业车间调度问题
第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/0116273798.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 进行有效求解;启发式规则求解
基于深度强化学习的柔性车间调度问题现代研究
基于深度强化学习的柔性车间调度问题现代研究 摘要本文针对多目标柔性作业车间调度问题进行研究，分别以机器总负荷和设备利用率为性能指标，建立了多目标柔性作业车间调度模型。由于传统的企业调度算法忽略了历史数据的价值，在实时事件发生后不能快速响应支持，同时为了迎合“智慧工厂”的趋势，提出了一种适用于柔性作业车间调度的深度强化学习方法，实现了从状态输入到行为输出的直接控制。最后，通过实验案例验证了该方法在解决多目标柔性作业车间调度问题的可行性和有效性。 关键词柔性作业车间调度；深度强化学习；状态编码；多智能体 前言 近年来，市场中定制化服务已经成为一种普遍需求，“随需应变”的理念得到了企业管理者的高度重视。柔性生产是指通过先进制造设备来实现多品种、小批量的生产方式，其主要优点是增强了制造企业的灵活性和应变能力，提高了设备利用率。柔性作业车间调度问题（Flexible job-shop problem，FJSP）是传统作业车间调度问题的重要扩展，是目前车间调度问题的研究热点。 与传统的作业车间调度问题相比，柔性作业车间调度问题减少了机器能力约束，是更为复杂的NP-hard问题。目前的相关研究主要集中在算法效率改进[1-3]、问题实际化[4-7]、优化目标扩展[8-10]三个方面。在柔性作业车间调度问题上一般采用两种方法求解：启发式方法和集成方法[11]。问题实际化的研究主要通过加入更多生产相关约束，使得问题模型更加贴近实际生产。许多学者在上述三个方面进行了深入的研究，但是他们对于企業过去的生产调度历史数据并没有进行关注，忽略了其价值。 随着“中国制造2025”的提出，智能制造成为推进该项战略的重要举措。智能制造包括了智能制造技术和智能制造系统。深度强化学习作为一种端对端的感知与控制系统，为构建智能化的生产调度系统提供了重要指导和有效支持。 本文针对柔性作业车间调度问题，以最小化机器总负荷和最大化设备利用率为目标。通过对生产状态的编码，将每个工件构建为一个智能体。采用多智能体Actor-Critic算法，使得工件智能体学习彼此协作，为求解多目标柔性作业车间调度问题提供一种智能化的方法。 1 多目标柔性作业车间优化建模 1.1 问题描述 nm的FJSP问题可以描述为：一个拥有m台机器的加工系统，加工处理n 个工件。其中每个工件包含一道或者多道工序，每道工序可以在一台或者多台机器上进行加工处理，且相对应的加工时间取决于所分配的机器能力。对于该类问
求解作业车间调度问题的全局邻域搜索方法
第15卷第7期计算机集成制造系统 Vol.15No.72009年7月 Computer Integrated Manufacturing Systems July 2009 文章编号:1006-5911(2009)07-1383-06 收稿日期:2008 06 18;修订日期:2008 10 13。Received 18June 2008;accepted 13Oct.2008. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Fo undation item:Project supp orted by the National Natural Science Fundation, Ch ina(N o.70771008,70371057). 作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务的研 究。E mail:cuijs@manag https://www.wendangku.net/doc/0116273798.html, 。 求解作业车间调度问题的全局邻域搜索方法 崔健双,李铁克 (北京科技大学经济管理学院,北京 100083) 摘 要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmar k 问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。 关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:T P18 文献标识码:A Global neighborhood algorithm for Job Shop scheduling problem CUI J ian shuang,LI T ie ke (Scho ol of Economic M anag ement,U niversit y of Science &T echno lo gy Beijing,Beijing 100083,China)Abstract:T r aditional cr itical neighbor ho od alg or ithms fo r Jo b Shop scheduling problem w ere easily t rapped into local optimal and hardly to escape.T o deal w ith t his pro blem,a g lo bal neig hbo rhoo d swapping st rateg y wit h dynamic adapatability w as pr oposed.H ow ever,this new strateg y mig ht possibly induce infeasible so lutio ns.T hus,a new pr oposition concerning the neig hbor hood sw apping str ategy w as presented and pr ov ed,w hich could be used to v erify whether a neighbor ho od swapping w as accept able or not.Based on this g lo bal neig hbo rhoo d st rateg y,a new alg o r ithm w as develo ped and tested by a gr oup of benchmark instances.T he r esults indicated that the new algo rithm ob tained satisfactor y results both on solut ions quality and computat ion time. Key words:neig hbo rhoo d structur e;crit ical path;Job Sho p scheduling ;neighborho od sw apping;scheduling alg o rithms 0 引言 自从20世纪50年代以来,调度问题相关理论及其应用技术的研究已经发展成为一门重要的学科,从经典的单机调度、并行机调度、车间调度发展到后来的多目标调度、随机调度和模糊调度等内容。调度问题成为从事运筹学、人工智能学和应用数学等学科领域的学者们关注的焦点,相应的应用领域在不断地扩大。随着问题研究的深化,人们对解决 调度问题的难度有了进一步的认识,发展了关于调度算法的有效性和计算复杂性理论,并且证明出许多调度问题包括多数作业车间调度问题(Jo b Shop Scheduling Problem,JSP)都是NP 完备问题[1]。JSP 是利用一组有限资源对一批有限任务在满足给定约束条件下求解最优目标函数的一个复杂的组合优化问题,也是迄今为止人们研究最多、研究成果最丰富、但仍未得到根本解决的问题之一。事实表明,有些NP 完备问题存在有限时间内的可行解,
制造业车间作业计划与调度研究
制造业车间作业计划与调度研究 车间作业计划（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）合理性。综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素，通过合理地排程方法，达到满足交付和有效利用资源的目的。
基于遗传算法的流水车间调度问题
中文摘要 流水车间调度问题是研究多个工件在若干个机器上的加工次序的问题，有效的调度算法对企业提高生产效率有着重要作用。本文使用遗传算法求解流水车间调度问题，把一个染色体编码成若干个自然数，表示相应工件的排序权值；通过简单交换两个父代的若干相同位置的基因，产生能够继承父代优良特性的子代；并且采用均匀变异，更好地保持种群中的基因的多样性。实验表明，该方法能取得较好的效果。 关键字：遗传算法，流水车间调度方法，实数编码，基因链码，群体，适应度。
外文摘要 Abstract: Flow-shop scheduling problem study the problem the processing sequence of A plurality of workpieces on some working machine,and it makes good effects on proving production efficiency to the industries with effective methods.In the case,we deal with flow-shop scheduling problem using a algorithm,the Genetic Algorithm.There is a chromosome we've just coded into some natural numbers to represent the weight order of these workpieces; exchanging simply two fathers' places of some gene to produce new children that carried good feature on two fathers;we also use the Uniform Mutation,and it keeps its diversity of gene on the population.This experiment show this method can achieve good results. Key Words: Genetic Algorithm, Flow-shop scheduling problem，natural number coding，genic bar code,group，fitness.
02流水线车间生产调度的遗传算法MATLAB源代码
流水线车间生产调度的遗传算法MATLAB源代码n个任务在流水线上进行m个阶段的加工,每一阶段至少有一台机器且至少有一个阶段存在多台机器,并且同一阶段上各机器的处理性能相同,在每一阶段各任务均要完成一道工序,各任务的每道工序可以在相应阶段上的任意一台机器上加工,已知任务各道工序的处理时间,要求确定所有任务的排序以及每一阶段上机器的分配情况,使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA、m % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→ %-------------------------------------------------------------------------- % 输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵,存储m个工件n个工序的加工时间 % P 1×n的向量,n个工序中,每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中,各工件各工序的开始时刻,可根据它绘出甘特图 % Y2p 最优方案中,各工件各工序的结束时刻,可根据它绘出甘特图 % Y3p 最优方案中,各工件各工序使用的机器编号 % Xp 最优决策变量的值,决策变量就是一个实数编码的m×n矩阵 % LC1 收敛曲线1,各代最优个体适应值的记录 % LC2 收敛曲线2,各代群体平均适应值的记录 % 最后,程序还将绘出三副图片:两条收敛曲线图与甘特图(各工件的调度时序图) %第一步:变量初始化 [m,n]=size(T);%m就是总工件数,n就是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步:随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N
遗传算法在生产调度方面的应用
遗传算法在生产调度方面的应用 合肥工业大学吴磊（20080313）陈超峰（20080321）方振中（20080322）周超（20080332）王伦良（20080340） 摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。 关键词：生产调度生产调度方式遗传算法 1.遗传算法 遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。 1.1遗传算法的基本运算过程 选择：从当前种群中选出优良的个体作为父代个体。 对各染色体v k计算适合度eval（v k）；k=1,2,3，…，m 计算选择概率： 对各染色体v k ， P=eval（v k）/∑eval(v k) 交叉：对群体中的个体进行两两随即配对 对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点 对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。 变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。 2.生产调度 生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。 在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情
基于改进遗传算法的柔性作业车间调度
第39卷 第7期2007年7月 哈 尔 滨 工 业 大 学 学 报 J OURN AL OF HARBI N I NSTI T UTE OF TECHNOL OG Y Vo l 139N o 17Ju.l 2007 基于改进遗传算法的柔性作业车间调度 席卫东1,2 ,乔 兵1 ,朱剑英 1 (1.南京航空航天大学民航学院,南京210016,E 2m ai:l x wdn@j 163.co m;2.远东控股集团,江苏宜兴214257) 摘 要:应用遗传算法解决柔性作业车间调度问题,针对柔性作业车间问题的特点提出了一种新颖直观的双子串基因编码方法,并设计了独特的交叉和变异算子,从而取消了运用遗传算法求解作业车间问题时为使基因合法化而进行的基因修复和重建过程,仿真结果表明用该遗传算法解决柔性作业车间调度是有效的.关键词:柔性作业车间;遗传算法;作业车间调度中图分类号:TP18;TP 273 文献标识码:A 文章编号:0367-6234(2007)07-1151-03 A genetic a lgor ith m for flexi b le job shop schedu li ng based on t wo 2sub str i ng gene cod i ng m ethod XIW e i 2dong 1,2 ,Q I A O Bing 1 ,Z HU Jian 2ying 1 (1.The College of C i vil Avi atio n ,N an ji ng University of Aero nauti cs and Astronautics ,Nanji ng 210016,Ch i na ,E 2m a i:l x wdn@j 163.co m;2.F ar EastH oldi ng Gro up Co .,LTD ,Y i xi ng ,214257China) Abstr act :A novel genetic algorithm f or solvi n g flexi b le job shop scheduling prob le m is elaborated .An intui 2ti v e gene cod i n g method ,called t w o-substri n g gene cod i n g ,and a spec ial cross operator aswell as a mutation method are proposed .By doing tha,t the repa iring process to va lida te the schedu le gene is successf ully can 2ce lled .The co mputer si m u lations are carried out and the results are worked ou t to sho w the eff ecti v eness of the proposed a l g orithm.K ey w ord s :flexi b le j o b shop;genetic algorithm ;j o b shop schedu li n g 收稿日期:2005-04-29. 作者简介:席卫东(1967)),男,博士研究生; 朱剑英(1937)),男,教授博士生导师. 作业车间调度问题(JSSP :Job Shop Schedu 2li n g Prob le m )通常出现在工业制造环境中,为了完成一个作业,必须按顺序在若干台机器上处理一系列不同工序,并且同时有若干个作业需要完成,管理人员必须根据作业的生产方式和工艺要求设计一个调度表,以获得某种生产指标的最优化,如加工周期最短、设备利用率最高等. 在古典作业车间调度中约定,任一工序只能由指定的某台设备加工,而在柔性作业车间调度(FJSSP :Flexible JSSP)中,则允许工序由一个机床集合中的任意一台加工,这更符合实际的生产状况,调度的目的是将工序分配给各机床,并对各机床上的工序进行排序以使完成所有工序的时间最小化.FJSSP 比JSSP 更为复杂,因为FJSSP 不但 需要确定所有工序在所有机器上的安排,而且还要确定每一台机器上工序的序列. JSSP 已被证明为NP-hard 问题 [1] .由于它的 高度并行性和重要的实际意义,学者们对其进行了广泛的研究,并提出了许多算法.这些算法可以分为下面几类:启发式方法、人工智能方法、最优化方法和近似最优法 [2] .近年来,对于这类具有高度 并行性和复杂性的问题,学者们提出了一些非经典、非线性的求解方法,获得了很好的效果 [3] ,如神 经网络算法、模拟退火算法、遗传算法等.其中,由于遗传算法(GAs)良好的全局搜索性能、内在的并行处理能力及其在解决TSP 一类组合优化问题方面的成功应用,引起了JSS P 研究人员的重视,Gen and Cheng [4] 提供了一个很好的关于G As 应用于JSSP 研究的综述并提出了若干JSSP 遗传算法,但是对于应用G A s 解决FJSSP 却未做研究.基于上述分析,本文试图采用遗传算法来解决FJSSP .