混合工作日历下作业车间调度遗传进化方法

曾 强 邓敬源 常梦辉 张进春

河南理工大学能源科学与工程学院，焦作,454000

0 引言

作业车间调度问题(job shop scheduling problem，JSP)是复杂的NP-hard问题[1-2]，多年来一直是学术界的研究热点。考虑到设备自动化程度、运行可靠性、固定成本、生产任务量的不同及人性化管理的需要，我国多品种小批量机械加工企业或车间内各设备往往采用不尽相同的工作日历，即混合工作日历现象在多品种小批量机械加工企业中普遍存在。然而，现有作业车间调度研究成果尚不能有效解决混合工作日历下的作业车间调度问题。

作业车间调度对于工作日历的处理主要有三种情况：不考虑工作日历、假定待调度设备采用统一的工作日历、假定待调度设备采用混合工作日历。绝大多数现有作业车间调度属于第一种情况。在这种情况下，调度在连续的时间轴上安排工序[3-5]，虽然计算量最少，但得到的调度方案未与具体的日历时间挂钩，故难以有效指导生产实践。第二种情况属于调度后考虑工作日历，其出发点是假定待调度设备采用统一的工作日历，先抛开工作日历的约束，使调度在连续的时间轴上安排工序，待得到最优调度方案后根据统一的工作日历进行时间推算，将最优调度方案“映射”到具体的日历时间上[6]，但它仅适用于待调度设备具有统一的工作日历的情况。第三种情况属于调度过程中考虑工作日历，即为设备安排工序时依据其工作日历进行。由于在调度过程中的时间推算过程需要进行大量的判断，所以比第一、二种情况的计算量明显增加。万春辉等[7]进行作业车间调度时在调度过程中考虑了混合工作日历。在调度前对设备的工作日历进行个性化的设置，即为每台设备设置工作日及工作班次，因为设备的工作日历会经常发生变化。由于待调度设备往往较多，为每台设备做个性化的工作日历设置需要花费大量时间，若调度周期较长，其包含的日历时间数据增多，会使调度过程中的时间推算计算量大大增加。因此，在计算效率和工作日历的精细化程度之间需要进行适当权衡。

作业车间调度求解方法主要有最优化方法、启发式方法、仿真方法、专家系统方法、神经网络方法、智能搜索方法等。最优化方法通过数学规划方法获取最优调度方案，仅适用于求解小规模调度问题。启发式方法基于调度规则获取近似调度方案，缺乏对整体性能的有效把握和预见能力，在实际应用中常将它与其他方法结合使用。仿真方法通过对实际生产环境的建模来模拟实际生产过程从而得到近似调度方案，仿真结论往往因模型不同而不同，很难获得一个一致的结论[8]。专家系统通过基于知识的系统根据车间信息选择最好的调度规则从而得到近似调度方案，但开发周期长、成本高昂，需要丰富的调度经验知识，对新的环境适应性较差。人工神经网络方法通过模仿生物神经系统来获取调度方案，仅适用于解决实验环境下规模较小的问题[9]。目前作业车间调度应用较多的求解方法是智能搜索方法，包括遗传算法[10-11]、禁忌搜索算法[12]、模拟退火算法[13]、蚁群搜索算法[14]、粒子群搜索算法[15]、蜂群搜索算法[16]、蝙蝠算法[17]及其混合算法等[18-19]。其中，遗传算法因其有较好的全局搜索性能、鲁棒性好、可扩展性好等优点被广泛用于求解作业车间调度问题。

基于以上分析，针对混合工作日历下作业车间调度问题，笔者提出了一种遗传进化优化方法。

1 数学优化模型构建

1.1 问题描述

车间需在c台设备(编号依次为1,2,…,c)上安排m个工件(编号依次为1,2,…,m)的加工任务。假设：①各设备按事先被指定的工作日历运行。本文的工作日历是工作制和工作时段的合称。一旦某设备的工作制和工作时段被设定，则该设备在同一个调度周期内每个工作日均按相同且固定不变的工作时段运行。②各设备采用的工作日历不尽相同。③各工件的工艺流程事先被确定。④各工件每道工序所用设备事先被唯一确定。⑤各工序在指定设备上的调整时间和加工时间事先被确定。⑥工件加工是非抢占式的，即当一个工件正在加工时，不能停下来加工其他工件。⑦设备调整或工件加工可跨越设备停工时段，即当设备按工作日历停工时，设备停止调整、工件停止加工，待设备重新开工时继续未完成的工作。⑧设备初始状态时其时间轴连续，即尚未被安排任何任务。⑨调度从调度起始时刻往后进行，该调度起始时刻由调度人员给定。要求：在以上假设条件下进行合理调度，在满足一定约束条件下使生产周期最短。

