作业车间调度是实现生产自动化的重要基础，其理论研究具有重要的实践意义。作业车间中加工时间是生产过程中的关键因素，直接影响完工时间、生产效率、设备负荷、能耗等经济效益指标，也是科研工作者关注的重点内容。对制造企业的生产过程调查统计显示^[1]：加工时间在整个生产制造过程的时间占比在10%以下，而非加工过程时间占比在90%以上，表明了其它辅助加工时间具有不可忽视的作用。大部分作业车间调度问题的研究主要考虑加工时间，近年来研究人员对作业车间调度中辅助时间的影响越来越重视，但相对研究成果还是比较少，由于辅助时间定义的出发点不同，各种时间存在着重复、模糊、不一致的地方。文中通过分析生产过程时间，从调度的角度出发，对模糊不一致的时间进行统一，综合考虑加工时间、调整时间、故障时间和运输时间，研究多种时间因素的作业车间调度优化问题，提高车间调度的实践应用效果。

1 作业车间调度概述

作业车间调度问题(job shop scheduling problem，JSP)是车间生产过程调度的简化模型，具有普遍性和抽象性。一般的JSP问题可描述为：有m台设备，需要完成n个工件的加工任务，每台设备能且只能完成1个工件的1道工序加工，每个工件有多道加工工序。由于工件的工序工艺特点和要求，工件的加工次序是确定的，工件工序的加工设备及加工时间也是确定的。在满足上述约束条件下，调度优化就是通过合理安排设备上加工工件的先后次序，优化完工时间、经济效益、能耗等指标，并且确定工件在设备上工序加工的开始时间和结束时间，从而排出工件加工的甘特图，便于安排实际生产。

在作业车间调度过程中，工件加工时间是目前大部分研究关注的重点，近年来研究人员对辅助时间逐渐加以重视，开始在作业车间调度问题研究中考虑某种或几种辅助时间^[2-6]。文献[2]对维修调度任务进行了研究。文献[3]从批量调整时间、非批量调整时间、顺序相关非批量调整时间、顺序无关非批量调整时间等角度，对考虑调整时间的作业车间调度进行了总结。文献[4]按照单机、并行机、装配车间、流水车间、装配车间、作业车间、柔性作业车间等车间类型，对顺序相关调整时间、顺序无关调整时间、组调整时间的车间调度进行了总结。文献[5]全面总结了20多年来柔性作业车间调度论文的分布情况、年份、性能指标、技术方法等，其中涉及到辅助时间的论文仅有少量几篇。文献[6]研究了考虑调整时间和物料运输时间的作业车间调度问题并设计了混合PSO求解算法。上述研究取得了一定的成果，但大部分研究把某种辅助时间作为一个影响因素考虑，对重叠、模糊、不一致的时间一般采用增加约束条件来解决，并没有从车间生产调度的角度进行分析，文中从工件生产实际出发分析生产过程中多种辅助时间因素，在此基础上建立考虑多种辅助时间的作业车间调度模型，并设计改进遗传求解算法，进而为作业车间调度的实践应用奠定基础。

2 作业车间的时间因素

从作业车间生产过程出发，结合调度理论研究和应用，对包括加工时间、准备时间、等待时间、运输时间、故障时间等因素进行分析研究。

2.1 加工时间

加工时间指工件的某道工序在作业车间生产设备上进行加工的时间，其时间长短由工件的工序加工工艺特性和加工设备决定，不同工序加工时间不同。

2.2 准备时间

一般可以假设准备时间为零，表示工件已经准备就绪，可以安排设备对工件加工。

2.3 等待时间

等待时间一般指工件前后工序加工停顿的时间，其时间的长短与工序工艺特点有关系，与加工设备能力和数量有关系，与车间设备布局有关系。等待时间受多种复杂因素影响，是比较复杂也需要深入研究的难点，对调度优化性能有重要的影响。为了车间调度研究的需要，对等待时间进一步进行细化分析。

根据工件实际生产过程，通过分析研究，可以把等待时间分为占用时间、运输时间、故障时间、调整时间等4种类型。

2.4 占用时间

占用时间为当工件工序准备就绪可以加工时候，此时需要的加工设备正在加工其它工件的工序，该工件只能等待而产生的等待时间。占用时间发生的时候，其设备没有空闲，正在加工其它工件，隐含在加工时间，所以其长短对整个车间工件的完工时间的优化没有影响。

2.5 故障时间

故障时间是当机器设备故障时候，工件不能正常加工而等待的时间。一般从机器不满足工件加工质量要求开始计时，对设备进行维修、修复、重新启动直到正常工作开始加工工件为止。具体时间跟故障的严重程度、维护维修等相关。机器故障是车间生产活动中比较常见的一种情况，由于故障而导致工件等待时间对最大完工时间有较大影响，应该与普通等待时间分离，把故障时间单独进行研究。

