任务时间约束（精选7篇）
任务时间约束 篇1
0 引言
空间在轨服务[1]具有巨大的研究价值和发展空间,近年来各国加紧了空间论证实验的步伐。由于空间环境复杂,扰动因素多,试验成本高昂,需要地面测控系统的全力支持。现阶段的空间试验任务同过去相比,更加强调多个操作之间的时序关系,同时,空间试验任务需要在特定的条件下进行,这些条件复杂繁多,包括自然条件和人为需求,可以分为严格的刚性条件以及柔性的可变条件,给任务的调度规划增加了很大的难度。现有的航天规划调度模型以观测卫星为主[2,4],重点考虑卫星地面站可见窗口约束,Frank[5]考虑了卫星任务之间的时序关系,但缺乏一种统一的表述方式。本文分析空间试验任务间的关系以及部分试验条件及需求,提出了一种时间窗口描述方式,将复杂空间试验任务映射为时间窗口分配问题,并设计了一种时间窗口运算的方法,加快计算过程。
1 空间任务规划调度模型
1.1 问题描述
卫星在执行大多数任务时,需要测控系统[6]支持,本文建模时做如下假设:
(1)地面设备同一时间只能服务于一颗卫星;
(2)每个任务都可以由一颗卫星在连续时间内完成;
(3)不考虑任务准备时间及卫星储存容量限制;
(4)不考虑中继卫星。
1.2 约束满足模型
空间任务规划调度问题可用约束满足模型[7,8]来描述,定义:
S:试验任务可用卫星集合;
G:地面测控设备集合;
M:任务集合,Dm表示完成任务m所需持续时长,Tm表示任务m开始执行的时间,Wm表示任务m的权重,其中m∈M;
TW:一些离散时间段的集合,TWi,j表示卫星i与地面测控设备j的可见窗口集合,其中i∈S,j∈G;
Cm,t:任务的测控条件,仅当任务m的所有试验条件在t时刻都满足指标时,Cm,t=1,否则为0,其中m∈M,t∈R;
Xm,i,j:完成任务所使用的卫星及地面测控设备,当且仅当任务m通过卫星i及设备j完成时Xm,i,j=1,否则为0,其中m∈M,i∈S,j∈G;
约束满足模型如下:
式(1)表示规划调度的目标为最大化任务权重和;(2)确保了每个任务由一颗卫星及地面测控设备完成;(3)表示空间任务必须在地面测控设备的支持下完成;(4)表示卫星完成空间任务的时段必须满足空间任务的所有条件;(5)约束了地面站测控设备在同一时间只能服务于一颗卫星。
2 统一时间窗口约束
2.1 时间窗口描述方法
空间任务的执行在时间上受到严格的约束限制,必须在星地可见时间窗口[9]内进行。时间窗口是离散时间段的集合,时间段可用起止时间组来表示,星地可见时可以描述为其中i∈S,j属于G。除此之外,空间任务主要还受到空间试验条件约束、人为需求约束[10]、资源冲突约束以及任务相关性约束限制,这些约束可用转化为时间窗口约束。
空间试验条件窗口TWC。空间试验条件主要指空间任务执行时载荷各类参数满足一定指标需求,如光照需求、温度需求、姿态要求等,根据卫星轨道根数及空间环境分析计算,可以得到相应的可用窗口集合,这类窗口与可见时间窗口类似,是离散的窗口集。,其中m∈M。
人为需求窗口TWD。任务的执行时间需要考虑用户的需求,在特定的时间完成。这样的时间往往是具有弹性的时间区间,因此也可将其视作是离散的时间窗口集。
地面测控设备冲突窗口TWG。设备j在某一时间t,已被占用的时间窗口可表示为,。
任务相关性窗口TWR。任务间的逻辑关系较为复杂,A与B间可能的关系有图1所示9种,这种相关性可描述为B在A结束后S时间开始,B在A结束后E时间结束,即,其中A,B∈M,Start和End的取值范围见表1。
2.2 时间窗口运算
本文将满足各类约束的过程转化为时间窗口的运算,任务最终可以安排的时间窗口为TW=TWV(40)TWC(40)TWD(40)TWR-TWG,表示可用时间窗口是可见时间窗口、试验条件窗口、人为需求窗口、任务相关性窗口的交集,并且需要扣除任务所需地面设备的已用窗口,这里涉及到的主要运算为时间窗口的“交”运算以及“减”运算,如图2:
由图2可知,为实现时间窗口运算,需要对A、B中每个窗口的起止时间依次相互比对,对于两个规模为n的时间窗口,计算时间复杂度为O(n!),在窗口数量增多,任务繁重的情况下,成为计算效率的瓶颈。本文设计了一种时间窗口优化算法,通过时间窗口出栈对比,得到结果,如图3,计算过程见图4:
图4中“pop”为出栈操作,删除栈中顶端数据,“～”为逻辑取反操作。优化时间窗口算法仅需遍历两个时间窗口一次,时间复杂度为O(2n)。
3 仿真测试
为测试时间窗口算法的改进效率,本文设计了包含50个高冲突度任务的规划调度测试用例,采用遗传算法[11]进行求解,将调度的成功任务的权重和作为遗传算法适应度函数。在参数不变的情况下测试时间窗口最大数量分别是5个,20个和50个三种规模的任务集,适应度随时间变化曲线如图5:
图5中横坐标表示时间,纵坐标表示适应度,虚线为原始算法适应度变化曲线,实线为优化时间窗口计算方法后适应度变化曲线。可以看出,在相同时间限制,优化算法总能得到适应度更高的解,这种优势在时间窗口较多的大规模计算中尤为明显。
4 结论
本文将空间任务规划调度过程中4类主要约束转化为时间窗口约束,并提出一种加速算法优化时间窗口间的运算。空间任务规划调度是一类复杂的约束满足优化问题,往往需要启发式算法来求近优解。时间窗口运算的加速使得用户可接受时间内算法迭代更多次,从而找到更接近最优的解。
参考文献
[1]崔乃刚,王平,郭继峰.程兴空间在轨服务技术发展综述[J].宇航学报,2007,28(4):805-811.
[2]陈峰,武小悦.多星侦察系统任务建模及规划技术研究平[J].北京航空航天大学学报,2010,36(5):534-539.
[3]Mancel C.Complex optimization problems in space systems[J].American Association for Aritficial intelli-gence,2003.
[4]冉承新,王慧林,熊纲要.基于改进遗传算法的移动目标成像侦测任务规划问题研究[J].宇航学报,2010,31(2):458-465.
[5]Frank J,Jonsson A,Morris R,et al.Planning and Scheduling for Fleets of Earth Observing Satellites.Pro-ceedings of the6th International Symposium on Artificial Intelligence,Robotics,Automation and Space2002,Mon-treal,2002.
[6]谢红卫,张明.航天测控系统[M].国防科技大学出版社,长沙,2000.
[7]金光.卫星地面站测控资源调度CSP模型[J].系统工程与电子技术,2007,29(7):1117-1120.
[8]陈英武,方炎申,李菊芳,等.卫星任务调度问题的约束规划模型[J],国防科技大学学报,2006,28(5):126-132.
[9]刘洋,陈英武,谭跃进.一类有时间窗口约束的多资源动态调度模型与方法[J].运筹与管理,2005,14(2):47-53.
[10]凌晓冬,武小悦,刘琦.面向需求的航天测控资源调度算法[J].系统工程与电子技术,2009,31(7):1661-1666.
[11]Fatos Xhafa,Junzi Sun.A Genetic Algorithm for Ground Station Scheduling.[C].International Conference on Com-plex,Intelligent,and Software Intensive Systems,2011.
任务时间约束 篇2
针对抗震救灾坏境中宏观任务的下达,任务的分解细化过程,研究一种任务的分解机制[1,2,3]。该机制首先依据任务的具体状况定义任务的唯一标识、开始时间、生命周期及任务重要度,实现对任务的初始化标识。其次定义任务间的约束关系[4,5,6],包括同步、串行、父子关系以及同步下受时序和资源约束等,确定任务之间的相互联系,为执行任务分解做好准备。然后,研究一种基于任务分解树的算法:建立一棵空的任务树,将任务节点放入任务队列中,依据任务间的约束关系从任务队列中提取并放入任务树的适当位置,直至任务队列为空,这样最终依据任务间约束关系通过任务分解树的方法实现对任务的分解。
1 任务的四要素
任务可以分为复杂任务和简单子任务,为了更好地完成某个目标,其对应的任务应该进行分解和调度,以保障更好更快地完成。
定义每一个任务为一个四元组[7,8]G = ( ID,Begin,Time,I)
① 其中ID代表每一个任务的名字,不同的任务具有不同的ID,且不可相同;
② Begin代表任务的开始时间,因为任务的分解与调度中常有时序约束,所以要考虑不同任务的开始时间;
③ Time代表任务的持续时间;
④ I代表任务的重要度。所谓重要度指当遇到突发情况时,每个节点的紧急情况可能各不相同,重要的节点应优先考虑处理,不同的任务可能具有不同的重要度。
2 任务的关系约束
定义如下几种关系约束:
① 同步执行任务集P = { T1,T2,T3} ,即任务T1、T2、T3 可以同步地执行,主要是对于同层的节点,如图1 所示。
② 串行执行任务集S = { T3,T4,T5} ,即任务T3、T4、T5 必须逐个执行。 用集合表示为如图2 所示。
③ 父子关系任务集F = { T5,T6,T7} ,即任务T5 可以进一步分解为T6、T7。表示T5 是T6 和T7的父节点,父子关系任务集中,父节点可能全面的包含子任务或是部分包含,全面包含指的是子任务全部完成,父任务才可执行,用集合表示为: T = { T5,A{ T6,T7} } ,如图3 所示。而部分包含指的是完成部分子任务后即可开始执行父任务,用集合表示为T = { T5,O { T6,T7 } } ,如图4 所示。用方框置于外侧是表示这是一个任务分解模块,T5 是由T6 和T7组成的。
④ 同步执行的任务可能受到时序或资源的约束,若两个任务A、B。A在时间或资源方面需在B之前完成,则定义如下。所以对1 中任务集{ T1,T2,T3} 进一步完善,若T1 对T3 有时序约束约束,则定义。
综合分析上述情况可以把任务分解表示在一个大的集合内。
待执行任务,表示在一个大的集合内可以直观地看出几个任务之间的关系与层次。
根据上述定义可以得出任务分解树,如图5所示。
其中T1 对T3 有时序或资源方面的约束,在图中用T1 - 3 来表示这种约束关系。T3、T4、T5 是串行执行的。T6、T7 全包含于T5。针对不同任务节点的重要度,可以对任务分解图进一步优化,节点的重要度可以开始时由更高层级直接指定,若没有指定,则依据节点重要性的算法来衡量。假设图5 中高层级指定了T3 的重要度高于T2,则在出现紧急情况时优先考虑T3。若没有指定,以节点重要性的角度去考虑,T3 节点的度数高于T2,所以T3 重要度大于T2( 以节点的度来衡量重要性) ,根据以上两种情况,可以把任务分解树优化。
3 基于任务树的任务分解
在进行任务调度时,首先要考虑节点间的时序约束,其次当在进行任务调度出现紧急情况时,同层中左边节点的重要度大于右边,所以优先处理左边节点出现的情况,这种任务分解树看上去直观,且考虑的更加全面。
基于任务树的任务分解算法[9,10]步骤如图5所示。
步骤1: 初始化任务树节点置为空,把每项任务定义为任务树中的节点,并把节点间的相互约束关系置于节点关系表中;
步骤2: 为每个节点分配唯一的ID,初始化任务的开始时间Begin和预估执行时间Time,根据需要判断是否初始化重要度I,若需要则给定相应等级,否则置为空;
步骤3: 设置一个队列,把所有任务节点置于队列中,首先输出代表源节点的节点S;
步骤4: 从队列中依次输出每个任务节点;
步骤5: 输出的节点是否需要进一步分解,若是则符合父子约束关系,在任务分解树中生成该节点的子节点,其层次为父节点加一,并由父节点指向子节点。若不是则跳转到7;
步骤6: 判断父节点是全包含还是部分包含,若是全包含则所有子任务执行完成才认为父节点完成,是部分包含则部分子任务完成,父任务就认为完成;
步骤7: 以节点任务表中的约束判断输出的节点是否符合同步执行约束,若是则任务分解树中节点间层次相同并假设层次为n,且由n - 1 层节点同时指向它们。若不是则跳转到步骤8;
步骤8: 以节点任务表中的约束判断输出的节点是否符合串行执行约束,若是则任务分解树中任务节点的层次逐步递增,且层次低的节点指向层次高的节点,若不是则跳转到步骤9;
步骤9: 按节点重要性算法计算未置初值的任务节点的重要度,判断是否需要优化,若是则跳转到步骤10,不是则跳转到步骤11;
步骤10: 同层中把没有时序约束且重要度高的节点i( 包括它的子节点) 不断左移,直到其左侧节点对i有约束则停止,所有节点优化完跳到步骤11;
步骤11: 重复执行步骤3,直到队列中节点为空,生成任务分解树。
4 实例验证
假设某次抗震救灾补给灾区运输车加油,由于搭建基地就只有一个,所以每个运输车按串行补给,总补给任务称为S,假设有n辆运输车,表示为B1、B2…Bn则n辆车之间的关系为串行关系,也就是当第1 辆车加油完毕后,第2 辆车才能加油。
步骤1: 对任务进行初始化标识,定义唯一标识为S,任务分为两类,即运输油A和加油B,开始时间为ts,生命周期为T,任务重要度为非常重要;
步骤2: 定义任务间的约束关系,只有运输油到的情况下,才能加油。因此对运输油任务A对加油任务B有时序约束。在运输加油任务中,由于加油基地只有一个,所以只能一个一个进行加油,因此加油任务A为同步关系; 运输油任务B可以并行进行;
步骤3: 建立一棵空的任务树S,将任务节点( 任务A和任务B) 放入任务队列中,依据两个任务间的约束关系( 任务A对任务B有时序约束) ,从任务队列中提取并放入任务树的适当位置,任务分解树如图6 所示。
5结束语
为保证抗震救灾环境下任务的执行,提出了救灾网络任务分解方法。文中提出的几种约束关系,考虑到了任务和任务间,总任务和子任务间的关系。而重要度的提出也是考虑到作战任务的特殊性,所谓重要度是指任务节点分主次,当出现紧急情况时优先考虑重要度高的任务,这可以保证在救灾环境下作战任务能最大限度地不受其他因素的影响。
参考文献
[1]肖增良,乐晓波.基于与或依赖图的多Agent系统任务分解算法[J].计算机工程与设计,2009,40(2):267-272.
[2]钟琪.基于启发式算法的任务分解策略[J].煤炭技术,2010,30(12):25-29.
[3]秦娜,乐晓波,刘武.基于Petri网模型的JSP粒子群优化调度[J].计算机应用,2008,28(8):2167-2169.
[4]White J E.Mobile Agents In:Bradshaw,Jeffrey eds.Software Agents,Menlo Pork[M].California:Press/The MIT Press,1996.
[5]Lange D B.Mobile Objects and Mobile agents:The Future of Distributed Computing[C]∥Proc of the European Conf on Object Oriented Programming’98.Brussels,1998:49-52.
[6]杨学会,王精业.基于任务分解的作战仿真研究[J].系统仿真学报,2006,18(10):18-21.
[7]刘波,罗军舟.大规模网络管理中的任务分解与调度[J].通信学报,2010,42(6):48-51.
[8]刘波,罗军舟.网络管理中多agent的半在线调度算法[J].计算机研究与发展,2006,27(3):65-72.
[9]王红霞,刘治国,潘成胜.分布式网络管理中的任务管理与任务调度的研究[J].沈阳工业学院学报,2009,30(11):15-19.
时间约束下生鲜配送线路优化研究 篇3
发改委于2010年7月出台了首部《 农产品冷链物流发展规划》 ,该规划提出到2015年,建成一批效率高、规模大、技术新的跨区域冷链物流配送中心,使流通环节产品腐损率分别降至15%、8%、10%以下[1]。 为了完成该发展规划,需要整个冷链物流体系合理运作,以提升整体效益。 而生鲜配送作为冷链物流系统中最重要的环节之一, 对该环节中路径的优化不仅能提高配送的时效性, 还能有效降低物流成本。 目前,国内外关于配送线路优化问题的研究大多归为车辆路径问题(VRP),而VRP问题又可细分为带载重约束VRP问题、带时间窗VRP问题、带回程载货VRP问题等; 而早在1959年,Dantzig和Ramser就首次提出了相应的VRP规划模型和求解算法,以解决需求已知情况下,不同种类的车辆的组成和配送线路,达到运输费用最少的目的[2]。 在2012年Jun等人提出了改进后的经典启发式算法,通过路线构造、改造、干扰三阶段得出最优解[3];同一年,庄景明等基于改进的遗传算法对车辆运行路线进行了优化[4]。 在本文中,我们对具有时间约束的冷链车辆配送线路优化展开了相应研究。
二、模型提出
(一)问题描述
时间约束下生鲜品配送线路优化问题可描述如下: 生鲜品配送中心VO接到各网点(Vi=1,2,···n)订单后, 根据各网点订单量(Qi=1,2···n)和时间窗要求,安排冷链配送车辆依次进行货物配送。 其中各配送点Vi与配送中心的距离(di=1,2···n)以及配送量(qi=1,2···n)已知, 冷链配送车辆具有相同的载重量Q0;各网点都有配送时间约束, 超过网点规定时间窗送达则需要承担延误成本, 该成本与相应生鲜品的价格、数量以及延迟时间相关。 本文的目的是在各网点时间约束的条件下,确定合理的配送路线、 配送顺序、配送车辆数,从而有效降低配送总成本。
(二)数学模型
为了简化配送条件,以优化生鲜品的配送线路,我们做了如下假设:一是配送中心车辆能够满足配送需求;二是单一网点生鲜品需求量不超过每辆车的运载量; 三是每个网点生鲜品由一辆车一次送达; 四是各网点间以及各网点与配送中心距离已知; 五是各网点生鲜品需求量已知;六是各网点间路况相同,配送车辆匀速行驶;七是各网点时间窗、可接受时间窗以及延误的惩罚系数已知。 本文的目标是确定合理的生鲜配送路线、 配送顺序以及配送车辆数,从而有效降低配送总成本;在本文中,配送总成本主要包括运输成本、货损成本、延误所致的惩罚成本以及车辆能耗成本。
1.运输成本。 由于冷链配送车辆相同,因此运输成本主要与运输里程相关,用公式可表示为:
其中:C1为运输成本,c为单位里程运输成本,tij为运输车辆从网点Vi到Vj的运输时间,Xijk为0,1变量, 若车辆经过网点Vi到Vj,则为1,反之为0。
2.货损成本。 由于生鲜品具有易损、易腐特点,加上运输途中挤压、新陈代谢等问题,会造成生鲜品损耗;我们假定全程路况一致, 则货损成本与车辆的运送时间相关,公式可表示为(假设车辆先到达Vi网点再到Vj网点):
其中:C2为货损成本,α 为货损系数,Pj为网点Vj货物的价格,ΔQjk为K车辆在Vi点卸货后车辆的剩余载货;Xijk同上,Si为配送中到Vi网点的距离,Sj为配送中心到Vj网点的距离,h为变量。
3.惩罚成本。首先,每个网点都有自身的时间窗约束, 车辆未在指点时间范围内送达, 则会影响网点日常经营情况,需要加入一定的惩罚成本,惩罚成本与货物量、货物价格以及延误时间相关;其次,我们假定了网点可接受的延误时间, 若超过可接受的延误时间, 则网点拒绝收货,公式表示为:
其中,C3为惩罚成本,β 为惩罚系数,Pj为Vj网点所需生鲜品的价格,Qj为Vj网点所需生鲜品的需求量,tjk为K车运送至Vj网点的时间,[tj~td]为Vj网点时间窗,[Ti~Tj] 为Vj网点可接受的时间窗(包含了延误时间)。
4.能耗成本。 冷链车辆相较于普通运输车辆而言,需要消耗更多的能源以保证生鲜品温度的要求; 因此生鲜品配送过程中能耗与载货量、配送里程有关,可用公式表示如下:
其中:C4为能耗成本,γ 为耗能系数,Pj为网点Vj货物的价格,ΔQjk为K车辆在Vi点卸货后车辆的剩余载货量,Xijk同上,Si为配送中到Vi网点的距离,Sj为配送中心到Vj网点的距离,h为变量。
因此,根据配送总成本最小的思想,建立了如下目标函数:
其中的约束条件为:
在该约束条件中,(1)表明每个网点仅配送一次货物;(2)表明每个网点都在配送范围内,不存在遗漏;(3)表明配送中心的冷链配送车辆均被利用,不存在闲置车辆;(4)表明每个网点的需求量小于每辆配送车辆的最大载重量;(5)表明每个网点的配送完成时间需在该网点可接受时间范围内。
三、算法设计
考虑到生鲜品的特点及配送的软时间窗约束, 同时认识到上文建立的生鲜品配送模型求解问题属于非线性规划问题, 我们因故采取启发式算法中的节约算法来进行求解。
(一)具体思路
当配送车辆由配送中心发出时, 寻找“ 最邻近的网点” 作为第一条配送线路上的第一个被服务的客户;随后,选择尚未被加入任何线路中的网点加入当前线路中; 而且,在加入当前线路的网点选择中要遵守“ 综合成本最低”的原则。 其次,运用节约算法求解时,需将可行的网点加入现有回路中,并计算相应的节约值,从而将节约值最多的网点加入到回路中, 并不断重复这一过程直到所有网点纳入相应回路。 因此, 通过对第二节的模型进行优化,可以得到节约值最大化的配送线路模型,其目标函数如下:
其中,Yij为网点Vi到Vj的节约成本,c为单位运输成本,Wij为网点Vi到Vj的节约里程,h为变量,C3(tj)为Vj网点的惩罚成本,其他变量在第二章已提及,不再一一介绍。 通过上述目标函数,发现添加新网点时应遵循时间约束为第一顺序(降低惩罚成本),各网点运输里程为第二顺序(降低运输成本、货损成本和能耗成本)。
(二)算法步骤
根据节约算法的思想和节约值最大化的配送线路模型,我们认为具体算法步骤包括:(1)按各网点时间窗约束进行排序;(2)计算各网点间的节约里程;(3)按节约算法中 “ 最邻近网点”思想,在配送中心选择步骤1排序后网点中的“ 最邻近网点”为第一位配送网点;(4)按步骤3的思想逐个将满足条件的网点纳入当前线路, 当超过可接受时间窗约束或达到车辆最大载货量时, 则不再加入新的网点;(5)排除已选网点后,重复步骤3和4,直到所有网点均被纳入相应配送线路。
(三)实例分析
设某配送中心在约定时间范围内要向10个生鲜网点配送一批新鲜苹果,配送中心编号为V0,各网点编号为Vi=1,2···n; 配送车辆运行速度为30km/h, 载重量Q0为15吨,苹果的价格P为5000元/ 吨,生鲜品货损系数 α 为0.01%,超过时间窗的惩罚系数 β 为0.2%,车辆能耗系数 γ 为0.2%,单位运输成本c=1元/ 吨公里,各网点平均卸货时间为10分钟/ 网点。 各网点货物需求量以及时间窗约束见表1,配送中心及各网点间距离见表2。
按照算法步骤对以上实例进行计算:首先,计算出每个网点的时间窗约束先后顺序以及各网点间的节约里程;随后得出第一条配送线路中的第一个网点P1;其次, 对剩余网点的节约里程、节约运输成本、节约货损成本、 节约能耗成本、惩罚成本进行计算,得出各个网点的总节约成本; 因此, 得到的第一条配送线路为P0- P1- P10- P2- P5- P0,其中载货量为14.5吨,小于最大载货量Q0。 随后按以上步骤, 计算出第二条配送线路为P0- P3- P4- P6- P0, 载货量为13.5吨; 第三条配送线路为P0- P7- P8- P9- P0,载货量为9.5吨。 至此,所有的网点均被纳入相应线路。
四、结论
通过对生鲜品配送特点的认识, 构建了包含运输成本、货损成本、能耗成本和惩罚成本的线路模型,并采用节约算法,对该模型进行了优化,以期在最大化节约成本和时间窗约束的条件下,确定合适的配送线路;最终通过相应实例,证明了该配送线路优化模型的有效性。
摘要：我国冷链物流起步较晚,导致生鲜品在配送、装卸、储存等环节的损失率较高,建立完善的冷链物流配送体系意义重大。根据生鲜品的特点,构建了包含运输成本、货损成本、能耗成本和惩罚成本的线路模型,并采用节约算法,对该模型进行了优化,以期在最大化节约成本和时间窗约束的条件下,确定合适的配送线路,最终通过相应实例,证明了该配送线路优化模型的有效性。
任务时间约束 篇4
在协同产品开发中, 设计人员可能需要在某一段时间内处理多个任务, 有紧急任务, 也有时间较为松弛的任务。对于任务的轻重缓急, 需要有一个合理的安排以使得设计任务可以尽可能按照客户需求按时完成或者将延迟损失降低到最小[1]。协同产品设计涉及多个学科, 属于知识密集型活动。设计过程中各任务分布、并发、知识创造的特点导致协同设计过程中突显一些问题, 如工作过程的动态性和不确定性; 设计人员与设计资源的多样性; 设计活动与任务的复杂性; 设计成员之间信息-知识流的多向、传递和变化性[1,2,3]。这些问题导致各种设计冲突不断出现, 设计过程的协调也变得非常困难。而在解决协同设计冲突问题中, 明确任务之间的次序逻辑有助于解决设计任务之间的冲突[3]。目前任务排序解决方法主要集中在选择优化算法寻求排序总时间最短方面, 传统分布协同设计任务排序方式未考虑任务在各个设计者之间的析取关系以及任务的重要程度, 未能准确描述分布式协同设计任务之间逻辑关系和重要度, 造成排序结果不能真实全面反映排序要求与约束。本文综合协调理论中的依赖分析方法与图论中约束关系图描述协同设计任务之间的逻辑关系, 采用调度管理中的启发式排序算法对设计任务进行排序, 提出一种基于析取约束的带权协同设计任务排序方法。
2 协同设计任务之间依赖关系
协调理论是由美国麻省理工学院的协调学科研究中心提出的, 研究跨学科普遍存在的依赖关系, 在原理分析的基础上, 提出如何协调这些依赖关系的方法。协调理论将协调手段作为管理事物间依赖关系的流程或管理机制, 这一协调机制的作用就是协调各活动参与者间存在的依赖关系[4,5,6], 对于将复杂交叉的分布式协同设计任务按业务逻辑进行分类具有一定的借鉴意义。分布式协同设计任务由于人力、资源、时间的冲突关系存在任务之间的优先约束, 可用任务集T上的一个偏序关系≺表示。Ti≺Tj意味着必须完成任务Ti才能开始任务Tj.如果任务集T中至少有两个任务受到优先约束的限制, 集合T的任务称为相关的, 否则称为无关的, 这里根据协调理论的描述, 将这种定义为依赖关系。为直观起见, 采用一个称为优先约束图的关系图来表示。在随后的析取关系图中, 圈对应任务, 弧对应偏序关系, 始点为Ti、终点为Tj的弧对应Ti≺Tj.称Ti为Tj的先驱, Tj为Ti的后继[8]。对协同设计任务间的依赖关系、应用背景以及逻辑规则定义如下:
根据以上依赖关系的定义, 引入图论中的概念, 定义依赖约束关系图中的三种典型情况:如果每个任务最多有一个先驱和一个后继, 依赖约束图称为链 (chain) 。如果每个任务最多有一个后继, 依赖约束图称为入树 (in-tree) 。如果每个任务最多有一个先驱, 依赖约束图称为出树 (out-tree) 。 图1 (a) 、 (b) 、 (c) 分别给出了链、入树和出树的例子。
链、入树和出树是构成分布式协同设计任务的三种基本逻辑关系, 可构成不同协同设计目标下的协同设计任务图, 同时由于三种依赖约束关系对设计人员资源的依赖程度不同, 在处理过程中任务权重也有所不同, 结合三种依赖约束关系对资源的依赖关系和程度, 通常情况下, 三者权重关系为Win-tree≥Wchain ≥Wout-tree.
3 协同设计任务之间析取关系
设某协同设计任务包含任务集合Ts和设计人员集合D, Ts中的n个任务{Tsi}ni=1由D中的m个设计者{Dk}mk=1处理。每个任务包含m个操作, 这些操作将由不同的设计者完成, 且必须满足给定的任务顺序, 此为设计路径约束。每个任务具有指定的交付期和权重, 本文讨论基于析取约束规则的最小化设计时间问题, 可描述为Jm//Ci.
任务与设计者之间的逻辑关系可用析取图G (O, A, E) 描述[9]。其中:O≡{0, 1, …, *}表示在设计者集合D上处理的所有操作对应的节点构成的集合 (包括虚拟的开始操作0和结束操作*) ;A是由连接弧构成的集合, 连接弧具有确定的方向, 表示同一任务各操作的先后顺序 (体现设计路径约束) ;Ek是由析取弧构成的集合, 表示设计者Dk所有操作可能的设计顺序,
在图2中, 令变量yij表示任务j由设计者i处理的操作 (i, j) 的开始时间, pij代表处理时间。集合O表示所有操作 (i, j) 的集合, 集合A为所有设计路线 (i, j) → (k, j) 的集合, 它需要任务j在设计者k处理之前首先完成在设计者i处的任务, 双向虚线表示不同的任务处理顺序, 最小化设计时间目标函数可描述为[10]
min Cmax
s.t. ykj-yij≥pij (i, j) → (k, j) ∈A
Cmax-yij≥pij (i, j) ∈O
yij-yil≥pil∪ yil-yij≥piji, j=1, 2, …, m
yij≥0 (i, j) ∈O
约束1表示任务j在不同操作者之间的顺序, 约束3即为析取约束, 表示某设计者处理的任务存在某种排序。在以上基本规则的基础上还可结合WSPT、EDD、MS、LPT、LAPT等规则描述不同情况下的任务执行逻辑特征。
4 基于析取约束的协同设计
任务带权排序规则
建立在以上析取约束关系定义基础上, 对于m个设计者, 设有n个任务的操作集Oij, 其处理时间为Pij, 记Cij为操作Oij的完工时间。考虑如下排序问题:
记Pij和Wij分别表示操作集Oij的处理时间矩阵和权重矩阵。设矩阵Ym×n= (yij) 表示操作集Oij中的任务处理状态, 其中
对Yn×n= (yij) , 记Yi·为其第i行的行向量, Y·j为第j列的列向量。 由于每一个任务只需要一个设计者来完成即可, 所有设计者完成的任务数之和为n, 所以对yij有如下约束:
对于每一个设计者而言, 其所需要处理的任务数为
对Xn×n= (xij) , 记Xi·为其第i行的行向量, X·j为第j列的列向量。由于每一个任务只需处理一次, 设计者每次只能处理一个任务, 而任务在任何时刻这能处于被处理或不被处理的状态, 所以对xij有如下约束:
设计者I所需完成的NI个任务的加权完工时间之和为:
则所有任务加权完成时间之和
由以上描述得出目标函数为:
5 分布式协同设计任务
带权排序仿真实验
采用LEKIN仿真软件, 构造任务集以及任务顺序决定的设置时间集, 分别存放于数据文件中。每个任务有任务编号、任务提交时间、任务处理时间、任务完成时间、任务权重) 。即TASKS=[任务号, 提交时间, 处理时间, 完成时间, 任务权重]。以图2中4人11子任务的设计方案为例, 子任务1～3对应图2中设计任务1, 同理, 子任务4～7对应设计任务2, 子任务8～11对应设计任务3, 由4个设计者协同完成一个设计任务, 依据设计任务的逻辑关系以及权重参考Win-tree≥Wchain≥Wout-tree, 对各子任务权重赋值。设问题
当任务时间参数较大时, 可将协同设计任务之间的切换时间设为0, 这里考虑设计任务在不同设计者之间的切换时间, 设顺序决定准备矩阵如下:
基于WSPT规则通过LEKIN仿真计算得出协同设计任务排序方案为:设计人员1对应子任务9-5, 设计人员2对应子任务4-1-8, 设计人员3对应子任务10-7-2, 设计人员4对应子任务3-11-6, 任务最后完成总时间150, 造成最少延期任务数目为5, 图3为LEKIN输出的各协同设计任务排序甘特图界面。
6 结论
产品协同设计作为提升求业竞争力的重要工具与手段, 研究其任务之间的有序协调关系具有一定的理论与现实意义。通过研究可以得到以下结论:
①根据协调理论与图论中有向图的知识提出协同设计任务之间的依赖逻辑关系, 可为协同设计任务之间的权重分析以及逻辑分析提供一定参考依据。
②提出基于析取约束的分布式协同设计任务排序模型, 可根据协同设计任务目标, 结合不同的排序规则对协同设计任务进行最优排序。
③建立基于WSPT规则的分布式协同设计任务排序模型并通过一个4人11子任务的算例进行验证, 说明本方法能有效实现分布式协同设计任务排序。
进一步的研究将考虑采用模糊层次分析法或灰关联分析法对基于析取约束的协同设计任务权重进行赋值, 在此基础上研究分布式协同设计过程中的冲突消解策略以及基于协调理论中依赖关系的任务与资源逻辑分析。
摘要：传统协同设计任务排序方式未考虑分布式任务在各个设计者之间的析取关系以及任务的重要度。引入协调理论中依赖分析方法和图论中约束关系图的概念描述协同设计任务的逻辑关系, 提出基于析取约束协同设计任务排序问题的数学模型, 依据带权任务排序规则确定分布式协同设计任务的优化排序。通过工程算例验证该模型能够实现分布式带权协同设计任务的有效排序。
关键词：协同设计,任务排序,带权排序,析取约束
参考文献
[1]宋李俊等.协同产品开发中设计者任务排序研究[J].系统工程, 2007, 25 (5) :9~14.
[2]庞辉等.面向协同设计的任务调度问题研究[J].系统工程与电子技术, 2008, 30 (10) :1899~1903.
[3]宋李俊等.产品协同设计中任务的排序研究[J].中国机械工程, 2008, 19 (7) :798~803.
[4]The business rules group.Defining business rules-what are they really?http://www.businessrulesgroup.org/first paper/br01c0.htm.
[5]Von Halle B.Business rules applied:building bettersystems using the business rules approach[M].JohnWiley&Sons, 2002.
[6]Malone T W, et al.Organizing business knowledge:the MIT process handbook[M].The MIT Press, 2003.
[7]汪军.网络化制造中面向流程重用的业务流程组合研究[D].重庆:重庆大学, 2006.
[8]杨斌鑫.若干单机在线排序问题研究[D].西安:西北工业大学, 2004.
[9]张帆等.多目标最短路径进化求解方法[J].系统工程, 2005, 23 (9) :123~126.
[10]Pinedo M.调度:原理、算法和系统[M].北京:清华大学出版社, 2007:132~138.
任务时间约束 篇5
随着数字化、网络化和开放化在人们工作和生活中的普及,信息系统得到了广泛应用,让给人们带来了快捷、便利的工作生活环境,但随之而来的多用户、多终端可以远程操作信息系统的这一问题,这对信息系统的安全防患工作构成了巨大的挑战。目前信息系统采用的安全防患措施主要有两类:系统部署安全和软件设计安全。前者如采用防火墙、隔离设备、终端接入方式等对软硬件设备进行防护,属于系统部署级别的防护;后者如采用访问控制策略、用户终端验证等方法,属于软件设计级别的防护。在具体的应用中,后者更具有灵活性与可配置性,本文从用户的访问控制角度研究信息系统的安全性。
访问控制(Access Control)指系统限制对用户身份及其所属的预先定义的策略组限制其使用数据资源能力的手段,通常用于系统管理员控制用户对服务器、目录、文件等网络资源的访问。传统的访问控制类型有:自主访问控制(DAC,Discretionary Access Control)和强制访问控制(MAC,Mandatory Access Control),这两种访问控制都是通过直接关联用户和操作对象直接进行关联,约束用户的权限,而随着信息系统资源结构日益复杂,终端规模日益增大,这种用户和操作对象的直接关联模式满足不了系统需求[1,2,18]。
目前广泛采用的基于角色的访问控制(RBAC,RoleBased Access Control)模型,是在用户和操作对象之间加入了角色,通过对角色的访问进行控制,使权限与角色相关联,用户通过成为适当角色的成员而得到其角色的权限[3]。这种策略能为大规模系统中多权限多用户的管理带来便利,而在实际应用中,RBAC访问控制模型存在如下不足:
(1)临时授权用户操作不便。如果系统需要临时授予某个用户某个权限,目前的RBAC模型需要先建立一个新的角色,然后将权限与新角色建立联系,最后将这个新角色赋予给该用户,这样的操作流程对需要频繁进行临时授权的信息系统而言,显然不合理。
(2)缺少权限时间约束。RBAC模型中给用户授予的角色缺少时间约束,用户与角色一旦建立关联,就永久有效,不会随时间变化,这不满足临时授权用户的角色在指定时间段内有效的需求。
本文基于已有基于角色的访问控制(RBAC)模型的不足,对RBAC进行了改进,增加了用户与权限的关联关系,并且提出了时间约束因子,将其引入到用户角色指派和用户权限指派中,使得用户角色权限具有时间动态性,从而满足临时授权用户的权限动态变化的需求。
本文的结构如下:第一节提出信息系统中访问控制策略的需求,并提出本文需要解决的问题;第二节分析了已有的RBAC及其改进模型;第三节详细阐述了本文提出的带时间约束的访问控制TRAC模型;第四节将TRAC模型在实际的档案管理系统中进行了应用;最后对全文进行总结。
2 RBAC及已有改进模型(RBAC and The ImprovedModel)
2.1 RBAC模型
1992年Ferraiolo和Kuhn提出了RBAC的概念,逐渐成为当前流行的先进的安全管理控制方法。所谓角色(role)是指拥有一定权限和责任的某一特定职位。RBAC在用户和资源之间加入了角色,把对资源的使用权赋予角色,然后让用户属于某一角色,从而使用户具有角色的权限。这样,整个访问控制过程就分成两个部分,即访问权限与角色相关联,角色再与用户关联,从而实现用户与访问权限的逻辑分离,其模型如图1所示[4,5,6]。
RBAC使权限管理更为简单、更容易维护,更适合网络系统和大型管理信系统(MIS, Management InformationSystem)的使用,其特点是实现授权管理与角色的划分,职责分担以及目标分级等控制功能[15]。
2.2 RBAC改进模型
RBAC模型是访问控制的基本模型,其对访问控制的各个对象进行了定义,并给出了各对象之间的关联关系,在具体实施中,很多学者根据实际需要,对该模型进行了改进。
在RBAC模型的基础上,文献[7]引入了继承约束和时间约束,同时加入了用户多级授权,文献[14]引入了信任模型,文献[8]将访问控制的颗粒度细化到一个地理实体,这些策略都是使得访问控制的粒度更加细化,满足了模型对复杂角色关系的适应性。
文献[9]针对RBAC中角色私有权限处理方法的不足,引入公有继承方式和角色权限转换策略,保护角色的私有权限,而采用简单灵活的方式控制公有权限的继承,解决了角色继承的复杂度。
文献[10]将领域对象从系统中分离出来,在建立对象过程中采用向导方式,从而实现系统的动态可扩展功能,而扩展的系统应能实现对用户的安全访问控制。
文献[11]提出通过建立权限约束关系来支持角色之间的约束关系,定义了权限约束支持的基于角色的约束访问控制模型及增强权限模型,这种访问控制模型可以增强系统安全访问以及提供更灵活的授权机制,有效降低安全管理员的工作复杂性。
文献[12]针对Web系统中的应用,提出了一种基于角色—功能模型的用户访问控制方法,将最底层菜单中页面实现的业务功能进行划分,以业务功能作为权限配置的基本单位。这种方法在菜单及页面实现的业务功能上实施访问控制,可使Web系统用户访问控制较好地满足用户要求,有效降低Web系统开发的工作量。
综上所述,可以得出RBAC是各种访问控制改进模型的原型,学者们针对具体的业务需求,对RBAC进行了针对性的调整优化,提高管理信息系统的访问控制效率。
3 TRAC模型设计(The Design of TRAC Model)
假设系统中所有用户的集合用U表示,u∈U表示系统中的单一用户,系统中角色集合为R ,r∈R表示系统中的单一角色,系统中所有的权限集合为P ,p∈P表示系统中的单个权限,具体的权限应该是操作(Operation)与对象(Object)的二元关系,操作包括增加、删除、修改、查看、下载等动作,对象包括功能模块、页面、界面元素等基本界面操作对象[1,7,15]。
定义1:时间约束因子T(Time):指一系列描述时间区域的集合,t∈T为一个时间区域,t=null表示不考虑时间约束,即时间区域为无穷大。
定义2:带时间约束的用户角色指派(User RoleAuthorize Based on Time Constraint):指用户集合、角色集合和时间约束因子T的多对多关系,即其中表示用户u、角色r及时间约束因子t的一个三元关系,即用户u在时间区域t内具有角色r的所有权限。
定义3:角色权限指派(Role Permission Authorize):指角色集合R与权限集合P之间的多对多关系,即表示角色r与权限p之间的二元关系,即角色r具有权限p。
定义4:带时间约束的用户权限指派(Time-BasedUser Permission Authorize):指用户集合权限集合和时间约束因子T的多对多关系,用表示。其中表示用户u、权限p及时间约束因子t的一个三元关系,即用户u在时间区域t内具有权限p。
定义5 : 用户的带 时间约束 权限( T i m e - B a s e dPermission Authorize of User):是指经过指派给用户的带时间约束权限的集合,是权限P与时间约束T之间的多对多关系,用表示,表示用户u拥有的待时间约束权限,包括用户u通过指派的带时间约束权限可以有重叠。
根据以上定义,提出了带时间约束的访问控制(TBAC,Time-Based Access Control)模型,如图2所示。与图1中RBAC模型对比可知,配置流程时,TBAC模型在用户和权限之间建立了直接关联,且在用户角色指派和用户权限指派中,增加了时间约束条件。访问流程中,用户通过会话可以从用户角色指派间接获取权限,也可通过用户权限指派直接获取权限。
4 TRAC在档案管理系统中的应用(The applicationof TRAC in file management system)
档案管理系统是一个典型的MIS系统,其存储的信息是一个单位的重要存档资料,不同密级档案对访问人员开放程度不同,档案的增加、删除、修改、查看、下载等都受到非常严格的管控,且具有非常明确的临时授权需求:如经过批准的访问人员,可以在指定时间段内具有访问某一类型文件的临时权限,不在指定时间段内,该访问人员的临时权限则会自动失效;此外年末是需归档文件的井喷期,大量文件需要集中归档,档案管理员需要授予新用户临时增加档案角色,帮助档案的录入,一旦档案录入时间截止,临时授权人员的角色自动失效。
针对档案管理系统中对访问控制系统的需求,以下从数据库表设计、视图设计、系统流程分别进行阐述,最后给出带时间约束的访问控制系统实例。
4.1 数据库表
根据上一节阐述的带时间约束的访问控制模型,设计以下七个数据库表:
(1)用户表(T_USER)。存储所有用户集合U,包括用户实体及其属性。
(2)权限表(T_PERMISSION)。存储系统中所有权限集合U,权限划分情况体现了系统访问控制颗粒度的大小,主要包括操作和对象两个部分,操作可以是增加、删除、修改、查看、下载等动作,对象可以是功能模块、某一类型信息、按钮等界面元素。
(3)角色表(T_ROLE)。存储系统中所有的角色集合R,包括角色实体和属性。
(4)时间约束表(T_TIME)。存储系统中所有的时间约束信息。包括时间约束名Time Name、时间约束类型Time Type、开始时间Begin Time、结束时间End Time、生命周期Life Cycle和累计生命周期Account Time。
其中时间约束类型分为以下三类:
a.时间段约束:表示只有在指定的开始时间Begin Time和结束时间End Time内,该角色或功能才是活跃的,否则用户具有的该角色和功能无效。
b.生命周期约束:表示在受此约束的用户登陆后,其通过指定角色或功能进行操作的连续活跃时间不能超过生命周期Life Cycle,否则该用户将会被强制重新登录。
c.累计生命周期约束:表示受此约束的用户登录后,其通过指定角色或功能进行操作的累计活跃时间不能超过累计生命周期Account Time,否则该用户将不具有该角色或权限。
(5)用户权限表(T_USER_PERMISSION)。存储带时间约束的用户权限指派集合,主要包括用户编码User ID、权限编码Permission ID、时间约束编码Time ID三个外键字段。
(6)用户角色表(T_USER_ROLE)。存储带时间约束的用户角色指派集合,主要包括用户编码User ID、角色编码Role ID、时间约束编码Time ID三个外键字段。
(7)角色权限表(T_ROLE_PERMISSION)。存储角色权限指派集合,主要包括角色编码Role ID、权限编码Permission ID两个外键字段。
这七个数据库表的主外键关联关系如图3所示。
4.2 视图设计
考虑到用户既有与权限的直接关联关系,又有通过角色表与权限的间接关联关系,为了提高访问控制的查询效率,建立用户的带时间约束权限视图V_USER_PERMISSION_TIME,如图4所示。
建立带时间约束权限视图的SQL语句如图5所示,其中union all命令将用户的直接权限集合和间接权限集合合并起来。
4.3 系统流程
系统的访问控制配置及访问流程如图6所示。首先是系统访问控制的配置流程:系统管理员登录、新增用户信息、角色信息、权限信息;根据需要新增时间约束表信息;然后用户角色指派和用户权限指派,将用户具有的角色和权限与时间约束记录进行关联,也可以不指定时间约束记录,这样用户角色或用户权限关联关系将不受时间限制,永久有效;数据库视图将自动根据用户角色和用户权限关联关系的调整做出相应变化,这样系统管理员就完成了整个系统的访问控制配置。
其次是系统访问控制的访问流程:普通用户使用系统管理员新增的用户信息登录系统,从用户登录到用户退出系统的整个操作过程中,进行角色功能的生命期跟踪,根据用户登录时长和系统时间,对用户的角色功能进行实时的调整跟踪,通过登录用户查询带时间约束的用户权限视图,得到登录用户当前时间的所有权限,然后允许用户进行相应的对象操作。
4.4 带时间约束的访问控制实例
假设档案管理员为用户u配置了角色r1、角色r2、权限p1和权限p2,各角色和权限的时间约束条件如表1所示。
假设用户u在8:00登录系统,那么随着时间的变化,用户u的角色权限动态变化如图7所示,9:00以后用户的r2角色将失效,10:00以后用户的r2角色失效,11:00以后,用户将只具有p1功能也失效,且只具有p2的永久功能。
通过带时间约束的访问控制系统,档案管理员可以对用户的角色和权限进行灵活的动态配置,通过灵活的时间约束因子,让用户在指定的时间具有指定的角色或权限,当用户操作时间不在指定时间内时,用户相应的角色或权限或自动失效,这样能减少了系统管理员删除用户权限的操作。
5 结论(Conclusion)
任务时间约束 篇6
由于我国集装箱基础设施相对薄弱, 机械设备落后, 人们对配送的认识模糊等一系列原因, 造成配送还不能很好的改善企业的物流效率, 货损货差现象时有发生, 运输成本居高不下, 配送规模难以扩大。因此, 提高集装箱工作效率要从思想、设施设备建设上进行改进, 在学术界里, 研究者们将这类问题统称为车辆路径问题 (Vehicle Routing Problem VRP) 。
开放式车辆路径问题 (Open vehicle routingproblem, OVRP) 是另一种类型的车辆路径问题。它与基本的车辆路径问题 (Vehicle routing problem, VRP) 的主要区别是不要求车辆完成取送任务后返回原出发点, 或者是若要求返回原出发点, 则沿原去程路线返回。因此, 车辆的行驶路线是开放式的, 而不是闭合式的。OVRP广泛存在于物流配送和各种交通运输方式的运输路线优化中。
目前, 国内外对OVRP的研究都还比较少, 1981年, Schrage在一篇论文中首次对OVRP进行了描述, 引起了人们对开放式车辆路径问题在现实应用方面的关注。但是, 由于OVRP的特殊性和复杂性, 用传统的求解VRP的方法来求解OVRP得不到好的效果。在求解OVRP算法研究方面, 目前可供参考的文献主要有Bodin在1983年提出的解决航空邮件快递的方法;Sariklis和Powel在2000年提出的改进的C-W节约算法;Repoussis[等提出了一个求解带时间窗的OVRP的向前贪婪算法。本文作者提出的是用改进的遗传算法求解的时间窗的车辆路径优化问题。
1问题的描述
本文研究的是有时间约束的集装箱车站工作组织优化, 实际是带时间窗的车辆路径优化问题 (Vehicle Routing Problem with Time Windows, VRPTW) , 可表述为:配送中心拥有K辆车, 其容量相同, 车辆的最大负荷为Q, 需要完成n个客户的运输任务, 为构造数学模型, 定义变量如下:
K—所需的车辆数Q—车辆的最大载重量
L—车辆的最大行驶距离c—单位距离的成本
i, j—客户点和车场, 其中i=0表示车场;dij—从点i到j的直接距
di—点i的货物需求量tij—从点i到j的运输时间
ti—到达点i的时间si—地点i的卸货时间
ai—点i时间窗的最早时间bi—点i时间窗的最晚时间
d—早到的惩罚系数e—晚到的惩罚系数
如果客户i和客户j在同一条线路且客户j恰好在客户i之后服务, 由式 (2.1) 则tj=ti+si+tij
根据各客户的需求量和车辆载重量可以估计出车辆数目的下限由式 (2.2) :
模型如下:
在上述模型中, 式 (2.3) 为第一目标, 表示使需要的车辆数目最少;式 (2.4) 为第二目标, 第二目标是最小化车辆行驶成本, 由最短的行驶时间和超过时间窗的惩罚成本构成;式 (2.5) 表示的是每个客户只能被访问一次;式 (2.6) 表示车辆符合负载要求;式 (2.7) 表示最多使用K辆车;式 (2.8) 表示达到和离开每个客户的时间相同;式 (2.9) 表示的是车辆行驶的最大距离约束;式 (2.10) 表示的是整数约束。
2求解有时间约束的OVRP的改进遗传算法设计
2.1编码
由于VRP是一种基于次序的组合优化问题, 利用二进制编码存在解码难题, 因而对于车辆路径问题一般倾向于自然数编码, 即实数编码。所谓自然数编码方式, 就是编码字符集由自然数所组成{0, 1, 2, 3, …, n}, 其中0代表集装箱车站, 1, 2, …, n代表的是客户服务点。本文亦采取这种方式编码。
2.2初始解的生成
由于遗传算法是一种群体型搜索方法, 所以必须为遗传操作准备一个由若干个体组成的初始群体, 每个个体一般都通过随机方法产生, 并分别对应研究问题的一个解。研究表明, 遗传算法搜索最优解不依赖于初始种群。本算法采用随机方式生成初始种群。
2.3选择策略
结合以往VRP的遗传算法设计经验, 本文选用目标函数值加罚函数的倒数作为适应值函数。其公式为:
fi表示i染色体的适应值;zi表示i染色体加入惩罚项后的目标函数值 (惩罚包括超出载重量惩罚和超出车辆最大行驶成本的距离惩罚) ;z′表示的当前种群中的最好染色体的目标函数值。
2.4交叉算子
交叉算子的设计应根据所研究的实际问题的特征来确定, 目前, 对基于自然数编码求解的VRP, 一般选用的交叉算子有:部分匹配交叉法 (Partially Matched Crossover, PMX) 、顺序交叉法 (Order Crossover, OX) 等。其中, 部分匹配交叉法其主要效率较低。针对其不足, 文献等综合了OX、PMX和OBX (Order-Based Crossover) 等交叉算子思想的基础上, 提出了交叉算子A。该算子与PMX等的区别在于, 父代个体2中将被交换的基因是由父代个体1中交叉区域里的相匹配的元素来定义的。所产生的两个子代个体都是合法的, 无须对其它的基因进行重新映射, 运算效率得到提高。因此本算法中将尝试使用交叉算子A来求解OVRP。交叉算子A的具体过程如下:
父代1: (3 2 1 4 5 6 9 7 8)
父代2: (4 6 2 1 8 7 3 5 9)
随机从一个父代 (如父代l) 产生两个交叉点, 把两个交叉点之间的部分作为交叉基因段, 并保存在临时记录S中。
父代1: (3 2 1|4 5 6|9 7 8)
父代2: (4 6 2|1 8 7|3 5 9)
记录S: (4 5 6)
再从另一个父代中找出和记录T中相同的基因, 用其中的基因序列替换先前父代中记录S中的待交叉片断得到子代1。同理得到子代2。
2.5变异算子
本文采取的变异操作为:一旦随机数小于变异概率, 则进行变异操作, 随机选取两个顾客点交换位置;如果交换位置之后与前代染色体的适应值相比, 改良了则接受, 否则放弃;如此循环下去, 直到产生出的交换达到了最好的染色体为止。上述的变异操作, 每接受一次交换, 都要根据约束条件重新安排车场位置。经过验证, 这种变异操作能够在较少的进化代数之内找到优良基因。
2.6参数设置
在遗传算法中, 交叉概率pc和变异概率pm是影响遗传算法行为和性能的关键, 直接影响着算法的收敛性。一般的VRP的遗传算法中交叉概率pc和变异概率pm都是分别取固定的值。为了避免发散和陷入局部最优点, 我们引入自适应机制, 动态地调整pc和pm, 即通过高适应值的解降低和, 而对低适应值的解是通过提高和来实现, 具体为:
其中, k1=0.6, k2=0.5, k3=0.9, k4=0.05;f0为种群中的最大适应值, f′表示交叉的两个个体中较大的适应值, f为种群的平均适应值, f是变异个体的适应值。交叉概率随着适应值趋向于f0而减少, 当适应值等于f0时, 即对具有最大适应值的解, 其pm和为pc零, 这样, 种群中最好的解就直接复制到下一代 (即精英选择) 。
2.7算法流程
根据上文对带软时间窗的开放式车辆路径问题的遗传算法的详细设计, 可以得出该算法的流程图, 如图1所示。
3基于遗传算法的算例分析
3.1实验结果
用C语言实现求解有时间约束的OVPR的改进遗传算法, 在C++Builder5.0上调试成功, 并做了实验, 下面给出其中1个具有可比性的实验结果及分析。
假设某集装箱车站有一个配送中心和8个需要服务的客户, 表1给出了配送中心与各客户间的距离 (单位:公里) , 这些客户由容量为8吨的相同车辆完成配送, 汽车的行驶速度设为50km/h, 行驶的最大距离为300km, 本文也将配送时间、配送车辆早到惩罚和晚到惩罚的权重设置为:0.1:0.3:0.6。各客户的货物需求量为di (单位:吨) 。每个客户的服务时间Ti (单位:小时) 以及客户要求的服务时间范围[ai, bi]由表2给出。
实验20次, 得到的实验数据见表3所示, 由表中可知, 需要的车辆数为:3辆。总距离570公里, 总成本570.6元。
最终的路径示意图如图2:
3.2算例比较
文献中设计的遗传算法计算该算例的表4:
与本文计算结果的比较, 如表5:
从表5可以看出, 与文献[2]相比, 本算法运输距离减少了5%, 运输费用减少了4.9%, 但偏离时间窗的时间却增加了, 所以从本文优化的目标来说, 该算法的性能良好, 计算结果得到了优化, 尽管时间窗偏离没有什么改变, 但从全局上得到了优化。
4结束语
本文基于集装箱运输的现状和对车辆问题的研究方法的缺陷, 提出了有时间约束的开放式车辆路径问题。并做出开放式车辆路径问题和带时间窗的车辆路径问题的模型, 设计了改进的遗传算法来解决有时间约束的开放式车辆路径问题, 取得了较优的结果。
参考文献
[1]索占鸿, 朱昌锋.集装运输.北京:中国铁道出版社, 2005.
[2]张宏.物流配送中车辆路径优化问题研究.黑龙江:哈尔滨工业大学, 2007.
[3]Schrage L.Formulation and structure of more complex/realistic routing and scheduling problems[J].Networks, 1981, 11:229-232
[4]Bodin L.D, Golden B.L, Assad A.A, and Ball.M.O.Routing and scheduling of vehicles and crews:the state of the art[J].Computer s and Operations Research, 1983, 10 (2) :63-211
任务时间约束 篇7
传统的运输问题可以转化为一个标准的线性规划,通过表上作业法、单纯形法或lingo软件等求解。在实际的运 输过程中,常受到许 多因素的 限制,如运输时间、选择的路径、费用、运输的安全可靠性等。在传统运输问题的基础上发展形成了多 目标运输问题,对于确定性的多目标运输问题有了较成熟的解决方案。虽然多目标运输问题对解决现实问题提供了有效的解决手段,但在一些具有随机性的现实问题中还是不能精确 地描述。李珍萍等对带时间窗约束的运输问题进行探讨,但只是限于经典模式下的运输问题,没有涉及到随机条件下的此类问题。
已有许多文章对运输问题进行研究和探索,但在实际运输问题过程中,是一个复杂的受多种不确定因素影响的优化问题,为此,在传统经典运输问题的基础上,增加了运输过程中运输线路能力的约束,运输过程中的时间约束由于一些意外原因,如可供应量、需求量、线路能力、时间等都 具有随机 性,提出一种基于时间约束的随机机会规划运输问题模型,并利用混合遗传算法求解,进行算例验证。
1运输问题模型
1.1传统运输问题
设某物资有m个产地Ai(i= 1,2,…,m),其产量分别为ai(i=1,2,…,m);有n个销地Bj(j= 1,2,…,n);从Ai到Bj运输物资 的单位运 价为cij(i=1,2,…,m;j=1,2,…,n);
在产销平衡的条件下,即的数学模型为
但在一般情况下,产销并不能总保持平衡,当产销不平衡时,问题可转化为产销平衡的运输问题模型。
1.2带有时间约束的随机机会约束规划运输问题模型
在实际中通常要考虑其可靠性(或风险),即利于(或不利于)事件发生的概率,为此决策者可根据自己的喜好或一定的目的选择建立运输问题的随 机机会约束规划模型。机会约束规划理论最早是Charnes和Cooper提出的,其特征是随机约束条件参数至少以一定的置信水平收敛。
Liu在机会约束规划提出之后,给出在随机环境条件下,若决策者希望极大化目标值函数的乐观值,建立如下的机会约束规划模型
其中约束条件中第 一个是目 标约束,第二个是联合机会约 束,a和β是决策预 先给定的 置信水平。
在现实生活的运输过程中,产地、销地、选择的线路能力、运输时间都存在随机性,但这些约束条件在一定的置信水平成立,虽然已经有一些人对此做了研究,如在需求随机条件下运输问题的机会约束规划模型研 究,对运输问 题进行了 综合实际 考虑,但仍缺少时间约束,因此可建立目标函数为最小费用的 带有时间 窗约束的 机会约束 规划模型, 则有
式中:ulr,vlr为权系数;σl为目标函数的置信水平;αi,βj,ηk为给定的供应量、销量以及线路能力的约束置信水平;tijk为运输过程中需要的时间;Tk为运输过程中最晚到达时间;Tk为软约束;γk为时间约束的置信水平。
2模型求解并验证
在处理机会约束规划模型时,传统的方法是将他们转化为各自的等价形式,但这种情况只在极少数条件下才能成立,而对于一些较复杂的问题难以处理。因此将神经元网络与遗传算法结合起来,设计了混合遗传算法来求解一般的随机机会约束规划模型。
算法步骤
1)用随机模拟技术为上述不确定性模型函数生成培训输入输出的数据;
2)根据得到的输入输出数据进行训练,训练一个神经网络近似不确定函数生成的训练数据;
3)初始化pop_size个染色体,其可行性可由经过训练的神经元网络检查;
4)通过交叉变异操作得到新的染色体,子代染色体的可行性可由经过训练的神经元网络检验;
5)利用事先训练好的神经元网络计算所有染色体的目标值;
6)根据每个染色体目标值计算其适应度;
7)通过旋转赌轮选择染色体;
8)重复第4~第7步骤,直到完成给定的循环次数;
9)找出其中最好的染色体作为最优解。
将随机模拟 技术作为 不确定函 数,则有U ∶ x(U1(x),U2(x),U3(x),U4(x),U5(x)),产生输入输出数据,其中
训练一个神经元网络(3个输入神经元,15个隐层神经元,3个输出神经元),不断地逼近不确定性模型函数U。然后将已训练好的神经元网络与遗传算法相结合,得到混合遗传算法。
史峰在MATLAB智能算法的30个案例分析中,对遗传算法与神经网络相结合的混合智能算法给出了分析案例,结合书中的分析,通过MATLAB实现设计的混合智能算法。
为验证混合遗传算法对在求解随机机会约束 规划模型 时的有效 性,给出具体 的实例,利用MATLAB编制混合遗传算法程序求解,下面给出在求解随机运输问题时的参数:
1)种群规模为50;
2)交叉概率为0.7;
3)变异概率为0.1;
4)评价函数参数为0.05;
5)迭代次数为200;
6)训练次数为3 000;
7)模拟次数为5 000。
实例:给出有两个供应店,两个销售点,两种运输方式的示例。假定目标费用最小,费用、时间、线路能力等约束条件服从某种分布的随机变量,相关参数数据如表1~表3所示。
在表1中:u(a,b)表示该参 数服从区 间为 [a,b]均匀分布的随机变量;N(μ,σ2)表示该参数服从期望为μ,方差为σ2的正态分布的随机变量; T(a,b,m)为参数服从三角分布的随机变量。
利用MATLAB软件,通过混合遗传算法进行求解,得出最优解为
从以上结果可以看出带有时间窗的随机机会约束规划模型的求解结果比较理想。
3结束语
从不确定角度对随机参数建立运输问题模型, 并在经典的运输问题基础上增加了时间窗约束和线路能力约束,因此模型从经典的运输问题线性规划转变为非线性规划,增加了求解的难度,很难找到最优解,但是本文利用混合遗传算法求解此类非线性规划模型案例,并对解进行优化,可以找到最优解。
摘要：对传统经典的运输问题从不确定性随机规划角度进行探讨分析,针对随机环境条件下的此类优化问题提出一种随机机会约束规划模型,并考虑在运输过程中的线路能力和时间窗限制,对其利用随机机会约束规划的思想进行处理,建立随机机会约束规划运输问题的数学模型。此外,由于模型涉及大量具有复杂性和随机性的随机变量,设计一种混合智能算法,即基于随机模拟的神经网络遗传算法来求解模型的近似最优解。最后利用数值算例来验证算法的有效性和可行性。