摘 要

在实际生产中，作业车间调度问题一直是一个经典问题，对于企业来说，如何使有限的机器等资源发挥出最大的作用，优化时间与成本等指标是亟待解决的问题。由于该问题的NP-hard特性，传统最优化算法很难在合理时间内求出现实规模问题的最优解，常常需要借助启发式算法求解。

本文借助仿真软件plant simulation对考虑机器故障与无故障情况下的作业车间调度问题进行了模拟。通过模拟比较了无故障与有故障情况下的作业车间调度性能，利用Minitab软件对数据进行了分析，比较在考虑机器故障时九种派工法则的不同性能指标。

实验结果表明：没有完美无缺的派工法则，在不同的机器利用率和交货期系数下，不同的派工法则的调度性能各有差别，总体来说SPT法则的调度性能最为优秀，其次则是LWKR法则和EDD法则。而其中调度性能最差的是MWKR法则。在发生故障的情况下，多数派工法则的性能指标的相对无故障情况下的变化程度相同，而MWKR法则的变化程度比较明显。

关键词：机器故障；派工法则；仿真；作业车间调度

Abstract

In practice, job shop scheduling problem has been a NP-hard problem, the actual situation should be combined with the research of this problem to get the best schedule. It is a problem to be solved for enterprises that how to use the resources reasonably and minimize the cost.

In this paper, we use the simulation software plant simulation to simulate job shop problem subject to machine breakdown. By simulating the job shop scheduling problem with machine breakdown and normal job shop scheduling problem，and using Minitab software to analysis the data, we can compare the performance of nine dispatching rules in job shop scheduling with machine breakdown.

The results of experiments show that: there is no best dispatching rule, the performance of different dispatching rule is different under the different coefficient of deadline delivery date and utilization ratio of machines. The overall performance of SPT rule is the best, the second is that LWKR rule and EDD rule. And the worst scheduling performance is the MWKR rule. In the case of failure, the performance of the majority rule is the same, and the change of MWKR rule is obvious.

Key Words：Machine breakdown; dispatching rule; simulation; job shop scheduling；

目 录

第1章 绪论 6

1.1 问题背景及研究意义 6

1.2 国内外研究现状 6

1.2.1 作业车间调度问题研究现状 6

1.2.2 利用仿真的作业车间调度问题研究现状 7

第2章 作业车间调度 8

2.1 车间调度问题 8

2.1.2调度问题概述 8

2.1.2 调度问题分类 8

2.1.3 车间调度问题的优化方法 9

2.2机器故障下的作业车间调度问题 10

2.2.1机器故障下的作业车间调度问题定义 10

2.2.2机器故障下的作业车间调度策略 11

2.3 Plant Simulation软件概述 11

第3章 调度问题的仿真研究 12

3.1仿真设计 12

3.1.1问题描述 12

3.1.2加工产品概述 13

3.1.3工序的生成 13

3.1.4加工机器的生成 14

3.1.5设置机器故障 14

3.2仿真概述 15

3.2.1派工法则概述 15

3.2.2性能指标概述 16

3.2.3构建仿真模型 17

3.2.3仿真运行 22

第4章 派工法则的性能评价 24

4.1数据统计 24

4.1.1无故障情况下的运行结果 24

4.1.2考虑故障情况下的运行结果 27

4.2数据分析 35

4.2.2机器故障影响分析 35

4.2.1派工法则性能指标分析 35

第5章 总结与展望 37

5.1总结 37

5.2展望 37

第1章 绪论

1.1 问题背景及研究意义

当今工业4.0的快速前进既为企业的成长带来了一定的机会，但也加剧了行业的角逐。制造型企业必需快速提升自身竞争力才能在激烈的行业竞争中存活下来，降低产品的成本、提高产品质量以及缩短产品上市时间无疑是企业的必经之路。要实现这些目标，既要提高企业管理水平，也要提高在车间生产过程中的调度决策水平。

在经典的车间调度问题中，全部工件的信息和车间状态在调度的起点都是确定的，当调度方案生成后，作业车间根据生成的调度方案来调度生产。但是，在实际的生产环境中存在着许多扰动性因素，如机器故障、交货期更改等，这些扰动会影响原有既定的调度，打乱生产节奏，甚至导致作业车间无法继续生产。

作业车间调度问题（Job Shop Scheduling Problem）从实质上来说是现实中工业车间的理想模型。对于工业生产来说，如果企业能够合理的根据作业车间调度系统来安排生产计划,能够使生产线均衡运作,也能够进一步提高生产效率。而在现实的车间调度中，调度不是一帆风顺的，总是会受到各种各样的干扰，例如机器故障的发生就会影响到调度的执行。当机器发生故障，需要停机并且进行维护，这时需要在该机器上加工的工序就必须等待机器恢复正常工作后才能进行加工。考虑机器故障情况下的作业车间调度目的在于调度人员能够实时的调度生产，在资源约束和机器故障的影响下安排适当的加工顺序，使得加工任务能够及时完成。对于现实生活中的制造型企业来说，研究机器会发生故障的车间调度问题能够给决策者提供一定的指导，占有一定的重要地位^[1]。

1.2 国内外研究现状

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

