标准混合流水车间调度问题研究

1、标准混合流水车间调度问题研究标准混合流水车间调度(Hybrid flow-shcp scheduling problem, HFSP),也称柔性 流水车间调度是一般流水车间调度的推广，工程应月背景很强，广泛存在于化工、冶 金、纺织，机械，半导体、物流、建筑、造纸等工业领域的L本文析要研究的背景企 业的生产模式就可以归结为HFSP.它综合了一般流水车向和并行机两种调度的特点, 求解睢度更大。因此，研究标准11TSP不仅具仃重要的理论意义，而且对生产也有很 高的实际价值.-股来说，标准混合流水车间调度问以技照如下方式描述：修个工件在包含 m个阶段的流水线上进行加工.每个工件都要依次通过m个阶段，每

2、个阶段至少包 含一台加工机器并且至少有一个阶段包含多台机器，同一阶段上的各机器加工工序相 同，工时可不相同.各工件的霁道T序可在相应阶段的任何一台机器上进行加工，仔 意时刻各工件至多在一台机器上加上，且每台机器同时只能加上一个工件。工件的任 何一道工序在加工过招中不允许中断.已知每个工件在各个阶段不同机器上的加工时 向，要求确定工件的加工先后顺序和每一阶段上的机器分配情况，使得某个畦能指标 最优,图工1给出了 HF$P问题的图例,其中假设有扪个阶段，每个阶段上有台 矶器，3.2模型构建(1)参数定义入工件的数目； 工件加工阶段的数目；N/t阶段j上的机器数目(14/£橇卜工件f在工序

3、/上的加工时间；(31)(3.2)(33)(3.(4)(3.(5)(3.(6)(3.(7)(3.(8)(3.(9)(3.(10)5"：工件i在工序j上的开始加工时间；Cy：工件，在工序/上的结束加工时间；Cm：工件总完工时间C2)变量定义v fo工件i未被安排在第卬个位置加工、E 1工件i被安II在第W个位置加工''y =(0工件i未在工的上的第七台机器上加工*=(1工件J在工用上的第k台机器上加工_10工件i未在工学上的第4台机器上第7顺位加工 刘二1工件i在上时上的第上台机器上第/顺位加JL(3)目标由数min J -(4)约束条件/1工几=1 w = 1,2,Z

4、I七人=1 i = 12, W-1才 =1 i = l,Z,用/ =】2,m *1m 21ZNj>m,NjNl J = /-»N,.hl />!Cv =跖乜 i = l,2,;/ = 12、mC MS” i = 1,2,，叫j =1,2,m;，= j + 1S,J >CMys=12,；)=1,2,、加；卬在之前且紧邻约束意义：式(3.1)为日标函数，这里取最小化最大完工时间为最终优化目标式(3.2)表示每个排序位置只能分配一个工件式(3.3)表示每个工件只能有一个排序位置式(14)表示任意一个工件在任何一个阶段只能由一台机器加工式(3.5)表示加工阶段至少为1式(3

5、.6)表示至少有一个阶段的机器数目大于1台式(3.7)表示工件在某台机器上的加工顺序唯一式(3.8)表示工件i在阶段J上的加工完成时间式(3.9)表示工件i在阶段j + 1上的开始加工时间不应早于在阶段/上的结束加 工时间式(3.10)表示工件i在阶段j上的开始加L时间小应早于其前一个丁件w在阶段 J上的结束加工时间3.3求解算法33.1算法总体思路及流程标准混合流水车间调度不仅要确定工件的加工顺序，还要确定每个阶段机器的分 纪情况，比一般流水车间调度问题求解更为复杂。鉴丁粒子群算法具有算法简单、所 需参数较少、收敛速度较快等优点，本章拟采用粒子群算法来求解标准混合流水车间 调度问题，同时为了

6、降低陷入局部最优的可能性，在种群更新环节引入模拟退火机制， 在一定程度上提升了所得解的质量。海合算法总体流程详见图3.2。（1）基于矩阵的编码方式参考文献57的方法，本算法采用基于矩阵的编码方式，即每个候选解都是一个 具体的机器分配矩阵.具体编码方式如式（3.n）.其中，为区间（LN/+1）上的一个实数，对外取下整数|为|则表示工件，的第/ 道工序是在第1% I台机襦上完成的。当出现1% 1=1% I、上时，即表示两个工件在问 一道T序上选择了同一台机播加工。此时,若j = 1,即处在第一阶段，则按照%的大 小来决定加工顺序,a“越大的工件优先加工：若则按照前一阶段加工结束时 间先后顺序来决定

7、加工顺序，当前一阶段加工结束时间相同时，参照阶段1的方法来进行比较，具体示例如下°假设产生的机器分配矩际为:LI 2.2 2.2A 2.1 2.3 3.2(3.12)1.6 18 12 通过上述矩阵就可以得出以下对应关系：上述矩阵首先表明了是三个T件在二个阶段上的加工问题矩阵的第一列表明工件1和工件3都在第一台机器上加工，且由于1.6X.1,故 工件3比工件1先加工。工件2的加工机器为第二台。矩阵的第二列表明工件1和工件2都在第二台机器上加工，具体先后顺序要参考 前个阶段的结束时间.工件3加工机器为第一台.矩阵的第三列表明工件1在第二台机器上加工，工件2在第三台机器上加工，工 件3在

8、第一台机器上加工。通过这种工件-机器对应关系，在已知加工时间矩阵的前挑F,就可以推算出最 大完工时间.(2)种群初始化假设种群规模为”“Me,对种群中的各个粒子进行初始赋值，即生成x/Eze个 机器分配矩阵4tM”，其中qz=l+" xrand()o(3)参数设置速度参数：速度矩阵匕，.与机器矩阵的配置相同，其中 匕=k十(%,-)xedO,乙。为速度下限，曦,为速度上限。学习因子G，G；初始化g=%m，在此后的迭代当中，学习因子不 再采用固定不变的方式，而是为了防止陷入局部垠优而采用线性时变学习因子.G = 0皿 一 (C-CeiKf)x generation! N(3.13)。2

9、 = C以 + (C5 - C*) x generation) N(3.14)其中为当前迭代次数.N为最大迭代次数.惯性权重w：这里采用线性微分递减策略M来设定惯性权重.w = Wr + (吗5 -卬2) x generational / N八2(3.15)当前粒子最优位曾R4:每个粒子对应的机器矩阵即为当前最优位置.当前粒子最优值川而。屣卯切：计算初始种群中所有粒子的最大完成时间，即为 每个粒子的pldmakespcn。全局最优位置pgd;初始种群中pldmhsp最小的粒子所对应的机器矩阵。 全局最优值pgdmakespat ：初始种群中最小的pldtnakespai。温度参数。：，。是后续

10、metropolis选齐概率中的重要参数。4 = - pgdmakespanX / ln(0.2)(3.16)(4)更新温度参数、速度、位置在进行每一次迭代时，对温度参数、种群中每一个应子的速度和位置都要进行更 新，更新公式见式(37)、(318)和(3.】9)。=也(3.17)A = A + V(3.18)V = WX 0 +CXandx(pld- 4) + C2 乂 rand 乂 (pgd 一/)(3.19)其中4和%必须在所限定的范围之内，如果超出这个范围就必须重新初始化。(5)更新 pld、pldmakespai、pgd 和 pgdmakespai在迭代过程中，对种群中的每一个粒子变换

11、位置和速度，计肆当前最大完工时间, 与当前粒子最优位置相比较，若前者较优，则将当前粒子位置赋给p/d,将当前最大 完工时间赋给pldmcikasptn 在完成一次迭代之后，选出最小pldmaktrspcn与 pgdmakcspcn相比较，若前者较小，则用彘小pld来替换pgd ,用最小pldmakc卬6来 瞽捡:pgdmakespai否则.则按.照metropolis选择概率将本次迭代最优值gm。鹿甲a”和 最优位置分别赋值给pgdmah印an和pgd。其中，metropolis选择概率公式见(320)p = exp(pgdmakexpc9i - gntakespan) f tQ )(3.20

12、)(6)算法终止条件当迭代达到最大迭代次数时，算法终止.3.4算例验证3.4.1 验证说明为验证算法的有效性，本文采用Matlab进行编程实现算法，在配置为2G内存、 2.5301kIntel双核CPU的计算机上进行实验，测试集采用文献19中的两类问题，每 类问题各计算5次，将实例1所得结果与文献19中的绍果进行比较，将实例2所得 结果与不考虑SA所得结果进行比较。具体丁时数据和计算结果见表3.1、3.2、3 3、 3.U 具体交数设置为 C“-2.5, C“-0.5, pops 法= 50, N = 2000,- 0.9 ,Ww=04,mn=2，曝ex = 2，A = 0.9 表3.1实例1

13、时数据阶段1阶段2阶段3-TtMlM2M3MlM2M3MlM2M312234532324543445436544214254434659一6585453312465665423439575244634358354751364工件阶段1阶段2阶段3MlM2M3MlM2M3MlM2M39254127865103643448671152435676512654543475表3.2实例1结果次数12345AIS27GA3027262729SFLA2424242424EDA2324232323HPSO2222232322奏3.3实例2工时数据工件阶段1阶段2阶段3阶段4MlM2M3MlM2M3MlM2M

14、lM214548503535303035252624550453536353534253035045463536363!343031450484834383532332731545464830355034322831645454530355033323026747504731303535312925850454832303434302427948464633343034302525104S47473333303s34322611465045343050303s31251248504735313532302530表3.4实例2结果次数12345PSO307313306311308HPSO306307305308305注：HPSO代表本文算法，PSO代表不考虑SA条件下的算法3.42结果分析通过表12 以发现，本文算.法在5次运行中所得结果均优于文献19中所对比 的结果，且有3次结果优于文献19°通过表3.4可以发现，考虑SA的新算法比标 准PS。算法具有更弹的寻优能力，能在一定程度上降低陷入局部最优的可能性.图 3.3、3.4分别给出了实例1问题的收敛图和甘特图。在收敛图中，横轴代表迭代代数, 纵轴代表适应值，绿线代表迭代过程中种群均值变化趋势，红线代表迭代过程中种群 最优个体适应值的变化趋势。在甘特图中，横轴代表加工时间，纵轴代表加工机器，