协同调度控制

2024-06-14

协同调度控制（精选7篇）

协同调度控制篇1

网络控制系统(NCS)[1]的性能不仅取决于控制策略,而且与网络服务质量(QoS)有着密切关系。然而,通常情况下,网络控制系统的设计是分两步进行的,即设计好调度器后再设计控制器,这样往往会导致控制性能不好,资源利用率偏低等结果,也就很难满足实时要求较高的NCS,因此很有必要从系统实时性出发,将控制策略的选择与网络服务质量的调节相结合,这种设计问题称为网络控制系统的协同设计[2,3,4,5]。

研究控制和调度的协同设计,其目标是利用有限的网络资源维持良好的闭环控制系统性能。本文提出一种自适应遗传算法,对网络控制系统进行优化调度,实现系统控制与调度协同设计的目的。仿真结果表明设计方案既能提高系统性能,又能提高网络资源利用率。

1 网络控制系统调度

1.1 NCS时态特性分析

随着当前工控技术的发展和CPU价格的降低,许多控制场合都使用了性能强大的带有CPU的实时控制系统,这种控制方式不仅能减少控制器的使用数量,还能有效地集成多个控制环,便于相关的控制环之间进行协调。如图1所示,一个网络可以由多个控制回路/节点共享,同一控制器可以负责执行多个控制任务。

考虑NCS中的单个控制回路,网络时延可以表示为:

式中,k为采样序号,τkc为控制器计算时延,τksc和τkca分别为传感器至控制器和控制器至执行器的端到端通信时延。

当多个控制回路共享同一嵌入式控制器时,单个回路的计算时延将会大大增加,其变化的范围也将会变大。对于确定的计算平台以及相同的控制任务来说,单个回路的计算时延将在很大程度上依赖于控制器内部所采用的调度策略。

1.2 RM静态调度算法

速率单调(RM)算法,最初是由Liu和Layland提出[6],并在单处理器任务调度中得到了广泛的应用。所谓的RM调度,就是为每一个周期任务指定一个固定的优先级,该优先级按照任务周期的长短顺序排列,任务周期越短,其优先级越高,调度总是试图最先运行周期最短的任务。网络调度任务是非先占型的调度任务,判断一组网络调度任务可行性的充分条件由定理1给出。

定理1[7]由N个不相关的、非先占的、周期性任务集(用i的降序代表权限优先级,i=1表示最高优先级,i=N表示最低优先级)是可调度的,若对于任意i∈{1,2,…,N},满足:

式中,bl,i为相应第i个任务由于低权限引起的最差情况下的闭锁时间,即。

定理1给出了一组网络任务调度可行性的充分条件,作为拓展联想到问题:对于网络的某个性能指标,如何选择最优的网络调度策略,使得该性能指标最优呢?考虑由N个NCS组成的耦合系统,每一个任务的传输周期为hi,上界为hup,i,传输时间为ci。假设对每个NCS都定义一个性能指标,其为传输周期hi的函数,记为Ji(hi),于是可得优化问题:。

其中约束条件为:

1)RM调度算法约束:

2)NCS稳定性约束:

其中hup,i为使NCS稳定的传输周期上界,文献[8]给出求取该值的方法。bi为第个任务的闭锁时间,在设定hi的上界时,必须将其考虑进去。

这样,就得到一个关于NCS的优化问题,优化的对象是各个NCS任务的传输周期。这里性能指标函数Ji(hi)的选取是优化问题的关键所在,在NCS的调度策略中,一般将其选取为传输周期的二次函数或指数函数。

2 自适应遗传算法

遗传算法参数中,交叉概率pc和变异概率pm的选择是影响遗传算法行为和性能的关键,直接影响算法的收敛性。另外,遗传算法用来求解多峰函数最优化问题时应具备两种能力:1)局部搜索能力;2)全局搜索能力。这两方面的均衡是由pc和pm来保证的。因此,确定pc和pm是设计遗传算法时一项很重要的工作[9]。传统的遗传算法通常根据不同的优化问题,经反复实验来确定pc和pm,非常繁琐且很难找到适应于每个解的最佳值。针对此问题,Srinvivas等[10]提出一种自适应遗传算法(AGA)。

AGA基本思路为:当群体中各个个体适应度趋于一致或局部最优解时,pc和pm增加;而当群体适应度比较分散时,pc和pm减少。同时,对于适应度值高于群体平均适应度值的个体,对应于较低的pc和pm,使该解得以保护而进入下一代;而低于平均适应度值的个体,对应于较高的pc和pm,使该解有机会被淘汰。因此,自适应的pc和pm能够提供相对某个解的最佳pc和pm。算法公式如下:

式中,fmax为群体中最大的适应度值;favg为每代群体的平均适应度值;f'为要交叉的两个个体中较大的适应度值;f为变异个体的适应度值。

这里,只要设定k1、k2、k3、k4取(0,1)区间的值,pc和pm就可以自适应地进行调整。对式(2)和式(3)进行分析可知:适应度与交叉率和变异率之间呈简单的线性映射关系,如图2所示。图中有k1=k2=k,k3=k4=k'。

由图2可以看出,当适应度值越接近最大适应度值时,交叉和变异概率的值就越小;当等于最大适应度值时,交叉和变异概率的值为零。这种调整方式对群体进化后期比较合适,但对进化初期不利。这是因为在进化后期,群体中每个个体基本上表现出较优的性能,此时不宜对个体进行较大的变化,以免破坏个体的优良性能结构;而在初期阶段,群体中较优的个体几乎处于一种不变的状态,但此时的优良个体并不能保证就是问题的全局最优解。为此,对该方法进一步改进,使群体中最大适应度值的个体的交叉和变异概率不为零,分别提高到pc2和pm2,这就相应地提高了群体中表现优良的个体的交叉和变异概率,使它们不会处于一种近似停滞不前的状态。经过改进后,算法公式为:

3 调度优化设计

3.1 编码

编码是应用遗传算法时所要解决的首要问题。对NCS任务采样周期进行编码,如图3所示。

图3中,hi(i=1,2,…,N)表示各个网络任务的传输周期,采用二进制编码,其位数m由所需要的精度决定。

3.2 适应度函数

适应度函数是根据目标函数确定的,用于区分群体中个体优劣的标准,是算法演化过程的驱动力,也是进行自然选择的唯一依据。在NCS中,优化的目的是使性能指标f(hi)最小化。也即是说,越低的f(hi)对应NCS的性能越好。在算法设计过程中,选取适应度函数为F=(hi)。

3.3 遗传算子

遗传算子主要包括选择、交叉和变异。选择是在群体中选出生命力强的个体产生新群体的过程。这里采用轮盘赌选择方法。交叉是指对两个相互配对的染色体按照某种方式相互交换其部分基因,从而形成两个新的个体。这里选取单点交叉方法。变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换,从而形成一个新个体。这里采用基本位变异方法。根据前面介绍的自适应遗传算法,交叉概率和变异概率能够随着适应度进行自动调整。

4 仿真研究

考虑如下NCS:

式中,x(t)表示被控对象状态,x赞(t)为控制器状态,其为分段连续的,i=1,2,…,N。

取N=3,相应α的取值分别为25,20,15;k的取值分别为50,45,30。假设各任务执行时间相同,为c1=c2=c3=4ms。

定义传输误差为e(t)=x(t)-x(tk),t∈[tk,tk+1),则e(t)也为分段连续的,并且有e(0)=0。利用传输误差e(t)作为系统(6)的性能指标。根据文献[8]定义第i个任务的性能指标为:

式中,ai=ai-ki。

取适应度函数为:

相关参数及结果如表1和图4所示。

由仿真结果可知,三个任务均满足可调度条件。通过文中提出的自适应遗传算法的优化迭代,系统传输误差得到了最小化处理,系统性能以及网络利用率均得到了一定程度的改善。

5 结论

调度是网络控制系统中的基本问题之一,尤其在对实时性和控制性能要求较高的网络控制系统中,调度是至关重要的。本文研究了控制与调度协同设计的方法,基于RM静态调度算法,在满足系统稳定性和网络可调度性双重约束的条件下,提出一种自适应遗传算法,对网络控制系统各任务传输周期进行优化。仿真结果表明了该方法既能提高系统性能,又能提高网络资源利用率。

摘要：针对网络控制系统的性能由控制策略及网络服务质量共同决定,研究了控制与调度协同设计的问题。基于RM静态调度算法在满足系统稳定性和网络可调度性双重约束的条件下,提出一种自适应遗传算法,对网络控制系统各网络任务采样周期进行调度优化。仿真结果表明了该方法既能提高系统性能,又能提高网络资源利用率。

关键词：网络控制系统,自适应遗传算法,网络服务质量,协同设计,调度

参考文献

[1]杨灿,朱善安,孔万增.一种网络控制新方法及其液位控制应用[J].计算机测量与控制,2006,14(5):638-641.

[2]Colandairaj J,Irwin G W,Scanlon W G.Wireless networked control systems with qos-based sampling[J].IEE Proc.,Control Theory Appl.,2007,1(1):430-438.

[3]Zhang L,Hua-Jing F.A novel controller design and evaluation for networked controlsystems with time-variant delays[J].Frankl J.Inst.,Eng.Appl.Math.,2006,343:161-167.

[4]Lian F L,Yook J K,Tilbury D M,et al.Network architecture and communication mod-ules for guaranteeing acceptable control and communication performance for networkedmulti-agent systems[J].IEEE Trans.Ind.Inform.,2006,2(1):12-24.

[5]Ben Gaid M E M,Cela A,Hamam Y.Optimal integrated control and scheduling of networked control systems with communication con-straints:application to a car suspension system[J].IEEE Trans.Control Syst.Technol.,2006,14(4):776-787.

[6]Liu C L,Layland J W.Scheduling algorithm for multiprogramming in a hard-real-time environment[J].Journal of the Association forComputing Machinery,1973,20(1):46-61.

[7]Sha L,Rajkumar R,Lehoczky L.Priority inheritance protoclos:an approach to real-time synchronization[J].IEEE Tansactions on Com-puters,1990,390:1175-1185.

[8]Zhang W.Stability analysis of networked control systems[D].Ph.D.dissertation,Case Western Reserve University,2001.

[9]Wang L,Zhang L,Zheng D Z.The ordinal optimization of genetic control parameters for flow shop scheduling[J].The InternationalJournal of Advanced Manufacturing Technology,2004(23):812-819.

[10]Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems,Manand Cybernetics,1994,24(4):656-667.

协同调度控制篇2

装备制造业的快速发展,对设备的性能和可靠性提出了更高的要求;这类设备中很大一部分是运动控制系统(即对机械运动部件的位置、速度等进行实时的控制管理,使其按照预期的运动轨迹和规定的运动参数进行运动)。而运动控制系统是一种典型的控制循环周期短且具有高精度、高动态响应要求的控制系统,除了要求高性能的传输之外,它要求系统能在极短的时间内做出响应。过去的单机系统和点对点的连接方式,不能满足各节点对实时性和快速性的要求和需要交换的信息量的迅速增长。例如:高速、高精加工、设备状态的在线监控等对数据的实时性和快速动态响应提出的高要求。为满足运动控制系统的高可靠性和高实时性要求,需要借助嵌入式技术和网络技术来实现。