2.6 调整时间

由于加工设备上加工的工件工序的变换，需要进行模具、家具、装卸、启动等操作而产生的时间为调整时间。设备调整是生产活动中必不可少的内容，由于设备调整而产生的等待时间是必不可少的辅助时间。随着研究的深入，把调整时间分离出来单独研究更加符合生产的实际情况，有利于优化调度的实践应用。文中把机器调整时间与等待时间分离独立起来进行研究。

2.7 运输时间

工件在不同设备上完成各道工序的加工，在加工过程中把工件从一个设备运输到另一个设备，工件前后工序加工之间就会因为运输而产生等待时间，这就是运输时间。大部分研究没有考虑运输时间，忽略了不同设备之间工件运输而消耗的时间，这不利于调度的实际应用，也影响了车间完工时间的优化性能。近年来，考虑运输时间的车间调度问题研究逐渐增加。这种由于在设备之间运输工件而产生的等待时间，也是工件加工中不可或缺的辅助时间，对调度优化有重要的影响，应该把运输时间与等待时间进行分离，独立起来进行研究。

在实际生产活动中，对某类型工件而言，其体积、重量、运输方式比较固定明确，不易变动，可以假定为常数G，用f(d)代表运输距离的正比例函数。此时，运输时间表达为：t_jh=f(d)+G。

2.8 作业车间生产过程的时间因素

通过上述分析发现，在车间调度优化中，生产过程中各个时间因素的定义有不严谨和模糊的地方，对车间调度理论的研究有较大的影响。文中结合生产实际过程，从调度的角度出发，特别是把通常意义的等待时间进行细分，划分并界定了占用时间、运输时间、故障时间、调整时间，如图 1所示。把调整时间、故障时间、运输时间与加工时间分别优化，从而分析各个时间因素对作业调度完工时间的作用及影响。该分析方法，结合调度的理论研究，从实际生产过程出发，时间界限划分明确，没有重叠，含义清晰，符合车间实际生产情况，符合车间调度理论研究的需要，有利于调度理论的实践应用。

3 多时间因素下作业车间调度问题建模

综合上述分析，针对作业车间辅助时间，分离调整时间、故障时间、运输时间等多种辅助时间，考虑多种时间因素对作业车间调度优化的作用和影响建立调度模型来研究作业车间调度优化问题。

调整时间可以为参考工件的加工时间的随机数。同时考虑到调整时间的工序顺序性质，一个三维数据可以同时表示顺序相关和顺序无关调整时间。其中，第一维表示所有的加工设备，可以确定那台设备的调整时间，第二维表示该设备当前加工的所有工序，第三维表示上道加工的工序，从而可以确定任意设备上任意两道工序的顺序相关调整时间。如果当前工序和上道工序相同，表示该设备的顺序无关调整时间，即矩阵对角线表示顺序无关调整时间。

在工件运输中，运输时间与工件的体积及运输方式、工件相关，可以简化为固定常数G，且与工具在设备之间的距离相关，运输时间公式可以表示为

$ t_{j h}=f(d)+G, $

(1)

其中：G可以设定为固定值；f(d)与设备的间隔数量成正比，可以简化为间隔数d。

设备的故障时间是不确定和随机的，根据车间生产的实际经验并参考调度用例时间的大小，设备以10%的概率发生随机故障。

下面分别考虑加工时间、调整时间、运输时间、故障时间以及综合考虑调整时间、运输时间和故障时间来研究调度问题，以最大完工时间为目标，工件工序的开始时间如下。

只考虑加工时间：

$ s_{j h}=\max \left\{C_{j(h-1)}, Z_{i}\right\}。$

(2)

考虑调整时间：

$ s_{j h}=\max \left\{C_{j(h-1)}, Z_{i}+S_{i}\right\}。$

(3)

考虑运输时间：

$ s_{j h}=\max \left\{C_{j(h-1)}+t_{j h}, Z_{i}\right\}。$

(4)

考虑故障：

$ s_{j h}=\max \left\{C_{j(h-1)}, Z_{i}+B_{i}\right\}。$

(5)

考虑故障时间、调整时间和运输时间：

$ s_{j h}=\max \left\{C_{j(h-1)}+t_{j h}, Z_{i}+S_{i}+B_{i}\right\}。$

(6)

工件工序的完工时间：

$ C_{j h}=s_{j h}+p_{i j h}。$

(7)

其中:j表示工件号; h表示工序号; i表示设备号; s_jh表示加工开始时间; C_jh表示完工时间; t_jh表示工件的运输时间; Z_i表示设备空闲时间，即上个工件工序的完工时间; S_i表示该工序的调整时间; B_i表示设备故障时间; p_ijh表示工艺加工时间。

