一种两阶段装配流水车间调度方法

摘要

本发明属于车间调度技术领域，具体的说是一种两阶段装配流水车间调度方法。该方法包括以下步骤：步骤一、建立不同交货期窗口约束下的两阶段装配流水车间调度的目标函数；步骤二、确定调度过程的约束条件；步骤三、采用基于细胞受体的人工免疫系统算法求解所述目标函数，经过迭代运算，将满足停止条件的解解码后作为最终的调度方案。本发明是一种基于细胞受体的人工免疫系统算法获得工作加工最优调度的两阶段装配流水车间调度方法，解决了现有技术在求解不同交货期窗口约束下的两阶段装配流水车间调度问题时无法求解大规模问题、收敛精度低、收敛速度慢的问题。

说明书

技术领域

本发明属于车间调度技术领域，具体的说是一种两阶段装配流水车间调度方法。

背景技术

两阶段装配流水车间调度问题(Two-stage Assembly Flowshop SchedulingProblem,TSAFSP)是一种车间调度问题，广泛存在于各种生产过程中，如计算机制造和消防车生产等。经典TSAFSP包括制造与装配两个阶段，其中制造阶段有m台并行同速机，装配阶段只有一台装配机。一个工件的加工工艺包含m+1项操作，其中m项操作在制造阶段进行，而后经过装配操作将零部件组装成最终工件。当制造阶段机器的数量为2时，该问题就被证实为NP-hard问题，所以TSAFSP是一个NP-hard问题。经典TSAFSP调度问题对实际问题做了较大的简化，然而实际生产环境要复杂的多，出于理论研究和工程实际的需要，研究者提出了各种TSAFSP调度问题模型进行研究。首先，制造阶段每项操作加工处理的零件可以是多个同类型的零件，如果将每项操作理解为一个批次的话，每项操作可以拆分为多个小的批次，并在不同的并行同速机上进行加工，这更贴近实际生产情况。其次，由于零件类型的不同及拆分的处理，准备时间应当从加工时间中分离出来，在每项操作前都会有相应的准备时间。另外，之前大多数的研究成果在考虑工件交货期约束时，将其视为一个时间点。然而，在制造业生产中，工作更倾向于被要求在一个时间窗口内完成。工作早于这个时间窗口的起始时间完工的话，会产生库存成本；而晚于这个时间窗口结束时间完工的话，会产生延迟费。如何综合考虑上述实际生产因素，科学地制定车间调度方案，对于降低生产管理成本、提高机器利用率、和满足客户个性化的收货时间窗需求起着至关重要的作用。

两阶段装配流水车间调度方法的研究最初主要应用动态规划、分支定界等精确算法，但这些方法通常计算时间较长，不适用于求解大规模问题。今年来，随着计算智能方法的发展，越来越多的智能优化算法，如变领域搜索算法(International Journal ofProduction Research,2014,52(19):5626-5639)、粒子群优化算法(Computers&Operations Research,2009,36(9):2682-2689)、模拟退火算法(Advances inEngineering Software,2010,41(10):1238-1243)被应用于求解两阶段装配流水车间调度问题。但这些算法由于收敛能力不足，对于上述更接近实际环境的两阶段装配流水车间问题，不能在规定的时间内求得满意解。

发明内容

本发明提供了一种基于细胞受体的人工免疫系统算法(RAIS)获得工作加工最优调度的两阶段装配流水车间调度方法，解决了现有技术在求解不同交货期窗口约束下的两阶段装配流水车间调度问题时无法求解大规模问题、收敛精度低、收敛速度慢的问题。

本发明技术方案结合附图说明如下：

一种两阶段装配流水车间调度方法，该方法包括以下步骤：

步骤一、建立不同交货期窗口约束下的两阶段装配流水车间调度的目标函数；

步骤二、确定调度过程的约束条件；

步骤三、采用基于细胞受体的人工免疫系统算法即RAIS算法求解所述目标函数，经过迭代运算，将满足停止条件的解解码后作为最终的调度方案。

步骤一中所述的目标函数如下：

i为工件号，n为工件个数；

α_i为工件i的单位提前惩罚成本，β_i为工件i的单位滞后惩罚成本；

E_i为工件i的提前时间，T_i为工件i的滞后时间；

Z为提前与滞后惩罚成本加权和。

步骤二中所述的约束条件包括：

零件在并行同速机上不同位置约束：

零件拆分处理约束：

M×x_jtk≥q_jtk>

q_jtk-1≥M×(x_jtk-1)>

同一并行同速机不同位置上的零件完工时间约束：

C_0k＝0>

工件在装配机不同位置约束：

装配机不同位置上的工件完工时间约束：

C_r≥F_i+A_i-M×(1-y_ir)i,r＝1,2,...,n(13)

工件提前成本与滞后成本约束：

E_i≥e_i-C_r-M×(1-y_ir)i,r＝1,2,...,n(15)

T_i≥C_r-d_i-M×(1-y_ir)i,r＝1,2,...,n(16)

E_i≥0i＝1,2,...,n(17)

T_i≥0i＝1,2,...,n(18)

上述公式(2)～(18)中，存在以下决策标量：

r为装配机上工件加工的位置号；

m为并行同速机个数；

k为并行同速机号；

