张 英，郭劲添

（武汉理工大学 物流工程学院，武汉430063）

我国部分造船企业早在20世纪80年代初就开始陆续应用CAD、CAPP、CAM、GT等技术进行船舶设计和建造，90年代后，造船的先进制造技术和装备也得到了大量引进和使用。然而造船生产的效果较差、竞争力低［1］，与世界造船先进水平相比，差距最大的是船舶生产组织和生产过程控制等方面［2］。

生产计划是将产品按时段进行分解，计算得出零部件在各阶段的时间节点，而零件的具体加工安排是借助车间作业调度来完成的。因此车间作业调度问题JSSP（job-shop scheduling problem）是实际生产计划问题的关键，也是产品全生命周期管理中的一个关键环节，直接关系到造船企业的生产效率和成本。

目前有关JSSP的研究［3］在理论上探索较多，对于小规模的调度效果较好，但对于设备与零件数量都较多的实际问题，运算时间过长，工程应用不太理想。

船舶制造的生产组织形式属于典型的大型单件小批生产类型，生产过程复杂，没有可供借鉴的实用模式，所以，研究这类生产计划与调度模式，对提高我国整体造船水平具有现实意义。

1 造船生产特点与车间作业调度

现代船舶生产具有以下特征：①船舶制造属于工程项目型的单件小批量生产类型，建造周期长，占用资金大，成本高；②是劳动密集型与技术密集型并存的、综合性的大型组装工业，工种、专业繁多，生产过程复杂，设备利用率低；③高空、立体交叉作业多，拼焊装配的工件大、重，且形状不一，移动困难，劳动生产率低，工作环境差；④配套企业多，配套产品复杂。

以上特征带来船舶主要产品（如大型柴油机）的加工制造具有以下特点：①产品品种多、规格多变，加工设备多、设备柔性强；②生产管理难度大、生产周期长；③产品各部件之间的时序约束关系和成套性要求严格，约束条件复杂多变；④受多资源约束，诸如紧急件插入、设备故障、工作日程变更和组合件加工等问题［4］。

在现代造船模式下，合理地安排众多的任务包的生产，满足资源约束要求，并做到资源利用的均衡，是生产计划的基本要求。面对复杂的造船生产，仅靠计划制订者个人的经验很难制订出合理的生产计划。

根据研究对象的复杂性，车间调度问题分为单机调度、并行机床调度、流水车间调度和作业车间调度问题JSSP，其中JSSP是指加工系统中有一组功能不同的机床，待加工的零件包括多道工序，每道工序在一台机床上加工，零件的加工路线互不相同。车间作业调度问题是一个典型的NP难题，是最困难的组合优化问题之一。由于调度问题涉及的因素很多，目前还没有一个方法能够对车间调度问题进行全面而有效的求解［5］。尤其是对于车间调度问题中的高度动态性和复杂性还缺乏有效的研究方法。

遗传算法以其内在的隐并行性和较好的全局寻优能力，在JSSP问题求解中得到了较好的应用，而且随着遗传结构的不断改进，它的有效性也在不断提高［6］。然而，遗传算法并不能较好地处理JSSP问题的高度动态性和随机性问题。为此，对JSSP问题先采用遗传算法寻优，然后利用EXTEND仿真软件进行建模和仿真，有效地弥补了遗传算法的不足。

2 JSSP问题的数学模型及特征

2.1 JSSP问题的数学模型

JSSP问题的一种简单情形可描述为，有m个任务（产品）需要分配给n个工序（机器）去完成，每个任务只能分配给1个工序处理，并且每个工序只能处理1个任务，不同的分配将会花费不同的代价。JSSP问题要求找到1种分配方案使所花费的总代价最小。

若第i个工序完成第j项任务的代价Cij≥0，则可以构成代价矩阵Cn×m。在求解如何把任务分配给各个加工工序的条件下，使得所花费的总代价为最小。假设

则排产问题可以转化为求解排产矩阵Rn×m，其约束条件如下：

因此所求目标函数为：

4.防治方法。彻底清塘，有机肥要充分发酵后再使用，保持优良的水质，加强管理，科学投饵，提高鱼体免疫能力，有寄生虫时及时杀虫。发病季节定期泼洒生石灰或漂白粉，防止此病发生。

其中，Cij∈Cn×m，Rij∈Rn×m。

2.2 JSSP问题的特征

对于实际的JSSP问题，如多个工作中心处理一系列不同的作业，这种问题属于NP-hard问题。其中，如果有m个任务要经过n个加工工序进行加工，并且所有的任务都要经过所有的加工工序，那么就有（m！）种可选的作业排序。因此，即使是小规模的生产排产也会有大量的排产方案，如果仅仅使用数学方法来进行求解往往是比较困难的，此时有必要结合其他的优化算法（如遗传算法）来缩小解空间并求解出较佳的排产方案。

在进行排产问题的研究时，对方案的衡量标准通常应具有以下四个方面［7］：

