摘 要

装配作业车间调度问题是典型的NP-hard问题，具有求解难度大、时间长并且难以求出最优解的特点，同时它又是企业在生产运作中亟待解决的问题。决定调度性能的关键因素是调度规则，因而高效的调度规则有利于提高装配作业车间调度的性能，降低生产成本，增加企业的经济效益。

为了构造高效的调度规则，本文提出了一种基于GEP的仿真优化方法：GEP算法作为优化组件是方法的核心，起到驱动作用；基于Plant Simulation软件的装配作业车间调度模型作为仿真组件起到辅助的作用。具体而言，GEP算法通过遗传操作不断产生新的CDR，仿真组件对这些CDR进行评价并返回适应度值，然后GEP再根据这些适应度值不断地更新迭代，选出更加优秀的CDR。在该方法中，一方面仿真组件通过仿真模型和参数的设置实现了对调度过程中不确定性和随机性的模拟，从而满足一定的动态调度要求；另一方面GEP不断地对调度规则进行优化，从而得到性能更加优秀的CDR。

最后，在Lateness和Deviation两种调度目标下，以 JDD和TWKR为比较对象，对CDR的调度目标值和稳定性进行分析。实验结果表明，在这两种调度目标下CDR都要比JDD和TWKR具有更好的调度性能。

关键词：装配作业车间调度；GEP；仿真优化方法；调度规则

Abstract

Assembly Job Shop Scheduling Problem is a typical NP-hard problem. It is difficult to solve and find the optimal solution. At the same time, it is an urgent problem for enterprises to solve in the production and operation. The critical factor that determines the scheduling performance is scheduling rules. Therefore, effective scheduling rules are beneficial to improve the performance of assembly job shop scheduling, reduce production costs, and increase the economic efficiency of enterprises.

In order to construct efficient scheduling rules, a GEP-based simulation-optimization approach is proposed in this paper: GEP algorithm is the core of the method as an optimization component and plays a driving role; the assembly job scheduling model based on Plant Simulation software is used as a simulation component to assist the role. Specifically, the GEP algorithm continuously generates new Composite Dispatching Rules by genetic manipulation. The simulation component evaluates these CDRs and returns the fitness value. Then, the GEP continuously updates them according to these fitness values ​​to select a more excellent CDR. In this method, on the one hand, the simulation component realizes the simulation of the uncertainty and randomness in the scheduling process through the setting of simulation models and parameters, so as to satisfy the requirements of dynamic scheduling; on the other hand, GEP continuously optimizes the scheduling rules, resulting in better performance CDR.

Finally, under the two scheduling objectives of Lateness and Deviation, JDD and TWKR are compared to analyze the CDR's scheduling target value and stability. Experimental results show that the CDR has better scheduling performance than JDD and TWKR under these two scheduling objectives.

Key Words：Assembly Job Shop Scheduling；GEP；simulation-optimization approach；scheduling rule

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 研究目的及意义 2

1.2.1 研究目的 2

1.2.2 研究意义 2

1.3 研究现状综述 2

1.3.1 作业车间调度问题的研究现状 2

1.3.2装配作业车间调度问题的研究现状 4

1.4 本文的主要工作和结构 4

第2章 GEP原理及程序设计 6

2.1 GEP原理 6

2.1.1 GA与GP算法简介 6

2.1.2GEP与GA和GP的关系 6

2.1.3 GEP的基本流程 7

2.1.4 染色体的结构 8

2.1.5 GEP的遗传操作 11

2.2 GEP的程序设计 13

2.2.1运行环境 13

2.2.2 GEP的程序设计 13

2.3本章小结 16

第3章 基于GEP的装配作业车间调度问题研究框架 17

3.1引言 17

3.2 装配作业车间调度问题概述 17

3.2.1 装配作业车间调度问题简介 17

3.2.2 装配作业车间调度问题的特性 18

3.2.3 装配作业车间调度问题的性能指标 18

3.3 基于GEP的装配作业车间调度问题的研究框架 19

3.3.1仿真优化方法 19

