考虑准备时间和加工速度的纺织纤维实验加工调度

黄基诞，李 楠，晏爱敏，黄晓虎

（东华大学a.旭日工商管理学院；b.信息科学与技术学院，上海200051）

0 引 言

在平行机调度研究中，准备时间（安装时间）分两大类，一是准备时间与次序无关［1］，准备时间可视为实验任务加工时间的一部分来考虑；二是准备时间与次序相关时［2］，准备时间（安装时间）就会对调度结果产生影响，无法忽略。如何解决准备时间（安装时间）与次序相关的调度问题引起了学术界广泛的研究兴趣。具有与次序相关的准备时间（安装时间）的加工调度问题作为一类较为复杂的问题，在制造与实验领域中有着广泛的应用。Ozcan［3］考虑了一类安装时间与次序相关的装配调度。Sarahi等［4］考虑了安装时间与次序相关的平行机调度问题，并建立了混合整数规划模型。Shen等［5］在柔性车间模型中考虑了安装时间与次序相关的调度问题并讨论了问题的下界。

纺织纤维实验中制造或加工各类新型纤维需要有准备时间，而且该准备时间与纤维有关［6］，故安装时间与加工的材料次序相关；当他属于同种产品加工的时候，准备时间较少；否则具有复杂的准备时间，比如更换和清洗组件等操作。机器更换组件造成的准备时间是本文讨论实验的特征，可以视为依赖于任务序列的准备时间。金辉等［7］研究了涤纶短纤维制造过程中的管理优化，并提出基于TS/VDS算法对该调度问题进行优化。金辉等［8］继续针对纺丝组件更换比较耗时特点，提出了用数学动态规划法求解组件更换调度问题。随后陆晨［9］对化纤的制造特点和特征进行分析。

随着科技的发展及新问题的不断出现，近些年又出现一批新的算法，如灰狼优化算法［10］、烟花算法［11］，萤火虫算法［12］等.这些算法的优点是能够在很短的时间内给出接近最优的解。文献［13］中提出一种启发式算法：正弦余弦算法（Sine Cosine Algorithm，SCA）。该算法数学模型简单、参数设置少、且容易实现，仅仅通过正余弦函数值的波动变化来实现最优解的搜索。虽然SCA已被证明在部分问题优化、收敛速度、精度等方面均优于经典算法如遗传算法（GA）、粒子群算法（PSO）等［13］，但是也存在易出现早熟收敛缺点。已有学者将它用于电力系统经济调度［14］和应用反向学习改进SCA算法［15］。本文将改进正弦余弦算法（Improved Sine Cosine Algorithm，ISCA）求解实验排程，并取得了比较好的效果。

1 问题描述及数学模型

纺织学院所有学生（主要是硕士、博士）都有一个共享的纤维加工和制造实验室，供学生完成自己所需的实验新型纤维材料加工实验（以下简称实验）。研究一个时间周期内有N个实验（纤维加工实验）需要在M台机器上加工，每台机器加工速度不一致，机器m都有自己恒定的加工速度为vm，不失一般性，假定机器的加工速度v1≥v2≥…≥vM。并根据实际情况考虑每个实验i的教师布置时间（下达时间）ri，同时考虑加工不同纤维时机器需要更换和清洗组件的准备时间，正常情形下进行的每个实验任务i所需时间为～pi和教师要求正常完成实验期限di。要求实验室管理老师设计一个调度方案使得最小化最大完工时间最小。

1.1 模型假设

问题基于以下基本假设：

（1）每个实验的信息已知，即加工时间和交付期等信息；

（2）每台机器在任意时刻只能进行一个实验；

（3）机器一旦开始某个实验，中途不可中断；

（4）计划周期的初始时刻所要求做的实验材料已到位；

（5）除了一个实验与接下来另一个实验有转化组件间歇，机器的实验加工速率恒定并可持续工作。

1.2 参数符号

本文其他所使用的符号如下：

i—实验任务编号，0为虚拟初始实验任务。

B—机器的集合。m为机器的编号，m∈B，B＝｛1，2，…，M｝。

I—实验的集合，N为最后一个实验；i，j∈I，I＝｛1，2…，N｝。

