摘 要

随着国内外制造业市场竞争的越演越烈，制造企业不得不提高企业自身的管理水平以及生产效率，从而提升企业的竞争能力。企业的生产效率与生产车间息息相关，作业车间调度又是生产车间中关键的一环。作业车间调度问题属于典型的生产调度问题，具有规模大、不确定性、复杂性等特征。自作业车间调度问题提出至今，不少学者都对其做出了研究，并提出了许多算法用于求解此问题。智能搜索算法在求解这类规模大且复杂的问题时，运算时间成本高，不利于对对动态的生产车间做出及时的响应。而调度规则由于其求解时较低的时间复杂度，易于理解并且可以针对生产车间的动态非线性扰动做出及时响应等特点，使其非常适合用于求解这类复杂的调度问题。本文针对装配作业车间调度问题提出了一种新的调度规则。

本文提出的是一种基于调度属性权值确定的调度规则挖掘机制，即将调度属性的权值作为输入而得到的一调度规则。本文是使用神经网络与模拟退火算法相结合的方法来实现这一调度规则。对装配作业车间调度规则的研究需要大量的学习数据，本文使用plant simulation软件建立仿真平台，运行得到用于神经网络学习的样本数据。

关键词：作业车间调度 装配作业车间调度 调度规则 BP神经网络 模拟退火算法

ABSTRACT

With the increasing competition in the domestic and foreign manufacturing markets, manufacturers have to improve their own management level and production efficiency, so as to enhance their competitiveness. The production efficiency of the enterprise is closely related to the production workshop, and the job shop scheduling is the key part in the production workshop. Job shop scheduling problem is a typical production scheduling problem with large scale, uncertainty and complexity. Since the scheduling problem of the workshop has been put forward, many scholars have studied it and proposed many algorithms to solve this problem. The intelligent search algorithm has high computation time cost and is not conducive to timely response to the dynamic production workshop when solving such large and complex problems. But scheduling rules due to its solving low time complexity, easy to understand the dynamic nonlinear disturbance and can be aimed at the production workshop to make timely response, etc, to make it very suitable for solving this kind of complex scheduling problems. In this paper, a new scheduling rule is proposed for the scheduling problem of assembly workshop.

In this paper, a scheduling rule mining mechanism based on scheduling attribute weights is proposed, and the weight of the scheduling attribute is used as the input. This paper uses neural network and simulated annealing algorithm to realize this scheduling rule. The study of assembly job shop scheduling rules need a lot of study data, this article uses the plant simulation software to establish the simulation platform and run back to sample data for neural network learning.

Key words：Job shop scheduling ；Assembly job shop scheduling；Scheduling rules；

BP neural network；Simulated annealing algorithm

目录

第一章 绪论 1

1.1 研究背景 1

1.2研究目的及意义 1

1.3国内外研究现状 2

1.3.1国内研究现状 2

1.3.2 国外研究现状 3

1.4研究内容和技术路线 3

1.4.1 研究内容 3

第二章 装配作业车间调度问题描述 1

2.1传统作业车间调度问题 1

2.1.1作业车间调度问题介绍 1

2.2.2作业车间调度问题的分类 2

2.2.3作业车间调度问题的特点 2

2.2 装配作业车间调度问题 2

2.2.1 装配作业车间调度定义 3

2.2.2 装配作业车间调度问题的求解方法 3

2.3作业车间调度规则 3

2.2.1 调度规则定义与分类 3

2.2.2 基本调度规则 4

2.2.3 调度规则的选择 5

2.2.4调度规则评价指标与评价方法 5

2.4本章小结 6

第三章 装配作业车间调度规则求解思路 7

3.1 整体框架 7

3.2 主要算法介绍 7

3.2.1 BP神经网络 7

3.2.2模拟退火 9

3.3 本章小结 11

第四章 求解与结果分析 12

4.1求解 12

4.1.1 BP神经网络拟合Job-shop 12

4.1.2模拟退火算法优化求解 15

4.2 结果分析 17

第五章 环境经济分析 21

5.1环保性分析 21