1.2 符号定义

表1给出了本文涉及参数的定义。

表1 相关参数

1.3 优化模型

以生产周期最短为优化目标，建立一类混合工作日历作业车间调度优化模型。

(1)目标函数

(1)

(2)约束条件

tsbij≥tcei(j-1)若Ji工序j采用设备p,工序j-1采用设备q加工且p=q

(2)

tcbij≥tcei(j-1)若Ji工序j采用设备p,工序j-1采用设备q加工且p≠q

(3)

At(tcbij～tceij)=ctij∀i,j

(4)

At(tsbij～tseij)=stij∀i,j

(5)

tsbij∈Wktseij∈Wktcbij∈Wktceij∈Wk∀i,j,Jij所用设备号为k

(6)

tsbij≥bttseij≥bttcbij≥bttceij≥bt∀i,j

(7)

式(1)表示生产周期最小化，这里的生产周期是指m个工件的加工结束时刻与最早的设备调整时刻之间的日历时间；式(2)表示若Ji的工序j-1与工序j所用设备相同(p=q)，由于设备被占用无法提前调整，故工序j必须在工序j-1加工结束时刻之后才能开始设备调整；式(3)表示若Ji工序j-1与j工序所用设备不同(p≠q)，则工序j可以提前开始进行设备调整以保证工序j-1加工结束后它能尽快开始加工；式(4)表示任意工序的加工开始时刻与加工结束时刻之间的有效工作时间等于其加工时间；式(5)表示任意工序的设备调整开始时刻与结束时刻之间的有效工作时间等于其调整时间；式(6)表示任意工序的设备调整开始时刻和结束时刻、加工开始时刻和结束时刻必须落入所用设备的工作时段内；式(7)表示任意工序的设备调整开始时刻不能早于给定的调度起始时刻bt。

从以上优化模型可以看出，该调度优化模型不是常规的线性规划模型，约束条件式(4)～式(6)不属于常规约束条件。相对于传统的作业车间调度问题，该问题具有更高的复杂性，适合采用智能搜索算法求解。本文选用遗传算法对上述优化模型进行求解。

2 基于工作日历的时间推算方法

混合工作日历下作业车间调度的关键问题是如何基于工作日历进行时间推算。按照假设条件①，本文的工作日历是工作制和工作时段的合称。基于此，本文用Excel设计了若干张工作表，每张工作表对应一个工作制，在此基础上设计设备工作表，在其中将工作制指定给各设备，并为其设置工作时段，最后利用Excel VBA设计了推算函数实现基于工作日历的时间推算。

2.1 工作日历设计

(1)工作制设计。以6天工作制为例，设计名称为6天工作制的工作表，其结构见图1。A～D列设置非周末但不工作的日期，E～H列设置周末但要工作的日期。

ABCDEFGH1序号日期周几备注序号日期周几备注212017/1/2112017/1/76322017/1/27522017/1/146︙︙︙︙︙︙︙︙︙

图16天工作制工作表

Fig.1Sixdayworkingsystemsheet

(2)工作制及工作时段设置。设计设备工作表，其结构见图2。D列为设备工作制，E列为日工作时段数，F列为日工作时间，从G列开始的各列为各工作时段的开工、停工时刻。工作时段须成对输入，范围从0:00～24:00，须保证各工作时段的停工时刻大于开工时刻且各工作时段之间不能有交叉。

ABCDEFGHIJKL1设备号设备代码设备类别工作制时段数时间开工停工开工停工开工停工21300T车床5天工作制288:0012:0013:0017:0032T52车床6天工作制3210:007:008:0015:0016:0023:00︙︙︙︙︙︙︙︙︙︙︙︙︙

图2设备工作表

Fig.2Machinessheet

2.2 基于工作日历的时间推算函数设计

以Excel VBA为平台设计了6个函数实现时间推算，分别是Isworkday、Nextworkday、Getsd、Forwardwd、Backwd和Getat。

(1)Isworkday函数。该函数有2个参数，md(Date型)和wds(String型)，其作用是根据设备工作制wds判断日期md是否为其工作日，若是工作日则返回1，否则返回0。