h为总的零件种类数；

j为零部件种类号；

t为并行同速机上零件加工的位置号；

J_i为工件i的零件种类集；

s_1j为加工零件j前的准备时间；

q_1j为零件j的总个数；

p_1j为零件j的单个加工时间；

s_2i为加工工件i前的准备时间；

A_i为工件i的装配时间；

e_i为工件i交货期窗口的起始时间；

d_i为工件i交货期窗口的结束时间；

C_tk为并行同速机k位置t上的零件的完工时间；

C_(t-1)k为并行同速机k位置t-1上的零件的完工时间；

C_0k为并行同速机k位置0上的完工时间即机器未进行加工状态下的时间点；

F_i为工件i进行装配操作的最早开始时间；

C_r为装配机位置r上的工件的完工时间；

C_r-1为装配机位置r-1上的工件的完工时间；

q_jtk为并行同速机k位置t上的零件j的个数；

M为一个足够大的正整数；

在上述公式(2)～(18)中，存在以下决策变量：

所述的步骤三的具体方法如下：

用RAIS求解不同交货期窗口约束下的TSAFSP包括编码、解码和适应度值计算的操作；

31)编码时，每个受体采用基于工件序列的编码，记作(π₁,π₂,...,π_n)，即加工位置i处的工件为π_i；

32)解码时，每个受体的解码步骤如下：

步骤3.2.1：依据公式(2)～(10)，采用拆分法确定每台并行同速机上零件种类、数量和完工时间；

a.设定i＝1,转b；

b.计算其中CT_0k＝0，如果i≤n，则计算并对TP_j按从大到小排序得转c；如果i＝n+1，则停止；

c.设定t＝1，MCT_k＝0(k＝1,2,...,m)转d；

d.令w为min(MCT₁,MCT₂,...,MCT_m)的机器号，如果q_1t′＝0，则令t＝t+1转d；如果同时满足q_1t′＞0，则q′_tw＝q′_1t，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，令t＝t+1转d；如果同时满足q_1t′＞0，则q_1t′＝q_1t′-q_tw′，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，转d；如果同时满足q_1t′＞0，则q_tw′＝q_1t′，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw令t＝t+1转d；如果且q_1t′＝0，则i＝i+1转b；

步骤3.2.1中存在以下决策标量：

i为工件加工位置号，j为零件号，k为并行同速机器号；

为加工位置号为i的工件的零件在制造阶段的完工时间下界；

CT_ik为加工位置号为i的工件的零件在并行同速机k上的最大完工时间；

CT_iw为加工位置号为i的工件的零件在并行同速机w上的最大完工时间；

CT_(i-1)k为加工位置号为i-1的工件的零件在并行同速机k上的最大完工时间；

为装配工件π_i所需的零件种类数；

为工件π_i的零件j的不拆分总处理时间；

为装配工件π_i所需的种零件中，第t大的不拆分总处理时间；

MCT_k为并行同速机k的完工时间；

MCT_w为并行同速机w的完工时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的总个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件在并行同速机w上的个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的准备时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的单个加工时间；

为对数a向上取整；

步骤3.2.2：依据公式(11)～(14)，采用空闲时间插入法确定装配机上工件的完工时间：

a.设定i＝1，ACT＝0，转b；

b.判断i≤n，如果不满足，设定i＝n，ξ_r＝0(r＝1,2,...,n)，l＝1，FJ_l＝LJ_l＝i转c；否则判断满足则ACT＝C_i，不满足则ACT＝C_i；令i＝i+1转b；

c.判断i≥1，如果不满足，则停止；否则判断i＝n，如果满足，则ξ_i＝1，否则判断如果满足，则ξ_i＝ξ_i+1，FJ_l＝i，否则ξ_i＝ξ_i+1+1，l＝l+1，FJ_l＝LJ_l＝i转d；

d.令σ_l＝{r|ξ_r＝ξ_i,r＝1,2,...,n}，若则若则若则η_r＝0；计算判断如果满足，则i＝i-1转c，否则转e；

e.若则若则Δ_1r＝M；若则判断ξ_i＝1，如果满足，则Δ_2l＝M，如果不满足，转f；

f.若则C_r＝C_r+Δ_2l，ξ_r＝ξ_r-1，FJ_l-1＝FJ_l，l＝l-1转c；若则转c；

CT_i1为加工位置号为i的工件的零件在并行同速机1上的最大完工时间；

CT_i2为加工位置号为i的工件的零件在并行同速机2上的最大完工时间；

CT_im为加工位置号为i的工件的零件在并行同速机m上的最大完工时间；

C_i为装配机位置i上的工件的完工时间；

C_i+1为装配机位置i+1上的工件的完工时间；

为加工工件π_i前的准备时间；

为加工工件π_i+1前的准备时间；

为加工工件前的准备时间；

为工件π_i的装配时间；

为工件π_i+1的装配时间；

为工件的装配时间；

ACT为装配机的完工时间；

ξ_i为装配机上加工位置号为i的工件的标记号；

ξ_i+1为装配机上加工位置号为i+1的工件的标记号；

ξ_r为装配机上加工位置号为r的工件的标记号；

l为集合σ_l的标记号；

FJ_l为标记号为l的工件集中最早进行装配的工件的加工位置号；