5.2经济性分析 21

第六章 总结与展望 22

6.1总结 22

6.2展望 22

参考文献 23

致谢 25

第一章 绪论

1.1 研究背景

近年来，国内外制造业市场的竞争愈加激烈，如今制造业正面临两大挑战。首先，随着生产力的不断提高，生产活动对资源的需求不断加大，使得当今制造企业正面临资源紧缺这一问题，因此，合理分配有限的资源是企业生产过程中的关键。其次，随着客户要求的不断提高，制造业的市场正朝着个性化与多样化发展，这使得生产系统在生产运行过程中会遇到更多的随机性以及不确定性因素，例如，待加工工件的临时到达、机器故障以及订单临时变动等。因此，应对解决作业车间面临的动态非线性的扰动和变化是如今制造企业的另一挑战。一方面，随着科学技术的不断发展，机器的加工精度以及自动化程度等都得到了提升，这使得车间的生产调度问题的难度加大，超出了经验调度的范畴。另一方面，随着市场竞争愈演愈烈，为了能够适应市场多样化、个性化以及及时相应的要求，提出了精益生产、敏捷制造、计算机集成制造等先进生产方式，以此期望降低成本、节约资源、缩短完工时间以及提高产品质量等。制造业孕育了生产调度理论，在车间资源有效的前提下，生产调度合理的将资源分配给各工作，并且给各工件指定加工顺序，来满足生产指标。在生产环境日益复杂的当下，更需要有效的生产调度方法和智能化的软件指挥整个生产过程，以使得整个生产过程更加高效。

本文在这一研究背景下，研究装配作业车间调度问题，提出一种新的调度规则。

1.2研究目的及意义

调度问题^[1]是一类处理在不同时间将资源合理的分配给相似或不同任务的组合优化问题。其研究的核心是模型的建立以及相应的求解的算法。作业车间调度问题（Jop-Shop scheduling problem）作为调度问题的一个重要分支，是一个典型的组合优化调度问题，其主要任务是在现有的资源条件下，对工件在相关设备上的加工顺序以及开始加工时间做出合理安排，从而使得某些性能指标最优。作业车间调度问题自20世纪50年代由Johnson^[1]提出以后，引起了人们广泛的关注。研究学者们提出了不少的解决方法，早期针对一些小规模的问题提出了一些传统的数学运筹学方法，例如，分支定界法、束搜索法以及动态规划方法。但由于生产规模的不断扩大，上述的方法已不能表现出良好的性能。逐渐的不少学者提出了一些启发式规则方法，例如，SPT规则、WSPT规则以及EDD规则等。随着计算机技术的快速发展，不少算法结构复杂的元启发式方法都取得了不错的结果，例如，遗传算法、禁忌搜索算法以及模拟退火算法等。

对作业车间调度的研究有以下两个层面的意义：首先，对作业车间调度问题的研究具有重要的理论价值和现实意义。调度问题作为复杂的组合优化问题，已被应用到了很多领域，并且通过几十年的发展已经被抽象为一类数学和运筹学问题。但随着社会的不断发展，调度问题的规模越来越大，使用传统的数学运筹学方法，如数学规划方法、分支定界法等求解不能很快的得到使人满意的解，因此研究更多的新的性能较优的算法来求解调度问题具有重要的理论价值和现实意义。其次，它可以提高企业的市场竞争力，提高企业的经济效益。近些年，制造企业之间的竞争更加激烈,客户的个性化要求越来越多,各企业不得不通过提高生产管理水平和生产车间的自动化水平,来提高生产效率, 从而缩短产品完工时间,降低生产成本,最终达到实现经济效益最大化这一目的。而对于制造企业来说提高生产管理水平和生产自动化水平的关键是在作业车间应用合适的调度方法。

1.3国内外研究现状

1.3.1国内研究现状

近年来，国内学者主要用仿真的方法研究动态作业车间调度问题，用仿真模型模拟不同调度规则，分析评价各类调度规则的性能，从而选择最优的调度规则。