(2)Nextworkday函数。该函数有3个参数，md(Date型)、x(Integer型)和wds(String型)，其作用是获得根据设备工作制wds从日期md推算x天后的工作日，x>0时为正向推算，x<0时为反向推算。

(3)Getsd函数。该函数有2个参数，t(Double型)、mn(Integer型)，其作用是根据设备mn的工作时段获得时间t所在的位置，其返回值为数组A，该数组有2个元素，A(2)是标志元素，其值为0表示时间t属于设备mn第A(1)个非工作时段，其值为1则表示时间t属于设备mn第A(1)个工作时段。在图3中，该设备的工作日有2个工作时段，8:00～12:00(编号为1)和13:00～17:00(编号为2)，它们把时间0:00～24:00划分成5个时间段，另外3个时间段为非工作时段，0:00～8:00(编号为0)、12:00～13:00(编号为1)、17:00～24:00(编号为2)。

图3 某设备工作时段与非工作时段Fig.3 Work time and non-work time periods of a machine

(4)Forwardwd函数。该函数有3个参数，mdt(Date型)、tt(Double型)和mn(Integer型)，其作用是根据设备mn的工作日历获得从某个工作时刻mdt正向推算tt小时后的工作时刻。

(5)Backwd函数。该函数有3个参数，mdt(Date型)、tt(Double型)和mn(Integer型)，其作用是根据设备mn的工作日历获得从某个工作时刻mdt反向推算tt小时后的工作时刻。

(6)Getat函数。该函数有2个参数，mdt(Date型)和mn(Integer型)，其作用是根据设备mn的工作日历获得从某个时刻mdt正向推算得到的最早工作时刻。

3 遗传算法设计

针对混合工作日历下作业车间调度问题的特点，以Excel VBA为平台设计了一种遗传进化算法(genetic algorithm，GA)。

3.1 相关工作表设计

除2.1节设计的工作制工作表和设备工作表外，根据需要，设计了参数设置、工件、工艺流程、进化过程、最优解等工作表，用于输入参数的设置和进化结果的输出。

3.2 定义类型、变量及数组

根据需要，定义了图4所示的自定义类型mach、proc、job、chr和表2所示的全局变量及数组。其中，chr.R为tpnum×10的矩阵，1～10列依次存储任务序号、工件号、工序号、设备号、调整时间、加工时间、设备调整开始时刻、设备调整结束时刻、加工开始时刻、加工结束时刻。MA为mnum×22的数组(按8个工作时段设计，当然还可以增加列数从而增加工作时段)，用于存储各设备的参数。JB为jnum个元素的数组，其元素类型为job，用于存储各工件的参数。MMB为mnum个元素的数组，其元素类型为mach，用于存储调度前各设备的时间状态。算法流程见图5。

图4 自定义类型

图5 算法流程Fig.5 Flow of the algorithm

3.3 获取参数

从工作表中读取相关参数赋给表1中的变量。其中，MA从设备工作表读取第2行及以后的数据。MMB按如下方法赋值：按照假设条件⑧，调度初始时刻各设备时间轴连续，假设条件⑨表明调度从调度起始时刻bt往后进行，因此在本算法中采用for循环为各设备的空闲时间段各赋两个元素，bt和tln。以设备i为例，令MMB(i).TS(1)=bt，MMB(i).TS(2)=tln。JB按如下方法赋值：采用For循环从1～jnum分别对JB的每一个元素赋值。对工件i，先从工作表“工件”中读取第i个工件的工件名称、型号、工序数分别赋给JB(i).name，JB(i).type、JB(i).pnum，再用RedimJB(i).PR(JB(i).pnum)重新定义JB(i).PR的维数，再用for循环从工作表“工艺流程”中读取该工件对应工序参数分别赋给JB(i).PR(1)～JB(i).PR(JB(i).pnum)。

3.4 编码方式

采用基于工序的编码方式对个体进行编码：

(8)

ch.R为tpnum×10的矩阵，第2列为编码所用，基因值为1～jnum的随机整数，各整数出现的次数等于对应工件的工序数，其他各列为辅助或解码所用。

3.5 种群初始化

按照图6所示的流程分别产生popsize个随机可行个体，依次存入种群OLDPOP，从而完成种群初始化。图中，给第4列赋设备号的方法如下：根据工件号R(i,2)、工序号R(i,3)直接从JB对象数组中读取。例如，对于第i行，有R(i,4)=JB(R(i,2)).PR(R(i,3)).mn。