作业车间调度问题 (Job Shop Scheduling Problem)的求解是典型的 NP-hard问题。该问题的研究开始于20世纪60年代，S.M.Johnson研究了求解最大流程时间的流水车间^[2]，并提出了著名的Johnson算法，从此开启了调度问题研究的大门^[3]。但在这个阶段所研究的问题都是比较理想化的模型，比如产品在机器上的处理时间只是产品的加工时间，不包括预热时间等。随着现代化生产模式的发展，许多符合实际生产的不确定性因素增加进来，使得关于调度问题的研究更加深入。由于本身的复杂性，JSP求解方法一直以来以启发式算法为主，也有如禁忌搜索、遗传算法等。

随着不同算法的提出，调度领域产生了许多研究该问题的相关文献。Church和Uzsoy（1992）^[4]研究了在作业动态到达的单机生产系统下的事件驱动的周期性重新调度（额外考虑紧前交货期作业的周期性调整）。结果表明当重新调度的周期长度增加和事件驱动方法获得高绩效时周期性调度的绩效会降低。Sanjay V. Mehta，Reha M.Uzsoy^[5]讨论了在系统中按照概率来停机的情况下，在调度决策中加上空闲时间的预调度法。Yamamoto及Nof^[6]研究了在静态调度环境下的机器随机发生故障的重新调度策略。每当机器发生故障时将进行重新调度。结果表明，这种方法的表现比固定的排序策略和派工法则两种方法要好。

1.2.2 利用仿真的作业车间调度问题研究现状

Oliver Holthaus^[7]运用仿真的方法研究了机器故障下 Job Shop 的派工规则。从所得出的数据来看，机器故障参数不同对于派工法则的目标的作用是不同的。

何伟^[8] 使用Matlab探索了发生停机的柔性作业车间的预调度和重调度策略，旨在使调度更加稳健。

裴小兵，谭林林^[9]针对数学建模理想化假设的局限性，借助plant simulation仿真软件对作业车间实际生产运作情况进行仿真建模，并优化模型。经实例验证，使用根据仿真模型所算出的批量能够明显的降低总时间，证明了使用仿真来研究该问题是正确的

吴正佳,何海洋^[10]等人依据机器故障发生时加工机器所处的状态，构建了故障机器上剩余工件约束模型，概括了两种重调度策略的优劣，并提出了一种递进方法，最后运用该调度策略对企业生产实际中案例进行计算，发现其完工时间比企业实际加工时间缩短了 44.8%，验证了文章所提出的策略的正确性。

李伟^[11]研究了W公司加工车间需要进行改进的地方，对症下药定制车间对于生产调度的需求。根据车间的调度需求利用Plant Simulation搭建了AGV模型和作业车间模型,运行模型并根据需求进行了优化。利用仿真优化解决了W公司加工车间中一直存在的问题,给公司管理层决策提供了重要参考。

第2章 作业车间调度

2.1 车间调度问题

2.1.2调度问题概述

调度是调度制定人员在不打破一定约束 (产品的加工次序、订单完成期限和车间容量等)的前提下对需进行的操作的排序,利用这个顺序来这些操作来合理的分配资源,并且使得整个系统的性能最优化(如总执行时间、拖延时间和生产成本等)。从其本质角度来看，车间调度就是一个如何合理分配车间资源的问题，这里的资源大体来说都是指代车间中能够工作的机器，问题的目标是找到一个在系统性能最优的条件下将待加工的工件安排到机器上去的最优化方案。一般来说车间调度问题的限制比较多，因此使得该问题成为NP-hard问题，目前还没有能够证明求出了最优解的算法^[12]。

2.1.2 调度问题分类

问题背景是n个工件在m台机器上加工。首先，一台机器运行单次仅能够加工单个工件。其次，每个工件只能在指定的一台机器上加工，并指定了每个工序花费的时间。总体来说，车间调度问题可分为以下三大类^[15]：

(1)作业车间调度问题(Job Shop Scheduling Problem)

在作业车间中，每个工件的工艺路线不同。在作业车间调度问题中，每个产品的任何一道工序都必须指定加工方式和加工机器。调度的职责是安排需要加工的工件进入机器的顺序，使得整个加工任务的最大完工时间最短。在加工次序和车间容量的制约下，作业车间调度成为了所有还没有找到多项式解法问题中比较难的问题 ^[13]。

(2)流水车间调度问题(Flow Shop Scheduling Problem)

在流水车间中，订单中需要进行加工的工件都会以相同的次序进入机器，并且被执行相同的加工动作。无论什么产品，即使产品的规格大小不同，同一批产品在流水车间中的生产总是使用一样的生产流程。从实际生产来看，流水车间主要适用于订单量大的大型的生产企业或者具有完备流水线的生产车间。流水车间调度问题其实就是无论多少产品需要加工都使用相同的加工路线的作业车间调度问题，从本质上来说是作业车间调度的简化问题^[13]。

(3)开放式车间调度问题(Open Shop Scheduling Problem，OSSP)

在开放式车间调度问题中，待加工产品的移动是随机的，一个工件的前序后序是任意的，不存在固定的工艺路线。在这种环境中很容易生成调度，且任意的加工顺序更是大大降低了问题的难度，可以生成更多合适的调度方案 ^[14]。但是当需要描述的车间规模较大时，想要生成最优调度也是非常困难的^[15]。

2.1.3 车间调度问题的优化方法

车间调度问题是一个所有还没有找到多项式解的问题，很难在短时间内得到问题的最优解。针对该问题，一般来说要求在一定时间内求出最优或者次优的可行调度。历经多年的研究，在调度领域，已经取得了一定成果，针对该问题的算法可以分为以下几类：