FJ_l-1为标记号为l-1的工件集中最早进行装配的工件的加工位置号；

LJ_l为标记号为l的工件集中最晚进行装配的工件的加工位置号；

为装配机位置LJ_l上的工件的完工时间；

为装配机位置LJ_l-1上的工件的完工时间；

为工件π_r的单位提前惩罚成本；

为工件π_r的单位滞后惩罚成本；

η_i为装配机上加工位置号为i的工件的完工时间增加一个单位造成的成本减少值；

η_r为装配机上加工位置号为r的工件的完工时间增加一个单位造成的成本减少值；

为工件π_r交货期窗口的起始时间；

为工件π_r交货期窗口的结束时间；

σ_l为标记号为l的工件集；

Δ_1r为工件在不改变其完工状态(提前、滞后或如期完工)时，完工时间允许的最大增加值；

Δ_2l为集合σ_l中的工件在不影响其他工件集中的工作时，完工时间允许的最大增加值。

步骤3.2.3：依据公式(1)和(15)～(18)计算目标函数；

33)由于优化目标为提前和滞后惩罚成本加权和最小，采用目标函数的倒数作为适应度函数对每个受体进行评价；

34)RAIS算法求解不同交货期窗口约束下的TSAFSP的步骤如下：

步骤3.4.1：随机初始化NB个B细胞受体和NT个T细胞受体种群，转步骤3.4.2；

步骤3.4.2：采用选择和插入的方式对B细胞受体和T细胞受体种群进行基因再排列：首先将当前适应度值最高的受体作为标准受体，然后从其他受体的工件序列中随机选择R个加工位置号，将这R个加工位置号上对应的工件分别插入到其在标准受体中的加工位置上，若这个新的工件序列解码的适应度值大于被选择的受体适应度值，则更新被选择的受体，否则被选择的受体保持不变，转步骤3.4.3；

步骤3.4.3：比对B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，如果存在工件相同，则B细胞与T细胞发生同源相互作用，转步骤4.4.4，否则B细胞与T细胞不发生同源相互作用，转步骤3.4.6；

步骤3.4.4：采用部分随机排序的方式对B细胞受体进行细胞突变：对比B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，工件相同情况下组成的加工位置号集合为工件不相同情况下组成的加工位置号集合为δ，集合中加工位置号上工件保持不变，对集合δ中加工位置号上的工作重新随机排序生成新的集合δ′，若解码的适应度值大于被选择的B细胞受体适应度值，则更新被选择的B细胞受体，否则被选择的B细胞受体保持不变，转步骤3.4.5；

步骤3.4.5：采用交换、插入、和颠倒的领域搜索机制对B细胞受体进行抗体转换：由于B细胞在T细胞受体的帮助下可以大量分化为分泌IgG、IgA、和IgE形态抗体的浆细胞进而消灭抗原，所以对被选择的B细胞受体，分别以1/3的概率进行交换、插入、或颠倒搜索进而达到局部最优，每个被选择的B细胞受体共进行I次抗体转换，若抗体转换后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤3.4.7；

步骤3.4.6：采用插入和交换的领域搜索机制对B细胞受体进行IgM抗体转换：由于B细胞在不与T细胞发生同源相互作用时，只是表达IgM抗体，提供一个快速的早期防御机制，所以被选择的B细胞受体先进行插入，再做交换，若IgM抗体的表达后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤3.4.7；

步骤3.4.7：当前适应度值最高的受体保持不变，其他受体重新随机生成，转3.4.8；

步骤3.4.8：判断是否满足预先设定的最长CPU运行时间T_max，如果满足，将当前最好的解作为最优解，得到最终的调度方案并停止，如果不满足转步骤3.4.2。

本发明的有益效果为：

1.本发明采用拆分法对制造阶段零部件进行加工安排，可以提高解的质量；

2.本发明采用空闲时间插入法对装配阶段工件进行安排，可以提高解的质量；

3.本发明引入T细胞对B细胞的帮助过程，通过判断它们之间是否发生同源相互作用，将B细胞的增值分化分为两个方向：1.先进行细胞突变，再抗体转换；2.只表达IgM抗体，在保证解的收敛的速度的同时提高了收敛精度。

附图说明

图1为本发明中基于细胞受体的人工免疫系统算法的实现流程示意图；

图2为4工件基因再排列示意图；

图3为4工件细胞突变示意图；

图4为4工件9零件实例最优调度甘特图。

具体实施方式

参阅图1，一种两阶段装配流水车间调度方法，该方法包括以下步骤：

步骤一、建立不同交货期窗口约束下的两阶段装配流水车间调度的目标函数；

步骤一中所述的目标函数如下：

i为工件号，n为工件个数；

α_i为工件i的单位提前惩罚成本，β_i为工件i的单位滞后惩罚成本；

E_i为工件i的提前时间，T_i为工件i的滞后时间；

Z为提前与滞后惩罚成本加权和。

步骤二、确定调度过程的约束条件；

步骤二中所述的约束条件包括：

零件在并行同速机上不同位置约束：

零件拆分处理约束：

M×x_jtk≥q_jtk>

q_jtk-1≥M×(x_jtk-1)>

同一并行同速机不同位置上的零件完工时间约束：

C_0k＝0>