钱国洁^[2]用仿真实验的方法对调度规则算法进行了系统全面的研究。选择了One-by-One DJSP 问题、Batch-by-Batch DJSP 和 Machine Breakdown DJSP 问题这三类典型的动态作业车间调度问题作为研究对象，分别对这三类典型动态作业车间调度问题，提出了调度问题各要素（包括机器实体、工件实体、工序实体、投放期和交货期）的基本属性生成方法、建立了数学模型并生成案例数据。

戴伯尧^[3]将模具生产企业可能遇到的突发状况加入到了作业车间调度中，提出了一种基于累积延迟的反应式调度策略，并使用Plant Simulation 软件来建立仿真模型，将所有提出的策略置于仿真模型中运行，针对运行得出的结果做系统的分析并做出了评价。

金峰赫、崔楠等人^[4]以注塑模具装配车间为研究对象，提出了多种优先调度规则，并利用仿真平台以多种评价指标对所提出的优先调度规则的性能进行了分析。

王振江^[5]提出了一种基于调度属性选择的调度规则发掘方法。建立一个基于Multi-Pass的作业车间最优调度方案生成平台，并通过运行仿真平台，得到用于调度属性选择和调度规则挖掘的数据样本。然后给出了基于概念格的调度属性选择方法和基于属性选择的调度规则挖掘方法，并通过仿真实验对各挖掘方法的有效性进行了验证。

1.3.2 国外研究现状

国外学者对作业车间调度问题的研究较早、较为全面。

Toru Eguchi和Fuminori oba^[6]提出了一种基于神经网络的两阶段训练法来求解作业车间调度规则。该方法第一阶段是将调度条件分为有限的调度条件和特定的调度条件，通过模拟退火方法，对各特定条件下的有效神经网络进行了单独训练。在第二阶段中，将所有特定调度条件的神经网络集成到一个鲁棒性的神经网络中。该方法可以很好的解决在求解调度规则时要将所有调度条件考虑在内带来的耗时长及不切实际的问题。

A. Azadeh 和 B. Maleki Shoja^[7]等人提出了一种基于离散事件仿真和人工神经网络的新方法，从一组规则中给每一台机器确定最优的优先调度规则从而使作业车间调度问题中的完成时间最小。

Lu M S,Romanowski R^[8]指出重新调度可以描述机器(MIT)和作业停留时间(JWT)的空闲时间，描述在给定时间内动态加工车间的独特特征，文章是基于模拟测试研究了11个基本的调度规则和33个由重调度组成的复杂调度规则。

Shiue^[9]等提出了一种基于遗传算法和决策树分类算法的知识挖掘调度方法。该方法利用遗传算法从当前的生产调度属性中寻找出最优属性子集将其作为决策树分类算法的输入属性，并利用决策树分类算法进一步了解挖掘调度知识。仿真结果表明，该方法的调度性能优于已有的基于决策树分类调度知识挖掘方法。

Gradisar^[10]等提出了一种基于数据建模方法的生产调度过程Petri网模型，利用企业生产管理信息系统具有的历史生产数据，建立了生产调度过程的Petri网模型。该模型可用来预测生产调度过程的相关性能指标值，或结合已有的启发式调度算法生成完整的生产调度方案。

1.4研究内容和技术路线

1.4.1 研究内容

全文共分为五章，将按照以下的章节架构展开研究：

第一章主要介绍了研究的背景、目的及意义，以及作业车间调度问题的研究现状，引出了本文要研究的内容。

第二章主要介绍了作业车间调度问题以及装配作业车间调度问题，比较了两类问题的区别，为后文的研究奠定了理论基础。

第三章主要介绍了神经网络和模拟退火算法的基本思想，一般计算过程等。为后文算法的使用提供了理论支持。

第四章主要介绍了本文的求解过程以及结果分析，具体讲述了本文的调度规则挖掘机制，使用神经网络与模拟退火算法结合的方法，在可接受的时间范围内得到一令人满意的调度规则。

第五章总结全文工作，提出不足的改进以及对未来的展望。

1.4.2技术路线

图1.1 技术路线图