图6 产生随机个体流程Fig.6 Flow of generating random individuals

3.6 遗传操作

(1)遗传操作流程。本文设计的遗传操作流程见图7。

图7 遗传操作流程Fig.7 Flow of genetic operation

(2)交叉操作。根据个体编码方式的特点，为减少计算次数，基于遗传算子改进策略，采用基于工序顺序的交叉方式来保证子代个体可行性[20]。具体方法如下：同一工件的工序之间具有先后顺序，为保证交叉操作不破坏这种先后顺序，固定某父体的某个工件号所在行内容(工件号、工序号和设备号)不变，从上到下依次用另一父体中除该工件号所在行之外的其他行取代本父体剩余行。例如：

(9)

若P1.R中固定工件1，P2.R中固定工件2不动，则P1.R与P2.R交叉后的结果如下所示：

(10)

(3)变异操作。与交叉操作类似，为减少计算次数，基于遗传算子改进策略，采用基于工序顺序的变异方式来保证子代个体可行性[20]。具体方法如下：随机产生一个1,2,…,tpnum之间的整数mp作为变异点，以此点为基准向上向下分别寻找与该点工件号相同的最近位置s1和s2，若向上没有找到则令s1=0，向下没有找到则令s2=tpnum+1；取k1=s1+1，k2=s2-1，随机产生k1～k2的整数k，将该工件号、工序号及设备号滑移至k位置。例如，式(3)中，若P1′.R中假定mp=3，则可求得k1=2,k2=8，若随机产生的整数k=6，则P1′.R变异后的结果如下所示：

(11)

3.7 解码操作

解码操作的目的是根据ch.R的前4列及相关参数，从前到后依次安排每个加工任务，确定ch.R的第5～10列。由于本文优化目标是求生产周期最短化，为了尽可能缩短生产周期，采用如下两种措施。第一种是将工序时间细分为设备调整时间和加工时间，使得下道工序的设备调整工作有条件提前进行，从而使上道工序加工完毕后能尽早开始加工[21-22]；第二种是采用正向可插入式挤压调度方法，采用“见缝插针”的方式在设备的时间轴上安排工序，以便尽可能减少设备空闲时间。解码操作流程见图8，对应函数为Decode。

图8 解码操作流程Fig.8 Flow of decoding operation

解码第一步：将解码前设备时间状态对象数组MMB赋给MM，将ch.R赋给R。

解码第二步：令i=1，2，…，tpnum，从前往后依次安排各工序，确定ch.R的第5～10列值。此步又分为以下5个子步骤。

(1)获取设备调整时间st和加工时间ct。这一步可直接从JB读出，即st=JB(R(i,2)).PR(R(i,3)).st，ct=JB(R(i,2)).PR(R(i,3)).ct。

(2)获取工件R(i,2)的工序R(i,3)设备最早可开始调整时刻g。如图9所示，分三种情况分别处理。

图9 获取工件R(i,2)的工序R(i,3)的设备最早可开始调整时刻gFig.9 Obtaining the machines’ earliest start time g of the process R(i,3) of job R(i,2)

情况1：R(i,3)=1时，即待安排工序是工件R(i,2)的第1道工序。若不考虑设备的工作日历和已占用时间，则该工序的最早可开始设备调整时刻与调度起始时刻相等，故取g=bt。

情况2：R(i,3)≠1且工件R(i,2)的工序R(i,3)与R(i,3)-1均在同一台设备p上加工。这种情况下，工件R(i,2)的工序R(i,3)必须等到工序R(i,3)-1完工后才能开始设备调整，故取g等于工件R(i,2)的工序R(i,3)-1的加工结束时刻。设工件R(i,2)的工序R(i,3)-1在R中的行号为h，则取g=Getat(R(h,10),R(i,4))。

情况3：R(i,3)≠1且工件R(i,2)的工序R(i,3)与R(i,3)-1不在同一台设备上加工。此时工件R(i,2)的工序R(i,3)-1可从R(i,3)-1的加工结束时刻提前st小时开始设备调整，待设备调整完毕，工序R(i,3)-1正好完成加工，使工序R(i,3)可立即开始加工。设工件R(i,2)的工序R(i,3)-1在R中的行号为h，则首先采用Getat函数根据设备R(i,4)的工作日历正向推算得到工作时刻t(工序R(i,3)-1的加工结束时刻未必在R(i,4)的工作时间段内，其最早可能开始加工时刻为正向推算得到的工作时刻t)，再利用Backwd函数从t反向推算st小时得到设备最早可开始调整时刻g。具体地，第一步，令t=Getat(R(h,10),R(i,4))；第二步，令g=Backwd(t,st,R(i,4))。