工件在装配机不同位置约束：

装配机不同位置上的工件完工时间约束：

C_r≥F_i+A_i-M×(1-y_ir)>

工件提前成本与滞后成本约束：

E_i≥e_i-C_r-M×(1-y_ir)i,r＝1,2,...,n(15)

T_i≥C_r-d_i-M×(1-y_ir)i,r＝1,2,...,n(16)

E_i≥0i＝1,2,...,n(17)

T_i≥0i＝1,2,...,n(18)

上述公式(2)～(18)中，存在以下决策标量：

r为装配机上工件加工的位置号；

m为并行同速机个数；

k为并行同速机号；

h为总的零件种类数；

j为零部件种类号；

t为并行同速机上零件加工的位置号；

J_i为工件i的零件种类集；

s_1j为加工零件j前的准备时间；

q_1j为零件j的总个数；

p_1j为零件j的单个加工时间；

s_2i为加工工件i前的准备时间；

A_i为工件i的装配时间；

e_i为工件i交货期窗口的起始时间；

d_i为工件i交货期窗口的结束时间；

C_tk为并行同速机k位置t上的零件的完工时间；

C_(t-1)k为并行同速机k位置t-1上的零件的完工时间；

C_0k为并行同速机k位置0上的完工时间即机器未进行加工状态下的时间点；

F_i为工件i进行装配操作的最早开始时间；

C_r为装配机位置r上的工件的完工时间；

C_r-1为装配机位置r-1上的工件的完工时间；

q_jtk为并行同速机k位置t上的零件j的个数；

M为一个足够大的正整数；

在上述公式(2)～(18)中，存在以下决策变量：

步骤三、采用基于细胞受体的人工免疫系统算法即RAIS算法求解所述目标函数，经过迭代运算，将满足停止条件的解解码后作为最终的调度方案；

基于细胞受体的人工免疫系统算法的设计来源于自然免疫系统中的适应性免疫应答过程。在适应性免疫应答过程中，B细胞与T细胞共同发现并消灭侵入人体的病原菌，其中B细胞受体和T细胞受体起到关键性作用，它们的发展过程如下：

a：B细胞和T细胞在最初淋巴器官内经过基因再排列产生相应的抗原受体，而后B细胞会离开骨髓进入周边淋巴组织，T细胞会离开胸腺进入第二淋巴组织；

b：B细胞利用其表面受体蛋白质抓住胞外抗原后进入附近第二淋巴组织，在那里与T细胞受体接触并比对它们辨识的抗原构造；

c：如果B细胞受体与T细胞受体辨识的抗原相同，即它们发生同源相互作用，则B细胞会在T细胞的诱导下发生细胞突变，带有高亲和力受体的B细胞存活下来并分化为分泌抗体的浆细胞，B细胞受体从而以可溶型蛋白质-抗体的形式存在，包括IgG、IgA、和IgE共三种形态的抗体；如果B细胞受体与T细胞受体辨识的抗原不同，则B细胞只表达IgM抗体；

d：清除亲和力低的B细胞和T细胞。

所述的步骤三的具体方法如下：

用RAIS求解不同交货期窗口约束下的TSAFSP包括编码、解码和适应度值计算的操作；

31)编码时，每个受体采用基于工件序列的编码，记作(π₁,π₂,...,π_n)，即加工位置i处的工件为π_i；

32)解码时，每个受体的解码步骤如下：

步骤3.2.1：依据公式(2)～(10)，采用拆分法确定每台并行同速机上零件种类、数量和完工时间；

a.设定i＝1,转b；

b.计算其中CT_0k＝0，如果i≤n，则计算并对TP_j按从大到小排序得转c；如果i＝n+1，则停止；

c.设定t＝1，MCT_k＝0(k＝1,2,...,m)转d；

d.令w为min(MCT₁,MCT₂,...,MCT_m)的机器号，如果q_1t′＝0，则令t＝t+1转d；如果同时满足q_1t′＞0，则q′_tw＝q′_1t，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，令t＝t+1转d；如果同时满足q_1t′＞0，则q_1t′＝q_1t′-q_tw′，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，转d；如果同时满足q_1t′＞0，则q_tw′＝q_1t′，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw令t＝t+1转d；如果且q_1t′＝0，则i＝i+1转b；

步骤3.2.1中存在以下决策标量：

i为工件加工位置号，j为零件号，k为并行同速机器号；

为加工位置号为i的工件的零件在制造阶段的完工时间下界；

CT_ik为加工位置号为i的工件的零件在并行同速机k上的最大完工时间；

CT_iw为加工位置号为i的工件的零件在并行同速机w上的最大完工时间；

CT_(i-1)k为加工位置号为i-1的工件的零件在并行同速机k上的最大完工时间；

为装配工件π_i所需的零件种类数；

为工件π_i的零件j的不拆分总处理时间；

为装配工件π_i所需的种零件中，第t大的不拆分总处理时间；

MCT_k为并行同速机k的完工时间；

MCT_w为并行同速机w的完工时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的总个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件在并行同速机w上的个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的准备时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的单个加工时间；

为对数a向上取整；

步骤3.2.2：依据公式(11)～(14)，采用空闲时间插入法确定装配机上工件的完工时间：

