自适应队列调度算法

自适应队列调度算法（精选7篇）

自适应队列调度算法 篇1

0引言

随着网络技术的发展和应用,用户对网络的移动性和可靠性要求越来越高,基于IEEE 802.11系列标准的无线Mesh网络[1,2]近年来得到了快速、广泛的应用。随着网络应用的不断发展,特别是音频、视频等多媒体业务的广泛应用,这就要求无线网络不仅能支持传统的数据业务,还必须提供对带宽和延迟要求较高的音频视频业务的支持,同时还得保证各类业务间的业务区分。

无线Mesh网络为实现不同业务间的区分,IEEE802.11e在数据链路层提出了EDCA(增强分布式信道接入)机制。EDCA将不同的业务流分为4个不同的优先等级AC(Access Categories),每一个AC对应一个队列,通过设置仲裁帧间间隔(AIFS)、最小竞争窗口值CWmin、最大竞争窗口CWmax和传输机会(TXOP)4个参数设置不同的值实现不同业务流间的业务区分。很多研究[3,4,5]表明,由于无线网络状况的移动性和复杂性,EDCA算法中4个参数的静态设置并不能使无线网络的性能实现最优,特别在高负载或突发业务量较大的状况下,由于无线网络中有较高的冲突概率,EDCA的网络性能急剧下降,无法满足网络用户的要求。

而在有线网络环境下,由于网络环境的可靠性,一般在网络层通过采用不同的调度算法以实现各类业务的服务质量[6,7,8](Qo S)保证和各类业务间的业务区分。现有的调度算法包括:FIFO(first-in-first-out)、PQ(Priority Queuing)、FQ(Fair Queuing)和WRR(Weighted Round-Robin)。但由于无线Mesh网络本身的特性,这些算法用于无线Mesh网络中的分组调度时,由于无法根据网络流量及网络实际状态做出及时的调整,因而无法最大限度地利用无线Mesh网络的网络资源。

基于此,本文提出了一种用于无线Mesh网络中的自适应队列调度策略(AQSM)。该策略的基本思想是通过实时监控网络流量和无线链路的实际状态,动态地调整加权轮询WRR算法中的权值,以期达到变化的分组调度策略,最终实现充分的利用无线Mesh网络中的网络资源、提高网络性能及Qo S保证的目的。并通过仿真验证该策略对网络性能的提高及各类业务流间的业务区分。

1 WRR算法