通过网络将系统部件或子系统连接起来,带来了明显的优势:相对点对点连接,简化了布线,降低布线和维护成本;实现设备即插即用和互换;采用数字信号传输,抗干扰性提高;便于系统信息集成和设备诊断。但是,网络环节的加入使经典控制中的很多假设条件(等时间采样、同步控制、无延迟的传感器和执行器信号)不再成立,使系统的分析和设计增加了很大的难度:网络时延、数据丢包等。

网络化运动控制系统(NMCS)就是构建在控制器与多轴电机驱动器之间,能够实时、同步地传送运动控制指令和接收运动状态的控制系统,是一类特殊的网络控制系统。网络化运动控制的性能不仅取决于控制算法设计,而且与网络和计算资源的调度密切相关。所以,有必要专门针对运动控制系统在网络化环境下的资源调度和性能优化进行深入研究,这对促进我国高性能装备制造业的发展有较强的理论和现实意义。

2 网络化运动控制系统的典型结构

传统的多轴运动控制系统主要采用分层结构实现,即各轴具有独立的控制器和传感器及触发器,再由主控制器对各轴进行协调控制,分层结构具有明显的缺点:不便于节点的加入和功能的扩充;在线任务监控需要两步才能完成(主控制器到各从控制器;再从轴控制器到传感器和触发器);信息交换量大,控制算法复杂。

随着嵌入式处理器功能的不断增强和体积不断缩小及与网络技术的融合,以往分层的控制结构正在逐渐被扁平(单层)结构取代。扁平结构:借用现场总线系统的概念,既要求所有节点(主控制器、轴控制器、传感器和触发器)都具有一定数据处理能力和通信能力,并且挂接于同一共享总线,形成分布式和网络化的反馈控制系统,这种结构就是典型的网络化控制系统(Networked Control Systems),又因为其用于运动控制,所以可以称作网络化运动控制系统NMCS (Networked Motion Control Systems)。由主控制器完成控制任务,各轴均通过具有通信功能和简单数据处理能力的智能节点组成,负责与主控制器进行数据交换和控制功能指令的实施,主控制器上运行多个控制任务来实现对各轴的独立控制和协调同步控制,共同完成系统功能。我们可以将NMCS抽象为一种典型结构,这里主要考虑主处理器与各轴传感器和触发器的数据交换,所以可以看作单CPU下的多任务控制系统,NMCS的典型结构图见图1。又因为各轴的控制器任务可以直接施加给触发器(即触发器与控制器直接连接),可以将各控制任务映射于各节点,这样,各轴的控制系统可以看作一个个单独的闭环,通过传感器和控制器与网络连接,结构如图2所示。

3 研究现状

NMCS是由网络和控制组成的控制系统,其闭环性能不仅依赖于控制算法的设计,而且依赖于对网络资源的调度。目前,专门针对NMCS的研究并不多见,主要偏重于对通用的网络控制系统NCS的研究,大多数对网络控制系统的研究集中于两个方面:网络方面和控制方面。

网络方面:采用实时网络,改善网络性能(减少网络诱导时延和丢包的可能),尽力保证QoSt

控制方面:网络协议作为已知条件,考虑时延和丢包来设计优化算法补偿网络带来的不利影响,尽力保证QoC。

上述方法的共同缺点:割裂了网络和控制的内在联系,无法取得良好的整体性能。因为网络控制系统的性能不仅依赖于控制算法设计,还与网络传输资源的调度密切相关。

从时延和丢包产生的原因来看:

多个控制任务共享同一CPU一>任务冲突一>任务丢失和任务时延;

多个节点共享同一总线—>数据包传输冲突一>数据包丢包和网络时延;

而且由共享引起的竞争具有随机性,必然导致时延和丢包也具有随机性。

所以,从兼顾QoS和QoC的角度出发的综合控制与调度的研究策略将网络运行性能、带宽资源限制等更多的网络因素融入控制系统设计和性能优化中,在控制系统设计的同时考虑网络实现的问题,实现系统的总体性能优化,必将成为解决NMCS问题的有效方法。而调度作为影响QoS和QoC的主要方面,它的性能优劣直接与系统的采样周期、时延长短、负载多少和控制性能等密切相关,可以作为协同设计的切入点。

网络化运动控制系统中的调度,从处理的对象上可分为:基于共享CPU资源的任务的可抢占调度;基于共享网络的数据包传输的不可抢占调度。网络调度主要考虑在多个回路的数据包共享通信网络的情况下,如何决定数据包有序地、实时地传送来满足控制系统的实时性要求。从调度的层次上可以分为:基于应用层之上的调度;基于网络协议底层(主要是数据链路层)的调度。下面对目前网络化控制系统中调度问题的主要研究方法做简单概括。

3.1 借鉴处理器任务调度的方法

NCS中的网络调度与CPU调度类似,都需要为并发任务分配共享资源、周期性激发并发任务以及满足任务截止期要求等(二者之间的对比详见表1),所以,在一定条件下可以借鉴任务调度的理论和方法对网络调度进行研究与分析。基于该思想,Zhang和Branicky等人[1,2,3]对经典的RM(Rate Monotonic)算法进行了改进,提出具有非抢占特点的RM调度算法,并将其应用于网络控制系统,同时给出了网络可调度的充分条件,蔡骅等人[4]在此基础上又提出了网络控制系统渐近稳定的充分条件。该类算法的关键在于RM调度策略的可调度性判据可表示为采样周期的函数,从而减小了NCS优化问题模型建立的难度。该调度策略的可调度性条件可以用数学表达式描述,是比较成熟的调度算法,适用于调度NCS中的周期数据。

3.2基于网络协议层的调度

Walsh等人[6]基于支持优先级的CAN网络提出了TOD(Try-Once-Discard)调度方法,基于最大误差优先技术(Maximum Error First),动态分配网络资源。规定节点信息传送的优先级与其相应的误差(同一信息经网络传输,其输出与输入之差)范数成比例,基于在线获取的网络诱导传输误差,动态分配网络带宽;当多个节点在传输中发生冲突时,具有最大误差的节点将取得网络资源使用权,竞争失败的节点放弃本次传输。该方法中,MEF将信息网络镜像值与传输值之间的误差控制在规定范围内,TOD丢弃旧的采样数据,始终采用最新的控制量更新系统,两方面的结合可以一定程度上保证信息的可靠性和实时性。

3.3 从采样周期或采样时刻角度开展的调度

根据Lian[7]对连续控制(CC)和数字控制(DC)方式下采样周期对系统性能影响的比较,可定性地建立网络控制(NC)方式下采样周期、网络运行性能和控制系统性能三者间的关系。在NC方式下,控制系统性能不仅受到采样周期的影响,而且受到网络运行性能的限制,为实现与DC方式下相同的控制系统性能,需减小采样周期以克服网络因素对系统性能的影响。从三者的关系图中可以看出,随着采样周期的减小,网络负荷虽然增大但网络运行性能基本不变,故系统性能逐步提高,但是当采样周期减小到一定程度(C点)后,由于网络负荷超过网络有限的承载能力,使网络时延增大,甚至引起抖动、丢包等问题,此时不但不能保证原有的系统性能,反而会导致系统性能的下降和恶化。所以,对于NCS,采样周期需要控制在适当的范围[TB,TC]内,否则系统性能很难保障。

从控制角度出发,seto[8,9]提出在系统稳定性和资源有限的约束下,寻找最优采样周期,使数据可以采用经典的RM或EDF算法进行调度。在此基础上,cervin[10]进一步研究了对时延变化系统选择采样周期的方法,并讨论了时延小于一个采样周期时对系统的影响。何坚强等人[11,12]分析了采样周期和时延对系统性能的影响,基于系统的稳定条件和可调度条件,以最小化实现系统性能指标函数为目标,提出了网络控制系统采样周期的选取方法,并且以网络可调度性和控制系统稳定性作为优化的约束条件,选取传输误差为目标函数,用遗传算法实现了调度优化。Kim和park等人[13,14,15,16]利用最大允许时延上界MADB (Maximum Allowable Delay Bound)进行采样时间的调度。首先利用Lyapunov方法、黎卡提方程、线性矩阵不等式LMI等方法获得MADB,进一步得到保证系统稳定的且不超过MADB的最大采样周期,并且对每个采样周期进行了带宽分配,从而保证周期性数据和偶发数据的实时性,同时使非实时数据对网络的占用最小。

3.4 基于时间窗口概念的调度

Raja等人[17]提出的动态时间窗带宽调度策略的基本思想是:每个循环周期可以分为周期时间窗和非周期时间窗,数据传输占用相应时间窗。为提高网络利用率,周期时间窗或非周期时间窗可以动态交替延伸(即在某一时间窗内未完成的传输可以占用下一时间窗),对周期信息可以采用RM算法或EDF算法来传输。Hong等人[18]提出调度窗口概念:使某一时间间隔内传输的数据包数目不超过动态分配的窗口数,从而保证传输。另外,刘鲁源等人[19]还利用窗口概念,在剩余时间窗口中调度非实时数据,在保证实时信息传输的同时,进一步提高网络利用率。窗口概念虽然可以保证网络化控制系统中各节点不会溢出,但是这类方法大多要基于支持优先级分配的网络(如CAN、Devicenet等),所以其实现依赖于底层网络的类型。

3.5 基于反馈控制的实时调度

当负载、任务性质和执行时间发生变化,在固定环境下设计的调度算法会使系统性能严重下降,此时必须根据系统当前状态,动态调整调度才能满足性能要求,利用控制理论中的反馈思想实现动态调度调整可以很好地解决这类问题。

Stankovic等人[20]提出的反馈控制实时调度概念的基本思想是:根据调度器的误差来调整调度器的参数,以维持系统的稳定性,并且使用PID控制器、服务等级控制器和准入控制器实现反馈控制EDF调度(Feedback Control Earliest Deadline First,FC-EDF)。在此基础上,Lu[21]等人进一步完善了FC-EDF调度算法,但是该算法仅仅考虑了CPU资源的分配,没有对网络资源的调度进行讨论。

3.6 基于QoC动态管理的调度

Marti等人[22]采用自适应控制器与反馈调度策略协同设计的方法,通过适当的信息调度,对所定义的控制质量QoC指标进行全面优化。利用在线自适应控制策略克服网络资源约束,通过信息调度实现动态QoC管理。

3.7 从QoS角度进行的调度

QoS可以通过若干性能指标来度量,它可以反映网络对不同级别的流量或应用给予相应级别服务的能力。常用的性能度量指标包括:带宽、延迟、延迟抖动(delay jitter)和丢包率等。通过对网络QoS进行动态管理,可以提高网络传输效率,减少传输时延及其抖动程度,进一步改善网络控制系统的控制性能QoC。Mo-Yuen等人[23]指出,由于时变的网络通信和扰动,网络QoS会发生变化,必须动态调整才能使系统控制性能不至于大幅度下降。并提出可以通过调整控制器增益来补偿QoS需求的变化,在此基础上,用网络化直流电机控制系统中验证了该方法的有效性。