a.设定i＝1，ACT＝0，转b；

b.判断i≤n，如果不满足，设定i＝n，ξ_r＝0(r＝1,2,...,n)，l＝1，FJ_l＝LJ_l＝i转c；否则判断满足则ACT＝C_i，不满足则ACT＝C_i；令i＝i+1转b；

c.判断i≥1，如果不满足，则停止；否则判断i＝n，如果满足，则ξ_i＝1，否则判断如果满足，则ξ_i＝ξ_i+1，FJ_l＝i，否则ξ_i＝ξ_i+1+1，l＝l+1，FJ_l＝LJ_l＝i转d；

d.令σ_l＝{r|ξ_r＝ξ_i,r＝1,2,...,n}，若则若则若则η_r＝0；计算判断如果满足，则i＝i-1转c，否则转e；

e.若则若则Δ_1r＝M；若则判断ξ_i＝1，如果满足，则Δ_2l＝M，如果不满足，转f；

f.若则C_r＝C_r+Δ_2l，ξ_r＝ξ_r-1，FJ_l-1＝FJ_l，l＝l-1转c；若则转c；

步骤3.2.2中存在以下决策标量：

CT_i1为加工位置号为i的工件的零件在并行同速机1上的最大完工时间；

CT_i2为加工位置号为i的工件的零件在并行同速机2上的最大完工时间；

CT_im为加工位置号为i的工件的零件在并行同速机m上的最大完工时间；

C_i为装配机位置i上的工件的完工时间；

C_i+1为装配机位置i+1上的工件的完工时间；

为加工工件π_i前的准备时间；

为加工工件π_i+1前的准备时间；

为加工工件前的准备时间；

为工件π_i的装配时间；

为工件π_i+1的装配时间；

为工件的装配时间；

ACT为装配机的完工时间；

ξ_i为装配机上加工位置号为i的工件的标记号；

ξ_i+1为装配机上加工位置号为i+1的工件的标记号；

ξ_r为装配机上加工位置号为r的工件的标记号；

l为集合σ_l的标记号；

FJ_l为标记号为l的工件集中最早进行装配的工件的加工位置号；

FJ_l-1为标记号为l-1的工件集中最早进行装配的工件的加工位置号；

LJ_l为标记号为l的工件集中最晚进行装配的工件的加工位置号；

为装配机位置LJ_l上的工件的完工时间；

为装配机位置LJ_l-1上的工件的完工时间；

为工件π_r的单位提前惩罚成本；

为工件π_r的单位滞后惩罚成本；

η_i为装配机上加工位置号为i的工件的完工时间增加一个单位造成的成本减少值；

η_r为装配机上加工位置号为r的工件的完工时间增加一个单位造成的成本减少值；

为工件π_r交货期窗口的起始时间；

为工件π_r交货期窗口的结束时间；

σ_l为标记号为l的工件集；

Δ_1r为工件在不改变其完工状态(提前、滞后或如期完工)时，完工时间允许的最大增加值；

Δ_2l为集合σ_l中的工件在不影响其他工件集中的工作时，完工时间允许的最大增加值。

步骤3.2.3：依据公式(1)和(15)～(18)计算目标函数；

33)由于优化目标为提前和滞后惩罚成本加权和最小，采用目标函数的倒数作为适应度函数对每个受体进行评价；

34)RAIS算法求解不同交货期窗口约束下的TSAFSP的步骤如下：

步骤3.4.1：随机初始化NB个B细胞受体和NT个T细胞受体种群，转步骤3.4.2；

步骤3.4.2：采用选择和插入的方式对B细胞受体和T细胞受体种群进行基因再排列：首先将当前适应度值最高的受体作为标准受体，然后从其他受体的工件序列中随机选择R个加工位置号，将这R个加工位置号上对应的工件分别插入到其在标准受体中的加工位置上，若这个新的工件序列解码的适应度值大于被选择的受体适应度值，则更新被选择的受体，否则被选择的受体保持不变，转步骤3.4.3；

步骤3.4.3：比对B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，如果存在工件相同，则B细胞与T细胞发生同源相互作用，转步骤4.4.4，否则B细胞与T细胞不发生同源相互作用，转步骤3.4.6；

步骤3.4.4：采用部分随机排序的方式对B细胞受体进行细胞突变：对比B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，工件相同情况下组成的加工位置号集合为工件不相同情况下组成的加工位置号集合为δ，集合中加工位置号上工件保持不变，对集合δ中加工位置号上的工作重新随机排序生成新的集合δ′，若解码的适应度值大于被选择的B细胞受体适应度值，则更新被选择的B细胞受体，否则被选择的B细胞受体保持不变，转步骤3.4.5；

步骤3.4.5：采用交换、插入、和颠倒的领域搜索机制对B细胞受体进行抗体转换：由于B细胞在T细胞受体的帮助下可以大量分化为分泌IgG、IgA、和IgE形态抗体的浆细胞进而消灭抗原，所以对被选择的B细胞受体，分别以1/3的概率进行交换、插入、或颠倒搜索进而达到局部最优，每个被选择的B细胞受体共进行I次抗体转换，若抗体转换后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤3.4.7；