同时，加工需要满足约束条件：一台机器某时刻只能加工一个工件；一个工件某时刻只能在一台设备上加工；工件工序加工过程中不中断且无故障；工件工序按工艺先后顺序加工；工件的首道工序到设备的运输时间都是相同长短；设备故障后进行调整，不考虑调整后设备故障；首工序考虑调整时间。

4 改进遗传算法求解设计

对经典JSP问题求解算法已经有了许多的研究，其中遗传算法由于其鲁棒性和并发性等优点得到广泛的关注和研究^[7-9]。在参考文献[9-11]研究改进遗传算法的基础上，设计了一种改进遗传算法，可以有效求解多种时间条件下作业车间调度优化问题。

编码：采用整数编码，用工件号表示染色体的基因位，每一位基因表示一个工序，工件号出现的先后次序表示工序。整个染色体基因数目等于所有工件的工序总数，其初始化采用随机生成的方式。

交叉：父代的两个染色体通过相互交换基因，从而生产新的子代染色体。交叉方法采用POX方法，POX方法通过对染色体中的多个工件进行操作，很好地保持父代个体的优良特征^[9]。

变异：文中采用随机互换两点基因进行变异的方法。在染色体中随机选择2个基因位置，然后把这2个基因交换位置，在实现变异的同时保证了编码的合法性。

局部搜索：经过变异后的个体，按照一定概率进行局部搜索。在个体中选择3个不同随机的位置，对这3个基因进行排列产生另外5个候选解。

选择：选择方法采用锦标赛方法，具有更小的复杂度、易并行处理等优点。

解码：从左到右，逐位对染色体基因代码进行解码。首先，确定基因位的工件代码工序含义；然后，按照机器约束选择加工机器；最后，对所有工件工序进行加工先后排序得到调度结果，计算调度最大完工时间。

1) 读取一个染色体基因，转换成相应工序O_jh。

2) 计算该工序O_jh加工的开始时间s_jh和结束时间C_jh，如图 2所示，根据考虑时间因素不同，选择不同公式计算开工时间s_jh，最后根据公式C_jh=s_jh+p_ijh计算完工时间。

3) 染色体基因解码是否完毕，如读取完毕，则解码过程结束；否则，转1)继续下一位基因解码。

图 2中，在工序O_j(h-1)完工后，考虑不同辅助时间的O_jh调度示意图，其中，M_i考虑加工时间，M_is考虑调整时间，M_ib考虑故障时间，M_it考虑运输时间，M_im考虑调整、故障、运输时间等多种时间。

5 测试实例

用VC++编程，程序在酷睿i7，CPU主频2.8 G，内存32 G的笔记本上运行，采用上述遗传算法对FT06、LA01、LA02等作业车间的典型用例进行对比测试，参考用例加工时间大小，运输时间中G为1，运输距离采用设备间隔数，首工序运输时间为1；调整时间为小于3的随机数；设备以10%概率发生故障，故障时间为小于4的随机数。初始种群数量为200，交叉概率0.8，变异率为0.01，迭代100，并采取保优策略。其优化结果数据如表 1所示，表中最优解是表示仅仅考虑加工时间的最优完工时间；时间因素表示考虑的细分辅助时间；改进前表示优化时不考虑该辅助时间，但实际生产具有辅助时间的情况下的最大完工时间，即直接把相应辅助时间插入调度中的最大完工时间；改进后数据表示优化时考虑辅助时间优化的最大完工时间；改进百分比为改进后完工时间相对改进前完工时间的减少百分比。其测试结果显示优化性能有较明显的改进，3个标准用例平均改进：调整时间的改进有6.2%；运输时间的改进有3.4%；故障时间的改进有2.6%，综合调整时间、运输时间和故障时间3种因素的改进有6.3%。其中，LA01和LA02的改进效果相对FT06较差，是由于假定的辅助时间相对于其工件工序加工时间比较小。

6 结束语

从作业车间生产实际过程出发，分析车间生产中存在的各个时间段，特别是细分了等待时间，从调度的角度，定义和界定了占用时间、调整时间、运输时间、故障时间等辅助时间，并建立了多时间因素的作业车间调度模型，设计了改进遗传求解算法。最后，采用JSP的典型用例，对考虑调整时间、故障时间以及运输时间因素的作业车间调度问题进行了验证、对比、分析和总结。研究结果表明，调整时间、运输时间和故障时间等辅助时间是生产过程中不可忽略的重要部分，对优化性能有较好的改进作用，对作业车间调度理论研究和实际应用有重要的意义，对作业车间调度的优化性能指标有较大的改进。