(3)获得设备R(i,4)当前空闲时间段数赋给frnum。方法如下：令frnum=Ubound(MM(R(i,4)).TS)/2。

(4)令tb=MM(R(i，4)).TS(2k-1)，te=MM(R(i，4)).TS(2k)，Δ=te-tb。

(5)令k=1～frnum，依次判断是否Δ大于等于ct且te大于等于g，若不满足上述必要条件，则考虑下一个空闲时间段；否则将g和tb的最大值赋给t1。令tsb=Getat(t1,R(i,4))得到设备调整开始时刻，再令tse=Forwardwd(tsb,st,R(i,4))得到设备调整结束时刻，令tcb=Getat(tse,R(i,4))得到工序加工开始时刻，令tce=Forwardwd(tcb,ct,R(i,4))得到工序加工结束时刻，然后判断tce是否小于等于te。若不满足上述条件，则转向下一个空闲时间段；若满足条件则表示当前工序可插入设备R(i,4)的第k个空闲时间段。将ct,st,tsb,tse,tcb,tce依次存入R(i,5)～R(i,10)，并更新MM(R(i,4)).TS。

图10 更新MM1(R(i,4)).TSFig.10 Updating MM(R(i,4)).TS

图10为更新MM(R(i,4)).TS的示意图。MM(R(i,4)).TS的初始长度为2，仅包含2个元素，第1个为调度起始时刻bt，第2个为时间大值tln。此时空闲时间段数frnum=1。当为设备R(i,4)安排某工序a后，需在bt～tln之间插入2个值，分别是tsba(设备调整开始时刻)和tcea(加工结束时刻)。此时bt～tln被分割成2个空闲时间段，分别是bt～tsba和tcea～tln，空闲时间段数frnum=2。当再为R(i,4)安排某工序b后(假设工序b安排在工序a加工结束时刻之后)，空闲时间段分别为bt～tsba、tcea～tsbb、tceb～tln，空闲时间段数frnum=3。依次类推，随着工序的不断安排，MM(R(i,4)).TS的长度动态变化、元素动态更新。需说明的是：若tcea=tsbb则MM(R(i,4)).TS数据结构仍旧不变，空闲时间段数和空闲时间段保持不变。只是第2个空闲时间段的时间差为0，在后续的工序安排中，由解码操作流程可以看出不会在tcea～tsbb之间插入工序。设插入时段为设备R(i,4)的第k个空闲时段，则更新MM(R(i,4)).TS的步骤如下：首先，将MM(R(i,4)).TS的长度增加2位；然后，从k空闲时段对应的第2个数据起，将后面的数据后移2位，从而腾出两个空位；最后，在两个空位处分别填入待插入工序的设备调整开始时刻和加工结束时刻。

解码第三步：当把1～tpnum个工序全部安排完毕后，将得到的调度数组R及MM赋给ch。即令ch.R=R,ch.MMA=MM。至此，解码操作结束。

3.8 计算适应度

计算个体适应度的流程见图11。首先，利用解码函数Decode对个体ch进行解码得到调度数组ch.R，然后采用for循环找出ch.R第7列的最小值赋给smin、第10列的最大值赋给smax，再计算目标值ch.o，ch.o=smax-smin。由于本文优化目标是生产周期的最小化，故适应度值需由优化目标转化为最大化值。转化的方法一般有两种，一种是取倒数，另一种是用足够大的正数减去目标值。本文采用第二种方法计算适应度，用大数ln减去目标值ch.o得到适应度，即ch.fit=ln-ch.o。

图11 计算适应度流程图Fig.11 Flow of calculating the fitness

4 案例分析

某机加车间在某调度周期内要在9台设备上安排15个工件的加工，工件信息见表3、工艺流程见表4，设备信息见表5。本例中设备所用工作制共有3种，即5天工作制、6天工作制和7天工作制。对于5天工作制，由于非周末节假日不工作，故将表6的非周末节假日填入工作表5天工作制的A～D列；由于周六、周日不工作，故将E～H列留空。对于6天工作制，将表6的非周末节假日填入工作表6天工作制的A～D列；将表7中所列周六需工作的日期填入工作表6天工作制的E～H列。同理，对于7天工作制，将表6的非周末节假日填入工作表7天工作制的A～D列；将表7中所列周六需工作的日期填入工作表7天工作制的E～H列，再将表8所列周日需工作的日期填入7天工作制E～H列；其他参数见表9。