3.3.2基于GEP的装配作业车间调度问题的研究框架 19

3.3 本章小结 20

第4章 基于GEP的装配作业车间调度问题研究 21

4.1引言 21

4.2 装配作业车间调度问题描述 21

4.3 模型构建与参数设计 22

4.3.1模型构建 23

4.3.2参数设计 24

4.4 实验结果分析 25

4.4.1目标分析 25

4.4.2稳定性分析 27

4.4.3GEP构造的CDR分析 28

4.5经济性与环保性分析 29

4.5.1经济性分析 29

4.5.2环保性分析 29

4.6 本章小结 30

第5章 总结与展望 31

5.1 工作总结 31

5.2 工作展望 31

参考文献 33

致谢 36

第1章 绪论

1.1 研究背景

现实生活中的许多组合优化问题（Combinatorial Optimization Problem，COP）本质上是NP-hard问题，例如物流、运输、生产、医疗保健、金融，电信和计算应用等^[1]。这些组合优化问题通常规模庞大并且需要在短时间内获得高质量的解，因而寻找高效的求解方法一直是研究者们努力的方向。

作业车间调度问题（Job Shop Scheduling Problem, JSSP）是组合优化领域内研究的热点问题，同时它又是典型的NP-hard问题，具有求解难度大、求解时间长并且难以求出最优解的特点。因此，以经典运筹学方法为代表的最优化算法已经难以解决此类问题，人们越来越来关注于采用基于启发式和元启发式算法的近似算法来求得多项式时间内的近优解。启发式和元启发式算法不同于严格数学意义上的最优化算法，它是人们凭借直观或经验构造的一类算法。这类算法能够在可接受的时间成本内求出问题的满意解，从而为人们求解作业车间调度问题提供了有效的途径。

装配作业车间调度问题（Assembly Job Shop Scheduling Problem, AJSSP）是一类特殊的作业车间调度问题，它在作业车间调度问题的基础上增加了装配工序，使得一些工序之间产生了相互影响和约束，因而更加的独特和复杂。决定车间调度性能的关键因素是调度规则，并且目前缺少针对装配作业车间调度问题特点而开发的调度规则，因此开发出一种更加高效的适合装配作业特性的调度规则具有重要的意义。但是由于装配作业车间调度问题的复杂性，人工开发调度规则必然存在时间和经验上的局限性，因此利用元启发式的进化算法自动构造调度规则是目前最为有效的方法^[2]。

遗传算法（Genetic Algorithm, GA）是一种成熟的进化算法，它在处理复杂组合优化问题时具有天然的优势，已经被广泛地应用到作业车间调度问题的研究中并取得了良好的效果。然而同时GA也存在着表达能力有限、学习能力不强、适用性不广的问题。为了克服GA因染色体结构导致的不足，以及能更加方便地处理树形程序，Cramer 于1985年提出了遗传编程算法（Genetic Programming，GP），1992年Koza^[3]对其进行了改进。GP采用不同形状和大小的解析树来代表个体，这些解析树拥有更加丰富的组成元素及结构，因而能够解决更为复杂的问题。然而，GP依然需要解决一些问题，例如它仍然没有实现基因型和表现型的分离，在进化后期会因为代码膨胀而降低算法速度等。

基因表达式编程（Gene Expression Programming, GEP）是2001年由葡萄牙学者Ferreira^[4]提出的一种新的进化算法。GA的优势在于简单的编码方式，它采用定长线性的字符串编码来表述问题，降低了编码难度并获得了较快的运算速度，但也存在着表达能力弱的缺陷。GP的优点在于拥有其丰富的表达体系。GP采用树形编码，一方面增加了其灵活性并增强了其表达能力；但另一方面也大大增加了编码难度，并且降低了算法的运行速度。GA和GP之所以都存在着一些自身无法克服的缺陷，本质上是因为他们没有成功地实现基因型和表现型的分离。当染色体既是遗传信息又直接是问题的解时，就会产生编码难度和表达能力之间无法调和的矛盾。GEP继承了GA和GP的优点，同时克服了两者的缺陷，实现了基因型和表现型的分离，因而在运算速度上比GA和GP提高了100~60000倍^[5-6]。

