在多平行工作站环境下, 为使限定资源分配下的车间调度问题（Job Shop problem, JSP）具有最小总延迟时间; 同时又可设定各订单具有不同的开工日（release date）及到期日, 提出以可开工时间与结束时间为基础的分解解法, 并在遗传算法的基础上构造混合遗传算法（hybrid genetic algorithm, HGA）来实现目标设定。实验结果表明, HGA在问题求解质量与Lingo解的最佳解差异在15％以内, 并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。
690 计算机应用研究 第30卷 工3(5×[(6)/(6+8)]=2),配置两组处理单元于加工4(5-2S,1=(11,10,5,3,15),S2=(12,14,1,8,6)及S3=(9,13, 3)。根据步骤d),加工7于时点2.67完工。回到步骤a)~2,4,)。组合S1,S,及S后,即可得新的染色体组合S2= b),将加工4与9排入A,6。重复步骤a)~d),直到所有九笔(11,10,5,3,15,12,14,1,8,6,9,13,24,7 加工均完成处理。表3为各加工的开始处理时间(ST)、结束 机制1强调在较佳解中寻找可能存在的最佳解组合。比 时问(C)及延迟时间(T)的结果。 较机制1,机制2则兼顾搜寻路径的深度与广度。执行选择机 表3工数据与廷迟吋间 制1后,剩余染色体数PS×(1-a)-1的染色体尚待决定。 加工编号47982 b 机制2采用基本遗传算法屮常见的方法.包括选择、交叉、变异 02.673.33778.339.8310.6 阶段 G3.332.67 710.678.339.8312.412.3 1)选择阶段 3.332.674.333.们73.671.331.52.571.6 在选择阶段中,基本遗传算法的遺择运算是根据父代中各 d 7899 染色体所得的适合度值的优劣,决定各染色体被使用在子代中 0.330003.670.330.833.42.33 的几率。原则上适合度值较佳者,被选择到子代中的几率较 高。木文使用轮盘赌算法选择所要复制的父代染色休。 2.4适应度函数及目标值 步骤如下: 适合度函数是遗传算法用于评估每一」代解的优劣程度 a)计算各染色体的适合度。l为各染色体代号,l∈N。 的效率指标,以此决定各染色体被选择的几率。原则上适合度 b)对各染色体的适合度加总求和,求得总适合度F= 值较佳者,被选择到子代中的几率较高。为了计算适合度,必∑f。 须先根据目标函数求得各染色体的解。本文使用的目标函数 c)计算各染色体的几率prb1=∑/1F。 奴下 d)计算各染色体的累进几率P1-∑prob 总延迟时间=∑7=∑max(0,7-) e)随机产生一个介于0,1间的值Ran 适合度函数适合度函数值/=max-∑ f)当P1<Ran<P1+1,则选择第l+1染色体进行复制。 其中:max为日前群体中最大日标值;l为各染色体代号,∈N 2)交叉阶段 2.5选择 交叉是遗传算法产生适合度更高的子代染色体所采用的 选择是遗传算法产生子代的主要机制,其概念是期望父代方法。本文使用均匀交叉算子进行交叉。 屮表现较佳的染色体可被子代持续使用.进而提升子代对环境 步骤如下 的竞争适应丿。合适的选择算子可有效提升遗传算法获得最 a)随机选出父代中两组染色体(PA1及PA2) 佳解的几率与速度,否则将导致遗传算法求解过程过早收敛, b)根据染色体长度,随机产生一组二元字符串 从而失去求得最佳解的机会。为提升求解效率与质量,本算法 c)将PA1(PA2)中处于字符串1之位置的基因,移至子代 结合两种选择机訇,以使选择过程中能兼顾∫代中染色体的质 CH2(CH1)的相对位置 量与多元性,进而演化出较佳解。 d)将CH1中尚未填入基因的位(处于字符串0之位 机制1基于时间序刎的选择机制 置),依序填入PA1的基因。当该基因在步骤c)时已被置人 当≤n,d≤B≤p,在加工处理顺序jk下,存在CH1时,则忽略该基因,直接搜寻下一个基因 e)反复步骤d)直到所有PA1的基因被置入CH1 着使∑T最小的最佳解。但是当多加可同时处理,且处理时 3)变异阶段 随资源使用量多寡而改变的情况下.加工处理顺序拥有多种 变异是提升子代染色体多样化的方法,以避免遗传算法在 组合的可能性 求解过程中过早收敛至一组区域最佳解,而失去搜寻全局最佳 机制1的执行步骤如下: 解的机会。本文采用交换变异方式进行变异。 a)将父代中各染色体根据适合度值排序,较佳者排列于前。 步骤如下 b)选择排序中前a×100%的染色体进行选择 a)从子代中随机选出一个染色体 c)将被选择的各染色体分别等分为三区间。当加工数无 b)随机标志出该染色体中的两个位置。 法等分为三等份时,所余的加工归入第二部分中。令位丁前 c)将此两个位置的基因彼此互换,产生一个突变后的染 份的一区间的加工排序为S,令位于后三份的一区间的加工色体。 排序为S3,以及令其他位于中段三份的一区间的加工排序2.6停止条件 为S2 考虑运算时问与计算效率,设定的停止条件包含三项指 d)任意收变S1、S2及S3中的加上排列顺序 枟,当满足以下江一指标时,遗传算法即停止运作 e)组合S1、S2及S3为新的加工排列顺序S。 a)当遗传算法执行500代时 札制2选择、交义、变异 b)当遗传算法执行超过1.5h时; 例如,假设父代中某一位于适合度排序中前a×100%的 c)当遗传算法解与最佳解相同,或当出现迕续执行30代 染色体之订单排序为S,S=(11,3,5,10,15,6,1,14,8,12,9,的還传算法解均无改善时。 13,7,4,2)。将S等分为三区块Sn1、Sn2及S3。其中S (11,3,5,10,15),Sn,=(6,1,14,8,12)及Sn=(9,13,7,4,2)。 3实验分析 任意改变S,1、S2及Sn3中之订单的排列顺序,得到新的排序 考虑不同规模的工作站生产调度与资源分配,分别用订单 第3期 景波,等:基于遗传算法的 Job Shop调度问题研究 691 数(n)、工作站数(m)及加工设备数(R),以(n,m,R)来表示 450 在测试中,各订单的r采用随机产生,C在[5.50中随机产 生。为保证d>r,设d=+CRxu,其中∈[L/R,1]。遗传 算法中初始种群规模为50,交叉概率为0.8,进化代数为500 代 为测试混合算法的有效性和稳健性,将所得之结果与基本 型遗传算法及 Lingo7.0进行比较。测试环境为台式机 图1 lIngo、基本算法、混合算法求解结果比较 1.73GHz单核CPU,1 GB RAM,实现话言用VC++。在算法 的选择阶段,a取值为[0.1,0.4进行测试。测试问题规模包4结束语 括(10,2,5)、(20,4,10)、(30,6,15)、(40,8,20)及(50,10,25) 五组,每组问题测试30次。表4为测试运行结果。由表4各 针对 Job Shop调度冋题,基于算法混合的思想,提出混合 组测试结果对比可知,n值介于0.1~0.3间可获得较佳的求遗传算法。本文以解决实务问题为研究方向,除考虑各订单拥 解质量。与 Lingo比较可发现混合算法的求解结果虽较Ling有各自的可开工时间外,还设定各工作站的资源分随作业负 差,但偏差比PD均小于15%;除(10,2,5)问题外,基于混合算荷可弹性调整。但算法若能考虑加工时间的因素,并克服加工 法的求解时间均较liφ短。虽然基本型算法比混合算法有吋间随资源投入量而改变的问题,应能进一步提升求解效果。 更好的偏差值和更短的求解时间,但由表4屮的变异数结果可本研究将资源使用量与加工时间偎设成线性关系,而未考虑两 知,其求解稳定性随问题规模而逐渐变差。总体而言,当问题者问其他的关系型态,这将在未来的研究中进行考虑 规模达(30,6,15)以上时,混合算法在求解结果与求解稳定性参考文献: 上表现较优。比较结果如图1所示。 [ I PINEDO M Scheduling: theory, algorithms and systems[ M I. 2nd ed 表4測试运行结果 New Jersey Prentice-Hall, 2002 初始种群 規模算法 时间/812」 SIIADTAY D, KASPI M. Parallel machine scheduling with a convex 平均最佳最差平均方差PD/%平均 resource consumption function[ J]. European Journal of Operatio Li 110.21 J154 231. 52 110. 21 112. 19 110.9 0 58 0.63 9.08 [3 VALENTE JMS, AIVES R A FS. An exar t approach lo early/lardy a=0.I183.88110.2111.19I0.450.180.229 scheduling with release dates[ J]. Computers Operations Re (10,2,5) a=0.2183.94110.2l111.19110.570.750.69.14 search,2005,32(11):2905-2917 a=0.3 183. 27 110. 21 111. 64 110.71 0 34 0.45 9.14 [4 Van WASSENHOVE L N, BAKER K R. A bicriterion approach !=0.4184.32110.21111.19110.590.170.359.16 time cost trade-Dffs in sequencing J. European Journal of Opera- 215.96 tiona research,1982,11(1):48-54. 1t:4 443. 08 229.96 238 1 232. 76 10.58 7.78 46.1 [5] VICKSON R G. Two single machine sequencing problems involving a-0.1417.83228.27234.94231.786.37.3246.3 controllable job processing times LJ. Institute of Industrial Engi- 20,4,10) a=0.2414.48226.83234.6230.867.596.946.43 neers Transactions, 1980, 12(3): 258-262 a=0.3 412.3 229 58 234. 92 231.53 4.19 7. 21 46.51[6 OGUZ C, ERCAN M F. A genetic algorithm for hybrid flow-shop -0.4413.93231.06237.79233.167.557.9646.5 scheduling with multiprocessor tasks[J]. Journal of Scheduling Lingo 253.89 205,8(4):323-351 H5 4 538.73 270 38 292. 33 280. 55 52. 11 10.5 91. 37[7 CHEN Zhi-long. Simultaneous job scheduling and resource allocation 06.15;a-D.145.132679279.973.1521.517.99.03 on parallel machines J]. Annals of Operations Research, 2004 a=0.2453.73265.15280.65272.9715.177.5292.29 129(1-4):135-153 a=0.3 455.03 266.47280.47 272 44 14.4 7.3. 8 DANIELS R L, HOOPES B J, MAZZOLA J B Scheduling parallel -0.4454.7265.76281.5273.9823.077.9192.44 manufacturing cells with resource flexibility[ J]. Management Sci 313.18 4473 ence,19%6,42(9):1260-1276. 基本811.17358.31389.69370.59101.5118.33141.62 [9 YANG KK, SUM CC. A comparison of resource allocation and activi a=0.1805.71333.97359.42346.1165.2510.51142.76 ty scheduling rules in a dynamic multi-project environment[ J. Jour 408,20) a=0.2808.13330.04362.36344.684.0610.03143 nal of Operations Management, 1993, 11(2): 207-218 n=03807.3236.7235.183454737.2810、31143.05「101王凌·车间作业调度及其遗传算法「M].北京:清华大学出版社, a-0.4808.01344.67369.76357.5873.114.18143.27 [11 TSAI T I. A genetic algorithm for solving the single machine carlin ness Lingo 381.16 18340 基本1285.6406.03430.85421.59116.1113.04230.42 hardiness problem with distinct due dates and ready times[ 1. Inter- national Journal of Advanced Manufacturing Technology, 2007 a=0.1707.55391.58409.32401.4443.377.39232.13 (50,10,25) 31(9-10):994-1000 a=0.2707.66397.94420.06408.2763.0510.21232.5 a=0. 3 712. 46 401. 92 423 2G 414. 67 (2.07 11.04 233. 2 [ 12] SEXTON R S, GUPTA J D Comparative evaluation of genetic algo- rithm and back propagation for training neural networks[ J 1. Informa a-0.4711.98407.68427.18415.1753.9312.07233.36 tion sciences,2000,129(1-4):45-59