ti，j，m—实验i完成后紧接着实验j在机器m的准备所需时间，其中t0，i，m为在机器m上的初始实验i的准备时间。

L—一个足够大的正数。

1.3 决策变量

pi，m—实验i在机器m的实验时间，其中，pi，m＝i/vm。

Xi，j，m∈｛0，1｝—如果实验任务i的在机器m上完成后，紧接着做实验任务j，则Xi，j，m＝1；否则为0。

δi，m∈（0，1）—如果实验任务i的在机器m上加工，则δi，m＝1；否则为0。

Si，m—机器m对实验任务i开始时间。

Ci，m—机器m对实验任务i完成时间。

Cmax—最大完工时间，即最后一个实验任务完成时间。

1.4 目标函数

目标函数是最小化最大完工时间。

式（2）为最大完工时间不小于每个实验i的完成时间。式（3）为实验i在机器m上加工的完成时间和开始时间的关系。式（4）为实验i开始时间必须大于等于实验布置时间（下达时间）。式（5）为实验i和实验j在同一台机器上加工，先后顺序时间限制。式（6）为实验i完成时间必须小于教师要求的时间。式（7）为实验i在机器m上的加工时间计算方式。式（8）～（11）为实验i的只能在某一台机器上加工，并且只加工一次。式（12）为决策变量的取值范围。

2 正弦余弦算法（SCA）

在SCA［14］中，当正余弦函数系数大于1或者小于-1时，进行全局寻优；当正余弦函数系数介于-1到1之间时，进行局部寻优。该算法最大的特点是利用正余弦函数值的波动来实现最优解搜寻。在SCA中，假设种群规模为N，优化问题的每个解对应搜索空间（维度为d）中对应个体的位置，并Xi＝｛xi1，xi2，…，xid｝，表示第i（i＝1，2，…，N）个个体的位置，当前所有个体经过的最好位置表示为X*，在每一次迭代中，群体中个体均按如下更新位置［11-13］，即：

式中：t为当前迭代次数；为阈值，本文取值为0.5。为3个随机参数［14-15］，1称为控制参数，是一个关键参数，会影响算法全局寻优和局部搜寻最优解的性能。2的定义［14-16］如下：

式中：t为目前迭代次数；α＞0为预设的常数；T为最大迭代次数。标准SCA算法流程或伪代码参见文献［13-14］。

3 改进的正弦余弦算法（ISCA）

3.1 编码方式

假设有N个实验任务，按实验的下达时间排序（如果下达时间一样，按实验任务从大到小排序）。为了编程方便，本文采用2N维实数位置向量表示N个实验任务和M台机器的调度序列。向量中的2N维实数的取值范围是［1，M+1），M表示机器数量。编码分成两个部分，前N位表示实验任务加工顺序；后N位的整数部分表示N个实验任务分配在哪台机器上加工。

3.2 解码方式

用一个例子说明编/解码的过程。例如有2台机器处理4个实验任务（按释放时间排序）：v1＝1，v2＝2，，（r1，r2，r3，r4）＝（2，3，4，5），为了简明扼要地说明问题，暂时都假设ti，j，m＝2，编码信息见表1。

表1 4个任务2个机器的编码信息

解码：

（1）取前N位，这里4个实验（N＝4），取前4位，根据数字的大小排序，得出加工顺序：1⇒3⇒4⇒2。

（2）然后，取接下来的N位（N＝4）整数部分，计算出每个实验任务被分配的机器号。这里有4个实验，表1分别列出第1、3个实验的在机器2（见图1中M2）加工，第2、4实验任务在机器1（见图1中M1）上加工。

图1 2台平行机4个实验任务的调度方案

3.3 差分变异策略

差分进化算法优点是具有强大的寻优能力，收敛速度快。为了快速引导群体找到最优解，本文在差分进化算法的基础上提出了差分变异策略：

3.4 改进正弦余弦算法（ISCA）流程

综上所述，纺织纤维实验排程调度的ISCA流程可描述如下：

步骤1初始化种群Xi，（i＝1，2，…，n），如种群规模NP，问题维数D、阈值，最大迭代次数等参数T、预设常数a等。

步骤3利用式（14）计算控制参数1。