GEP在经过十几年的发展之后已经趋于成熟，并得到了广泛的应用。对于作业车间调度问题，GEP同样表现不凡。聂黎^[3]将GEP应用于动态作业车间调度问题，他的研究表明GEP的运行速度更快，学习时间最小只是GP的27.90%；同时，利用GEP构造的调度规则稳定性好、鲁棒性高，在各种加工条件和调度目标下具有与GP相当的水平，与简单派工法则相比具有明显优势。尽管利用GEP求解作业车间调度问题的前景广阔，但是迄今为止此类研究的数量依然很少，并且对于本文所研究的装配作业车间调度问题，大多数研究者采用的是仿真的方法^[7-11]，GEP算法的应用还是空白。因此，本文提出将GEP应用于装配作业车间调度问题具有重要的理论价值和现实意义。

1.2 研究目的及意义

1.2.1 研究目的

当前，对作业车间调度问题的研究较多并且取得了不小的成果，特别是GEP的成功应用为装配作业车间调度问题的研究开辟了新的途径。然而，对于特殊的装配作业车间调度问题的研究却依然存在不足且数量较少。因此，本文的研究力求达到以下目标：

一是根据装配作业车间调度问题的特点，提出基于GEP的仿真优化方法和装配作业车间调度问题的研究框架；二是在最小化平均拖期（Lateness）和最小化平均交货期偏差（Deviation）两种目标函数下，利用GEP自动地构造出复合调度规则（Composite Dispatching Rules, CDR），并通过仿真实验验证其性能相对于JDD和TWKR等简单调度规则（Simple Dispatching Rules, SDR）是否有显著地提升。

1.2.2 研究意义

装配作业车间调度问题不同于一般的作业车间调度问题，主要区别在于前者还要考虑装配工序之间的协调和约束。一些简单的调度规则已经被证明在求解装配作业车间调度时具有良好的性能，如NUP^[12]和TWKR^[13]。然而由于这些简单调度规则是基于人们直观和经验的产物，必然存在时间和经验上的局限，因此如果能构造出更加高效且适合装配作业车间特点的复合调度规则，就能进一步地提高装配作业车间调度的性能。本文利用GEP算法构造复合调度规则来求解装配作业车间调度问题，有利于提高企业的装配作业效率，从而提升企业的经济效益。

1.3 研究现状综述

1.3.1 作业车间调度问题的研究现状

作业车间调度问题由于其广泛的代表性和实用性，几十年来一直是研究的热点。然而，作业车间调度问题作为及其复杂的组合优化问题，至今仍没有形成完整的理论和方法。一般地，作业车间调度问题的求解算法可以分为两类：(i)最优化算法；(ii)近似算法。

研究初期，学者们尝试利用最优化算法来求解作业车间调度问题。最优化算法是指能够求出最优解的算法，如分支定界法和动态规划法等经典运筹学方法。从本质上来说最优化算法是一种穷举搜索算法^[14]，所以它一定能够求出最优解。但是当问题规模较大时，想要搜索完整个解空间就需要花费大量的时间。作业车间调度问题作为极其复杂的组合优化问题，其解空间的规模非常大，这时最优化算法的求解时间几乎是难以想象的。

随着计算机技术的发展，以启发式算法和元启发式算法为代表的近似算法的提出让作业车间调度问题的求解效果得到了极大地改善。近似算法的目标并不是求出最优解，其致力于在较短的时间内求出问题的满意解，来更好地解决实际生活中的复杂组合优化问题。下面将对一些近似算法在作业车间调度问题中的应用情况作简要说明。

（1）启发式算法