在有线网络中为实现各类业务间的业务区分,一般采用WRR算法。WRR算法的基本思想是网络中的路由器给不同类型的业务流分配不用的子队列(在IP DiffS erv中共分为3大类子队列:BE(尽力而为:Best-Effort)、AF(确保转发:Assured-Forwarding)、EF(快速转发:Explicit-Forwarding),同时为每一个子队列分配一个对应的权值。在路由器调度数据时,按照轮询的方式调度,某一子队列包含的分组数大于或等于分配的权值,则该子队列调度对应权值个分组后进行下一队列的调度,若某一子队列包含的分组数小于分配的权值,则把队列中的分组全部调度完毕后进入下一子队列,如此轮询调度。对于WRR调度算法而言,如果每一个分组的大小一致则可以提供很好的公平性;但如果分组的大小有区别就会对较小分组的子队列造成不公平。

WRR算法的权值固定分配,在有线网络环境下能提供很好的网络性能和业务流间的业务区分。但在无线Mesh网络中,由于网络链路本身的不稳定性和数据到达的突发性,使得在某一时刻即使调度成功但无法正确传输数据(而按照MAC层的工作原理该数据将重传),造成网络资源的浪费。为充分利用无线Mesh网络的网络资源,同时保证各类业务的业务区分,在无线Mesh网络中采用动态的WRR调度算法是完全必要和可行的。

2 AQSM算法实现

基于权值固定分配的特性,WRR算法不能根据无线网络的链路状态和网络流量的实际情况,动态地调整各子队列的权值。AQSM算法就是希望通过无线Mesh网络的网络链路和网络流量的实际状态动态调整各对应子队列的权值IWi。其功能框图如图1所示。

图1 AQSM功能框图(参见右栏)

2.1 变量说明

Ratei:子队列i实际数据到达速率;

Raterefi:子队列i数据到达的参考速率,可由系统管理员自行设定。为实现各业务流间的业务区分一般建议高优先级的参考速率值较小,即Rateref[高]

RFi:速率因子,表示达到子队列i分组到达速率对ΔWi的影响大小,RFi=max(Rate[i]/Rateref[i],1);

SLWB:标准链路带宽,也就是理想链路带宽,由网络设备及采用的物理层传输技术决定,其为一固定值;

ALWB:有效链路带宽,通过链路状态监视器测得的实际可用的链路带宽;

LSFi:链路状态因子,表示在调度子队列i时链路状态对ΔWi的影响大小,其大小为LSFi=ai×ALWB/SLWB,其中ai为子队列i的影响因子。

SWi:子队列i初始化权值,其值是在采用WRR调度算法的网络设备初始化时给子队列i分配的固定权值;

ΔWimax:表明子队列i允许的最大权值增量,用以保证即使各种外界情况变化极端的情况下,各类业务间维持基本的业务平衡,不至于出现“饥饿”现象。

ΔWi:表明子队列i相对于SWi的增量,其值通过计量器和链路监视器的结果共同获得,ΔWi =RF×LSFi×ΔWimax;

IWi:子队列i对应的实际权值,IWi=SWi+ΔWi 。

2.2 IWi的确定

如图1所示,某一分组到达时,分类器根据IP分组的特性对其进行分类,然后测量该分组所属的子队列i分组到达速率Ratei。调度器在按WRR算法调度分组时,当调度器调度到某一子队列i时,首先根据判决器获得的链路状态信息和计量器获得的数据到达速率相关信息决定本轮调度子队列i所对应的权值IWi,也就是本次可调度子队列i中的最多分组个数。其中

3 仿真分析

为了验证AQSM算法性能,通过网络仿真工具NS2实现该算法和WRR算法的性能比较。仿真所采用的拓扑结构如图2,仿真时物理层采用802.11b,物理带宽设为11Mb/s,8个移动终端,每一移动终端节点分别发送BE、AF、EF等3种业务流,这3种业务流占总负载的比例为1:2:4,各业务BE、AF、EF的初始化权值SWi分别为2、4、8。分别对AQSM、WRR算法的各类业务的丢包率及系统的吞吐量进行了仿真,仿真结果如图3、4、5所示。

从图3、图4的仿真结果可以看出,AQSM算法能降低各类业务的丢包率,特别是高优先级EF的丢包率降低更为明显,从而提高了无线信道利用率;同时从图3中可以看出AQSM算法能实现业务类型BE、AF、EF间的业务区分;从图5仿真结果可以看出AQSM算法能增加移动节点AP的吞吐量,特别是在网络负载比较高的情况下,从而提高了网络的QoS。

4结论

本文提出的AQSM算法能够根据当前的网络实际情况和数据达到速率动态地调整WRR算法中的各自队列对应的权值,从而实现动态调度无线AP中的数据分组,以实现改善无线网络性能的目的,同时实现各类业务流间的业务区分。通过仿真分析可知,AQSM算法不仅能够提高网络性能,而且可以实现对不同业务的业务区分。

一种自适应主动控制队列算法 篇2

关键词：RED,拥塞控制,路由缓冲资源

本文在分析RED算法基础上, 提出了一种新型AQM算法, 能够动态调整Pmax参数, 并且采用非线性函数代替原有的丢包率计算方法.通过动态调整Pmax来调整向源端发送拥塞通知的速率, 维持队列的稳定;通过新丢包率计算方式, 提高缓冲的利用率和使队列长度尽量稳定于期望值附近。

1、一种新的自适应RED算法

丢包率p相对于RED算法在Qmin附近取值更趋近零, 并且随着参数k的取值而改变.K值决定队列的期望值, 如果是期望值是, 则k值取2。

(2) 调整Pmax算法

修改Pmax算法描述如下:

2、结语

本文提出一种改进的算法, 新算法在队列控制和丢包率控制方面优于RED算法。

参考文献

[1]S.Floyd, V.Jacobson.Random early detection gateways for con-gestion avoidance.IEEE/ACM Transactions on Networking, 1993, 1 (4) :397-413.

[2]F.P.Kelly, A.Maulloo and D.Tan.Rate control in communicationnetworks:shadow prices, proportional fairness and stability.Journalof the Operational Research Society, 1998, 49:237-252.

联合处理中自适应调度算法研究 篇3

在目前的3GPP长期演进 ( Long Time Evolution, LTE) 系统中, 小区边缘用户的吞吐量远小于中心用户的吞吐量, 为了提升边缘用户的数据速率, LTE - Advanced将协作多点传输 ( Coordinated Multi- Point Transmission /Reception , COMP) 技术列为其重要的候选技术之一[1], 其主要目的是通过小区间的协作[2]来改善小区边缘用户的吞吐量[3], 以及提高整个系统的吞吐量和平均吞吐率。

COMP技术是LTE - A的研究热点, 每次3GPPRAN会议上都会有众多的提案。现有的下行COMP技术可以分为协调调度/波束赋形 ( CS/CB, Coodinate Beamforming /Schedule) 和联合处理 ( JP, Jiont Processing) [4]。对于CS/CB技术, 针对的是资源分配过程中相邻小区频率资源分配相同或相近产生干扰的情况, 为避免临近小区同时在同一RB调度同一方向的用户, 通过彼此间的协作联合进行调度决策和波束赋形。而对于JP技术, 又可分为联合传输 ( JT, Joint Transmission) 和动态小区的选择 ( DCS, Dynamic Cell Selection) 。联合传输中, 多个传输节点在相同的时频资源上同时向一个或多个用户发送物理下行共享信道 ( PDSCH) 信息, 从而达到提高接收信号质量抑制其他用户对此用户的干扰的目的。动态小区选择技术, 用户可以根据信道质量动态的选择接受哪个基站发送的PDSCH信息。

对于联合传输, 文献[5 -7]针对COMP单用户多输入多输出 ( single user multiple input multiple output , SU - MIMO) 的传输特点, 把频谱资源划分为中心用户频段和COMP用户频段, 并提出了不同的分配方案, 来提高系统性能。但是, 由于各扇区中用户的数目是动态变化的, COMP频段的划分很难做到精确, 而且簇中各扇区间的信令开销也很大, 因此其在LTE - A系统中难以实现并达到满意的系统性能。文献[8, 9]在此基础上对频谱资源划分不同频段, 而是对于每个时频资源 ( resource block , RB) 进行调度, 这有效减少了各扇区信令开销。但是此方法是协作簇中每个基站优先级最高的中心用户之和与COMP用户优先级间的比较, 不能很好地反映出中心用户与COMP用户间的优先级的关系, 甚至有可能会降低中心用户的优先级。本文针对这一问题, 在此基础上提出了一种自适应的调度算法, 对每个时频资源块RB, 很好的比较了非COMP ( No COMP) 的中心用户与COMP用户的优先级, 从而选择较优的传输模式, 进而提升系统性能。

2 系统模型

在COMP - SU - MIMO系统中, 将整个网络划分为若干个不重叠的小区簇, 其中每个小区簇含有3个相邻的扇区 ( 由虚线表示将一个小区划分为三个扇区) , 如图1所示。

对于SU -MIMO传输系统, 考虑一个有M个小区的下行蜂窝系统, 每个小区分为3个扇区 ( sector) 。每个基站有Nt根发送天线, 而每个UE有Nr根接收天线, 协作基站数为N, 每个扇区有K个用户, 则COMP -SU -MIMO第m个基站下第k个UE的接收信号可表示为:

其中等式右边第一部分是当前主基站传输的用户信息, 第二部分代表来自其他基站和用户的干扰, 第三部分为高斯白噪声。其中, s (m k) 是用户的发送信息, 是一个lk×1维向量, lk是基站传输的数据流的个数, H (m k) 是由第m个基站到第k个用户UE的信道增益矩阵, 其维数Nr×Nt, W (m k) 是由H (m k) 得到的预编码矩阵, 其维数Nt×lk, n (m k) 是一个Nr×1维的加性高斯白噪声, 服从均值为0, 方差为σ2的高斯分布。

在COMP模式下, 边缘用户可获得协作簇中基站的协助, 因此其接受信号可表示为:

其中等式右边第一部分是当前协作簇中的基站对用户k的传输信息, 第二部分代表来自其他簇中的基站和用户的干扰, 第三部分为高斯白噪声, 其中c表示的是当前协作簇。

关于每个用户的信号干扰噪声比 ( output signal to interference plus noise ratio, SINR ) 的计算, 在COMP - SU - MIMO系统中, 因其区分中心用户即No - COMP用户和COMP用户, 其SINR计算也有所不同。对于No -COMP用户来讲, 其接受有用信号来自当前主基站的传输, 故其SINR可表示为

其中Pr表示发射信号功率, σ2是接受的高斯白噪声的功率。

对于边缘用户, 其接收到的信号不仅有来自主基站的信号, 还有协作基站的信号, 因此其SINR可表示为:

3 资源调度方案

3. 1 调度算法

目前在实际中应用的经典调度算法有: 最大载干比 ( Maximum Carrier to Interference Ratio, Max C/I) 调度算法、轮询调度 ( Round Robin, RR) 算法、比例公平 ( Proportional Fair Scheduling, PFS) 调度算法及在实时流业务中使用广泛的改进最大权重时延优先 ( Maximum - Largest Weighted Delay First, M LWDF ) 调度算法和指数 /比例公平 ( Exponential /proportional Fair, EXP /PF ) 调度算法等。最大载干比Max C/I调度算法是在无线信道中, 总是选择为使系统容量最大的用户提供服务, 公平性较差。轮询RR调度则是所有用户优先级相同, 对所有用户一一遍历, 具有较好的公平性, 但此时系统性能会有所下降。本文采用同时兼顾了用户的公平性和系统容量的比例公平调度算法PFS来判定用户的优先级, 是对系统吞吐量和用户公平性的折中。

3. 2 COMP - SU - MIMO 自适应调度算法

COMP - SU - MIMO系统中存在中心用户和边缘用户, 对于边缘用户来说, COMP传输可以提高其性能, 但是对于中心用户来讲, 其服务小区的信号质量要远优于其他非服务小区, COMP传输就没有必要, 使用后不仅会增加系统复杂度, 还会降低传输效率。所以一般系统会限定中心用户和边缘用户, 分别使用No -COMP和COMP传输。本文以UE接受到的SINR为基准来区分其为边缘用户还是中心用户, 并通过一预定义的门限值进行判决。当且仅当该UE的SINR满足下式时可判断为边缘用户, 从而需要进行联合传输:

根据是否满足公式 ( 5) , 系统区分出COMP用户和非COMP用户, 然后对同一协作簇的小区进行联合调度, 以3小区协作簇为例, 具体过程如下: 针对每个RB, 每个用户按照PFS调度算法计算出优先级, 对协作簇中三个基站下所有中心用户在Non- COMP模式下按传统的PF调度算法进行排序, 选出优先级最高的用户j, 记为priorj; 对协作簇中边缘用户在COMP模式下计算其优先级, 并选出优先级最高的用户k, 记为priork; 然后根据式 ( 6) 比较两者大小:

其中是ρ是一个可根据实际进行调整的权值因子, 若满足上述公式则当前RB分配给COMP用户, 进行COMP模式传输; 反之, 当前RB分配给Non COMP的中心用户, 进行单基站传输; 然后对系统中每个小区簇和设定的所有RB都执行以上操作, 直到所有小区簇和RB都执行完; 具体流程图如图2所示。

该算法在每个RB上都灵活的选择兼有的传输模式, 实现最大化系统频率分集增益, 相对于文献方案, 该算法给予边缘用户和中心用户平等被调度机会, 可保持较好公平性的同时又可以很好地提升平均扇区吞吐量和边缘用户的性能。

4 仿真分析

本文采用LTE系统级仿真平台, 对COMP - SU- MIMO系统进行性能仿真, 主要从平均扇区频谱效率和小区边缘频谱效率等几个方面对本文方案与传统的SU -MIMO方式进行比较, 仿真参数如表1所示。

采用的系统级仿真平台生成的仿真场景为19小区模型, 每个小区划分为3扇区, 每扇区均匀分布10个用户, 不同基站下三个扇区构成一个协作簇。本文将用于判决用户类型的门限值γ取0dB, 具体仿真结果如下:

由图3、图4可以看出, 本文提出的自适应调度的COMP方案在边缘用户频谱效率和小区平均频谱效率相对于Non - COMP方案分别有43. 2% 和18. 3% 的增益。虽然小区平均频谱效率增益较小, 但是边缘用户性能的提升相当明显。由此可见, 基于本文提出的调度机制的COMP技术可以很大程度上保证边缘用户的频谱效率, 还可以有效提高系统总体性能。

5 总 结

本文主要针对COMP -SU -MIMO的资源调度策略进行了研究, 并在经典比例公平的基础了提出了针对每一时频资源RB合理进行判决, 从而选择不同的传输模式的调度方案。通过仿真结果可以看出本文提出的调度策略可以充分发挥COMP多点协作的优势, 相对于No - COMP来讲, 不论是从边缘用户性能还是总体吞吐率都有很大的提升。

参考文献

[1]XiaoFeng Tao, Xiaodong Xu, Qimei Cui.An overview of cooperative communications[J].Communications Magazine, 2012, 10 (1) :65-71.

[2]El Ganal Aly, Annapureddy V Sreekanth, Veeravalli Venuagopal V.On optimal message assignments for interference channels with CoMP transmission[J].Information Sciences and System, 2012, 46 (2) :1-6.

[3]Zetterberg, Moghadam, An experimentel investigation of SU-MIMO, interference-aignment (IA) and coordinated multi-point (CoMP) [J].Systems, Signals and Image Processing, 2012, 19 (2) :211-216.

[4]3GPP, TS TR 36.819-2012.Coordinated multi-point operation for LTE physical layer aspects[S].USA:3GPP Organizational Partners, 2012.

[5]R1一094092, Further discussions on feedback framework for SU/MU-MIMO[Z].Samsung, 2009.

[6]3GPP R1一090613.Discussion on COMP-SU-MIMO[S].2009.

[7]3GPP R1一091415.Further discussion of frequency plan scheme on COMP-SU-MIMO[S].2009.

[8]刘邦辉.LTE-Advanced协作多点传输系统中下行用户调度算法研究[D].南京:南京邮电大学, 2011:39-45.

自适应队列调度算法 篇4

近几十年来, 随着CAD/CAM、FMS等先进制造技术的快速发展, 越来越多的学者对生产调度问题进行研究[1,2]。由于多品种小批量的生产需求, 工件之间形状各异但加工工序相同, 因此这种生产过程就不再是简单的平行设备或者流水线作业, 而是多级多机的混合流水车间 (Hybrid Flow-shop, 简称HFS) 生产。混合流水车间调度问题 (Hybrid Flow-shop Scheduling Problem, 简称HFSP) 是两类经典调度问题Flow-shop和Parallel-shop的推广, 也称作具有多并行设备的Flow-shop、柔性Flow-shop等, 比一般Flow-shop调度问题更加复杂, 相当普遍地存在于现代制造工业中。

自从1954年Johnson发表第一篇关于Flow-shop调度问题的文章以来, 很多学者对纯FSP作了深入的研究, 遗传算法也被成功地应用于求解FSP[3,4,5,6,7]。最早将遗传算法应用于车间调度问题的是Davis, 他于1985年发表了第一篇关于将遗传算法运用于车间调度的论文, 他使用遗传算法在求解车间调度问题中取得了近似最优解[8]。1996年, 黄宇纯等结合遗传算法和REAS启发式规则, 求解Flow-shop调度问题[9]。2004年, 王万良等提出了改进的自适应遗传算法, 并将其运用于作业车间调度问题中, 改进的自适应遗传算法在获得最优解的速度上有很大的提高[10]。2007年, Victor等改进了遗传算法的交叉操作, 并将改进的遗传算法应用于求解混合流水车间调度的问题中[11]。2008年, Pezzella等将遗传算法应用于求解并行机的柔性作业车间调度优化问题[12]。

混合流水车间调度问题可以被描述为:假设有N个独立的工件 (J1, J2, …, JN) , 所有工件的加工路线都相同, 都需依次通过S道工序, 在所有工序中至少有一个工序存在着多台并行机器。而每个工件的每道工序只能在一台机器上进行加工, 而且每个工件在每台并行机器上的加工时间是确定的。需要解决的问题是同一台机器上工件的加工顺序以及确定并行机器的分配情况, 目标是最小化最大流程时间, 如图一所示。

1 基于自适应遗传算法H FS P的求解

混合流水车间问题是大规模组合优化问题的一种, 属于NP-hard完全问题, 难以用传统的数学规划方法进行求解。早期解决混合生产车间调度问题的算法主要有分枝定界算法、混合整数规划、启发式算法等, 但这些算法都只能解决规模较小的生产调度问题, 无法对较大规模的生产调度问题进行求解。近来, 更多的学者运用模糊逻辑、神经网络、遗传算法来求解这种大规模调度问题。本文采用自适应遗传算法来求解混合生产调度问题, 该算法能够在优化过程中自动改变交叉概率和变异概率, 从而提高搜索效率, 保证遗传算法的收敛性, 仿真结果表明了此算法对于求解混合调度问题的优越性。

2 混合流水车间问题的编码

对混合流水车间调度问题进行遗传算法编码的关键是怎样处理好各工序之间的约束关系, 使得产生的每个染色体都对应一个可行的调度, 而且在进行遗传算法操作时也不会产生非法解。本文采用矩阵形式进行编码, 编码矩阵不但能够很好地处理每道工序间的约束关系, 使得生成的每个染色体都对应一个调度方案, 而且在遗传操作过程中不会出现非法的解[4,9]。下面构造一个n×m维的混合流水车间的调度矩阵:

编码矩阵中的元素aij是区间 (1, Mi+1) 上的实数, 代表加工过程中第i道工序上的工件j的是在这道工序的第Int (aij) 台并行机器上加工的 (函数Int (aij) 是对实数x的取整) 。在加工过程中很有可能会出现Int (aij) =Int (ais) , j≠s, 这代表着加工同一道工序有多个工件是在同一台机器上进行的, 这样的情况如果发生在第一道工序中, 就按照工件排序的升序进行加工。如果情况不是出现在第一道工序, 则比较工件的前一道工序的完成时间, 前一道工序先完成的先加工;如果前一道完工时间也相同, 则按照工件排序的升序进行加工。

染色体由编码矩阵确定, 每条染色体都有n小段, 每个小段都由m个基因组成。编码矩阵的每一行对应染色体的一个小段, 用标识符“0”将每小段隔开, 以此表示不同的加工工序。染色体的长度为n×m+n-1。染色体可以表示为:[a11, a12, …, a1m, 0, a21, a22, …, a2n, 0, …, an1, an2, …, anm]。

3 基于遗传算法的求解方法

3.1 初始群体的产生

为了进行遗传算法操作, 首先必须产生初始种群。产生初始种群的方法是利用随机函数, 根据染色体的编码方式, 随机的产生一些编码矩阵, 构成染色体, 组成初始种群。其中基因aij的大小与第i道工序的并行机器数量有关。一般情况下, 需要满足1≤aij≤Mj+1, 其中Mj为第i道工序的并行机器数量。

3.2 适应度函数 (Fitness Function) 的设计

求解混合流水车间调度问题的目标是获得最小化的最大完工时间, 所以取最大流程时间的倒数作为适应度函数。

以Make span为指标的混合流水车间调度可用混合整数线性规划模型来描述:

根据上述混合流水车间调度问题的描述, 确定适应度函数为:

式 (6) 中, Cmax表示第k个染色体所代表的一个调度的最大流程时间。

3.3 选择

选择操作是为了从当前的群体中把优良的个体选出来, 作为父代进行下一代的遗传操作。通过比较个体的适应度值来判断个体优良程度, 即个体的适应度值越高, 就有更多的机会被选择。本文的选择操作采用轮盘赌注方法。在该方法中, 每个个体被选择的概率与其适应度值的大小成比例。如果群体的规模为N, 个体i的适应度值表示为fi, 则个体i被选择的概率为:

3.4 交叉操作

遗传算法中起核心作用的是交叉算子, 也称为基因重组, 采用的交叉方法应该能够使父串的特征遗传给子串。子串应该能够部分或者全部地继承父串的结构特征和有效基因。但交叉概率Pc越大, 新个体产生的速度就会越快, 而Pc过大时遗传模式被破坏的可能性就会越大, 具有高适应度的个体结构会被很快的破坏;Pc过小就不会产生新的个体结构。为了解决这种问题, 本文运用自适应遗传算法, Pc能够随着适应度自动改变。当种群各个体适应度趋于一致或者趋于局部最优时, 使得Pc增加, 从而跳出局部最优;而当群体适应度比较分散的时候, 使得Pc减小, 以利于优良个体的生存。

Pc按照以下公式进行调整:

式 (8) 中, fmax是种群中最大的适应度值;favg是每代种群的平均适应度值;f'是要交叉的两个个体中较大的适应度值;k1, k2是 (0, 1) 之间的常数。

根据上面的编码方式, 为了保证个体的合法性。本文采用分段交叉的方式, 对每小段进行两点交叉操作, 每段的交叉点可以相同也可以不同。

在两个父体的各段中随机的选取一部分基因进行交换得到子代个体。例如:

经过交叉操作, 结果为:

3.5 变异操作

变异的目的是保持群体的多样性, 修复和补充在选择和交叉过程中可能丢失的某些遗传基因。本文采用扰动式的变异操作, 对父代个体附加一定的扰动来实现变异。变异步骤为:

(1) d=rand (1) ;

其中, d为实数, aij为进行变异的个体, a'ij为变异后的个体。通过这种变异方法可保证a'ij在 (1, Mi+1) 区间内, 也就可以确保个体的合法性。同时变异操作也具有很好的随机性。

4 某汽车玻璃生产车间调度实例

某汽车玻璃有限公司的夹层玻璃生产需要通过5道工序, 即预处理工序、烘弯工序、合片和初压工序、高压釜工序和检测包装工序。每道工序的并行机器数分别为3, 3, 2, 2, 2。本文通过在日常生产数据库中随机抽取8个批量合计2230个工件的数据进行研究。夹层玻璃的生产都是根据订单的需求量进行批量生产的, 为了便于运算及处理, 本文将一个批量的夹层玻璃产品的订单作为一个工件来处理, 公式如下:

处理后的数据如表一所示。

遗传参数设置。设置算法中的使用参数, 种群规模值为50, 最大迭代次数为100。经过100次的自适应遗传迭代运算, 从图二中可以明显看出目标函数最小值随着种群的进化逐渐减小, 最后收敛于极值。在程序迭代到95代左右时, 算法获得了近似最优解;通过多次模拟仿真操作可以获得经100次迭代运算的比较好的近似最优解。如果在进行100代迭代的过程中没有获得近似的最优解, 则可以通过增加初始种群的规模或者增加遗传迭代的代数来解决。但是, 增加初始种群的规模和遗传迭代的代数不可避免的会增加程序运行的时间, 所以需要根据具体的问题合理的对种群规模和迭代的次数进行取值。

最优染色体为:

5 结束语

自适应队列调度算法 篇5

车间调度是先进制造系统实现管理技术、运筹技术和优化技术发展的核心。有效的调度方法和优化技术的研究应用则是实现先进制造和提高生产效益的基础和关键。早期这方面的研究主要集中于考虑单个因素的静态或动态作业车间调度问题。现阶段研究的重点集中于使整个现代制造系统更具有开放性、动态性和柔性等方面,同时对制造过程的模糊加工和模糊优化控制等方面也有较深入的研究。其中,柔性job-shop调度问题由于减少了机器约束,扩大了可行解的搜索范围,提高了问题的复杂性,与传统的job-shop调度问题相比更加接近实际生产环境的模拟[1,2,3,4]。

本研究提出一种自适应蚁群算法以求解柔性job-shop调度问题,在机器的选择策略方面选择能完成工件工序最早的机器。

1 柔性job-shop调度问题描述

1.1 问题的描述

假定一个加工系统有若干台机器和n个待加工工件,每个工件包含一道或多道工序,工件的工序顺序是预先确定的,每道工序可以在多台不同的机床上加工,工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器,以及确定每台机器上各工件工序的最佳加工顺序及开工时间,使所有工件在系统中的流通时间最短。下面是针对该调度模型的假设条件:

(1) 每台机床一次只能加工一个工件;

(2) 工序一旦进行不能中断;

(3) 假定工件之间具备相同的优先级;

(4) 每个工件在固定时刻只能在一台机器上加工;

(5) 在零时刻,所有的工件都可被加工;

(6) 工序在可选择的若干机器上加工的时间已经确定。

1.2 自适应蚁群算法求解柔性job-shop调度问题策略

1.2.1 机器选择规则

柔性job-shop调度问题与一般job-shop调度问题相比,不同点是增加了机器选择这一环节,待加工工件的工序可以在多台机器上加工,因此选择最优的机器加工工件将提高算法解的质量[5,6]。本研究用一种简单有效的方法即选取完成加工第i个工件的第j道工序pij最早的机器,使工序pij能最早地完成,从而也能减小整批工件的最大完成时间,机器选择规则如图1所示。

假设M1,M2,M3为可加工工序pij的3台机器,τ为工序pij的顺序约束,T1,T2,T3分别为机器M1,M2,M3的机器约束,斜线花纹方框表示工序pij分别在3台机器上的可加工最早时间段,由图1可知,工序pij在3台机器上加工的最早完成时间分别为:t1,t2,t3,且t1<t2<t3,因此本研究选择机器M1加工工序pij。

1.2.2 状态转移规则

第k只蚂蚁由节点r转移到节点s的概率P${}_{rs}^k$为:

${\rm P}{}_{rs}^k=\{\begin{array}{cc}\frac{\tau {}_{ij}^{\alpha }\cdot \eta {}_{ij}^{\beta }}{{\displaystyle \sum _{i\in p}\tau }{}_{ij}^{\alpha }\cdot \eta {}_{ij}^{\beta }}& \text{i}\text{f}(p{}_{ij}<p{}_{i\text{m}\text{a}\text{x}})\\ 0& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(1)$

式中 τij—节点r到节点s(其中s表示第i个工件的第j道工序)的信息素;ηij—节点r到节点s的可见度;pij—第i个工件的第j道工序;pimax—第i个工件的最大工序;α、β—信息素和可见度的偏重系数。

可见度ηij为:

$\eta {}_{ij}=\frac{1}{t{}_{\text{w}\text{a}\text{i}\text{t}}+\text{c}}(2)$

式中 twait—在加工pij前的等待时间[7]。

为了避免twait=0而使可见度趋于无限大,同时分母为1时,ηij=1,偏重系数β不起作用,故在分母加上常数c(c>1)以保证可见度对节点选择的影响,在算法具体实现时取c=2。经过式(1)计算后,再用轮盘赌方法从工件集中选择一个节点,并记下这个节点的起止时间,以便计算等待时间和最后完成所有工件的加工时间。

1.2.3 自适应信息素更新策略

在前一步判断算法是否陷入局部收敛的基础上,本研究采用两种信息素更新策略。这样可以使算法快速跳出局部收敛,向全局最优解方向搜索。两种更新策略如下:

(1) 当算法未陷入局部收敛时,采用全局更新和局部更新结合的策略。

首先,按下式更新该代最优路径l上的信息素:

τij=(1-ρ0)τij+Δτij (3)

其中,Δτij=Q0/L,L为路径l的长度。

然后,更新所有蚂蚁爬行路径上的信息素,同式(3)。

(2) 当算法陷入局部收敛时,信息素更新策略如下:

①计算除最优蚂蚁l外所有其他蚂蚁经过路径上的信息素增量:

$\text{Δ}\tau {}_{ij}={\displaystyle \sum _{k=1}^m\text{Δ}}\tau {}_{ij}^k‚\text{Δ}\tau {}_{ij}^k=Q{}_0/L{}_k‚k=1,\cdots ,l-1,l+1,\cdots ,m(4)$

②计算蚂蚁l经过的路径上的信息素增量:

Δτ${}_{ij}^{(l)}$=Δτ${}_{ij}^l$,Δτ${}_{ij}^l$=-Q0×(n-n0)/Ll (5)

③更新除蚂蚁l外所有其他蚂蚁经过路径上的信息素:

τij=(1-ρ0)τij+Δτij (6)

④更新蚂蚁l经过路径上的信息素:

$\tau {}_{ij}^{(l)}=\left(1-\left(1-\frac{1-\rho {}_0}{n-n{}_0}\right)\right)\tau {}_{ij}^{(l)}+\text{Δ}\tau {}_{ij}^{(l)}(7)$

当算法陷入局部最优时,陷入局部最优解路径上的$Q=-Q{}_0\times (n-n{}_0),\rho =1-\frac{1-\rho {}_0}{n-n{}_0}$,因此当算法陷入局部收敛越深,即n越大,则Q越小,ρ越大,这样使得局部最优解路径上的信息素快速减小,而其他路径上的信息素继续积累,最终减小了局部最优解路径与其他路径上的信息素差距,使算法跳出局部收敛,最终收敛到全局最优解。

2 柔性job-shop调度问题的自适应蚁群算法

在柔性job-shop调度中,由于存在并行机和多功能机,使得蚂蚁在爬行每一步时不仅要确定待加工的工件而且要确定该工件的工序在哪台机器上加工最优,对于一个实际问题,本研究分以下几个步骤执行:

(1) 构造一个动态数组m_NodeArray用于记录蚂蚁下一步可以搜索的节点信息,包括Accessory_number(工件号),procedure_number(工序号),procedure_sum(总工序)。再定义一个二维数组m_machine[][]用于记录各工件的各道工序可在哪几台机器上加工的机器信息,包括machine_number(机器号),time(加工时间)。定义二维数组m_MachineAnt[][],用于记录每只蚂蚁爬行的路径信息,第一维为蚂蚁号,第二维为机器号,该数组的元素为动态数组m_AntArray,记录了所有在某台机器上加工工件的信息,包括Accessory_number(工件号),procedure_number(工序号),starttime(开始时间),endtime(结束时间),intervenetime(等待加工时间),machine_number(机器号)。初始化代数为0。

(2) 若蚂蚁爬行第一步,则随机从动态数组m_NodeArray中选择一个工件,从二维数组m_machine[][]中查询出可加工该工序的所有机器并选择加工时间最短的机器进行加工,将选择的结果存于m_MachineAnt[][]中,并将m_NodeArray中对应工件的工序号加1。若不是第一步,则先为各可加工工件工序选择机器,依据是选择完成加工该工件工序最早的机器。然后,在确定了各可加工工件工序机器的条件下根据蚂蚁转移规则选择工件。将选择的结果存于m_MachineAnt[][]中,并将m_NodeArray中对应工件的工序号加1。重复(2),直到所有蚂蚁爬行完毕。

(3) 当所有蚂蚁爬行完毕后,根据自适应信息素更新策略更新该代蚂蚁爬行路径上的信息素。根据判断该代最优蚂蚁搜索解是否陷入局部收敛而采用两种不同的信息素更新规则,这样更有利于算法的全局收敛。若本代最优解优于历代最优解则替换最优解。最后代数加1,若未达到规定代数,则转到(2),否则转到(4)。

(4) 输出最优解,算法结束。算法流程图如图2所示。

3 示例仿真

为了便于比较,本研究以文献[8]的算例为例。该加工系统有6台机床,要加工4个工件,每个工件有3道工序,如表1所示(如工序p11代表第一个工件的第一道工序,可由机床1用2小时完成,或由机床2用3小时完成,或由机床3用4小时完成)。

经过多次试验,本研究确定了算法主要参数(蚂蚁数目,循环次数,Q0,ρ0,α,β)的最优选择范围,其结果如表2所示。

算法运行300代后,得到最优解为17,优于文献[8]得到的最优解18。甘特图历代最优解收敛图分别如图3和图4所示。

由图3可以看出机器6并没有加工任何工件。这是因为它虽然可以加工工序p23,p33,p42,p43,但从表1可知机器6的加工时间大于其他可加工机器,特别是p23,p33的加工时间,因此机器6并未分到任何加工任务。

由图4可知,算法在大约30代以前就收敛到最优解,且各代最优解相差不大,表明算法较为稳定。为了研究算法的有效性,将本研究与文献[9]及文献[10]中的算例结果相比较,如表3所示。

从表3可以看出本研究提出的自适应蚁群算法所得到的解明显优于文献[9]及文献[10],从而证明了该算法的有效性。

注:最优解和平均解分别为各算法经30次仿真得到的最优解和平均解。

4 结束语

本研究在蚁群算法的基础上提出了新的求解柔性job-shop调度问题的自适应蚁群算法。FJSP与JSP的不同在于增加了机器选择这一环节,使得求解更加复杂,本研究采取选择最早加工完工件工序的机器,该方法实现起来简单有效。同时采用自适应信息素更新策略,使算法能够快速跳出局部收敛,达到全局最优。经仿真比较,证明该算法是有效、可行的。

摘要：针对经典作业车间调度问题的局限性,结合实际生产情况,提出了具有路径柔性的作业车间调度模型,给出了求解模型的自适应蚁群算法的具体实现过程。在搜索解路径的过程中,该算法首先确定下一步可供选择加工的工件在哪台机器上加工最好;接着在选择机器后再确定该加工哪个工件;当所有蚂蚁爬行完毕后,针对算法是否陷入局部收敛,分别对各路径上的信息素进行了自适应调整,有助于快速得到全局最优解;最后,通过实例仿真验证了算法的有效性。

关键词：蚁群算法,柔性作业车间调度,自适应

参考文献

[1]DORIGO M,MANIEZZO V,COLORNI A.The ant system:optimization by a colony of cooperating agents[J].IEEETransactions on Systems,Man,and Cybernetics:PartB,1996,26(1):29-41.

[2]王常青,操云甫,戴国忠.用双向收敛蚁群算法解作业车间调度问题[J].计算机集成制造系统,2004,10(7):820-824.

[3]杨阿莉.一种改进蚁群算法在车间作业调度问题中的研究与应用[J].机械与电子,2005(4):9-12.

[4]CHAMBERS J B,BARNES J W.Tabu Search for the Flexi-ble-Routing Job Shop Problem[R].Austin:Technical Re-port Series ORP 96-10,Department of Mechanical Engi-neering,the University of Texas at Austin,1996.

[5]JANSEN K,SOLIS-OBA R,SVIRIDENKO M I.A LinearTime Approximation Scheme for the Job Shop SchedulingProblem[C].Dorit S Hochbaum,Klaus Jansen,Jose D PRolin,Alistair Sinclair,eds.Proceedings of the Second In-ternational Workshop on Approximation Algorithms(AP-PROX 99).Berkeley:Springer,1999.

[6]庞哈利.柔性job-shop集成化计划调度模型及其求解算法[J].控制与决策,2003,18(1):34-39.

[7]LENG Sheng,WEI Xiao-bin,ZHANG Weny.Improved acoscheduling algorithm based on flexible process[J].Trans-actions of Nanjing University of Aeronautics&Atronau-tics,2006,23(2):154-160.

[8]HISAO I,SHINA M,HIDES T.Modified simulated annea-ling algorithms for the flow shop S equencing problem[J].Euro J.of Operation Research,1995,81(2):388-398.

[9]赵巍,王万良.改进遗传算法求解柔性job-shop调度问题[J].东南大学学报:自然科学版,2003,33(z1):120-123.

自适应队列调度算法 篇6

供应链管理是对供应链商品流、物流、信息流、资金流以及合作者关系等规划、设计、运营、控制过程进行一体化的集成管理思想、方法和技术体系, 并且能够对市场的快速变化作出相应的反应。物流作为供应链管理过程的一个子过程, 可以解决生产点和消费点之间的计划编制、处理和货物存储控制等问题。实际上物流中心的货物流转控制是一个调度问题, 也是物流管理的一个核心问题, 这类问题通常都属于NP难问题。

在调度理论中, 供应链的调度问题是近几年才出现的。Shen和Norrie介绍了解决这个问题的几种方法, 但是由于这几种方法操作简单, 对于复杂的供应链优化问题具有其局限性。本文将自适应蚁群算法应用到供应链的调度中解决了这种局限性。

1 供应链调度描述及数学模型

物流过程作为供应链管理中的一个子过程一般分为五个部分, 订单到达、物件需求、物件到达、调度分派、订单交付。在物流过程中的一个关键环节就是资源分配, 即物件的调度分派问题, 如何对物流中心已有的物件进行分配, 并且使得需要按时交付的订单数目达到最优?物件的调度分配如图1所示。

本文使用自适应蚁群算法来解决这个组合优化问题。为此设物流中心有m个订单Oi (i=1, …, m) , 每份订单需要n种不同种类的物件Cj (j=1, …, n) , Oi需要Cj的数量为qij, 每份订单都要有一个到达时间ri和交付时间dr, 订单需要在货物延迟时间Lj内交付, 库存中已有的物件种类表示为Q, 每种物件的数量为qj (j=1, …, n) , 则物流调度过程的数学模型可以表示为:

minimize f (T) (Cost) (1)

Subject:${\rm O}{}_i\in 0(\text{i}\text{f}{\rm O}{}_i={\displaystyle \sum _{j=1}^{n}q}{}_{ij})i=1,\cdots ,m$ (2)

$q{}_{ij}\le q{}_j\in Qi=1‚\cdots ‚mf({\rm T})=\frac{1}{n{}_{{\rm T}}+\frac{1}{{\displaystyle {\sum }_{j=1}^n|}{\rm T}{}_j|}}$ (3)

(2) 式表示已经分配好的订单, 其中订单Oi由物件类型及其所需要的数量组成, 符合条件的订单所需要的物件的数量不能超出库存物件的数量。

2 基于自适应蚁群优化的物流调度算法

蚁群算法由 M.Dorio等人首先提出, 它是一种新型的拟生态系统算法, 自适应蚁群算法是蚁群算法一种改进型算法, 解决了蚁群算法容易出现的一些问题, 如:计算时间较长, 容易出现停滞等问题。

2.1 基本蚁群算法原理

蚂蚁在觅食的过程中会在其走过的路径上留下蚂蚁特有的一种称为信息素的分泌物质, 信息素能够影响一定范围内的蚂蚁, 经过某些路径的蚂蚁越多, 信息素的浓度就越大, 后来蚂蚁选择这些路径的概率也就越大, 更加增强了这些路径上信息素的强度。蚂蚁的这些群体行为表现出了一种正反馈现象:某条路径上走过的蚂蚁越多, 后来就会有更多的蚂蚁选择这条路径。

2.2 基于自适应蚁群优化的物流调度算法实现

在物流调度问题中, 等待交付的定单由图表中的一些节点组成;物流调度过程中存在两个实体, 订单及其物件, 物流中心的调度问题实际上就是订单所需物件的分发交付过程, 物件交付给订单的过程可以使用蚁群觅食过程来模拟实现。每种类型的物件可以看作食物源, 订单可看作是蚁巢, 对应于每个蚁巢可以寻找不同数量的不同类型的食物, 不同的蚁巢也可以有相同类型的食物。解决物流调度问题最主要的一个方面就是每只蚂蚁所访问的节点的数目是不相同的 (在TSP问题中, 每只蚂蚁所访问的节点的数目是相同的) 。

假设有m只蚂蚁, n个蚁巢, 每个食物源放一只蚂蚁。蚂蚁的主要工作就是把食物C送到n个蚁巢中, 在蚂蚁将食物C搬到n个蚁巢的过程中, 蚂蚁采用自适应的伪随机比率选择准则来选取下一个蚁巢节点, 同时, 在路径上留下信息素τ, 当来自各食物源的蚂蚁所剩物件的数量为空或者是均不能满足剩余的订单需求时称为一次周游。每只蚂蚁从Ci个物件中取出qij个传送给订单, 其中i= (1, …, m) , j= (1, …, n) 。因为蚂蚁要去多个蚁巢, 所以蚂蚁根据概率公式 (6) 选择下一个蚁巢, 这里, τ (i, j) 表示物件Ci分配给订单j后留下的信息素浓度, η (i, j) 表示物件Ci分配给订单j的启发式因子, β表示启发式因子的相对强弱, 通常, η (i, j) 与订单的日期延迟有关, 我们取日期延迟的指数函数。

η (i, j) =edj (4)

其中, dj表示订单的延迟, 即实际日期与被要求的日期之间的差值。我们规定η (i, j) =1 (dj=0) 表示所需物件能够按时交付订单, η (i, j) < 1 (dj<0) 表示被延迟的订单, η (i, j) > 1 ( dj>0) 表示正在等待处理的订单。

在选择下一个订单节点之前生成q, 如果q的值小于等于q (λ (t) ) , 则根据公式 (4) , 从订单节点到所有可行的订单节点中找出τ (i, u) ·ηβ (i, u) 中延长时间最长的订单, 即为下一个要选择的订单;如果随机数q大于q (λ (t) ) , 则按公式 (6) 来选择下一个订单。

q (λ (t) ) =λ (t) /N (6)

其中, λ (t) ∈[2, N]表示第t次循环的平均节点分支数, N表示订单数。τ (i, u) 表示i与订单u之间的信息素量, η (i, u) 是启发式因子, β表示启发式因子的相对强弱。

这里Γ为禁忌表, 代表了第k只蚂蚁已经完成的订单或者是不需要物件类型Ci的订单。蚂蚁选择了要处理的订单后, 在链接物件i和订单j的路径上留下信息素, 设信息激素的蒸发系数为ρ (0<ρ<1) , 表示信息素的蒸发程度, 路径上信息素的更新按下式进行调整,

公式 (8) 表明了蚂蚁k在是否选择订单j时要根据物件Ci的数量q${}_{ij}^k$是否满足订单j的数量qij需求进行选择;如果q${}_{ij}^k$≥qij时, 值为μ·edj, 因为如果有物件Ci的数量能够同时满足两个订单的需求, 则需要根据订单的延迟时间dj选择将物件分配给哪个订单, 如果q${}_{ij}^k$≤qij时, 物件Ci的数量不能满足订单j的需求, 则蚂蚁不能将物件Ci分配给订单j。

这里f (x) 是一个优化测试函数, 蚂蚁每完成一次游历都将结果存放在f (x) 中, 如果f (x+1) >f (x) , 则说明第x+1次游历要比第x次的优化结果要好, 此时, 信息素浓度应该增加, 否则, 信息素的浓度减少。

其中, (1-ρ) 表示信息素的消逝程度。

基于自适应蚁群优化的供应链调度算法描述如下:

3 仿真试验结果及其分析

设库存中有10种不同种类的物件, 有7份等待交付的订单, 每种不同种类的物件的数量分别为10, 每份订单所需要的物件的数量如表1所示。

τij的初值、α、β、ρ的值的变化对算法的结果, 算法运行时的稳定性等的影响很大, 因此本文分别对τij的初值, α, β, ρ的值进行多次试验, 最后结果表明, 当τij的初值为0.5, α=0.5, β=5, ρ=0.1时结果最优, 按时交付的订单为:3-7-4-2-5, 试验结果如表2所示;此时, 所交付的订单数目及其剩余的物件的数量达到了最优, 即按时交付的订单最多, 剩余的物件数量最少;算法的稳定性也比较好, 运行时间也相应减少了。

4 结束语

物流调度是供应链过程的一个关键的环节, 物件分派调度是物流调度的核心, 发挥着至关重要的作用。所涉及的调度算法能够有效地解决物流过程中物件的动态分派调度问题, 加快了物流中心物件的流通, 提高了工作效率。

参考文献

[1]Barbuceanu M, FoxM.Coordinating multiple agents in the supply chain[J].In:Proceedings of the Fifth Workshops on Enabling Technologyfor Collaborative Enterprises, WET ICE_96, IEEE Computer SocietyPress, 1996:134-141.

[2]Shen W, Norrie D H.Agent-based systems for intelligent manufactur-ing:a state-of-the-art survey[J].Knowledge and Information Systems, an International Journal, 1999, 1 (2) :129-156.

[3]Sousa J M, Palm R, Silva C, Runkler TA.Optimizing logistic processesusing a fuzzy decision making approach[J].IEEE Transactions on Sys-tems, Man, and Cybernetics Part A:Humans and Systems, 2003, 33 (2) :245-256.

[4]Colorni A, Dorigo M, Maniezzo V.Distributed optimization by ant colo-nies[A].Proc.1stEuropeanConf.Artificial Life[C].pans, France:Elsevier, 1991:134-142.

[5]胡小兵, 黄席樾, 等.一种新的自适应蚁群算法及其应用[J].计算机仿真, 2004, 21 (6) :108-109, 110-111.

自适应队列调度算法 篇7

关键词：蚁群算法,动态作业车间调度,自适应蚁群算法

0 引 言

车间调度是先进制造系统促进管理技术、运筹技术和优化技术发展的核心问题。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。早期这方面的研究主要集中于静态作业车间调度问题[1,2],而在实际的制造环境中,特别是在敏捷制造模式下,由于市场需求的变动导致动态的作业调度,新工件(或急需件)会随时加入作业队列,因此加工任务的发生时刻并不是被固定在时间轴上的单一点,而是出现在随机点。同时,由于设备故障等原因,加工所需的机床并非随时可利用,它们的可利用起始时间在时间轴上也呈随机分布。整个制造系统呈现开放性、动态性。因此,动态的作业车间调度问题(dynamic Job-Shop scheduling problem, DJSSP)更符合生产实际的需求特点。

本研究主要介绍基于自适应蚁群算法的动态作业车间调度问题的求解方法。

1 作业车间动态调度问题描述

生产系统是一个非常复杂的系统,本研究充分考虑了其中的差异因素,以生产过程中最基本的约束—机床为限制资源,以最大完工时间最小化为调度目标,建立了动态调度模型。

该模型[3]描述为:在一个加工系统中,有m台机床和n批工件,一台机床可加工若干道工序,工序的加工时间与机床性能有关,生产环境是动态的,生产过程中有订单源源不断地到来,机床有可能发生故障等。另外,假设工件的到达时间是某一时间段内的随机数;一旦工件的到达时间确定后,工件的加工信息也就确定了;任何工件没有抢占加工的特权;机床的启动时间只与工件类型相关,问题是如何为工件安排加工机床以使最大工件完成时间最小。

2 调度策略

本研究采用事件驱动调度策略,使系统状态发生变化的事件有:新订单的到达、撤销订单、机器出现故障、机器修复等等。这种策略可以很好地解决突发性事件对加工系统的影响问题,并且不会出现多余的重新调度,使算法的效率最高。这样就将动态调度问题分解成各个静态调度问题。由于触发系统重新调度的事件不一样,因此每次重调度的初始状态也就不同,下面本研究针对不同的触发事件给出相对应的确定初始状态的方法:

(1)订单任务的变化。当某时刻t0有订单任务发生变化时,此时需要重新确定各机器的可开始加工时间以及总的加工任务,如图1所示。

假设在t0时刻3台机器M1,M2,M3的加工队列如图1中的黑边方框所示,此时在t0时刻要重新调度,由于机器M2,M3有工件未加工完,要等加工完后才能加工其他工件,所以M2,M3的可开始加工时间分别为T2,T3,而M1在t0时刻没有加工任务,所以其可开始加工时间为t0。若是有新的订单到达则总加工任务为新到达的任务与上次调度在各机器本次调度可开始加工时间之后未加工的任务之和。若是撤消某个加工任务则总加工任务为上次调度在各机器本次调度可开始加工时间之后未加工的任务减去撤销的加工任务。

(2)可加工机器发生变化。当某时刻t0可加工机器发生变化时,此时需要重新确定各机器的可开始加工时间和总的加工任务,如图2所示。

在t0时刻前机器M1,M2,M3可用,M4有故障而不可用。从t0开始机器M1,M2,M4可用而M3由于出现故障而不可用。由于t0时刻机器M1没有加工任务,其可开始加工时间为t0;M2有加工任务,所以M2的可开始加工时刻为T2;M3出现故障,所以不可用;M4可开始加工时间为t0。重新调度的加工任务为上次调度在各机器本次可加工时间之后的任务加上机器M3在t0时刻上次调度安排的任务所得之和。

采用以上的事件驱动调度策略,便可将一个动态调度问题分解为若干个静态调度问题,对于单个静态调度问题,本研究在基本蚁群算法的基础上提出了一种自适应蚁群算法,该算法可以快速有效地跳出局部收敛,有利于搜索到全局最优解。

3 柔性Job-Shop调度中的自适应蚁群算法

由于柔性Job-Shop调度更符合实际生产情况,所以本研究将分解成的静态调度视为柔性Job-Shop调度问题[4]。

3.1 柔性Job-Shop调度问题的数学模型

3.1.1 描述柔性Job-Shop调度问题的变量

柔性Job-Shop调度问题的变量可描述为:n-工件数量;m-机器数量;Ji-工件i所包含的工序数;mijk-工件i的第j道工序在机器k上的加工时间;Sijk-工件i的第j道工序在机器k上的开始时间;Eijk-工件i的第j道工序在机器k上的完工时间;MPk-所有工件在机器k上的完工时间;MS-所有工件的最后完工时间。

则:

$\begin{array}{l}R{}_{ijegk}=\\ \{\begin{array}{l}1⌶\text{件}i\text{的}\text{第}j\text{道}⌶\text{序}\text{和}⌶\text{件}e\text{的}\text{第}g\text{道}⌶\text{序},\\ \text{在}\text{同}\text{一}\text{台}\text{机}\text{器}k\text{上}\text{执}\text{行}‚\text{若}⌶\text{序}j\text{先}\text{于}⌶\text{序}g\\ 0\text{其}\text{他};\end{array}\end{array}$

$X{}_{ijk}=\{\begin{array}{l}1\text{若}⌶\text{件}i\text{的}\text{第}j\text{道}⌶\text{序}\text{在}\text{机}\text{器}k\text{上}\text{执}\text{行},\\ 0\text{其}\text{他}。\end{array}$

3.1.2 柔性Job-Shop调度问题的数学描述

(1) 目标函数—使所有工件在系统中的流通时间最短:

${\rm M}in({\rm M}S)=\underset{k=1,2,...,m}{{\displaystyle mas}}({\rm M}{\rm P}{}_k)$

(2) 约束条件:

①顺序约束—工艺要求的同一工件相邻工序间的加工顺序:

Eijk-Ei(j-i)m≥mijk (1)

其中,i<j<Ji,Xijk=Xi(j-1)m=1。

式(1)表示工件i的第j道工序必须在第j-1道工序完成后才能开始。

②资源约束—同一机器k上一个加工任务完成后才能开始另一个任务的加工:

Eegk-Eijk≥megk (2)

其中,Xijk=Xegk=1,Rijegk=1。

式(2)表示任一确定时刻,机器k不能同时加工任意两个不同的工件,也不能同时加工任意两道不同的工序。

③其他约束—任何一道工序的完工时间不能小于其加工时间:

Eijk≥mijk,∀J (3)

其中,Xiqk=1。

3.2基于自适应蚁群算法求解柔性Job-Shop调度问题的过程

(1)机器选择规则。

柔性Job-Shop调度问题与一般JobShop调度问题的不同之处是增加了机器选择这一环节,待加工工件的工序可以在多台机器上实现,因此选择最优的机器加工工件将改善算法解的质量。本研究采用一种简单有效的方法,即选取完成加工第i个工件的第j道工序pij最早的机器,使工序pij能最早完成,从而也能减小整批工件的最大完成时间,机器选择规则如图3所示。

假设M1,M2,M3为可加工工序pij的3台机器,τ为工序pij的顺序约束,T1,T2,T3分别为机器M1,M2,M3的机器约束,斜线花纹方框表示工序pij分别在3台机器上的可加工最早时间段,由图3可知,工序pij在3台机器上加工的最早完成时间分别为:t1,t2,t3,且t1<t2<t3,因此选择机器M1加工工序pij。

(2)状态转移规则。

第k只蚂蚁由节点r转移到节点s的概率为:

式中τij—节点r到节点s(其中s表示第i个工件的第j道工序)的信息素;ηij—节点r到节点s的可见度;pij—第i个工件的第j道工序;pimax—第i个工件的最大工序;α、β—信息素和可见度的偏重系数。

可见度ηij为:

式中twait—在加工pij前的等待时间

为了避免因twait=0而使可见度趋于无限大,同时考虑到分母为1时,ηij=1,偏重系数β不起作用,故在分母加上常数c(c>1)以保证可见度对节点选择的影响,在算法具体实现时取c=2。经过式(4)计算后,再用轮盘赌方法从工件集中选择一个节点,并记下这个节点的起止时间,以便计算等待时间和最后完成所有工件的加工时间。

(3)判断是否发生局部收敛。

各代所有蚂蚁爬行完毕后对所搜索到的最优解进行判断,看是否陷入局部收敛,判断方法如下:当连续几代最优蚂蚁搜索得到的路径相同时,算法即陷入了局部收敛,此时最优蚂蚁的爬行路径总长度相同,故认为当连续几代的最优蚂蚁爬行路径总长度相同时算法陷入了局部最优,在Job-Shop调度问题中即为:连续几代搜索到的最大完工时间相同时发生局部收敛。

4)自适应信息素更新策略

在前一步判断算法是否陷入局部收敛的基础上,本研究采用两种信息素更新策略。这样可以使算法快速跳出局部收敛,向全局最优解方向搜索。两种更新策略如下:(1)当算法未陷入局部收敛时,采用全局更新和局部更新相结合的策略[5]。

首先,更新该代最优路径l上的信息素,如下所示:

其中,Δτ=Q/L,L为路径l的长度

然后,更新所有蚂蚁爬行路径上的信息素,同式(6)

(2)当算法陷入局部收敛时,信息素更新策略如下:首先,计算除最优蚂蚁l外其他所有蚂蚁经过路径上的信息素增量:

其次,计算蚂蚁l经过的路径上的信息素增量:

然后,更新除蚂蚁l外所有其他蚂蚁经过路径上的信息素

最后,更新蚂蚁l经过路径上的信息素[6]:

当算法陷入局部最优时,陷入局部最优解路径上的Q=-Q0×(n-n0),ρ=1-(1-ρ0)/(n-n0),因此当算法陷入局部收敛越深(即n越大)时,则Q越小,ρ越大,这样使得局部最优解路径上的信息素快速减小,而其他路径上的信息素继续积累,最终减小了局部最优解路径与其他路径上的信息素差距,使算法跳出局部收敛,最终收敛到全局最优解

限定信息素的范围

通过缩小各路径信息素的差距,可以使算法有更好的全局收敛性。本研究对各路径上的信息素进行了限定,以防止某些路径上的信息素过大或过小而影响算法的全局收敛性。仿真结果表明,τ的最优取值范围为:τ∈(1.0,3.5)。

4示例仿真

本研究试验选用的例子来自文献[7]和文献[8],该加工系统有6台机床,每批订单要加工4个工件,每个工件有3道工序,如表1所示(如工序p11代表第一个工件的第一道工序,可由机床1用2小时完成,或由机床2用3小时完成,或由机床3用4小时完成)。

经过多次试验,确定算法主要参数(蚂蚁数目,循环次数,Q0,ρ0,α,β)的最优选择范围,其结果如表2所示。

假设每隔10个时间单有1个批次工件进入车间,共有3个批次,对于单个次,文献[7]的结果是19,献[8]的结果是18,而本研提出的自适应蚁群算法的果是17,优于文献[7]和文[8]。甘特图如图4所示。

当对3个批次进行调度时,求得所需要的时间为39,调度结果甘特图如图5所示

从以上仿真结果可以看出,无论是用于解决单批次还是多批次调度问题,本算法均能获得较好的解,并优于文献[7]和文献[8]的结果,从而验证了算法的有效性。

5结束语

本研究采用事件驱动策略求解动态作业车间调度问题,针对订单任务的变化、机器加工情况的变化给出了详细的调度策略,将动态调度分解为各个静态调度区间,对于每次的静态调度,笔者在基本蚁群算法的基础上提出了一种新的自适应蚁群算法,该算法通过判断“搜索结果是否陷入局部收敛”自动调整信息素更新策略,使算法快速跳出局部收敛,向全局最优解进行搜索。

参考文献

[1]杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间调度问题[J].计算机集成制造系统,2004,10(9):1114-1119.

[2]王常青,操云甫,戴国忠.用双向收敛蚁群算法解作业车间调度问题[J].计算机集成制造系统,2004,10(7):820-824.

[3]LIN S,GOODMAN E D,PUNCH W E.A Genetic Algo-rithm Approach to Dynamic Job-Shop Scheduling Problems[C].The Seventh International Conference on Genetic Algo-rithm,San Francisco,1997.

[4]BIERWIRTH C,MATTFELD D C.Production Schedulingand Rescheduling with Genetic Algorithms[J].Evolution-ary Computation,1999,7(1):1-17.

[5]CHURCH L,UZSOY R.Analysis of periodic and event-driven rescheduling policies in dynamic shops[J].Interna-tional Journal of Computer Integrated Manufacturing,1992,5(3):153-163.

[6]王志亮,汪惠芬,张友良.动态Job-Shop调度问题的一种自适应遗传算法[J].中国机械工程,2004,15(11):995-999.

[7]阎志华,丁秋林.用蜂群算法实现动态作业车间调度[J].组合机床与自动化加工技术,2004(2):47-50.