【摘 要】
：
车辆分群调度问题是计算机科学和运筹学中一类重要的组合优化问题,其在现实生活中具有广泛应用,如磁盘碎片整理、程序重构、细胞检测、集成电路测试、考试时间表安排等等。因此,对其进行研究具有重要的理论与实际价值。本文主要研究几个特殊网络上单台车辆分群调度问题。给定一个网络图,若干个待服务的客户分布在该网络上,并且这些客户被划分为若干个子集,每个子集称为一个群。给定一台车辆,其需要服务所有客户,且每个群内的
论文部分内容阅读
车辆分群调度问题是计算机科学和运筹学中一类重要的组合优化问题,其在现实生活中具有广泛应用,如磁盘碎片整理、程序重构、细胞检测、集成电路测试、考试时间表安排等等。因此,对其进行研究具有重要的理论与实际价值。本文主要研究几个特殊网络上单台车辆分群调度问题。给定一个网络图,若干个待服务的客户分布在该网络上,并且这些客户被划分为若干个子集,每个子集称为一个群。给定一台车辆,其需要服务所有客户,且每个群内的客户需连续服务。每个客户有一个释放时间和一个服务时间。释放时间的含义是,车辆只能在该时刻之后才能对其进行服务。服务时间的含义是,车辆在对其进行服务时需花费一定的服务时间。问题的目标是寻找一个时间表,使得车辆按要求服务完所有客户并返回初始出发位置所花费的时间最少。本文从近似算法的角度对线型、圈型和星型网络上单台车辆分群调度问题展开了研究,分别给出了较好的近似算法,其主要结果如下:本文首先考虑的是线型网络上单台车辆分群调度问题。设G（28）（V,E）是一个线型网络,其中V（28）{0,1,2,,n-1}是该网络的顶点集,E（28）{（i,j）}是该网络的边集。初始时,有一台车辆位于h处。顶点集V\h中的每个顶点处有一个客户,它们被划分成K个连续子集V0,V 1,,VK-1。问题的目标是,计算一个客户服务顺序的时间表,使得车辆从初始位置出发,服务完所有客户且每个群内的客户连续服务,最终返回初始出发位置时所花费的时间最少。针对该问题,本文给出一个近似比为7/4的近似算法,其时间复杂度为O（n~2）。其次考虑的是圈型网络上单台车辆分群调度问题。该问题与线型网络上相应问题类似,其不同之处在于,K个客户群连续分布在一个圈型网络中。针对该问题,就客户服务时间为零的情形,本文给出一个时间复杂度为O（n~2）的动态规划最优算法;就客户服务时间任意的情形,本文首次给出一个近似比为13/7的近似算法,其时间复杂度为O（n~2）。最后考虑的是星型网络上单台车辆分群调度问题。该问题与线型网络上相应问题亦类似,其不同之处在于,K个客户群连续分布在一个星型网络中,每个客户群构成一个分支。针对该问题,就客户服务时间为零的情形,本文给出一个时间复杂度为O（nlogn）的动态规划最优算法;就客户服务时间任意的情形,本文首次给出一个近似比为5/3的近似算法,其时间复杂度亦为O（nlogn）。
其他文献
免疫细胞浸润实体瘤的性质和程度是治疗癌症的关键决定因素,了解肿瘤组织的免疫细胞比例对肿瘤患者的诊断和预后治疗具有重要意义。如何快速方便地识别肿瘤的细胞成分是生物信息领域的研究热点之一。许多基于机器学习的计算方法已经被开发用来进行肿瘤的异质性分解,从而替代价格昂贵、耗费时间长的实验方法。大部分现有的计算方法是基于样本内全部的细胞信息来预测样本组成,但在实际的临床实践中有些数据会丢失即仅有部分数据可用
近年来,暗纹东方鲀养殖效益欠佳,造成养殖户的积极性降低,亟需进一步丰富市场上暗纹东方鲀的养殖品种。然而,暗纹东方鲀的人工繁殖和杂交育种效率低下,通过人工方式对胚胎质量及胚胎发育的各个时期进行分类检测准确性不高。利用图像处理技术精确的识别分类出暗纹东方鲀胚胎的各个时期,并通过分析每个时期的特征建立合适的盐度、温度等养殖环境,可以提高人工繁殖和杂交育种的成活率,采用自动方式并提高暗纹东方鲀胚胎各个时期
近年来,由于我国国民经济的快速增长、电商行业的兴起以及物流速递等业务的蓬勃发展,中华绒螯蟹作为我国特色水产经济作物之一,已经拥有相当规模的销售市场。但是,目前市场上主流的大闸蟹追溯方式是采用捆扎条形码或二维码等电子标签于蟹钳上,由于标识物的可替换性,单单依靠这种方式追溯河蟹信息并不可靠。因为大闸蟹生长环境的变化,个体大闸蟹背甲图像中的隆起、凹陷、沟渠、纹理等形态性状会出现较为明显的差异,因此个体河
随着人们对于水产品需求的不断增加,根据国际粮食和农业组织估计,到2030年全球水产品需求缺口预计将达到3000万吨。海洋渔业农牧化也是我国现代海洋渔业发展的趋势,渔业的发展对于我国人民群众的生活和国民经济有着十分重要的意义。在水产养殖中,最重要的问题之一是通过自动化手段准确地、持续地监测鱼的各类形态特征,来评估鱼类健康状况并优化鱼群日常饲养流程,为确定最佳的捕捞时间提供科学指导。鱼类的体尺参数是评
GDP（二磷酸鸟苷）和GTP（三磷酸鸟苷）是核苷酸的一种,参与了生物中大部分生物化学反应,在DNA复制与转录、跨膜运输、肌肉收缩以及多种代谢过程中都发挥着不可替代的作用。在大多数生物细胞活动中,都需要蛋白质与核苷酸互相结合来发挥其作用。蛋白质-核苷酸结合位点的识别不仅有助于探索分子间相互作用的机制,而且有助于有效地解释疾病的发病机制,为药物的发现和设计提供帮助。传统的研究通常是使用生物学实验预测蛋
腹泻是影响畜禽发育和生长的多发病，它制约着养殖业的发展。我国的中药资源非常丰富，在抗病原微生物的同时，又能改善肠道菌群，并且提高机体免疫力，在畜禽腹泻的防治上具有独特的优势。该文在分析畜禽腹泻病因的基础上，针对细菌性腹泻、病毒性性腹泻、寄生虫性腹泻以及非感染性腹泻等不同情况常使用的抗腹泻中药，结合防治机制对中药防治畜禽腹泻的研究现状进行了全面的阐述，以期为后期的研发提供理论依据。
＜正＞在新课标的背景下,小学英语教师就要注重提高教学效果,改善作业质量,减轻学生在英语学习中的压力,对课堂教学内容进行深入的研究,掌握学生的真正学习状态,开展小学英语单元整体作业设计,促进发展学生的核心素养。优化评价方式,才能将学生的小学英语学习效果提升上来。在开展教学的过程中,
＜正＞我国的能源结构丰富而复杂,其中电力能源为重要的组成部分之一,多年来一直持续不断地支持着我国的现代化建设。但随着我国经济的飞速发展,电力能源有限性和不可再生性的弊端开始显露,我国的生态环境保护也在发展中受到了阻碍。于是新时期以来我国党和政府大力推行可持续发展战略,号召各大企业节能减排,合理规划能源资源利用,同时大力扶持新能源的开发和推广,
海面温度（Sea Surface Temperature,SST）与全球气候变化、海洋灾害、海洋生态系统密切相关,因此准确的预测海面温度是一个具有重要意义的课题。随着海洋监测技术的不断进步,海面温度等海洋环境要素数据被大量采集,数据驱动的海面温度时间序列预测方法逐渐显现出了其良好的效果。但现有的数据驱动方法忽略了海面温度与气温、风速等其它海洋环境要素之间的关联关系,限制了精度的提高。为了有效捕获不
在生物学研究领域,高通量测序技术催生了海量的生物学数据。从这些生物学数据出发,利用合适的生物信息学方法发掘与疾病发生机制相关的生物通路,研究疾病与生物通路间的关系,对疾病的诊断和治疗技术的发展具有重要的意义。从高通量的海量数据中获得对疾病深层次的认识,发现疾病的复杂机制依然是研究人员面临的一个挑战。虽然在过去的十几年,相关研究人员已经开发出一些基因富集分析方法来发现与疾病相关的生物通路。然而这些方