步骤3.4.6：采用插入和交换的领域搜索机制对B细胞受体进行IgM抗体转换：由于B细胞在不与T细胞发生同源相互作用时，只是表达IgM抗体，提供一个快速的早期防御机制，所以被选择的B细胞受体先进行插入，再做交换，若IgM抗体的表达后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤3.4.7；

步骤3.4.7：当前适应度值最高的受体保持不变，其他受体重新随机生成，转3.4.8；

步骤3.4.8：判断是否满足预先设定的最长CPU运行时间T_max，如果满足，将当前最好的解作为最优解，得到最终的调度方案并停止，如果不满足转步骤3.4.2。

实施例

本实施例是将RAIS算法应用到两阶段装配流水车间调度中，该车间生产4种工件，分别为工件A,B,C,D,其中装配工件A需要零件1,2，工件B需要零件3,4，工件C需要零件5,6,7，工件D需要零件8,9，工件的准备时间s_2i、加工时间A_i、单位提前惩罚成本α_i、单位滞后惩罚成本β_i、交货期窗口的起始时间e_i、和交货期窗口的结束时间d_i，零件的准备时间s_1j、总个数q_1j、和单个加工时间p_1j等加工参数如表1所示，且该车间有3台并行同速机M₁,M₂,M₃，一台装配机A。

表1工件与零件加工相关参数表

RAIS算法的解决不同交货期窗口约束下的两阶段装配流水车间调度方法，具体包括以下步骤：

(1)：对两阶段装配流水车间调度问题进行数学描述，并确立评价指标：提前与滞后惩罚成本加权和Z；

定义如下决策标量：

i为工件号；

r为装配机上工件加工的位置号；

n为工件个数；

j为零件种类号；

t为并行同速机上零件加工的位置号；

h为总的零件种类数；

J_i为工件i的零件种类集；

k为并行同速机号；

m为并行同速机个数；

s_1j为零件j零件的准备时间；

q_1j为零件j的总个数；

p_1j为零件j的单个加工时间；

s_2i为加工工件i的准备时间；

A_i为工件i的装配时间；

e_i为工件i交货期窗口的起始时间；

d_i为工件i交货期窗口的结束时间；

α_i为工件i的单位提前惩罚成本；

β_i为工件i的单位滞后惩罚成本；

E_i为工件i的提前时间；

T_i为工件i的滞后时间；

C_tk为并行同速机k位置t上的零件的完工时间；

C_(t-1)k为并行同速机k位置t-1上的零件的完工时间；

C_0k为并行同速机k位置0上的完工时间(即机器未进行加工状态下的时间点)；

F_i为工件i进行装配操作的最早开始时间；

C_r为装配机位置r上的工件的完工时间；

C_r-1为装配机位置r-1上的工件的完工时间；

q_jtk为并行同速机k位置t上的零件j的个数；

M为一个足够大的正整数；

定义如下决策变量：

(2)：建立目标函数；

(3)：建立约束条件；

M×x_jtk≥q_jtkj,t＝1,2,...,h,k＝1,2,...m(6)

q_jtk-1≥M×(x_jtk-1)j,t＝1,2,...,h,k＝1,2,...m(7)

C_0k＝0k＝1,2,...,m(8)

C_r≥F_i+A_i-M×(1-y_ir)i,r＝1,2,...,n(11)

E_i≥e_i-C_r-M×(1-y_ir)i,r＝1,2,...,n(15)

T_i≥C_r-d_i-M×(1-y_ir)i,r＝1,2,...,n(16)

E_i≥0i＝1,2,...,n(17)

T_i≥0i＝1,2,...,n(18)

上述表达式中：式(2)表式一台并行同速机上的一个加工位置上的零件种类小于等于1；式(3)表示一种类型的零件在一台并行同速机上的加工位置个数小于等于1；式(4)表示如果同一台并行同速机某一位置上没有安排零件加工，其后置位上也不会有零件加工；式(5)表示一种类型零件的总个数等于所有并行同速机上该类型零件个数之和；式(6)和式(7)表示如果零件j在并行同速机k位置t上加工，则q_jtk＞0，否则q_jtk＝0；式(8)表示并行同速机位置0上的完工时间为0；式(9)表示同一台平行同速机上后一个加工位置上的零件的完工时间大于等于该零件的准备时间、该零件单个加工时间与该零件在该机器上加工个数的乘积、和其前一个加工位置上的零件的完工时间之和；式(10)和式(11)表示工件只有在其所需的零件都加工完后才能开始装配操作；式(12)表示装配机上同一加工位置上只能有一个工件；式(13)表示一个工件在装配机上只能对应一个加工位置；式(14)表示装配机上后一个加工位置上的工件的完工时间大于等于该工件的准备时间、装配时间、和其后一个加工位置上的工件的完工时间之和；式(15)～(18)表示每个工件的提前惩罚成本与滞后惩罚成本。

(4)：针对上述两阶段装配流水车间调度问题的目标函数和约束条件，设计RAIS算法得到调度方案；

(4.1)编码时，每个受体采用基于工件序列的编码，如(A,B,C,D)表示工件的加工次序是A,B,C,D，即工件A在1号位置，B在2号位置，C在3号位置，D在4号位置；

(4.2)解码时，每个受体的解码步骤如下：

步骤4.2.1：依据公式(2)～(10)，采用拆分法确定每台并行同速机上零件种类、数量和完工时间；