3.8 基于死区的动态调度

网络性能恶化的一个很重要的原因就是通信趋于饱和,如果能够通过对信息的调度,减少网络通信流量,在某种程度上肯定能改善网络服务质量QoC,基于该思想,Otanez等人[24]提出了基于死区的动态调度策略,通过对网络各节点设置传输死区来控制访问网络的数据量,根据系统要求的性能确定死区的大小。该调度策略在确保系统性能的基础上动态地丢弃一定比率的数据来减轻网络负荷。存在的问题是,当多个获得网络访问权的数据包同时竞争网络资源时,该策略不能确定数据包发送的优先级。

3.9 利用网络中间件实现的动态调度

Tipsuwan[25]提出通过网络中间件在线获取网络当前的QoS状况,然后基于QoS动态调节控制系统的采样周期,并通过调节控制器的增益,获得可能的最优系统性能。Tipsuwan等人还用一个与随机延时网络相连的直流马达速度控制系统来阐述该控制方法。马达速度用一个PI控制器来控制,而要根据QoS调整的控制器参数为比例增益KP和积分增益KI。系统的性能由平均误差来表征:,网络QoS定义为:QoS(n)=[QoS,QoS2]T,n为表明QoS条件的索引,QoS1为点到点的网络吞吐量,QOS2为最大数据包的点到点最大时延上界。根据不同QoS(n)下的控制器增益,通过模拟的方法可以预先求得最优控制器的参数值并存放在一个查询表里面。这样当QoS发生改变之后,就可以根据当前的QoS在查询表里面找到当前应该设定的控制器的最优参数。该算法采用的是动态反馈调度模式,灵活性较好,但是控制器的增益需要人为进行调整,费时耗力,降低了算法的实际应用能力。

4 从网络调度出发的NMCS调度与控制协同设计方法

我们认为,调度与控制协同设计在网络化运动控制系统中具有双层涵义:

第一,考虑网络资源(带宽)调度和NMCS控制算法协同设计来共同优化系统性能;

第二,利用反馈控制理论解决网络资源的在线调度问题。

基本思想:根据调度器的误差(设定值和实际检测值之间的差值)来调整调度器的参数,在保证系统稳定的基础上,以最大化网络利用率和提高控制性能。

控制变量和被控输出变量的选择:在CPU的反馈调度中,通常可以选择利用率作为被控输出变量,但是在NCS中,不同于CPU调度的可抢占特点,网络调度是不可抢占的,所以很难获得一个准确的可调度利用率上界,而且在网络负载变化的条件下,网络利用率设定值也很难选择。丢包率也可以作为被控输出变量,因为通过将丢包率控制在某一(较低)水平,无论系统负载是否发生变化,都能够有效地将实际的网络利用率维持在其最大可能水平的附近,而且控制系统设计时往往都会留有稳定裕量,所以实际系统能够容忍一定程度的丢包。采样周期是反映控制性能和网络性能的重要指标,所以可以选择采用周期作为控制变量。NMCS反馈调度的基本工作原理可以描述如下:

反馈控制动态调度的系统结构:

反馈控制实时调度结构是由一个QoS资源反馈调度节点和一个QoC任务调度器组成的。其中,QoS资源反馈调度节点由监视器、QoS控制器以及调节器构成。反馈控制回路以时间触发方式,在每个采样周期都被激活,各部分作用可以简述如下:

QoC任务调度器:由实时操作系统内核提供的实时多任务调度,负责对各控制环在满足其控制性能的QoC指标要求下,进行整体调度。

QoS资源调度器:负责根据控制网络实际使用情况,在保证资源最大使用率的要求下,动态分配网络资源。

(1)监视器(Monitor):测量网络使用情况,将网络利用率和丢包率及时采集并且将采样值反馈到控制器。

(2)控制器(Controller):控制器把相应的网络资源控制变量与性能参考值相比较得出当前的误差,并且基于这个误差计算出总的预计利用率需求的改变量。控制器用一个控制函数来计算正确的操作变量的值来补偿负载的变化,使控制变量始终接近参考值。

(3)调节器(Regulator):在每个采样时刻k,调节器根据控制输入调整系统目标的等级,这样就能动态调整总的预计利用需求。调节器就是强制使总的利用需求达到控制器要求的预计利用需求。调节器使用一种最优算法来使系统值达到最大。

QoC任务调度器可以用实时操作系统支持的某种调度算法(如EDF或者RM)来调度共享网络的各控制环。调度算法的属性对于反馈控制回路的实时性非常重要,一般采用可抢占方式实现。设计反馈控制实时调度系统时,首先为QoC任务调度器选择调度算法,然后根据具体的调度算法相应地设计整个反馈控制调度系统。

一方面充分利用反馈调度可以最大化和在线对不确定环境(网络资源和负载的变化)进行调度,另一方面利用QoC周期与实时控制任务周期的一致性的特点,动态调整控制任务周期实现QoC动态变化,达到控制与调度集成,同时提高了网络资源的利用率与控制系统性能。为了进一步改善反馈调度性能,如何选择网络资源利用率的确切评价指标有待深入研究,如何将网络化运动控制系统中QoS反馈调度与QoC控制以最优化的方式结合,还需要进一步的探讨。

摘要：网络化运动控制系统是资源受限(带宽、时限)的系统，其控制性能不仅取决于控制算法而且与信息的调度密切相关。本文提出了网络化运动控制系统的典型结构，并对网络化运动控制系统中的调度问题作了综述。最后提出了基于网络调度的调度与控制协同设计的研究方法．

协同调度控制篇3

公交是一种高效利用道路资源的交通方式。世界上大城市公交系统承载的居民出行比重平均在50% ~60%,而我国大部分城市的公共交通出行比例不足30%[1]。换乘的不便使得我国公交对小汽车出行者的吸引力不强。有研究表明公交换乘是影响公交出行率的几个主要因素之一[2]。换乘在公交出行中又是非常常见的,如纽约有约36%的公交出行至少需要换乘一次,慕尼黑和巴黎有70%的公交出行至少需要一次换乘、40% 的公交出行换乘次数超过一次,伦敦有约30% 的公交出行至少需要一次换乘[3]。出行者特别是通勤出行者的换乘时间价值比在车时间价值要大2~3倍,同时公交需求量对换乘时间的敏感性要比在车时间高1倍[4]。因此,公交的同步换乘协调优化是提高公交吸引力的重要手段。

公交同步换乘协调优化问题已受到国内外学者的广泛关注。Ceder等[5]以最大化公交车同时到达换乘站的次数为目标,构建了混合整数规划模型,并设计了启发式算法,但这种同时到达的调度较为苛刻。Eranki[6]在Ce-der的基础上设定了一个换乘等待时间范围,在此范围内进行的换乘定义为同步换乘。而刘志刚等[7]则定义了一个协同系数来衡量公交同时到达车站的程度。石琴等[8]以车辆相遇总次数最大及总相遇点数最小为目标,研究了最大同步换乘的公交区域调度优化问题,但这种求总相遇点数最小的方法,会减少其他换乘站车辆相遇的次数,对其他换乘站的换乘造成不利影响。陈霞等[9]通过构建公交线网协同调度换乘复杂网络,以路网换乘点换乘车辆数最大作为优化目标,从路网结构层面提出换乘点换乘权重系数,建立了公交线网协同调度时刻表模型。Ibarra-Ro-jas O J等[10]以最大化同步的数量为目标,在给定同步换乘时间窗口下,研究了时刻表编制问题。Ang A,McIvor M[11]以直接换乘数量最大及总旅行时间的波动最小为目标,对比分析了滞站、越站策略增加直接换乘的情况。Nesheli M M,Ceder A[12]考虑同步换乘的数量及旅客出行时间,以总旅行时间最小为目标,研究了不同调度策略下公交同步换乘问题。上述研究大部分只考虑了换乘的同步性,没有考虑为其他乘客的等待时间及公交运营的成本。

本文综合考虑上述因素,以同步换乘人数最大、乘客总等待时间最小及公交车平均满载程度最大为目标,建立多目标公交同步换乘协同调度优化模型;采用基于小生境共享竞争复制算子的遗传算法求解该问题的pareto解集,并利用信息熵法对pareto解集进行决策优选。

2 问题描述

由于公交系统中固有的不确定性,很难调度有换乘关系的公交车同时到达换乘站,而在一个允许的换乘等待时间范围内进行换乘更具合理性。若一辆公交车到达换乘站的时刻与另一辆与其具有换乘关系的公交车出发时刻之差在某一个同步换乘时间窗口内,则称该辆公交车在该站可同步换乘另一辆公交车。在换乘时间窗口内的同步优化提高了不同线路之间的互动性、也为公交调度人员提供了更多的调度弹性。

由于公交系统中有多个换乘站,公交线路间存在多个换乘关系,可能会出现两辆公交车在一个站具有同步换乘,而在另一个换乘站却无法实现同步换乘,因此在衡量同步换乘时,不能以同步换乘的车站数量进行简单衡量,而应该考虑换乘站换乘旅客的数量,尽量使同步换乘的旅客数量最多。此外,公交运营管理者为了降低经营成本,往往会增大发车间隔,这会使得乘客在站等候时间增加,因而在进行公交调度时还需要综合考虑公交满载程度与乘客等待时间。

3 模型的建立

模型建立时考虑以下假设:

(1)公交线路上的车辆不存在超车情况;

(2)模拟期间,各公交线路的配车数满足派车数量要求。

3.1 符号及变量说明

L={l|l=1,2,…,N}为公交线路,N为公交线路数量,其中上下行线路分别表示;

V={Vl|l∈L}为公交站点集合,其中为线路l上的站点集合,vl0为停车场,ml为线路l的站点数量;

为换乘站点对集合,表示公交线路l1,l2在站点可以进行换乘;

B={Bl|l∈L}为公交车集合,表示公交线路l上的公交车集合,dl为公交线路l模拟期间的发车数;

表示公交车blk的载客能力,blk∈Bl,l∈L;

表示vli站公交车blk的乘客到达率及下车率;

表示公交线路l1在站点换乘l2线路的概率;

分别表示公交车blk在vli站的上、下车人数;

表示vli站未能上公交车blk的人数;

表示在vil站停站时公交车bkl上的乘客数;

g(bkl)表示公交车bkl的满载程度;

表示从公交站点vli-1至站点vli的行驶时间,i=1,2,…,ml,l∈L,当i=1时,表示公交车从停车场到始发站点的时间;

表示公交车blk在vli站的停站时间,blk∈Bl,vli∈Vl,l∈L;

w1,w2表示同步换乘的时间窗口;

表示公交车bkl从停车场发车的时刻,bkl∈Bl,l∈L;

表示公交车bkl到达车站vil的时刻;

T1,T2表示公交调度模拟时间窗口;

h1,h2表示模拟期间的最小及最大发车间隔;

为0,1变量,线路l1上的第k1辆公交车在是否可同步换乘l2上的第k2辆公交车.

