两机无等待流水车间调度问题与仿真

一、题目

两机无等待流水车间的调度与仿真

二、指导思想和目的要求

毕业设计（论文）是培养学生自学能力、综合应用能力、独立工作能力的重要教学实践环节。在毕业设计中，应独立承担一部分比较完整的工程技术设计任务。要求学生发挥主观能动性，积极性和创造性，在毕业设计中着重培养独立工作能力和分析解决问题的能力，严谨踏实的工作作风，理论联系实际，以严谨认真的科学态度，进行有创造性的工作，认真、按时完成任务。针对两机无等待流水车间调度问题, 提出目标函数最大完工时间最小化的快速算法, 并给出算法的复杂度.分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解.最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。

三、进度和要求

第一阶段：（共计5周）

第一周及第二周，翻译并完成教师指定的英文文献翻译； 

第三周及第五周，对所研究课题有个全面的了解。

第二阶段：（共计5周）

完成方案的提出，学习和用已知的方案方法进行实际问题的解决方案的提出和仿真。

第三阶段：（共计5周）

撰写论文及评阅。

四、主要参考书及参考资料

[1] S.M.Johnson.optimal Two-and Three-Stage Production Scheduling with Set-up Time Included[J]. Naval Research Logistics Quarterly.1954, 1:61-68

[2] Story A.E, Wagner H.M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,1963

[3] Gavett J.W.Three Heuristic Rules for Sequencing Jobs to a Single Production Facility[J].   Mgmt.Sci.1965,11:B166-176

[4] S.Panwalker,Wafik Iskander.A Survey of Scheduling[J].Ops.Res.1977, 25(1):45-61

[5] Stephen,C.Graves.A Review of Production Scheduling[J].Ops.res.1981,29（4）:646-675

[6] M.S.Fox.ISIS:A Retrospective Intelligent Scheduling.Intelligent Scheduling,Kaufmann, ed:Michael B.Morgan,1994:3-28

[7] B.Giffler,GL.Thompson.Algorithms for Solving Production Scheduling Problems[J].Ops   Res.1960,8:487-503

[8] 董海，梁迪．设施规划与物流分析．北京：机械工业出版社．2005

[9] Baker K R.A Comparative Study of Flow Shop Algonithms [J].Ops Res.1975(23）:62-73

[10] 王伟玲，马正元，王玉生．生产调度问题研究的动态与趋势[J]．管理技术，2005年第5期．

[11] 郑璐，顾鑫生，不确定条件下的零等待Flow Shop生产调度问题[J]．华东理工大学学报2004，30（2）：188-194．

[12] S.Panwalker, Wafik Iskander.A Survey of Scheduling[J].Ops.Res.1977, 25（1）:45-61.

[13] 谢源，谢剑英，郑小龙．混合有限月苏下带模糊交货期的单机调度问题的研究[J]．信息与控制2005，34（3）：369-372．  

[14] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer and Opreations. Research. 1986, 13:533-549.

[15] 卢冰原，陈华平，顾春生等，模糊环境下的柔性工作车间调度模型的研究[J]．运筹与管理．2004，13．

[16] 李福明，朱云龙，尹朝万等.基于遗传算法的模糊调度研究[J].信息与控制．2004，33（6）：703-708

[17] 吴仪，刘民等.JSSP基本约束特点分析及调度算法[J].清华大学学报(自然科学版)．2004，44(10)：

[18] Kinkpatric S, Gelatt CD, Vecchi M P.Operational by simulated annealing[J].Science.1983, 220:671-680.

[19] 吴梅，陆金桂.遗传算法的研究进展综述[J]．机床与液压．2008，36(3)．

[20] 孙卓明，余彬．遗传算法．计算机时代．2004年，第1期

[21] 陈国良等．遗传算法及应用．北京：人民邮电出版社，1996

两机无等待流水车间调度问题与仿真

摘    要

流水车间(Flow Shop)调度问题无论是在工厂经营管理还是在产品制造中都具有广泛的应用，因此对流水车间调度问题进行研究具有重大的理论意义和实际意义。

本文首先对车间调度问题国内外研究现状和发展趋势进行了系统的阐述。其次，对遗传算法的基本理论进行了详细的论述。然后对Flow Shop调度问题建立数学模型。再次，在掌握了遗传算法的基础之上给出了基于遗传算法求解Flow Shop调度问题的编码方案，遗传算子的设计。然后基于遗传算法对调度问题进行了实例分析。最后对上述两种调度的结果进行了分析，结果表明本文提出的方法是有效可行的。

关键词：生产调度，流水车间调度，遗传算法。

两机无等待流水车间调度问题与仿真

ABSTRACT

Flow Shop (Flow Shop) scheduling problem in both factory management and has wide application in the product manufacturing, so the study of Flow Shop scheduling problem is of great theoretical significance and practical significance.This article first to the workshop scheduling problem research status and development trend at home and abroad systematically in this paper.Secondly, the basic theory of genetic algorithm in detail in this paper.Then the Flow Shop scheduling problem to establish mathematical model.Again, in the mastery of the genetic algorithm based on genetic algorithm is given based on the Flow Shop scheduling problem of coding scheme, the design of genetic operators.Then based on the genetic algorithm for scheduling problems on the instance analysis.Finally, the results of the two kinds of scheduling are analyzed, the results show that the proposed method is effective and feasible.

Key words: production scheduling;Flow shop scheduling;Genetic algorithm;

两机无等待流水车间调度问题与仿真

目    录

摘    要I

ABSTRACTII

目    录III

第一章 绪    论1

1.1 引    言1

1.2 国内外车间调度问题的研究现状和存在的问题1

1.2.1 国内外车间调度问题的研究现状1

1.2.2 研究中存在的问题2

1.3 研究意义与目的3

1.4 本文的工作4

第二章 车间调度问题5

2.1. 车间调度问题的描述5

2.2 车间调度问题的特点6

2.3  车间调度问题的分类6

2.4  Job Shop 与Flow shop 比较7

2.5 调度问题的研究方法8

2.6 两机无等待流水车间调度13

2.6.1生产周期的计算13

2.6.2生产周期的快速算法14

第三章 遗传算法16

3.1 遗传算法的形成与发展16

3.2 遗传算法的基本思想17

3.3 遗传算法的特点17

3.4 遗传算法的过程和流程19

3.5 求解调度问题的遗传算法22

3.5.1 遗传算法的设计步骤22

3.5.2 编码方式22

3.5.3 适配值函数24

3.5.4 遗传算子的设计24

3.5.5 编码参数26

3.5.6 遗传算子26

3.5.7 算法的终止条件26

第四章 两机无等待流水车间调度问题仿真27

4.1 流水车间调度问题的描述与数学模型27

4.2 基于Johnson法则的两机无等待流水车间调度问题仿真28

4.3 遗传算法的设计31

4.3.1 编码方案31

4.3.2 群体的确定31

4.3.3 适应度函数31

4.3.4 遗传算子的设计31

4.4 基于遗传算法的两机无等待流水车间调度问题仿真32

4.5 结果分析32

第五章 全文总结33

参考文献34

致 谢36

毕业设计小结37