a.设定i＝1,转b；

b.计算其中CT_0k＝0。如果i≤n，则计算并对TP_j按从大到小排序得转c；如果i＝n+1，则停止；

c.设定t＝1，MCT_k＝0(k＝1,2,...,m)转d；

d.令w为min(MCT₁,MCT₂,...,MCT_m)的机器号。如果q_1t′＝0，则令t＝t+1转d；如果同时满足q_1t′＞0，则q′_tw＝q′_1t，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，令t＝t+1转d；如果同时满足q_1t′＞0，则q_1t′＝q_1t′-q_tw′，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，转d；如果同时满足q_1t′＞0，则q_tw′＝q_1t′，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw令t＝t+1转d；如果且q_1t′＝0，则i＝i+1转b；

步骤4.2.1中存在以下决策标量：

i为工件加工位置号，j为零件号，k为并行同速机器号；

为加工位置号为i的工件的零件在制造阶段的完工时间下界；

CT_ik为加工位置号为i的工件的零件在并行同速机k上的最大完工时间；

CT_iw为加工位置号为i的工件的零件在并行同速机w上的最大完工时间；

CT_(i-1)k为加工位置号为i-1的工件的零件在并行同速机k上的最大完工时间；

为装配工件π_i所需的零件种类数；

为工件π_i的零件j的不拆分总处理时间；

为装配工件π_i所需的种零件中，第t大的不拆分总处理时间；

MCT_k为并行同速机k的完工时间；

MCT_w为并行同速机w的完工时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的总个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件在并行同速机w上的个数；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的准备时间；

为装配工件π_i所需的种零件中，不拆分总处理时间第t大的零件的单个加工时间；

为对数a向上取整。

步骤4.2.2：依据公式(11)～(14)，采用空闲时间插入法确定装配机上工件的完工时间：

a.设定i＝1，ACT＝0，转b；

b.判断i≤n，如果不满足，设定i＝n，ξ_r＝0(r＝1,2,...,n)，l＝1，FJ_l＝LJ_l＝i转c；否则判断满足则ACT＝C_i，不满足则ACT＝C_i；令i＝i+1转b；

c.判断i≥1，如果不满足，则停止；否则判断i＝n，如果满足，则ξ_i＝1，否则判断如果满足，则ξ_i＝ξ_i+1，FJ_l＝i，否则ξ_i＝ξ_i+1+1，l＝l+1，FJ_l＝LJ_l＝i转d；

d.令σ_l＝{r|ξ_r＝ξ_i,r＝1,2,...,n}，若则若则若则η_r＝0；计算判断如果满足，则i＝i-1转c，否则转e；

e.若则若则Δ_1r＝M；若则判断ξ_i＝1，如果满足，则Δ_2l＝M，如果不满足，转f；

f.若则C_r＝C_r+Δ_2l，ξ_r＝ξ_r-1，FJ_l-1＝FJ_l，l＝l-1转c；若则转c；

步骤4.2.2中存在以下决策标量：

ACT为装配机的完工时间；

ξ_r为装配机上加工位置号为r的工件的标记号；

l为集合σ_l的标记号；

FJ_l为标记号为l的工件集中最早进行装配的工件的加工位置号；

LJ_l为标记号为l的工件集中最晚进行装配的工件的加工位置号；

η_i为装配机上加工位置号为i的工件的完工时间增加一个单位造成的成本减少值；

σ_l为标记号为l的工件集；

Δ_1r为工件在不改变其完工状态(提前、滞后或如期完工)时，完工时间允许的最大增加值；

Δ_2l为集合σ_l中的工件在不影响其他工件集中的工作时，完工时间允许的最大增加值。

(4.3)由于优化目标为提前和滞后惩罚成本加权和最小，采用目标函数的倒数作为适应度函数对每个受体进行评价；

(4.4)如图1，RAIS算法求解不同交货期窗口约束下的TSAFSP的步骤如下：

步骤4.4.1：设置参数NB,NT,R,I,随机初始化NB个B细胞受体和NT个T细胞受体种群，计算受体群的适应度值，转步骤4.4.2；

步骤4.4.2：采用选择和插入的方式对B细胞受体和T细胞受体种群进行基因再排列：首先将当前适应度值最高的受体作为标准受体，然后从其他受体的工件序列中随机选择R个加工位置号，将这R个加工位置号上对应的工件分别插入到其在标准受体中的加工位置上，若这个新的工件序列解码的适应度值大于被选择的受体适应度值，则更新被选择的受体，否则被选择的受体保持不变，转步骤4.4.3；

例如：参阅图2，R1表示当前适应度值最高的受体，R2为基因再排列的受体，R3为新的工件序列I。受体R1为(A,B,C,D),受体R2为(A,C,D,B),从受体R2中随机选取加工位置2，由于该位置处的工件C在受体R1中位于加工位置3，所以将受体R2中的工件C插入到位置3，得到新的工件序列R1为(A,D,C,B)。

步骤4.4.3：比对B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，如果存在工件相同，则B细胞与T细胞发生同源相互作用，转步骤4.4.4，否则B细胞与T细胞不发生同源相互作用，转步骤4.4.6；