1）满足顾客交货日期或者下游操作要求；

2）流程时间（工件在整个流程中的时间）最短；

3）在制品库存最小；

4）机器或者劳动力空闲时间最小。

3 JSSP问题建模与仿真优化

现实的车间作业调度系统都是离散事件动态系统（DEDS），任务的到达具有随机性及不确定性。EXTEND，为了方便用户解决DEDS的优化问题，专门开发了遗传算法优化模块。另外，EXTEND软件中所有模块的源代码都是公开的，用户只需要熟悉C语言，就可以轻松地嵌入自己改进的遗传算法程序。

3.1 问题描述

某船厂加工车间有4个产品要进行生产，而每个产品必须依次经过4个加工工序进行加工，各个产品在各个工序中消耗的时间见表1。现要求以总生产时间最短为目标，通过EXTEND软件建立仿真模型，然后求出最佳的排产方案。

表1 各产品在各工序间的生产时间

3.2 EXTEND建模

建立排产模型的最终目标是求解出产品生产时间最短的产品生产顺序，因此在建模的时候，可以把各个产品设置一个初始的优先权，然后通过仿真模型并结合遗传算法优化模块求解出各个产品的最佳生产优先权，然后再按照所求的优先权顺序进行排产生产就可以得到所有产品生产的最佳生产时间。根据实际生产布局以及相关的数据，通过EXTEND软件建模，见图1。

图1 排产仿真模型

在这个仿真模型中，首先给各个产品设定一个初始的加工优先权，产品1、产品2、产品3和产品4按照优先顺序在缓冲器进行排队，然后再依次进入各个工序（工序1、工序2、工序3和工序4）进行加工。当4个产品全部加工完毕后，处理时间统计模块对这4个产品所需要的总时间进行汇总统计。

图1中，标注有产品1～4、工序1～4以及处理时间统计的模块为层级模块，它们都各自包含自己的层级。使用层级处理是为了使模型看上去更加简洁、明了。产品1、工序1和处理时间统计层级块及各自的层级结构详见图2、3、4。产品2、产品3和产品4的层级块的结构与产品1类似，工序2、工序3和工序4的层级结构与工序1类似。

图2 产品1层级块

在产品1的层级中，它所要实现的功能为：对产品1进行输出，并设置其加工优先权以及在各个工序的处理时间。

图3 工序1层级

在工序1的层级中，工序1的加工机器能够读取前面各个产品在工序1的加工时间。

图4 处理时间统计模块的层级

在处理时间统计模块的层级中，对产品输出数量进行统计，当产品输出数量为4时，模型就会自动停止对产品加工总时间的统计，并输出4个产品加工所用的总时间。

3.3 仿真结果分析

首先，将决策的参数变量（各个产品加工的优先权）以及目标函数（最短的加工总时间）在遗传算法优化模块中进行设置，然后运行遗传算法优化模块。总共进化了51次，并且种群最终100%收敛，见图5。

图5 遗传算法优化图

从图5中可以看到，优化目标（最短总加工时间）很快收敛到最小值22，而种群也在迭代17次后100%收敛。

收敛后的结果见表2。

表2 遗传算法优化结果

从表2可以看到，产品1～4的优先权从小到大的排列顺序为产品3、产品2、产品4和产品1。在EXTEND仿真软件中，优先权越小，优先级越大。因此这4种产品在流水线上的加工顺序应为：产品3、产品2、产品4和产品1。

4 结论

为了便于证明方法的可行性，本文仅对一典型排产过程进行了分析，而且只实现了作业时间这一种资源的最小化的优化。但是从中可以看到，应用EXTEND仿真软件可以实现JSSP中的排产优化。在实际应用中，只需对作业对象以及相应的资源约束作相应的替换，就可以同样应用EXTEND软件实现在多种资源约束的条件下，确定最佳的作业生产顺序，制订出合理的生产计划。当实际生产过程中的情况发生变化时，应用EXTEND仿真软件，并通过计算机可以对生产作业及时地调整，使生产计划符合生产实际，保证造船生产的高效进行。

［1］朱汝敬.入世对我国船舶工业的影响及应对［J］.船舶经济贸易，2000（2）：10.

［2］徐学光.探索船舶工业的持续发展［J］.上海造船，1999（1）：15.

［3］何 霆，马玉林，杨 海.车间生产调度问题的研究［J］.机械工程学报，2000，36（5）：97-102.

［4］周宏根，蔡 勇，景旭文，朱文彬.船舶柴油机大规模动态作业车间调度系统及其关键技术研究［J］.机械设计与制造，2006（4）：177-179.

［5］Dagli C.H，Sittisathanchai S.Genetic neuro-scheduler：A new approach for job-shop scheduling［J］.Production Economics，1995（41）：135-145.

［6］玄光男，程润伟.遗传算法与工程设计［M］.北京：科学出版社，2000.

［7］李锦飞，马汉武，陈纪南.生产管理与调度［M］.北京：化学工业出版社，2005.