第二章 装配作业车间调度问题描述

2.1传统作业车间调度问题

2.1.1作业车间调度问题介绍

作业车间调度问题（Job Shop Scheduling Problem）可以描述为：

已知有一个包含n个作业的作业集[J_i]1≤i≤n，另有一个包含m台机器的机器集合[M_j]1≤j≤m，每个作业i有n_i道工序，每个工序必须按一定的次序在指定的机器上依次处理，作业i在指定的机器m_ij上处理所需的处理时间为p_ij。另外，作业i到达车间的时间是r_i，作业i的交货期d_i，并且依据作业的重要性，作业i有与之对应的权重w_i。

作业车间调度问题中对作业的约束：

（1）一个作业只可以在一台机器上处理一次

（2）一个作业的多个工序不能同时处理

（3）整个处理过程，一个工序不会在同一个机器上加工多次

作业车间调度问题中对机器的约束：

（1）一台机器同一时间只能处理一个作业

（2）作业缓冲区的容量无限大

（3）所有机器可以处理的工序都不同

调度的目标是：在满足所有约束的情况下，合理的将各个作业安排给每个机器，并且合理的安排每个作业的处理顺序以及开始加工的时间，从而使得某个性能指标最优。常用的评价指标的定义如表2.1。

表2.1 各个评价指标的定义和描述

F_i=每个作业的流经时间 C_i=每个作业处理完成时间

L_i=每个作业的推迟完成时间 T_i=每个作业的拖后时间

2.2.2作业车间调度问题的分类

作业车间调度问题根据不同的分类依据可以分为以下几类：

1. 根据作业到达情形的不同可以将作业车间调度问题分为静态调度和动态调度。静态调度是指，在车间调度实施前作业已全部到达车间，并且不考虑装配过程中可能遇到的机器故障等突发状况。动态调度是指，在车间调度方案实施过程中作业陆续到达，会考虑订单的突然变动以及机器突发故障等情况。
2. 根据车间环境的特点，作业车间调度可被分为确定性调度和不确定性调度。确定性调度是指调度问题中所用的参数都是确定的数值，建立的模型以及求解的过程都比较简单，但适用的范围有限。不确定性调度是指加工生产过程中一些参数并不是固定不变的，而是与生产批量、加工时间等因素有关。

2.2.3作业车间调度问题的特点

作业车间调度问题有如下特点：

1. 复杂性：在实际的生产过程中，工件，机器，缓冲区以及输送系统之间都紧密联系，一个环节发生变化都会影响整个调度过程，又由于实际生产过程的规模不断扩大，使得计算越来越复杂，一般的常规的优化算法经常是无能为力。
2. 不确定性：实际的生产过程中往往存在很多的动态的不确定的因素，例如机器非检修时间停止运行、订单临时修改等。不确定性的因素极大的制约了调度方案的准确性。
3. 目标的多样性：考虑到实际的生产过程，每个部门所期望的调度目标往往是不同的，并且这些调度目标往往是相互抵触的，因此想要同时满足这些目标是不可能的。当前的一些优化目标通常是多目标的综合考虑，例如完工时间目标、成本目标等。

2.2 装配作业车间调度问题

上文所述的作业车间调度问题是相对简单的模型，因为它并没有考虑工件之间的装配问题。而在现代制造业的实际生产过程中，装配工作通常是整个生产作业的最后一个阶段。一个装配工序的完成要建立在整个所需工件都加工完成的基础上，所以装配作业车间调度问题（Assembly Job Shop Scheduling Problem）要比一般的作业车间调度问题复杂的多，它不仅要考虑各工件在加工时的顺序约束，还要协调装配时各工序之间的先后顺序。

2.2.1 装配作业车间调度定义

装配作业车间调度问题可以定义为：某产品G由n个部件装配而成，每个部件有m道工序，要在a台机器上完成装配。已知该产品的结构、各工序的加工处理时间以及装配作业的顺序约束，要求确定各机器上各工序的开始时间，从而使得总加工完成时间最小。

装配作业车间调度问题需满足的约束条件：