3.2 公交车运行过程分析

(1)停站时间分析

公交车在车站的停站时间主要受车辆的停车、启动及乘客上下车的影响。Zolfaghari等[13]认为发车间隔不太大时,公交车的停站时间可以用线性方程近似表示。公交车的停站时间主要由两部分组成,分别为车辆的停车、启动及开关车门时间,乘客上车及下车时间,本文采用下式估算公交车的停站时间:

其中,c0表示车辆的停车、启动及开关车门时间,c1,c2分别表示每名乘客下车及上车时间参数。

高洁[14]通过调查分析发现开、关门时间一般为1~3秒,在直线式公交停靠站公交车进站停车时间一般在4~8秒,车辆离站启动时间一般在6~15 秒,每名乘客上车时间在2.6~3秒,下车为1.7~2秒。根据上述结果,本文分别取c0=0.27,c1=0.03,c2=0.05(分钟)。

(2)公交车到站时刻分析

公交车到达始发站的时刻为发车时刻与从停车场至始发站点的走行时间之和,即:

公交车到达非始发站的时刻为公交车到达上一站时刻与在上一站停站时间及上一站至本站走行时间之和,即:

3.3 公交车状态分析

(1)公交车上下车人数

公交车blk上的乘客在车站vli的下车人数为该站下车率与公交车上的乘客数之积,即:

乘客在车站的上车人数为公交车剩余容量与该站本时间段需要上车人数的较小值。该站本时间段需要上车人数包括前一辆公交车至本辆公交车到达时间段内陆续到达的乘客数、未能上前一辆公交车的乘客数及换乘本辆公交车的乘客数。在车站vli的上车人数可表示为:

(2)公交车上的乘客数

公交车上的乘客数为上一站公交车上的乘客数减去上一站下车乘客数加上一站上车乘客数,即:

(3)满载程度衡量

满载率一般可用车内实际的乘客数与车辆定员的比值来表示。可构建以下效用函数对满载率进行评价:

其中,α表示成本参数;β表示强度系数。本文取α=40,β=10。

3.4 乘客等待时间分析

(1)车站未能上车人数

车站未能上车人数为该站本时间段内需要上车人数减去实际上车人数,即:

(2)乘客候车等待时间分析

Larsen和Sunde[15]认为乘客平均候车时间为发车间隔的一半。如果公交车已经满载,乘客还需要等下一辆公交车,因此,乘客等待时间包括随机到达乘客的平均等待时间及未上车乘客的额外等候时间,即:

3.5 多目标公交同步换乘协同调度优化模型

根据上述分析,构建公交车同步换乘协同调度优化模型如下:

其中,式(10)表示最大化同步换乘人数,式(11)表示最小化乘客总候车等待时间,式(12)表示最大化公交车平均满载程度,式(13)为调度时间段约束,式(14)为公交车容量限制约束,式(15)为发车间隔限制约束,式(16)为同步换乘条件约束,式(17)为0-1变量约束。

4 模型求解算法

4.1 基于小生境共享竞争复制算子的遗传算法

(1)染色体的构造

CH=(ch1,chc,…,chN)表示一个染色体,N为公交线路数量,其中基因表示线路l上各公交车的发车时刻,发车时刻满足约束条件(13)及(15)。

依据约束条件(13)及(15),一个染色体的产生过程如下:

Step1:i=1;

Step2:如果i大于N,则终止,否则,k=1,转至Step3;

Step3:产生服从均匀分布u(h1,h2)的随机数u1;

Step4:如果k=1,则,否则,若,k =k+1转至Step3;否则,i=i+1,转至Step2;

随机产生pop_size个染色体,得到初始种群。

(2)选择操作

在不掌握任何偏好信息的情况下,可为决策者提供Pareto解。当产生了初始种群及每次迭代后,设种群中的Pareto解集为P.进行选择操作时,本文设计一种基于小生境的染色体竞争复制技术,无需计算染色体的适应值。其方法如下:

Step1:从Pareto解集P中随机选取size个染色体放入当代种群中,形成pop_size+size个染色体作为选择母体;

Step2:从选择母体中随机选择一对染色体CH1,CH2;

Step3:若CH1,CH2中有一个是Pareto解时,将其选作下一代染色体,若CH1,CH2均为Pareto解,或均为支配解,则依据Step4,Step5 的小生境数确定下一代染色体;

Step4:求小生境半径,设d1,d2,d3为选择母体中目标函数z1,z2,z3的最大值与最小值之差,小生境半径可表示为,θ为常数,一般取2~4;

Step5:为了保持群体中染色体的多样性,选择小生境内染色体少的进入下一代:统计CH1,CH2为中心的小生境内染色体数k1,k2,若k1<k2,则选CH1进入下一代,若k1>k2,则选CH2进入下一代,若k1=k2,随机选择一个进入下一代。

(3)基因交叉

按交叉概率Pc从父代选择一些染色体,两两分组,并对每组染色体进行如下操作:随机产生一个1到N的正整数,表示进行交叉的公交线路;将两条染色体中该公交线路的基因进行交换,从而得到两条新的染色体。

(4)变异操作

对pop_size个染色体以变异概率Pm进行变异:随机产生一个1到N的正整数,表示进行变异的线路;对被选择变异线路的基因,随机产生两个变异位置n1和n2,并重新产生其发车时刻,从而得到一条新的染色体。

4.2 Pareto解集的决策优选

信息熵法可反映目标信息熵值的效用价值,避免了人为的影响因素。利用遗传算法得到Pareto解集后,可以采用信息熵法对Pareto解集中的解进行决策优选,为公交调度提供参考。

利用信息熵法对Pareto解集中的解进行决策优选的计算过程如下:

Step1:写出Pareto解集的决策矩阵MAP×3,并对目标进行规范化,得到规范化矩阵Rij= [rij]P×3;

Step2:对规范化矩阵Rij进行列归一化运算,得归一化矩阵Hij= [hij]P×3;

Step3:计算第j个目标的熵值:

当hij=0时,令hijlnhij=0;

Step4:计算第j个目标的权重系数:

Step5:计算解i的综合目标值:

根据计算得到的综合目标值,按照从大到小进行排序,排在前面的解为综合效果较好的解。

5 算例分析

某区域内有四条公交线路,如图1所示。调度模拟时间窗口为8:00~8:30,最小及最大发车间隔h1,h2分别取3min及10min,同步换乘的时间窗口w1,w2分别为1min及5min,公交车载客能力为100人。主要换乘关系如表1所示,公交线路的站点及运行参数如表2所示。

运用本文设计的遗传算法及Pareto解集的优选方法计算,计算得到的Pareto解集及其目标值如表3 所示。Pareto解集中方案5的综合目标值最大,其线路发车时刻及运行状态如表4所示。具有同步换乘关系的车辆如表5所示。而采用固定发车间隔调度模式,本算例发车间隔在3min至10min间均未出现同步换乘情况。由此可见,本文设计的模型可以体现乘客的同步换乘问题。

5 结论

公交的同步换乘协调优化是提高公交服务水平的重要手段。本文综合考虑乘客及公交运营管理者两个方面,建立了多目标公交同步换乘协同调度优化模型,设计了基于小生境共享竞争复制算子的遗传算法求解该问题的pareto解集,并利用信息熵法对pareto解集进行决策优选。算例分析表明本模型在公交的同步换乘调度方面是合理可行的,但未模型未考虑滞站、越站等其它公交调度策略对同步换乘的影响,需要在今后进一步深入研究。

协同调度控制篇4

调度问题就是在规定的时间内进行资源调配和生产任务排序, 也就是根据生产车间的现状对生产任务按照时间进行分配。调度是生产管理中十分重要的一个方面, 特别是随着计算机集成制造系统的发展调度已经成为实CIMS的关键环节之一[1,2], 由此可见调度问题对于现代制造企业而言十分重要。

目前调度问题的求解主要有启发式[3]、规划调度[4]、人工智能调度[5]以及基于仿真[6,7]等自动形式的处理方法, 其核心是精确的数学模型或者仿真驱动模型, 并且都做了不同程度的问题或约束的简化处理。因此, 面对车间制造执行过程中存在的大量生产扰动因素, 以及调度自身的多约束、多目标等特点, 单纯依靠自动调度算法获得解析解的思路具有一定的局限性, 一方面难以形成满足实际复杂约束的调度方案, 另一方面, 无法适应由大量生产扰动事件导致的频繁的调度方案调整要求。而在调度排产过程中, 发挥核心因素的是具有丰富现场经验的车间调度人员, 而这正是目前调度系统缺乏深入考虑之处。

因此, 为了提高调度排产方案的实用性以及可行性水平, 以及应对实际生产过程中经常会发生的生产计划变更或者生产计划与实际生产不符等扰动现象, 必须重视调度排产中人因经验的介入机制和方法。所谓人机协同下的手动调度就是在计算机的辅助下由操作人员通过人机交互的方式生成车间排产方案。人机交下的调度方式能充分利用调度人员在实际生产中所积累起来经验, 手工调度方式能对实际生产过程中出现生产波动做出及时的反应[8]。因此人机协同下的手工调度能有效的辅助企业调度人员进行调度编排, 而目前缺乏这方面的研究[9,10]。

针对上述问题, 本文结合科研实际需求和生产经验, 采取面向对象的图形化工序块调度显示界面技术、标准化手动调度、调度过程中的约束传播控制以及调度数据结构等技术相结合的思路, 针对车间调度问题的实际需求研究并开发了人机协同的调度系统。需要指出的是, 在大量的调度任务面前如果仅仅依靠手工调度产生调度方案, 调度人员的工作量会很大, 而且提高调度效率的作用不明显, 因此本文提到的人机协同下的手工调度强调的是在自动调度基础上, 引入人机交互、协调的无缝集成操作机制, 实现计算机自动处理和调度人员经验的有机结合。

1 问题的提出

采用人机协同模式下的手工调度的目的是充分发挥人的认知作用和经验。在这样的系统中人可以通过人机交互界面监测数据和发布调度命令, 根据难以计算机化的经验规则对应用系统生成的辅助调度方案进行审查, 并执行修改调整操作。因此人机协同模式的调度系统就必须要解决以下问题:

1.1 以调度工序块为核心的图形化显示平台。

作为人机协同系统必须要向用户提供一个图形化操作的界面, 并且能够将传统排产方案图中的各个调度工序实现面向对象的离散化, 以支持用户通过该界面对调度方案进行生成以及修改等操作。以何种方式提供这个图形化的显示平台以及如何对调度操作进行响应都是需要解决的基础问题。

1.2 手工调整过程中的约束控制。

操作人员能够对调度方案进行修改是人机协同模式下的手工调度过程的一大特点, 但是同时必须要对此类操作过程进行约束, 例如当前调度块可加工设备的约束, 加工顺序的约束以及加工开始时间的约束等。只有在添加了约束后才能保证修改后的调度方案的合理性。

1.3 手工调度操作的标准化处理。