步骤4.4.4：采用部分随机排序的方式对B细胞受体进行细胞突变：对比B细胞受体与当前适应度值最高的T细胞受体在相同加工位置处的工件，工件相同情况下组成的加工位置号集合为工件不相同情况下组成的加工位置号集合为δ，集合中加工位置号上工件保持不变，对集合δ中加工位置号上的工作重新随机排序生成新的集合δ′，若解码的适应度值大于被选择的B细胞受体适应度值，则更新被选择的B细胞受体，否则被选择的B细胞受体保持不变，转步骤4.4.5；

例如：参阅图3，R4表示当前适应度值最高的T细胞受体，R5表示细胞突变的B细胞受体，R6表示新的工件序列II。受体R4为(A,B,C,D)，受体R5为(A,C,D,B)，与受体R4对比，受体R5在相同位置上相同的工件是A，相同位置上不同的工件是C,D,B，对工件C,D,B重新随机排序生成序列B,D,C，则新的工件序列R6为(A,B,D,C)。

步骤4.4.5：采用交换、插入、和颠倒的领域搜索机制对B细胞受体进行抗体转换：由于B细胞在T细胞受体的帮助下可以大量分化为分泌IgG、IgA、和IgE形态抗体的浆细胞进而消灭抗原，所以对被选择的B细胞受体，分别以1/3的概率进行交换、插入、或颠倒搜索进而达到局部最优，每个被选择的B细胞受体进行I次抗体转换，若抗体转换后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤4.4.7；

步骤4.4.6：采用插入和交换的领域搜索机制对B细胞受体进行IgM抗体转换：由于B细胞在不与T细胞发生同源相互作用时，只是表达IgM抗体，提供一个快速的早期防御机制，所以被选择的B细胞受体先进行插入，再做交换，若IgM抗体的表达后B细胞受体的适应度值提升，则更新被选择的B细胞受体，否则不变，转步骤4.4.7；

步骤4.4.7：当前适应度值最高的受体保持不变，其他受体重新随机生成，转4.4.8；

步骤4.4.8：判断是否满足预先设定的最大CPU运行时间T_max，如果满足，将当前最好的解作为最优解，得到最终的调度方案并停止，如果不满足转步骤4.4.2；

在当前的B细胞受体中选取目标函数最优的B细胞受体为(D,B,C,A)，其对应的目标函数值为19，具体的调度方案表如表2和表3所示：

表2并行同速机上各零件的种类、个数、开始时间、和完工时间

表3装配机上工件的开始时间和完工时间

最优调度甘特图如图4所示。

在本实施例中，将本方法与基于免疫球蛋白的人工免疫(IAIS)算法(AppliedSoft Computing,13(8),3729–3736)、变领域搜索(VNS)算法(European Journal ofOperational Research,130(3),449–467)进行性能比较，验证所提出的RAIS算法的有效性，实验环境采用C++语言编程，在CPU为Intel(R)Core(TM)i5-3210M 2.50GHz，内存为4.00GB的计算机上进行仿真试验。

加工参数设置：工件个数n∈{10,50,100}，并行同速机个数m∈{2,3,4}，零件的总个数q_1j＝U[2,5]，零件的单个加工时间p_1j＝U[1,6]，工件的装配时间A_i＝U[1,100]，准备时间与加工时间给出3个水平的比值：10％，20％，和30％，对应与这些比值，准备时间s_2i＝U[1,10],U[1,20],或U[1,30]，装配工件所需的零件类型数h_i＝U[2,5]。工件的单位提前惩罚成本α_i＝U[1,10]，工件的单位滞后惩罚成本β_i＝U[1,10]，交货期窗口的设置，先确定交货期窗口的中心DC＝max(0,U(PP(1-TF-RDD/2),PP(1-TF+RDD/2)))，其中滞后因素TF∈{0.2,0.6,1.0}，交货期窗口相对范围RDD∈{0.2,0.6,1.0}，PP为该车间调度问题最大完工时间的下界，工件交货期窗口的起始时间e_i＝max(0,DC-DC×H/100)；工件交货期窗口的结束时间d_i＝max(0,DC+DC×H/100)，其中交货期窗口宽度H＝U[1,10]。

RAIS算法参数设置如下：B细胞受体种群大小NB＝10，T细胞受体种群大小NT＝5，基因再排列选择工序号个数R＝n/5，抗体转换次数I＝5，最长CPU运行时间T_max＝0.2×n秒。工件个数、并行同速机个数、准备时间与加工时间的比值、滞后因素、和交货期窗口相对范围的不同组合构成3×3×3×3×3＝243种不同的问题规模，为了消除随机因素对计算结果的影响，每种问题规模下产生5个计算算例，共产生1215个算例，每个实例运行10次，并报告平均计算结果。如表4所示，其中以偏差百分比PD来表示算法的性能。

其中，Z^H表示由相关算法(VNS、IAIS、和RAIS)求得的目标函数值，Z^best表示三种算法求得的目标函数最小值。

表4针对1215个算例的运行结果比较

从表中可以看出，随着工件个数的增加，VNS、IAIS、和RAIS的偏差百分比呈增长趋势；VNS、IAIS、和RAIS的平均偏差百分比分别为188.36，6.86，和0.08，表明RAIS比VNS，IAIS有更好的求解性能。