Jackson^[15]和Smith^[16]提出了最早的基于启发式算法的优先分配规则；Foo Y P S; Takefuji 和T^[17]将神经网络应用于车间调度问题并取得了较好的效果。1999年，杨圣祥和汪定伟^[18]对此进行改进，他们提出了一种自适应神经网络和启发式算法结合的混合算法。该算法首先通过自适应神经网络求出问题的可行解，再利用启发式算法来增强神经网络的性能并提高可行解的质量。庄艺锋^[19]提出了另一种将自适应神经网络与遗传算法相结合的混合算法，该混合算法的性能相比单一的神经网络或遗传算法都有明显的改善。王秀萍^[20]利用一种基于工件优先选择和机器分配的启发式算法来求解作业车间调度问题。苏子林、车忠志^[21]等提出了一种基于组合优先规则的启发式算法，该算法通过随机调整多个调度目标所占的比例来产生高质量的调度规则。

（2）元启发式算法

王万良等^[22]提出用一种改进的自适应遗传算法来求解作业车间调度问题；张国辉、高亮等^[23]采用改进的遗传算法求解柔性作业车间调度问题。费红霞^[24]等将改进的GEP算法应用于作业车间调度问题。李俊^[25]等提出了一种改进模拟退火算法并将其应用于柔性作业车间调度问题。王云、冯毅雄^[26]等进行了基于多目标粒子群算法的柔性作业车间调度的优化方法研究。该算法采用精英保留策略和个体密集距离降序排列策略来选择优秀个体，并在进化过程中引入变异机制来提高种群的多样性。宋晓宇^[27]等提出将禁忌搜索算法与蚁群算法相结合的混合算法的应用于模糊作业车间调度问题，利用禁忌搜索算法较强的局部搜索能力来缩短蚁群算法的求解时间并提高解的质量，实验结果表明该算法的解的质量得到明显的改善。梁旭和黄明^[28]针对作业车间调度问题提出了一种禁忌-并行遗传算法。该算法能够避免自身过早收敛，从而有利于实现全局最优；同时得益于禁忌搜索算法强大的搜索能力，并行遗传算法的运行速度和解的质量都得到了改善。

1.3.2装配作业车间调度问题的研究现状

当前，对装配作业车间调度问题的研究仍然较少，且以仿真方法的应用居多。

S. Thiagarajan和C. Rajendran^[7]利用仿真实验对装配作业车间调度问题进行了研究，他们以最小化提前、延后惩罚和持有成本的加权总成本为调度目标，通过仿真实验对多个基于SDR的组合规则进行检验和优化，得到的调度规则有利于减少总成本的平均值和最大值。K. Natarajan^[8]等提出一种优先调度规则来求解多层级的装配作业车间调度问题，该调度规则被用来减小持有成本和拖期惩罚。Nabil R.和Adam^[9]等提出了一类优先调度规则来求解多层级装配作业车间调度问题，该规则旨在缩短交货周期。他们认为交货周期由流程时间和延迟时间构成，为了缩短交货周期，先构造出基于延迟时间的调度规则，再将该规则与基于流程时间的规则进行结合，得到的组合规则有利于缩短交货周期。G. Huang和Haili Lu^[29]研究了双层组合调度规则在装配作业车间调度问题中的应用。他们使用仿真方法对多对调度规则组合的性能进行评价，并寻找出最优的并行调度规则来实现减少订单的提前/延后和缩短生产流程时间的目标。Haili Lv和Guozhen Han^[30]将GP算法应用于装配作业车间调度的研究中，他们利用GP算法构造复合调度规则，并在平均拖期的调度目标下比较其与SPT和JDD等简单调度规则的性能，结果表明GP构造的复合调度规则相比简单调度规则的性能有明显的提高。

1.4 本文的主要工作和结构

本文以装配作业车间调度问题为研究对象，以基于GEP的仿真优化算法为技术手段，探究在Lateness和Deviation两种调度目标下构造出比JDD和TWKR更为高效的调度规则，以提升装配作业的运行效率和经济效益。本文的主要工作如下：

第一章首先介绍了课题的研究背景、选题目的及研究意义；然后对作业车间调度问题和装配作业车间调度问题的研究现状作了简要介绍；最后给出本文的主要工作和结构。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：