以人机协同模式下手工进行调度时或者手动进行调度方案修改时, 为了确保调度系统的模块化可扩展性以及实用性, 必须手工调度操作方式进行标准处理, 如将调度工序直接安排到某台加工设备上, 将加工工序插入到某道加工工序之后, 调整工序在设备内的加工顺序以及调整工序所使用的加工设备。

2 人机协同模式下的手工调度过程描述

为了充分发挥手工调度的处理效率和实际应用效果, 人机协同模式下的手工调度应该与自动调度相结合, 以充分发挥各自的优势。人机协同模式下的手工调度过程如图1所示。

人机协同下模式下的手工调度形成了一个闭环系统, 可以根据需求通过调整调度工序在设备内或者设备间的位置对调度方案进行调整。

3 人机协同模式下的手工调度关键技术

3.1 手工调度操作的标准化处理。

根据手工调度的目标和特点将其分为以下三种:指定加工设备、设备内移动调度工序块、设备间移动调度工序块, 分别以表1中的实例说明。

3.1.1 指定加工设备。

高工序, 需要某些指定的设备或者某个能力比较强的工人师傅进行操作, 才能够保证其顺利的加工, 所以提供了这种手动操作的模式, 如图4所示。设备内移动调

3.1.2 设备内移动调度工序块。

为了保证设备加工的连续性或者满足某些型号任务的交货期, 可以将已经排产后的任务的工序在其加工设备上的前移保证其能够尽快地完工, 则要求进行移动。设备内移动时调度工序块需要选定待移动的调度工序块和移动基准调度工序块, 如图5所示。

3.1.3 设备间移动调度工序块。

为了调整设备间的加工任务数, 平衡设备利用率, 或者通过转化后可以将原工序加工时间提前, 使任务能够尽可能的满足交货期, 系统提供了设备间移动调度工序块的功能, 移动时同样需要指定待转换移动的调度工序和基准调度工序, 如图6所示。

3.2 调度约束传播控制机制。

无论是指定加工设备、设备内移动调度工序块, 还是设备间移动调度工序块都必须在满足调度约束的情况下进行, 否则可能导致调度方案不可用。

本文采取的思路是在调度约束中引入了最早可开始加工时间的概念, 即如果该调度工序是零件的第一道工序则它的最早可开始时间为零件下达时间, 如果不是零件的第一道工序则它的最早可开始时间为该零件前一道工序加工完成时间。对调度问题描述如下:

i:设备指针;j:零件指针;p:调度工序在零件内的位置指针;q:调度工序在设备内的位置指针;TOi, j, p:尚未安排到设备上的调度工序集合;Oi, j, p, q:手工调度中待操作的含有零件和设备信息的调度工序, 若i, j, p, q取不同的值则表示相应的指针发生变化, 代表不同的调度工序块;Ci, j, p:工序Oi, j, p, q在设备i上的最早可开始加工时间;Bi, j, p, q:工序Oi, j, p, q在设备i上的开始加工时间;Ei, j, p, q:工序Oi, j, p, q在设备i上的加工完成时间;Ti, j, p:工序Oi, j, p, q在设备i上的加工工时;tr:当前调度安排可开始时间。

下面以插入到指定加工设备基准工序前为例对约束传播机制进行说明, 设备内移动调度工序块、设备间移动调度工序块以及受影响的调度工序块重调度步骤与之类似:

步骤1:在设备i上选择移动的基准工序Oi, j', p', q', 判断Ci, j, p是否早于Bi, j', p', q'?如果符合, 则转到步骤2;否则退出该算法;

步骤2:令Bi, j, p, q=Ci, j, p, Ei, j, p, q=Bi, j, p, q+Ti, j, p;

步骤3:判断设备i中Oi, j', p', q'前是否存在调度工序Oi, j", p", q'-1?如果存在, 则跳转到步骤4;否则, 跳转到步骤6;

步骤4:判断Ei, j", p", q'-1是否晚于Bi, j, p, q?如果晚于, 则跳转到步骤5;否则, 跳转到步骤6;

步骤5:令Bi, j, p, q=Ei, j", p", q'-1, Ei, j, p, q=Bi, j, p, q+Ti, j, p;

步骤6:判断Ei, j, p, q是否晚于Bi, j, p, q?如果晚于, 则跳转到步骤7;否则该算法结束;

步骤7:将受影响的调度工序块进行重调度。

3.3 调度数据结构。

在系统中为了保证每道调度工序在调度任务及调度方案中的数据完整性和严谨性, 以及手工调度的实用性, 对于每道调度工序采用两个数据链表对其进行约束。这两个链表分别为零件调度工序链表和设备调度工序链表。

其中零件调度工序链表中存储零件的加工工序序列, 可以用于确定工序的最早可开始加工时间等;设备调度工序链表中则存储在该台设备上所加工的调度工序序列, 当调度工序进行设备间或设备内移动时利用它对调度工序块进行定位。