表3 工件

表4 工艺流程

表5 设备

表6 非周末节假日

表7 周六需工作的日期

表8 周日需工作的日期

表9 计算参数

图12为某次独立进化的进化过程图。表10是本次进化得到的最优调度方案对应的调度表。图13、图14分别为该最优调度方案对应的工件甘特图和设备甘特图。由表10第22行可以看出，工序J4.3在设备3(代码为200T)上加工，其设备调整起始时刻为2017/3/7 16:24、结束时刻为2017/3/8 0:18，虽然2017/3/7 16:24至2017/3/8 0:18之间的日历时间远大于0.9小时，但根据该设备的工作日历可知，2017/3/7 16:24至2017/3/8 0:18的工作时间为0.9小时，正好于设备调整时间0.9小时吻合。同样，表10的第3行可以看出，工序J4.1在设备1(代码为300T)上加工，其工序加工起始时刻为2017/3/3 10:42、结束时刻为2017/3/7 11:06，虽然2017/3/3 10:42至2017/3/7 11:06之间的日历时间远大于16.4小时，但其工作时间却只有为16.4小时(其中，从表5～表7可以看出，2017/3/4、2017/3/5是设备300T的休息日)，也正好与工序的加工时间16.4小时相吻合。以上表明算法在工序的安排过程考虑了设备的工作日历(包括工作制和工作时段)，使得设备调整起止时刻、工序加工起止时间与实际情况完全吻合。

图12 某次进化过程Fig.12 An evolutionary process

图13 工件甘特图Fig.13 Gantt chart of the jobs

图14 设备甘特图Fig.14 Gantt chart of the machines

序号任务工件工序设备设备代码调整时间加工时间调整开始时刻调整结束时刻加工开始时刻加工结束时刻1J1.1111300T0.911.22017/3/1 8:002017/3/1 8:542017/3/1 8:542017/3/2 13:062J8.1811300T0.94.82017/3/2 13:062017/3/2 14:002017/3/2 14:002017/3/3 9:483J4.1411300T0.916.42017/3/3 9:482017/3/3 10:422017/3/3 10:422017/3/7 11:064J14.11413200T0.95.82017/3/1 9:002017/3/1 9:542017/3/1 9:542017/3/1 15:425J4.2422T521.211.22017/3/7 9:542017/3/7 11:062017/3/7 11:062017/3/8 0:186J9.1911300T0.95.82017/3/7 11:062017/3/7 12:002017/3/7 13:002017/3/8 9:487J5.1511300T0.911.12017/3/8 9:482017/3/8 10:422017/3/8 10:422017/3/9 14:488J15.11512T520.96.22017/3/1 8:002017/3/1 8:542017/3/1 8:542017/3/1 16:069J2.1211300T0.913.72017/3/9 14:482017/3/9 15:422017/3/9 15:422017/3/13 13:2410J5.2522T520.98.92017/3/9 13:542017/3/9 14:482017/3/9 14:482017/3/10 1:42

(续表)