步骤4随机产生参数4，根据概率值大小按式（13）进行个体更新，然后计算整个种群的最优值。将现有函数值与上一代最优值进行比较，若前者较好，则改变当前最优值，则接受新解。

步骤5对当前粒子进行差分变异机制的扰动，扰动后与当前质量最优的粒子进行比较；若较好，则改变当前最优值，选择接受新解，并用较好的个体进行替换。

步骤6判断当前粒子的适应度是否优于之前种群的全局最优解。若是，将当前的粒子的适应度值替换为全局最优解。

步骤7若未达到最大迭代次数，则返回步骤3；否则，输出全局最优位置。

4 仿真实验

为验证算法寻优性能，分小数据和大数据两部分进行试验。算法采用Matkab2014a编程，实验运行环境为：CPU 2.1 GHz，内存4 GB，Windows7 操作系统（64 bit）。

4.1 问题松弛的下界分析

定理1由于实验布置时间是随机的，如果最后一个实验下达时间远远大于此前其他实验下达时间；即假设最后一个实验下达时，其他先前实验都完成了，将最后一个实验安排到速度最快的机器1上加工，显然是最优解的一个下界：

定理2由于实验纤维种类是随机的，故松弛2个条件。假设本周期内所有的实验都是一个类型的，实验之间的切换时间可以忽略不计，那么只有一次准备时间；还有一个松弛条件，所有的机器加工速度都是一样的，都是最快的那种机器。该问题的下界为那么下界又可以表示为：

目前我国的教育对口支援主要有三种模式，包含教育部直接组织施行的对口支援、内地省市对西部地区的对口支援以及西部省（市、自治区）组织的大中城市对口支援工作。[1]从支援少数民族高校的政策发展历史中，可以看到国家对支援工作的重视程度。

4.2 评判指标

（1）将任一算法alg所求得的解的质量用相对偏差RPD指标来衡量：

式中：faig为算法alg中计算获得的目标函数值；LB*＝max（LB1，LB2）。本文运行5 次，取平均值Avg.RPD。Avg.RPD值越小，说明算法alg所得解的目标值越接近下界，表明解的质量越好。

（2）Time（s）：CPU平均运行时间，指算法求得最优解所花费的平均计算时间，算例运行5次，取5次的平均计算时间。

4.3 实验参数

本实验用ERD（Earliest Release Date）规则来做其中的对比之一。ERD规则（先到先服务规则）：实验根据下达时间从小到大排序，然后依次选择机器最空闲进行加工；若多于一个实验任务释放时间相同，则选择加工时间长的实验任务先进行加工。本文采用随机测试算例，算例规模和参数见表2。

各算法的参数设置见表3。其中c1和c2为粒子群算法中的学习因子，ω为PSO中的惯性权重。

表2 算例的参数分类和取值范围

表3 算法参数设置

4.4 实验分析

对于上述实例用ISCA、SCA和PSO 3种算法进行求解，并对实验结果做参照对比。由于篇幅有限，就算法收敛曲线图各随机选取2组：N＝200，M＝3和N＝100，M＝3。

从图2、3分别在N＝100和N＝200的两种情况下描绘了算法的收敛曲线；从图中可以看出，当达到一定的迭代次数的时候，优化目标无法再改进。另一方面，可以看出，SCA和PSO算法有着类似的收敛速度，而ISCA的收敛性能明显优于SCA和PSO。

图2 3台机器100个实验任务的算法收敛曲线图

图3 3台机器200个实验任务的算法收敛曲线图

通过不同规模下的实验，很好地验证了改进正余弦算法的有效性。从表4中的第3和第6列可以看出，该算法比我们经常在实际中用的ERD模式的RPD节约4%，说明各算法运行的稳定性较好，而且解的质量令人满意。

表4 各算法的性能指标比较

5 结 语

本文探讨了准备时间具有次序有关的短纤维加工实验调度，建立了混合整数规划模型，设计了ISCA进行求解，数值实验表明所建立的模型能有效地减少实验之间切换所必需的准备时间；达到减少整体实验完成时间，最终达到减少损耗和提高实验设备利用率；同时也证明了所设计的算法的有效性能。为今后存在类似有次序有关的准备时间的实验排程比如生物实验等方面提供参考。