假设零件j有m个调度工序, 其中第p (0

4 应用开发与验证

采用VC++6.0编程开发了人机协同调度软件系统, 实现了上述自动调度与手工调度的结合。所开发的软件已经在中船重工某研究所和航天某院的机加生产车间得到了应用, 取得了良好的效果。

5 结论

本文针对调度任务的复杂性和自动调度算法的局限性等问题, 提出了构建集自动调度和手工调度于一体的调度软件系统。通过对手工调度的分析为甘特图添加了出勤模式、鼠标拾取以及手动调度辅助功能, 形成了面向对象的图形化工序块调度界面。总结了手工调度的标准操作分为指定设备加工、在设备内进行调度工序块移动以及在设备间进行调度工序块移动三类。对三类操作下的约束传播机制进行了研究, 实现了对调度工序块进行手工调度时与之相关的调度约束一致性处理。通过将面向对象的图形化工序块调度界面、手工调度标准操作以及约束传播机制相结合, 形成人机协同模式下的手工调度。手工调度是自动调度重要补充, 是推动制造执行系统走向使用的关键技术。

摘要：针对自动调度模式无法充分发挥调度人员经验和有效响应制造执行复杂现场的问题, 提出了人机协同模式下的手工调度技术。建立了自动调度与手工调度相结合的人机协同模式;通过调度甘特图的分层显示处理, 采用设备出勤模式、鼠标拾取、手工调度辅助提示等技术, 实现了调度工序块的离散化面向对象处理;总结了手工调度中指定设备加工、在设备内移动以及设备间转换等三种标准化操作, 建立了以零件调度工序链表和设备调度工序链表为核心的调度数据结构, 分析了手工调度操作中的调度约束处理步骤, 采用重调度方法实现了调度约束满足的一致性处理;以工程应用背景, 开发了集自动调度和手工调度于一体的人机协同调度软件系统, 并通过实例验证了手工调度技术。

关键词：人机协同,手工调度,甘特图,调度约束,重调度

参考文献

[1]DUAN Congbi, YANG Jianjun.Research on Shop Control Systemof Nimble Manufacturing and FCS[J].New Technology&New Pro-cess, 2002 (7) :4-7 (in Chinese) .段丛斌, 杨建军.敏捷制造车间控制系统及有限能力调度研究[J].新技术新工艺, 2002 (7) :4-7.

[2]TANG Mao.Research and Develop on the Simulating System ofthe Intelligent Scheduling in the Agile Workshop[D].Chongqing:Sichuan Univercity, 2003 (in Chinese) .唐茂.敏捷化车间智能调度仿真系统的研究与开发[D].重庆:四川大学, 2003.

[3]CAO Quanjun, CHU Hongyan, FEI Renyuan.Application ofHeuristic Approach and Genetic Algorithm in Production Schedul-ing[J].China Mechanical Engineering, 2006 (S2) :211-214 (in Chi-nese) .曹全军, 初红艳, 费仁元.启发式算法和遗传算法在生产调度中的应用[J].中国机械工程, 2006 (S2) :211-214.

[4]JIN Feng, WU Cheng.Research status and prospects for massiveproduction scheduling[J].Computer Integrated Manufacturing Sys-tems, 2006, 12 (02) :161-168 (in Chinese) .金锋, 吴澄.大规模生产调度问题的研究现状与展望[J].计算机集成制造系统, 2006, 12 (2) :161-168.

[5]ZHOU Yongliang, HE Ping, LIU Liu.Computerized Schedule forLD-CC Steelmaking Based on Artificial Intelligence[J].SpecialSteel, 2003, 24 (3) :42-45 (in Chinese) .周永良, 何平, 刘浏.基于人工智能的转炉-连铸计算机化生产调度[J]特殊钢, 2003, 24 (3) :42-45.

[6]WANG Guoxin;NING Ruxin;WANG Aimin.Production optimalscheduling technology based on simulation[J].Computer IntegratedManufacturing Systems, 2007, 13 (7) :1419-1427 (in Chinese) .王国新, 宁汝新, 王爱民.基于仿真的生产调度优化技术研究[J].计算机集成制造系统, 2007, 13 (7) :1419-1427.

[7]ZHANG Xiaoping, LIU Quanli, WANG Wei.A Modeling Methodof Job Shop Scheduling Problem Based on SystemC[J].Control Engi-neering of China, 2007, 14 (4) :430-433 (in Chinese) .张晓平, 刘全利, 王伟.一种基于SystemC的Job Shop调度问题建模方法[J].控制工程, 2007, 14 (4) :430-433.

[8]Pang Hali, Wang Qing, Zheng Binglin.Distributive Production Su-pervision and Scheduling System for Steel Making Process[J].Journalof Northeastern University (Natural Science) , 1999, 20 (6) :580-582 (in Chinese) .庞哈利, 王庆, 郑秉霖.分布式炼钢—连铸在线生产调度系统[J].东北大学学报 (自然科学版) , 1999, 20 (6) :580-582.

[9]ZHAO Jun, CHEN Deren, HUANG Changqin.Visual schedulingbased on QoS in grid computing[J].Computer Integrated Manufactur-ing Systems, 2005, 11 (9) :1279-1284 (in chinese) .赵俊, 陈德人, 黄昌勤.基于服务质量的可视化网格调度研究[J].计算机集成制造系统, 2005, 11 (9) :1279-1284.

[10]XUE Bingliang, DUAN Xiangli, CHEN Dong.Gantt Chart Genera-tion of Production Planning for Advanced Manufacturing Shop-floor[J].Group Technology&Production Modernization, 2003, 20 (4) :23-26 (in Chinese) .薛炳良, 段香丽, 陈冬.先进制造车间生产计划的甘特图显示方法研究[J].成组技术与生产现代化, 2003, 20 (4) :23-26.

协同调度控制篇5

关键词：两级供应链,协同,遗传算法,生产作业调度

供应链如何以最短的时间生产出高质量、低价格的新产品已经成为市场竞争的新焦点。供应链要保持竞争力的关键就是有效的利用协同策略和技术,提高协同生产的能力和水平。研究显示,供应商和制造商之间的协同生产能够提高供应链的竞争力并实现供应链价值的增值[1,2,3]。

Alessandro A、Nicholas G H和Dario P从供应商的角度出发,以库存成本和运输成本最小化为目标,建立了一个供应商和多个制造商的两级供应链调度模型,并运用一种多项式时间算法进行求解[4]。Moon C、Kmj、Hur S以企业之间充分合作为基础,从产品总拖期时间最小的角度研究了供应链调度问题,建立了供应链优化模型,并采用遗传算法进行求解[5]。但是此文将供应链上个节点企业的生产资源进行统一规划进行调度,缺乏实际可行性。孙靖,林杰研究了信息不完全共享环境下的大规模供应链动态调度问题,提出了基于蚁群算法的企业交互调度模型,最后通过仿真实验对调度模型进行了求解[6]。

本文综合考虑水平型合作的供应商和纵向制造商的制造资源及加工工艺约束,以供应链实时信息交互为基础,研究包括一个制造商和多个供应商的两级供应链的协同生产,建立了供应链协同生产调度模型,并运用遗传算法对模型进行求解。

1 供应链协同生产作业调度模型

1.1 问题描述

综合考虑加工任务在制造商和供应商的分配和排序问题,假设制造商在某时刻需要加工零件Nk,k=1,2,…,p,p为零件总数。Nk={Oki|i=1,2,…,r,…,m},其中Oki表示零件Nk的第i道工序,m为零件Nk的工序数。

零件的前v(v∈{1,2,…,m})道工序由供应商生产,每道工序有多个供应商可以加工,而且加工时间不同;m-v道工序由制造商加工,在加工这些工序时存在并行机或多功能机床。加工过程中,假设同一零件的同一工序不能同时在2个供应商或制造商的两台机床上加工;零件的加工必须要按照工艺的约束依次进行加工,后道工序的加工必须在前道工序加工完成后才能进行;一台机床一次只能加工一道工序;零件的加工时间中包括运输时间。

调度的目标是通过为零件Nk的前v道工序选择合适的供应商,并由此确定该供应商中相应的加工机床;m-v道工序确定制造商中合适的加工机床。然后确定供应商、制造商每台机床所分配零件的加工顺序及开工时间,使得所有零件在供应链中的流通总时间最短。

1.2 供应链协同生产作业调度数学模型

模型的参数设定如下:E={1,2,…,l,…,e},指供应商集合。为方便描述问题,当l为e+1时表示制造商,供应商l拥有的机床集合Ml={1,2,…,j,…t,…,q},制造商的机床集合,MM={1,2,…,s,…,u}。Ptimkilj:零件Nk的工序Oki在供应商机床Mlj的加工时间;Stimkilj:零件Nk的工序Oki在供应商机床Mlj的开工时间;Ctimkilj:零件Nk的工序Oki在供应商机床Mlj的完工时间。

模型的决策变量:设定如下xkilj=1,如果零件Nk的工序Oki选择机床Ml,否则xkilj=0;yirlj=1,如果工序Oki先于Okr在机床Ml上加工,否则yirlj=0。

公式(1)表示目标函数,即最小化所有零件在供应链中的流通总时间,其中Ck表示零件k的完成时间;公式(2)和(3)表示一台机床在同一时刻只能加工一道工序,M为一个足够大的正整数;公式(4)表示每道工序只占用一台机床。

2 遗传算法的实现

由于车间调度问题多属于NP-hard问题,本文涉及到多个企业的车间调度,因此更加复杂。鉴于遗传算法具有并行搜素、鲁棒性和搜索效率高等优点[7],在求解NP问题上具有强大的搜索优势,因此本文选用遗传算法进行求解。

2.1 编码方法

本文选择一种基于工序调度优先级的编码方法。染色体采用整数编码,即每个染色体表示全部零件在所有制造商和供应商的机器上的加工顺序,对于加工p个零件,每个零件共有Okm道工序的情况,染色体长度为其中1至位表示所有零件的加工顺序,位表示零件Nk的第Okm工序的加工机器序号。

2.2 适应度值计算

由于遗传算法要比较适应度函数值,并在此基础上计算选择概率,适应度数值高的染色体被选择的概率也大,所以适应度值函数的值取正值并且能反映这一特性[8]。为了实现供应链的敏捷性,本文以所有零件在供应链中的流通总时间最短为目标,因此适应度函数定义如下:其中,g表示适应度函数,Ck表示零件k的完工时间。

2.3 选择操作

采用轮盘赌法选择适应度较好的染色体。首先按照轮盘赌选出:种群规模×代沟=临时种群,再由临时种群和保留适应度较好的染色体组成新的种群。

2.4 交叉操作

首先从种群中随机选取2个父代染色体为A、B,并取出每个染色体的前位,然后随机选择交叉位置进行单点交叉。举例如下,设交叉位置为7,交叉操作后得到子代染色体a、b。

交叉操作后,可能出现非法的子代染色体,即其中的部分基因对应的工序可能会缺失或者多余,因此需对子代染色体进行合法性分析及调整。按照交叉前染色体基因对应的操作机床来调整基因

2.5 变异操作

首先随机从种群中选取父代染色体A,然后随机的选择两个变异位置交换基因,再将两个变异位对应的加工机序号对换。如对父代染色体A进行变异,交换位置为4和10,操作如下:

3 算例研究

假设供应链中有1个制造商和2个供应商,在某时刻要完成N1,N2,N3,N44个零件的加工任务,零件的工序数分别为5、4、5、4道。零件N1,N2,N3的前三道工序由供应商加工,零件N4的前二道工序由供应商加工。全部零件的剩余工序由制造商完成,其中任一工序的加工过程中包含两台并行机。供应链中2个供应商拥有的机床集合分别为M1={M11,M12,M13}和M2={M21,M22,M23}。制造商拥有的机床集合为MM={MM1,MM2,MM3,MM4,MM5}。4个零件的工序在可选机床上的加工时间,如表1所示,其中“—”表示该工序不可在这台机床上加工。

运用Matlab7.0来编制遗传算法程序,计算在某品牌计算机上进行,运行环境为主频2.4G,内存512M。遗传算法的运行参数为:染色体的种群规模200,终止代数100,,代沟0.9,交叉率0.8,变异率0.1。按照本文的编码规则,对算例进行求解,得出所有零件的工序在供应商和制造商的机床上加工方案。近优调度方案,如图1所示,图中数字[101]表示零件N1的第一道工序O11,图1显示算例的最大完工时间Cmax=57。程序在运行到20代时,基本收敛到近优解。

对算例进行20次随机计算得到染色体适应值的最佳值fopt和染色体适应值的平均值fave。根据公式[9]δ=(fave-fopt)/fopt,计算染色体适应值的均值与最佳值的差别率δ。计算出δ小于9%,说明算法的寻优率达到90%以上,由此可见算法的有效性和鲁棒性。

4 结论

供应链协同生产作业调度的优化是一个很复杂而且具有现实研究意义的问题。本文从生产任务分配和排序协同解决的视角,研究了一个制造商和多个供应商的两级供应链生产调度,实现了供应链上生产任务的工序级协同调度。通过对算例的研究,表明了整数编码的遗传算法在求解该NP-hard问题上能很快找到近优解,并且具有很强的鲁棒性。

参考文献

[1]张翠华,范岩,于海斌,等.分散决策供应链生产计划协同研究[J].计算机集成制造系统,2008,14(8):1622-1629.

[2]聂兰顺,徐晓飞,战德臣.基于拉格郎日松弛和遗传算法的供应链协同计划[J].计算机集成制造系统,2006,12(11):1869-1875.

[3]TADEUSZ S.Coordinated supply chain scheduling[J].International journal of production economics,2009,120(2):437-451.

[4]ALESSANDRO A,NICHOLAS G H,DARIO P.Batch schedulingin a two-level supply chain-a focus on the supplie[rJ].European Journal of Operational Research,2006,173(1):226-240.

[5]MOON C,KMJ,HUR S.Integrated process planning and scheduling with minimizing total tardiness in multi-plants supply chain[J].Computers and Industrial Engineering,2002,43(1):331-349.

[6]孙靖,林杰.信息不完全共享下MC供应链动态调度模型研究[J].系统仿真学报,2007,19(9):1943-1948.

[7]ALAIN C,CALINHO T,VACHER J.Genetic algorithms usingmulti-objectives in a multi-agent system[J].Robotics and Autonomous Systems,2000,33(3):179-190.

[8]韩文明,范吉文.基于改进遗传算法的柔性作业车间调度问题研究[J].科学技术与工程,2008,8(22):135-137.

协同调度控制篇6

传统的制造系统采用自上而下的递进控制模式, 这种组织形式对生产过程的频繁调整和产品需求的动态变化反应迟缓, 从计划、调度和控制行为上看, 整个系统执行过程缺乏柔性, 个别环节的错误将导致整个系统的无法正常工作, 严重阻碍了JIT生产模式的实施。全球市场下, 迫切需要一种具有柔性良好、反应迅速和容错能力强的生产控制模式, 这种先进的控制模式既要兼顾到资源配置和资源成本, 同时要具备在一定成本效益优势情况下快速响应市场变化, 又具有自适应、自组织、自学习和自优化的能力。具体体现在以下三个主要方面:

①资源配置

人、材料和设备是制造过程中不可缺少的三种主要资源, 其中人是能动性最大的资源, 在柔性资源生产环境下, 定员制的刚性生产方式急需改变, 如何优化配置人员对产品准时交货起着重要的作用。企业在不改变生产设施布局的情况下, 希望通过把单功能机器升级为多功能机或者加工中心和调整不同技能水平的操作人员实现多品种和变批量的生产。因此, 在生产种类和数量频繁变化的生产环境下, 进行人员与多功能机或者工作中心的优化配置研究, 对提高柔性生产系统的生产率以及准时交货率具有现实意义。

②资源成本

企业各种活动的目标是盈利, 创造价值的过程有两种方式, 一种是通过产品生产过程中的价值附加实现, 一种是通过缩减资源成本来实现, 价值附加过程相对稳定的情况下, 通过缩减资源成本来提高企业的赢利能力就显得相对重要。人、材料和设备三种主要资源中, 在设备维护管理较健全和原材料市场相对稳定的情况下, 那么在生产线上, 不同的工人根据其技能水平的不同, 可以操作不同复杂程度的机器, 同样也需要支付不同的技能工资, 在最小化人员成本的情况下, 选择最佳的操作工人来操作相应的机器设备对节约人工成本来说至关重要。

③提前拖期惩罚

提前/拖期 (Earliness/Tardiness, E/T) 调度问题是为了监测生产进程和适应JIT生产方式的需要而提出的, 是非传统调度中最具代表性的一种, 在产品合同中, 产品 (工件) 的交货期服从时间窗分布, 如果在时间窗口内完成则惩罚为0, 如果提前和延迟完成都将受到惩罚, 从经济效益的角度来考虑, 提前完成会导致库存费用的增加, 它反映了占用资金和库存等费用。而拖期完成会受到合同惩罚, 它是反映快速响应市场的指标, 它反映了合同违约惩罚和失去顾客信誉等费用。

在近几年, 大量的生产调度研究论文相继发表, 但其中绝大多数的研究集中在仅机床设备受制约、工艺路线固定、以最小化生产周期为优化目标的单资源单目标的调度问题。然而, 实际的生产中, 调度体现出多样性、多约束性和动态性等特征, 如:多条工艺路线可选;多功能处理机或者加工中心可以处理不同工件的相应工序;工人操作熟练程度、工作技能和工资水平的差异性等。文献[1]以最小化完工时间为目标对多工艺路线调度进行了研究;文献[2]以最小完工时间和平均满意度最大为优化目标对双资源多工艺路线作业车间模糊调度进行了研究;文献[3]、[4]分别以混合粒子群和改进遗传算法对多工艺路线进行了优化;文献[5]以钢管生产调度为例, 研究了多产线共存下的生产工艺路线优化问题;但是都没有考虑生产中人的因素。工件的调度不仅要受到机床资源的制约, 而且受到工人资源的制约, 工人与机床不一定是一一对应的关系, 有的工人可以操作多台机床, 一味地追求调度算法的高效率而不考虑操作人员, 这种算法在车间生产中是无现实指导意义的。文献[6]考虑将机床和工人合理地分配给加工任务 (工序) ;文献[7]以各时间指标为目标对机床、人和机器人资源约束问题进行了研究;文献[8]对面向成本的车间调度优化模型进行了研究;这些文献仅考虑了人机配置优化, 但是没有涉及到人工成本。满足不同交货期的E/T调度问题是适应全球化市场的趋势下发展起来的, 目前, 对E/T调度的研究主要集中在单机问题上[9,10,11,12], 文献[13]对流水车间作业提前拖期调度问题进行了研究, 文献[14]研究了提前拖期调度问题在钢管生产上的应用, 可以看出关于车间作业的E/T调度研究几乎没有。

本文以适应现代先进制造模式的需求为出发点, 提出了资源优化配置、兼顾资源成本和提前拖期调度的模型和算法, 提高生产调度的自适应、自组织、自学习和自优化的能力。

1 问题描述及目标函数的确定

1.1 柔性生产系统调度问题描述

在生产车间加工过程中有Htotal个员工在m个加工中心S1, S2, …, Sm上处理n个工件J1, J2, …, Jn, 工件i (1≤i≤n) 的可选的工艺路线数为PJi条, 工件之间的加工顺序无约束, 每个工件的l个工序有先后约束, Ji= (Ji1, Ji2, …, Jil) 为工件Ji的工序序列, 其中可以操作第Si个加工中心的人数为Hi (1≤Hi≤Htotal) , 第Si个加工中心的机器数量为Sik, 每个工件Ji的加工时间为Pi, 完工时间为Ci, 交货期为di, 工件Ji的单位提前Ei、拖期Ti的惩罚系数分别为αi和βi.

1.2 工艺路线可变的车间作业调度问题描述

当多个工件在多台设备上加工时, 其工艺路线在加工前不能完全确定, 即每个工件的工艺路线可能有几条, 依据机器设备的空闲情况来决定。调度的任务是适当安排工件的加工顺序, 即确定各工件在各设备的加工开始时间, 在满足约束条件的同时, 优化某些性能指标。

1.3 生产调度常用目标体系

生产调度的目标可以是成本最小、库存最小、设备利用率最高、制造绿色度高、生产周期最短、生产切换最少等。生产调度目标归纳如图1所示。图中, 从生产制造商和客户的角度可以把调度目标进行细分, 制造商目标又可细分为能力指标和成本指标。本文分别选择三类指标体系中的优化资源利用、减少运行费用和按时交货为目标来研究车间调度。

1.4 目标函数

①每个工件Ji的加工时间为Pi, 完工时间为Ci, 交货期为di, 如果Ci<di, 则工件Ji受到提前惩罚;当Ji准时完成时, 损失为0;如果Ci>di, 则工件Ji受到拖期惩罚。工件Ji的单位提前Ei、拖期Ti的惩罚系数分别为αi和βi (i=1, 2, …, n) , 工件Ji所受到的提前、拖期惩罚分别为:

提前完工惩罚最小:

$F_{1} = \sum_{i = 1}^{n} E_{i} = \sum_{i = 1}^{n} α_{i} \cdot \max (0, d_{i} - c_{i}) (1)$

拖期完工惩罚最小:

$F_{2} = \sum_{i = 1}^{n} Τ_{i} = \sum_{i = 1}^{n} β_{i} \cdot \max (0, c_{i} - d_{i}) (2)$

②由于在实际生产的过程中, 企业追求的直接目标是最大化利润和最小化成本, 也就是说, 最佳的生产方式是工件能在规定的时间内以最小的成本顺利完工即可。

$\begin{array}{l} Η C \\ = \sum_{i = 1}^{n} \sum_{j = 1}^{l} \sum_{r = 1}^{R} Τ_{i j} \cdot W_{i j r} \cdot Η c_{r} \\ = \sum_{i = 1}^{n} \sum_{Q = 1}^{Ρ_{J_{i}}} \sum_{j = 1}^{l} \sum_{v = 1}^{m} \sum_{L = 1}^{S_{v k}} \sum_{r = 1}^{R} (Τ_{i Q j S_{v} L}) W_{i Q j S_{v} L} \cdot Η c_{r} \\ = \sum_{i = 1}^{n} \sum_{Q = 1}^{Ρ_{J_{i}}} \sum_{j = 1}^{l} \sum_{v = 1}^{m} \sum_{L = 1}^{S_{v k}} \sum_{r = 1}^{R} (F_{i Q j S_{v} L} - S_{i Q j S_{v} L}) W_{i Q j S_{v} L} \cdot Η c_{r} (3) \end{array}$

Tij:工件i的第j (Ji1≤j≤Jil) 道工序加工时间

TiQjSvL:工件i (1≤i≤n) 沿其第Q (1≤Q≤PJi) 条工艺路线在第Sv (1≤v≤m) 个加工中心上的第L个机器 (1≤L≤Svk) 上加工第j (Ji1≤j≤Jil) 道工序的加工时间

SiQjSvL:在设备L上的开始加工时间

FiQjSvL:在设备L上的完工时间

Hcr:能力等级为r (1≤r≤R) 的操作工人的单位工资成本

$\begin{array}{l} W_{i Q j S_{v} L r} \\ = {\begin{cases} 1, ⌶ 件 i 沿第 Q 条 ⌶ 艺路线在 S_{v} 加 ⌶ 中心第 L 个机 \\ 器上使用能力等级为 r 的操作 ⌶ 人加 ⌶ 第 j 道 ⌶ 序 \\ 0 ‚ 其它 \end{cases} \\ W_{i j r} = {\begin{cases} 1, ⌶ 件 i 的 j 道 ⌶ 序由能力等级 r 的操作 ⌶ 人加 ⌶ \\ 0 ‚ 其它 \end{cases} [B Τ 5] 1.5 约束条件 \end{array}$

①处理约束:不同工件的工序之间没有先后约束, 同一工件的工序之间有先后约束:

$\begin{array}{l} F_{i Q (j - 1) S v L} \leq S_{i Q j S v L} \leq F_{i Q j S v L} (4) \\ F_{i Q j S v L} = S_{i Q j S v L} + Τ_{i Q j S v L} (5) \end{array}$

②工人约束:两道不同的工序不能同时被一名工人加工, 而且任何一名工人在任何时候都不能加工一道以上的工序。

$\begin{array}{l} F_{i Q h w} - F_{p q s w} + Η Ζ_{i Q h p q s w} \\ + Η (1 - X_{i Q}) + Η (1 - X_{p q}) \geq Τ_{i Q h w} (6) \\ F_{p q s w} - F_{i Q h w} + Η (1 - Ζ_{i Q h p q s w}) \\ + Η (1 - X_{i Q}) + Η (1 - X_{p q}) \geq Τ_{p q s w} (7) \end{array}$

③每个工件的每道工序在任何一个工作中心上处理时不允许中断;

④所有工件在零时刻都可以被加工;

⑤机器约束:同一时刻一台机器只能加工一个工件

$F_{i h L} - F_{p s L} + Η (1 - Ζ_{i h p s L}) \geq Τ_{p s L} (8)$

其中, FihL和FpsL分别表示工件i的第h道工序在机器L上的完成时间和工件p的第s道工序在机器L上的加工时间, ZihpsL为机床L加工工序h和s的顺序判别条件, 如果工件i的第h道工序先于工件p的第s道工序被加工, 则ZihpsL=1, 否则ZihpsL=0;H为非常大的正数。TiQhw, FiQhw分别为工件i的第Q条工艺加工路线中的第h道工序由工人w加工的时间和加工完毕的时刻; ZiQhpqsw为机床L加工工序h和s的顺序判别条件, 当工序h和s都在机床L上被加工时, 如果工件i的第Q条工艺加工路线中的第h道工序先于工件p的第q条工艺加工路线中的第s道工序被加工, 则ZiQhpqsw=1, 否则ZiQhpqsw=0;

在保证以上约束的基础上, 同时要尽量减少各加工资源的空闲时间, 保证资源的利用率均衡。

2 算法设计

本文遗传算法的流程图如图2所示, 其具体的操作步骤如下。

2.1 编码及初始化

编码是实现遗传的基础, 是提高算法性能的瓶颈, 在过去的研究中, 已经提出了基于优先表、工件、优先规则和工序等9种编码方式, 考虑到计算时间和复杂性等因素, 本文采用基于工序的表达方式, 采用三层编码方式, 第一层表示工序, 第二表示机器, 第三层表示人员。初始化的伪代码如下:

其中, NIND表示染色体的个数。

2.2 适应度数值计算及非支配排序

分别以目标函数 (式 (1) 、式 (2) 、式 (3) ) 作为适应值函数。目标值不仅与工件的排序有关, 还受工件加工开始时间、完成时间和合适操作人员的影响。

步骤1: 取t=0, m个加工中心机器都可用, 假设第Sv (1≤v≤m) 个加工中心上的第L个机器 (1≤L≤Svk) 加工工件i (1≤i≤n) 的第j (Ji1≤j≤Jil) 道工序, ak=1, 工序计数器count=1。

步骤2: 如果count<Wnumber (全部工件工序之和) , count=count+1, 调入下一道工序, 并计算该工序在可用机器上的开始加工时间、上一道工序的完成时间和合适人员完成时间, 取最大时间为开始加工时间, 分别计算适应度值。

步骤3: 根据适应度值计算被支配解个数和不同个体距离d:

$d = \sqrt{\sum_{a = 1}^{Ν Ι Ν D} \sum_{b = 1}^{Ν Ι Ν D} \sum_{k = 1}^{n + 1} (Ο b j V (a, k) - Ο b j V (b, k))^{2}} (9)$

其中, a≠b, ObjV是个体目标值, k表示目标函数HC和n个工件的维数之和。

步骤4: 如果count==Wnumber, 则终止。

2.3 遗传操作及新种群产生

选择操作采用锦标赛选择策略, 交叉操作采用随机位置次序交叉, 变异操作中, 加工时间少的机器被选择的概率大。在交叉变异以后除去重复个体, 合并产生新染色体, 染色体个数仍然是NIND, 从而在保留资源利用的均衡性和较快的收敛速度的同时又不失个体的多样性。

2.4 终止条件

判断终止条件是否满足, 若满足算法终止, 输出调度结果;否则返回交叉和变异操作。

3 实验分析

根据上述算法设计, 采用MATLAB编程, 遗传算法中的运行参数为:群体大小NIND=20, 交叉概率XOVR=0.4, 变异概率MUTR=0.4。采用非支配解集的思想对三个目标 (F1, F2和HC) 同时优化, 然后依据适应度值和个体之间的距离对调度工序进行排序, 为寻找较优个体提供了一种快速实现方式。在操作工程中, 考虑某个工件某道工序可以选择的机器集合, 同时根据三层编码, 兼顾到可以操作该机器的合适人员。

表1是该算例的工件加工信息表;表2、表3、表4是工人与机床设备的加工关系及人员费用和惩罚系数表。从表1的工件加工信息表中可以看出, 该算例中有4个工件, 每个工件有3道工序, 能加工这些工序的机床数量是6台。这4个工件的任何一道工序都至少可以在2台机床上加工, 可以算出工件1、2和4的工艺加工路线有27条, 工件3的工艺加工路线有18条。根据设计算法在Matlab平台仿真, 输出结果列于表5。

表5显示, 在选定20个染色体的情况下, 对于人工成本和4个工件的提前或者拖期惩罚目标值。根据生产实际情况, 恰当的选择调度方案, 对生产实际具有重要的指导意义。

4 结论

针对动态车间调度的较多可变因素, 特别是针对多工艺路线可变, 操作工人可供选择的情况, 本文提出了三层编码方式, 保证了较快的收敛速度, 实现了人、机和工件的结合, 同时采用非支配解集思想对资源利用、运行费用和交货时限三个目标进行寻优。在遗传操作过程中, 根据选择空闲大的资源, 保证了资源利用的均衡性, 特别是实现了调度中的人机协作优化, 弥补了目前生产调度只关注工件和机器的缺陷, 为生产调度研究更接近实际生产提供了一个实现途径。

协同调度控制篇7

关键词：OS2,协同调度,转供能力,故障信息,供电电源

0 引言

电网调度业务涉及了输电、变电、配电等多个方面, 业务繁多, 处理的数据量很大。从目前的发展情况来看, 在实际中已经存在多种支持系统在电网的调度中实现应用, 对电网业务的开展提供了巨大帮助[1,2,3]。但由于之前技术的阶段性、缺乏统一规划以及专业分离等原因, 系统存在的一些问题也显现出来。主要体现在:没有统一的系统规划和相关标准, 功能分散, 数量众多, 容易重复投资, 信息不能分享, 运行维护量大, 协同调度难, 对大电网的综合智能化驾驭能力弱, 需要较多人员和资金成本, 在调度的管理中存在安全隐患[4,5,6,7,8]。

开发主配网协同的智能调度技术支持平台, 将主配网电网模型进行统一, 消除信息孤岛, 集成发电、输电、变电、配电、用电运行数据, 实现主配网调度的协同功能, 能解决上述问题[9,10]。南方电网近年提出了“二次一体化”的建设, 综合各专业业务需求, 将数据接口标准化, 形成标准的数据交换格式和方式, 建设一体化电网运行智能系统 (Operation Smart System, 简称OS2) 。该一体化基础支撑平台能实现系统运行相关数据全面贯通、系统运行业务全覆盖, 是南网公司对电网运行技术支撑平台的发展趋势。本文主要介绍了在OS2架构的基础上, 主配网调度的协同的具体几项功能, 如转供能力分析、故障信息判断等。

1 主配网协同调度功能实现

1.1 主配网模型的拼接与合并

确定调度自动化系统主网模型与GIS配网模型之间的边界定义, 是拼接与合并主配网模型的前提, 而将馈线设为边界是一个切实可行的方案。主网馈线负荷和配网馈线线路名字命名一致, 配网馈线与主网的馈线通过开关连接, 实现主配网模型的合并。

1.2 主配网转供能力分析

主配网转供能力分析涉及到多条线路, 系统根据现有电网框架, 制定几种可行的负荷转供方式, 计算线路容量并对数据进行分析, 确定转供方案的合理性以及最佳方式。主网转供电能力校核分析包括对110 k V主变、110 k V线路、220 k V主变、220 k V线路等设备的转供分析, 对电网安全具有重要意义。

(1) 110 k V主变转供

110 k V主变发生过负荷后, 首先看能否通过合上10 k V母联开关将过负荷状态恢复正常。若过负荷状态没有得到缓解, 则需要考虑将部分10 k V线路开关断开以减轻110 k V主变负荷的方案。110 k V主变转供方案制定的原则是, 对母联或变低等开关状态进行方式调整。若母联开关处于合位, 没有能够执行的负荷转供方案, 系统需进行提醒。

(2) 110 k V线路转供

若110 k V线路过载, 首先要对过载量进行测量和分析, 看能不能将负荷进行转供。如果转供方案无法制定出来, 系统得出结论进行提醒。若可以对过载量进行负荷转供, 则提供合理的转供方案, 并对潮流进行计算, 确定该方案不会导致设备出现过载情况。若变电站为串供方式, 可采取跨站操作的方案将负荷进行转供。例如220 k V变电站A和E给一串110 k V变电站供电, 如图1所示。

若L1过载, 则转供方案包括合7DL、断开6DL, 或者合7DL断开4DL。具体转供要根据线路Ll需转移的负荷量大小进行确定。

对于双回线路出现过载的情况, 需要进行转供时, 不能只对其中一条线路的负荷进行转供, 也不能将一条线路的负荷直接转移到另一条线路上。

(3) 220 k V主变转供

对于220 k V主变过载, 则对站内110 k V线路负荷逐个进行分析, 得到最接近主变过载量的线路组合。由其他电源点对该110 k V线路集合进行转供电, 并对转供方案的潮流进行计算分析, 避免出现新的设备发生过载情况。最终可能有多种转供方案, 包括转出一条线路, 或转出2条组合线路, 则对不同方案进行优先级排序, 排序原则是避免导致新的设备过载。

(4) 220 k V线路转供

220 k V线路通常为环网接线方式运行。对于220 k V线路负荷转供方案, 首先要确定转移的负荷量, 转供方案通过功率流向找到该线路的220 k V变电站。然后将该220 k V变电站内的110 k V线路负荷, 按第三条所述的转供方法进行负荷转供, 同时进行对潮流进行计算, 避免导致新的设备过载。

1.3 主配网故障信息的判断

实时获取主配网的故障信息, 即每隔10 s获取线路开关、主变变低侧、10 k V分段开关的事故跳闸信息以及重合是否成功到配用电系统中, 对10 k V母线失压信息进行分析和判断。

若主变的高压侧开关发生跳闸, 根据网络结构关系检测10 k V母线电压。如果是220 k V主变的变高开关发生跳闸, 则还要同时检测110 k V母线电压;如果是500 k V主变的变高开关发生跳闸, 则需检测220 k V母线电压。若10 k V母线电压为0, 则判断该母线失压, 则发送工单, 自动生成事故简报, 包括失压变电站名称、开关名称、10 k V失压母线名称、损失负荷信息以及影响用户信息等。若母线电压还有电压, 同时变低开关状态由合位变成分位, 则得到备自投成功的结论, 则生成事故简报, 包括变电站名称、开关名称、事故跳闸、备自投变电站名称、自投成功以及可能存在电压波动, 同时加上主变中压侧开关的说明。

若主变的低压侧开关发生跳闸, 根据网络结构关系检测10 k V母线电压。若10 k V母线电压为0, 则判断该母线失压, 则发送工单, 自动生成事故简报, 包括失压变电站名称、开关名称、10 k V失压母线名称、损失负荷信息以及影响用户信息等。若母线电压不为0, 则不发送工单, 生成事故简报, 包括变电站名称、开关名称、事故跳闸、备自投变电站名称、自投成功以及可能存在电压波动。

若220 k V线路两侧开关发生跳闸, 则检测线路两侧母线电压。若母线电压消失, 则根据网络结构继续检测与该母线相连的线路及主变, 一直到10 k V母线为止。若220 k V母线没有失压, 则不继续检测, 生成事故简报, 包括变电站名称、开关名称、事故跳闸以及可能存在的电压波动。

若220 k V线路单侧开关发生跳闸, 由于正常情况下应该是线路两侧开关都跳开, 因此得出其中一侧开关有问题可能没有跳开的结论。对于没有跳开的一侧, 母差保护或失灵保护动作, 会使与此母线相连的所有开关都跳开。对于由于母差保护动作跳开的断路器, 则按照上一段提到的方法逐个检测。

对于配网故障信息的判断, 系统分析SCADA系统中馈线开关动作信息, 判断开关跳闸是正常手分还是故障跳闸, 从营配一体化系统读取停电用户数、停电负荷情况并记录。若馈线分段开关跳闸, 判断出明确故障点后, 由调度员点选配网自动化图形, 从营配一体化系统读取停电用户数、停电负荷情况并记录。当线路跳闸重合不成功, 系统生成检修工单;当线路跳闸重合成功, 系统生成巡视工单。

1.4 供电电源智能动态识别

供电电源智能动态识别, 是指从设备端动态寻找供电电源的方法。若找到电源, 系统绘制出电源以及供电路径图。若没有找到电源, 则从设备另一端进行搜索, 并绘制出电源和供电路图。若两端都没有找到, 则查找供电电源失败。

为避免电源路径为“220 k V站-110 k V站-馈线-110 k V站”的情况出现, 在进行供电电源识别时要进行主配网隔离。即在进行主配网设备的供电电源识别时, 需要确保寻找电源时不能进入配网模型, 主网隔离图如图2所示。所以寻找电源遇到10 k V馈线开关时停止搜索该路径。

对配网设备的供电路径识别进行, 当搜索已经从配网搜索到了主网后, 该条路径不能回到配网模型, 配网隔离图如图3所示。

2 总结

基于0S2构架的智能调度技术支持平台, 将主配网模型进行拼接与合并, 对主配网海量数据进行处理, 实现主配网协同调度功能。在应用层面, 实现转供能力分析、故障信息判断、供电电源识别等功能, 能够有效提高电力企业内各部门间的协同工作效率。

参考文献

[1]李文朝.基于运行服务总线的主配网调度系统建设[J].广西电力, 2014, 37 (4) :19-22.

[2]吴任博, 彭依明, 杨世兵, 等.基于统一模型和SOA的主配网信息融合技术研究与应用[J].云南科技管理, 2015, 28 (1) :86-89.

[3]廖怀庆, 刘东, 黄玉辉, 等.基于大规模储能系统的智能电网兼容性研究[J].电力系统自动化, 2010, 34 (2) :15-19.

[4]林常真, 李林峰.区域性配网调度独立运作现状分析及建议[J].广西电力, 2009, 32 (3) :33-34, 54.

[5]汪磊, 魏丽芳, 王克谦, 等.主配网调控一体化图形平台设计[J].电力系统及其自动化学报, 2012, 24 (1) :142-146.