序号任务工件工序设备设备代码调整时间加工时间调整开始时刻调整结束时刻加工开始时刻加工结束时刻11J7.1711300T0.96.52017/3/13 13:242017/3/13 14:182017/3/13 14:182017/3/14 11:4812J8.2822T520.97.82017/3/3 8:542017/3/3 9:482017/3/3 9:482017/3/3 18:3613J15.21521300T0.952017/3/14 11:482017/3/14 13:422017/3/14 13:422017/3/15 9:4214J6.1611300T0.911.72017/3/15 9:422017/3/15 10:362017/3/15 10:362017/3/16 15:1815J11.11111300T0.96.42017/3/16 15:182017/3/16 16:122017/3/16 16:122017/3/17 14:3616J12.11213200T0.95.62017/3/1 15:422017/3/1 16:362017/3/1 16:362017/3/2 5:1217J8.3833200T0.962017/3/3 16:062017/3/3 17:002017/3/4 0:002017/3/4 6:0018J6.2622T520.911.52017/3/16 14:062017/3/16 15:002017/3/16 16:002017/3/17 4:3019J5.3533200T1.262017/3/10 0:302017/3/10 1:422017/3/10 1:422017/3/10 7:4220J14.21422T520.95.82017/3/1 16:062017/3/1 17:002017/3/1 17:002017/3/1 22:4821J12.21222T520.94.82017/3/2 4:182017/3/2 5:122017/3/2 5:122017/3/2 11:0022J4.3433200T0.96.12017/3/7 16:242017/3/8 0:182017/3/8 0:182017/3/8 6:2423J11.21123200T0.96.52017/3/17 13:422017/3/17 14:362017/3/17 14:362017/3/18 4:0624J6.3633200T0.98.42017/3/18 4:062017/3/18 5:002017/3/18 5:002017/3/18 14:2425J12.31231300T0.97.22017/3/17 14:362017/3/17 15:302017/3/17 15:302017/3/20 14:4226J1.2122T520.98.62017/3/2 12:122017/3/2 13:062017/3/2 13:062017/3/2 22:4227J6.4644J50010.913.32017/3/18 13:302017/3/18 14:242017/3/18 14:242017/3/19 5:4228J3.1311300T0.97.22017/3/20 14:422017/3/20 15:362017/3/20 15:362017/3/21 14:4829J13.11312T520.96.22017/3/2 22:422017/3/3 0:362017/3/3 0:362017/3/3 6:4830J2.2222T520.97.92017/3/13 12:302017/3/13 13:242017/3/13 13:242017/3/13 22:1831J11.31132T520.96.52017/3/18 3:122017/3/18 4:062017/3/18 4:062017/3/18 11:3632J7.2722T520.96.52017/3/14 10:542017/3/14 11:482017/3/14 11:482017/3/14 19:1833J1.3133200T1.213.22017/3/2 15:482017/3/2 17:002017/3/3 0:002017/3/3 14:1234J7.3733200T0.94.82017/3/14 16:062017/3/14 17:002017/3/15 0:002017/3/15 4:4835J4.4444J50010.98.32017/3/8 5:302017/3/8 6:242017/3/8 6:242017/3/8 16:4236J10.11011300T0.97.52017/3/21 14:482017/3/21 15:422017/3/21 15:422017/3/22 15:1237J12.41249111CNC1.282017/3/20 13:302017/3/20 14:422017/3/20 14:422017/3/21 4:4238J13.21321300T0.94.52017/3/22 15:122017/3/22 16:062017/3/22 16:062017/3/23 11:3639J7.4745J40011.25.62017/3/14 15:482017/3/14 17:002017/3/15 8:002017/3/15 14:3640J6.56563U51.511.62017/3/17 16:302017/3/17 18:002017/3/20 0:002017/3/20 13:3641J15.31533200T0.97.22017/3/15 7:482017/3/15 9:422017/3/15 9:422017/3/15 16:5442J12.51255J40011.28.22017/3/20 15:482017/3/20 17:002017/3/21 8:002017/3/22 8:1243J15.41544J50010.95.52017/3/15 16:002017/3/15 16:542017/3/15 16:542017/3/15 22:2444J14.31433200T0.96.32017/3/2 5:122017/3/2 6:062017/3/2 6:062017/3/2 13:2445J9.2922T520.98.32017/3/8 8:542017/3/8 9:482017/3/8 9:482017/3/8 19:0646J13.31333200T0.94.92017/3/23 10:422017/3/23 11:362017/3/23 11:362017/3/23 16:3047J2.3233200T1.29.92017/3/13 15:482017/3/13 17:002017/3/14 0:002017/3/14 10:5448J11.41143200T0.97.12017/3/18 14:242017/3/18 15:182017/3/18 15:182017/3/20 5:2449J1.4144J50010.99.92017/3/3 13:182017/3/3 14:122017/3/3 14:122017/3/4 2:0650J1.51563U51.57.32017/3/3 16:302017/3/3 18:002017/3/6 0:002017/3/6 7:1851J3.2322T520.96.22017/3/21 13:542017/3/21 14:482017/3/21 14:482017/3/21 22:0052J13.41344J50010.97.22017/3/23 14:362017/3/23 16:302017/3/23 16:302017/3/24 0:4253J9.3933200T0.95.32017/3/8 16:062017/3/8 17:002017/3/9 0:002017/3/9 5:1854J3.3333200T1.28.52017/3/21 15:482017/3/21 17:002017/3/22 0:002017/3/22 9:3055J11.51158120CNC1.152017/3/18 15:542017/3/18 17:002017/3/20 8:002017/3/20 14:0056J11.61169111CNC1.2102017/3/21 4:422017/3/21 5:542017/3/21 5:542017/3/21 17:5457J11.711772U51.26.52017/3/21 15:482017/3/21 17:002017/3/22 8:002017/3/22 15:3058J14.41445J40011.29.82017/3/2 11:122017/3/2 13:242017/3/2 13:242017/3/3 15:12

