论文部分内容阅读
车辆调度问题最早由Dantzig和Ramser在1959年提出,该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流系统、物流网等应用、研究领域中的基本问题之一,也是最重要的调度问题之一给定一行车地图,即无向图G=(V,E),对于每条边e=(i,J)∈E,有权值wi,j,表示车辆从地点i到达j所需时间.在每个顶点i∈V上,恰有一个任务,也记为i,每个任务有一个释放时刻r(i),截止时刻d(i),所需处理时间h(i),车辆完成该任务能得到的利益v(i).我们关注这样的车辆调度问题：寻找任务的子集J(?)V,以及车辆的路线,使得车辆能够完成J中所有任务,并且获得的值最大化,把该问题记作VSP(Val),本论文得到的主要结果如下：本文比较系统地分析了线形图上的VSP(Val)问题和模型,证明当r=0,v=1时VSP(Val)是NP难的,而当h=0,v=1时VSP(Val)是强NP难的.当所有任务的释放时刻都为0,且截止时刻都相同时,以及所有任务恰好有两个不同的截止时刻时,利用动态规划,分别给出了伪多项式时间算法.本文研究树形图上的VSP(Val)问题,分析了行车地图为星状图时该问题的复杂性,在释放时刻和执行时间都为0,截止时刻都相同,且车辆需要在规定时间内返回起点的情况下,给出了一个伪多项式时间算法,并且基于此算法,给出了该问题的FPTAS (Fully Polynomial Time Approximation Scheme),所需时间为O(1/εn4).对于一般图上的VSP(Val)问题,当所有任务的释放时刻和处理时间都是0,截止时刻和任务的利益都相同时,本文利用着色编码方法给出了w=1时,期望时间复杂度为O((4e)2kn3)的固定参数算法.本文研究VSP(Val)的一个变种—节目下载问题(Program Download Problem,简记为PDP),通过三元可满足性问题的受限情形到PDP的多项式时间归约,证明了当只有两个频道,每个节目在每个频道上最多播放两次时,且每个节目的播放时间都是单位长度时,PDP是NP完全的,以及当每个节目在每个频道上最多播放一次,且每个节目的播放时间都是单位长度时,PDP也是NP完全的.如果各个频道上的节目都是同时开始同时结束的,称为时间对齐.对于时间对齐的PDP问题,我们给出了一个多项式时间算法.证明了除非P=NP,否则优化问题MinPDP不存在1+X/(2n+1)-近似算法,其中X是任意整数,2n为频道数.对于参数化问题p-MaxPDP给出固定参数算法,算法所需期望时间为O(2°(l)(nm)3).