(续表)

序号任务工件工序设备设备代码调整时间加工时间调整开始时刻调整结束时刻加工开始时刻加工结束时刻59J6.6669111CNC1.211.82017/3/21 17:542017/3/22 1:062017/3/22 1:062017/3/22 14:5460J4.54563U51.515.32017/3/8 15:122017/3/8 16:422017/3/8 16:422017/3/9 16:0061J5.4545J40011.213.82017/3/9 15:482017/3/9 17:002017/3/10 8:002017/3/11 14:4862J14.51454J50010.96.82017/3/4 2:062017/3/4 3:002017/3/4 3:002017/3/4 10:4863J5.5558120CNC1.172017/3/11 13:422017/3/11 14:482017/3/11 14:482017/3/13 13:4864J9.4948120CNC1.162017/3/8 15:542017/3/8 17:002017/3/9 8:002017/3/9 15:0065J15.515563U51.27.82017/3/15 16:482017/3/15 18:002017/3/16 0:002017/3/16 7:4866J10.21022T520.94.92017/3/22 14:062017/3/22 15:002017/3/22 16:002017/3/22 20:5467J3.4344J50010.916.32017/3/22 8:362017/3/22 9:302017/3/22 9:302017/3/23 3:4868J3.53563U51.57.82017/3/23 2:182017/3/23 3:482017/3/23 3:482017/3/23 13:3669J4.6469111CNC1.26.22017/3/9 14:482017/3/9 16:002017/3/9 16:002017/3/10 4:1270J2.4244J50010.911.62017/3/14 10:002017/3/14 10:542017/3/14 10:542017/3/15 0:3071J8.48463U51.28.22017/3/6 7:182017/3/6 9:302017/3/6 9:302017/3/7 0:4272J1.6168120CNC1.18.52017/3/4 15:542017/3/4 17:002017/3/6 8:002017/3/7 8:3073J10.31033200T0.95.52017/3/22 16:062017/3/22 17:002017/3/23 0:002017/3/23 5:3074J10.41048120CNC1.14.82017/3/22 15:542017/3/22 17:002017/3/23 8:002017/3/23 13:4875J9.59572U51.27.92017/3/9 13:482017/3/9 15:002017/3/9 15:002017/3/10 14:5476J7.5754J50010.98.62017/3/15 22:242017/3/16 0:182017/3/16 0:182017/3/16 9:5477J8.58572U51.28.62017/3/6 15:482017/3/6 17:002017/3/7 8:002017/3/8 8:3678J2.52572U51.29.32017/3/14 15:482017/3/14 17:002017/3/15 8:002017/3/16 9:18

从表10第3行、5行、22行、35行、60行、69行可以看出，工件4有6道工序，分别在不同的设备上加工，因此可以提前进行设备调整，当上道工序完成加工时，可立即开始下道工序的加工，采用这种安排方式在一定程度上缩短了生产周期。其他工件在安排工序时与工件4采用了相同的处理方式。

从表10可以看出，按序号升序排列，设备8(代码为120CNC)上安排的工序依次为J11.5、J5.5、J9.4、J1.6、J10.4，而从图14可以看出，设备8上从左到右安排的工序依次为J1.6、J9.4、J5.5、J11.5、J10.4，二者不一定完全一致。产生这种现象的原因在于解码过程中采用了正向可插入式挤压调度方法，可以尽可能地减少设备空闲时间从而缩短生产周期。

5 结语

为解决混合工作日历下作业车间调度的困难，提出了一种遗传进化方法，该方法突破了传统作业车间调度的局限，能在可接受的计算时间内得到有效的作业车间优化调度方案。在该方法中，对于工序起止调整时刻、起止加工时刻的计算采用自定义的时间推算函数进行准确推算，能保证混合工作日历下作业车间调度方案的可行性。在解码过程中采用了两项技术用以缩短生产周期：将工序时间细分为设备调整时间和加工时间，能使下道工序的设备可提前开始设备调整；采用正向可插入式挤压调度方法安排工序。