一、求解指派问题的一个算法（论文文献综述）
吴元霄[1]（2020）在《一些网络排序和路径优化问题的算法设计与性能分析》文中研究表明本文主要研究了一些网络上的组合优化问题,包括网络排序问题,有容量约束的车辆路径问题和2-配送问题。我们研究了这些问题的性质,然后在此基础上为这些问题设计了算法,并分析了这些算法的最坏情形性能比和的复杂度。本文主要包含以下六个章节:第一章介绍了组合优化问题和网络优化方面的一些基本概念和定义,总结了本文相关领域的研究现状,最后阐述了本文的主要研究成果。第二章研究了树形网络和环形网络上的返回型和非返回型单机网络排序问题（SVSP）。我们设计算法的主要思路为构造多个备选解,然后从中选择最好的一个作为算法的输出解。在算法中,部分备选解通过求解原问题的简化问题得到,另一部分备选解通过一个基于客户集划分的方法求得。对于树形网络上的返回型SVSP问题,我们首先证明了该问题与树形网络上的返回型SVRP问题等价,然后通过设计后者的一个16/9-近似算法来得到前者的16/9-近似算法。对于树形网络上的不返回型SVSP问题,我们利用返回型问题的结果设计了一个48/25-近似算法。对环形网络上的返回型和不返回型SVSP问题,我们分别设计了一个5/3-近似算法和一个29/17-近似算法。第三章研究了最小化车辆总行程的容量约束的车辆路径问题（CVRP）。我们考虑了两种特殊情形下的问题,分别是线形网络上需求不可分的CVRP问题和环形网络上需求可分的CVRP问题。对于前者,我们定义了标准实例的概念,分析了问题的下界。基于这个下界,我们提出了一个5/3-近似解的结构,并依此设计了复杂度为O（n2）的5/3-近似算法。对于后者,我们分析了问题最优解的性质,并根据该性质设计了一个复杂度为O（nC）的伪多项式时间最优算法。第四章研究了最小化车辆最大行程的容量约束的车辆路径问题。该问题可以看作最小化总行程的CVRP问题的推广,因此该问题也是NP-困难的。我们如同上一章一样考虑了问题的两种特殊情形,即线形网络上需求不可分情形和环形网络上需求可分情形。对于前者,我们用划分问题进行归约,证明了该问题在P≠NP的假设下没有近似比小于2的多项式时间算法,然后给出了一个复杂度为O（n2）的2-近似算法。对于后者,我们给出了一个伪多项式时间的近似方案。第五章研究了2-配送问题（2-dTSP）。该问题是k-dTSP问题在k=2时的特殊情形。本章考虑了树形网络和一般网络上的2-配送问题。对于树形网络上的2-dTSP问题,我们通过对树形网络进行优化,提出了一个多项式时间的最优算法。对于一般网络上的2-dTSP问题,我们提出了一个多项式时间的5/2-近似算法。第六章总结了本文的内容,并提出了一些今后可以继续研究的方向。
张迎春[2]（2020）在《基于效率提升的单机多任务调度相关问题研究》文中认为随着经济全球化进程的加快、互联网技术的飞速发展以及我国社会主要矛盾的转变,现代企业的经营环境正在发生着巨大的变化。不管是资源的日益紧缺、企业之间竞争的日趋激烈,还是客户需求多样化和个性化趋势的日益加剧都对企业现有的生产制造模式提出了更高的要求。面对严峻的市场挑战,企业只有通过不断协调自身资源（如人力、生产）、时间、环境等多种因素,制定符合企业自身的生产、运营管理方式和调度规划策略,才能有效地提高企业的生产、服务效率以及综合调配能力,实现物尽其用、人尽其能从而增强自身竞争力。调度问题是一类经典的组合优化问题,能够有效解决资源的优化配置问题。面对复杂多变的工作环境,传统的生产调度模型已经不再适用,多任务调度概念应运而生,它的理论研究与现实推广在现代企业的生产与服务过程中发挥着巨大的价值。在此背景下,本文针对新环境下产生的新问题,建立、设计更加贴合实际多任务处理环境的调度模型,并对相关问题进行求解,进而提供优化算法,不仅具有重要的学术意义,还具有较强的现实价值。本文首先阐述了多任务调度问题的研究背景和意义,同时梳理了本文所涉及到的调度领域相关热点的研究现状。其次,针对企业的实际工况,本文提出了带有效率提升效应的多任务调度模型。在多任务处理环境下,任务之间不可避免地会发生相互干扰,因此,在经典的多任务调度模型中,多任务函数由切换函数和中断函数两部分组成,等待工件会中断主要工件的加工,从而使得主要工件的加工时间包括三部分,即主要工件的剩余加工时间、转换时间以及所有等待工件中断的加工时间。本文首次考虑了由多任务切换所产生的积极作用,在经典的多任务函数中,通过引入依赖于工件及其打扰位置的可变效率提升因子,从而建立了新的统一调度新模型,当且仅当效率提升因子全部为1时,则回归到经典多任务调度模型。同时,本文还提出了一个更具一般性的依赖于工件自身及其实际加工位置的DeJong恶化效应时间函数模型,它不仅克服了加工时间随着位置的无限后移而趋于无穷大的弊端,还可以通过改变因子M的取值,将其视为学习效应函数模型。随后,考虑到额外配置资源会对实际加工时间产生影响,故本文在多任务调度新模型中,进一步结合两种不同的资源配置模型,进而产生了两类更加贴合实际生产环境的多任务调度模型,这也是本文的一大创新点。除此之外,考虑到企业在实现快速响应市场需求的同时,还必须保证其产品或服务质量,为此,基于准时制生产背景,本文还研究了具有松弛交货时间窗的多任务调度问题。全文研究内容由浅入深、层层递进。首先,通过对效率提升效应进行分析与量化,建立带有效率提升效应的多任务调度模型。基于新模型,针对三个经典调度问题展开研究,即极小化制造期、极小化总完工时间和极小化完工时间差的绝对值之和,并给出了相应的多项式时间算法。其次,在新模型的基础上,分别讨论了具有恶化效应、资源分配以及松弛交货时间窗的多个单机调度问题,且均被证明是时间复杂度为O（n 3）的多项式可解问题。特别地,当任意效率提升因子都相同时且不为1时,可进一步优化带有松弛交货时间窗的调度算法复杂度,使其时间复杂度将至O（nlo g n）。最后,基于带有效率提升效应的多任务调度模型,本文综合性地研究了同时具有恶化效应、资源分配的松弛交货时间窗的多任务调度问题,分别在两种不同的资源配置模型中,讨论了总成本最小化问题,主要包括提前完工费用、延迟交付损失、设置松弛时间窗的开始时间和窗口大小的机会成本以及总资源耗费成本,经过逐步分析与求解,得出了解决这两类模型的最优算法。最后,通过设计数据算例、利用LINGO工具,逐步演示了本文第五章中最具复杂性的两个算法步骤,从实践的角度验证了所提算法的有效性和可行性。
张亚辉[3]（2020）在《多约束条件下多目标双边装配线再平衡方法研究》文中进行了进一步梳理双边装配线广泛应用于柴油发动机、装载机等大型机械产品的装配生产中,与传统的单边装配线相比,具有装配线长度短,资源利用率高,生产时间与成本少等优点。近年来,装备制造业升级加剧了市场需求的变化,迫使企业不断利用新的工艺和技术改建原有装配线。如何在原有平衡方案的基础上重新优化任务分配,以最小的成本完成装配线改建,并确保改建后装配线高效运行,是亟待解决的难题。双边装配线上任务再分配需要考虑任务移动的关联效应,以及装配工艺变化、任务再分配约束和空间维度约束的限制与影响,在尽可能提高装配线运行效率的同时,有效控制装配线的改建成本。因此,迫切需要开展多约束条件下多目标双边装配线再平衡方法研究。具体研究内容如下:（1）针对双边装配线上任务再分配受先序约束和左右边分配机制综合影响的问题,以改建装配线的产能和改建成本为目标,建立了多目标双边装配线再平衡问题的数学模型。在此基础上,研究了任务再分配过程中任务移动的关联效应,提出了吸入式、推入式和基于单工作站的三种任务再分配策略,设计了基于ε-约束法的多目标双边装配线再平衡启发式算法。通过国际公开的标准案例和工程案例对比分析了三种任务再分配策略的差异和优劣,结果表明基于单工作站的任务再分配策略优势明显。（2）针对工艺变化情况下装配任务、先序关系和工位数增减等改变引起的双边装配线再平衡问题,提出了优化装配任务分配的多目标遗传算法。研究了基于工作站内外任务移动差异的再平衡成本计算方法和基于工位内空闲时间的节拍估算方法,设计了基于成本和节拍控制的交叉变异算子,获得多约束下的可行解集;提出了基于估算节拍的任务再分配解码机制,保证快速搜索到解空间内的较优解集;使用基于非劣排序的Pareto最优解集更新机制,获得以优化产能和再平衡成本为目标的双边装配线再平衡最优解集。最后,通过双边装配线的国际标准案例集和工程案例验证了算法的有效性。（3）针对有限资源对任务再分配过程的影响与限制问题,提出了四类任务再分配限制约束,建立了以优化工位完工时间均衡度、节拍和改建成本为目标的再平衡模型。提出了一种基于帝国竞争算法的多目标优化算法,设计了一种由多种任务分配规则构成的多变权重法生成初始种群,保证解的可行性与多样性;改进了节拍估算方法,设置了受限任务的预分配机制和任务按边分配机制,提出了预分配与分配相结合的解码方法,确保左右工位任务分配均衡、有效;提出了满足任务再分配约束的启发式同化方法,在增大算法局部寻优能力的同时,保证解的可行性。利用双边装配线的国际标准案例集进行测试,从算法框架、改进的同化方法和解码方法等方面完成了算法有效性的分析验证。34组案例中,获得了28组的最优解,其中3组案例求得了迄今为止的最优节拍。最后的工程案例结果再次验证了算法的高效求解能力。（4）针对装配任务受时空约束共同作用导致再分配可行解搜索难度增大的问题,基于装配线与装配任务的UML模型,分析了工位内可作业空间对于任务再分配的影响,构建了问题数学模型。提出了一种时空约束下任务再分配的优化求解算法,设计了基于任务作业长度的工位作业长度上限估算方法,提出了基于估算节拍和作业长度共同控制的任务分配和再分配机制。最后,使用包含空间属性与约束的标准案例和工程案例,从求解能力、性能稳定性、运行效率和运算时间四个方面验证与分析了算法的性能。此外,工程案例的求解结果亦说明了空间约束的存在使得问题可探索到的Pareto解个数减少,且需要花费更多的成本实现节拍的优化和生产均衡,验证了模型的有效性。
周星[4]（2019）在《多机器人全覆盖问题的任务分配算法研究》文中提出机器人全覆盖问题是指利用移动机器人,在其物理接触范围或者在其传感器感知范围内遍历目标环境区域,并尽可能地满足任务完成时间短、重复路径少或未遍历区域小等优化目标。机器人的全覆盖应用出现在军事、农业、工业、商业、灾难救援、城市生活等各个方面,例如自动排雷、作物收割、空中交通巡查等。一般而言,全覆盖行动（mission）的各个任务（task）具有较为明显的空间并行性,能够并行地被处理。因此,随着全覆盖行动的规模越来越大,以及多机器人技术的发展等因素,多机器人系统被引入到了全覆盖行动中,期望能够加速行动的完成时间,从而取得更好的效益。多机器人系统处理全覆盖行动的过程中,需要经过若干个阶段,包括任务分解、任务指派（assignment）、任务调度等。任务分解阶段关注将整个行动分解成哪些任务或者将整个行动空间分解为哪些区域（region）,任务指派阶段关注将每个任务指派给哪一台机器人,而任务调度阶段关注每台机器人的任务执行顺序以避免路径冲突（如冲撞等）。这三个阶段在本研究中统称为任务分配（allocation）,任务分配是多机器人获得高效性能的核心。一个好的任务分配方案应该应对加速比、资源冲突性（例如路径冲突）、机器人数目不确定性（例如任务完成时间具有截止时限）或者环境的不确定性（例如环境概率性的转移）这三个挑战。寻找一个时间均衡性最优、冲撞少或者无冲撞、能处理数目或环境不确定性的分配方案,其搜索空间可能达到O（q N）,其中q是机器人的个数、N是任务的个数。一般地,N可达到成百上千,它指的是环境被分解为单机器人全覆盖直径为边长的方格的个数,或者环境被分解为其它原子类型区域的个数,因此最优分配方案的搜索空间十分巨大,大规模问题很难精确地求解,设计可行的、高效的近似最优分配算法是一个途径之一。本研究针对多机器人系统全覆盖任务分配中三种不同的情形（scenes）,每种情形带有了以上三个挑战中的不同组合,设计了三类算法。这些算法所基于的系统是同构的机器人组且带有中心计算通信节点的多机器人系统。本研究的贡献如下:（1）已知环境且已知机器人数目的情形下,两种均衡且无冲撞的多机器人任务分配算法。针对这一情形,本研究提出了适用于中小问题规模的基于混合整数线性规划（MILP）的精确算法milpflow和适用于较大问题规模的基于生成树切割进化的近似算法STED。其中,milpflow是学术界第一个解决均衡连通q-分割的精确（exact）算法,且其在2-分割上,能比现存的MILP多解决100个区域的任务指派(问题空间增大了2100倍);STED,也是学界第一个针对一般图的q-分割的近似算法,它能解决规模至3000个区域的分割问题,是已有算法能解决规模的10倍,并且它能通过进化几千个生成树个体,就能获得非常近似于理想最优值的解。（2）已知环境但未知机器人数目,而完成时间具有截止时限的情形下,一种优化机器人数目并给出具体分配方案的任务分配算法。本研究根据截止时限,预先计算出所需机器人数目的较紧的上下界b和a。不同于枚举机器人数目并优化对应数目的（近似）最优方案的传统算法,本研究提出了一个基于遗传算法的多目标优化算法,它能求得（近似）最少的机器人数目,并能给出机器人数目在范围[a,b]内的所有（近似）最优分配方案。实验结果显示,算法求出来的最小机器人数目是现存算法的0.6倍。该多目标转化方法具有较优秀的普适性,因此也被扩展应用到机器人拓扑覆盖任务分配等其它问题上,实验结果展现了求解的有效性和高效性。（3）非确定性环境情形下,一种基于强化学习的均衡任务分配算法。强化学习通过马尔可夫决策过程（MDP）建模,在全覆盖问题中能处理确定性环境的规划问题和非确定性环境下的学习问题,因此强化学习未来是迈向动态未知环境中全覆盖问题的一条可行途径。本研究将多机器人的均衡任务分配过程(状态空间达到236*36!≈1050)建模成MDP,并使用深度Q网络学习算法（即DQN算法）进行任务分配。实验结果表明,DQN算法在该问题上,通过部分的样本学习（样本数约108）,就能获得比常用的启发式算法更优越的解,并且能够优化未训练过的样本,展示出了良好的解的精度和泛化性能。在非确定性环境中,实验结果显示,该强化学习算法对大多数环境配置的平均步数是常用启发式最优步数的一半左右,并且强化学习算法与已知环境模型时的常用启发式结果相近,展示出了良好的对环境的学习能力。以上三部分工作共同服务于全覆盖任务分配,但关注了不同的情形,因此三部分内容是并列之关系。在每一部分内容中,都包含了一至两个具体研究点,形成了较完整的技术体系,适用于同构多机器人在二维环境中全覆盖问题的任务分配问题。
彭欣炜[5]（2019）在《微控制器硬件环境下的静态资源任务分配问题求解方法研究》文中研究指明随着人工智能的发展,自主智能设备将是未来应用领域的重要产品,其中的重要能力之一是能够自主优化地把有限的资源分配给既定的任务,以取得最大的工作效果。针对一些自主智能产品小型化、难以携带常规计算机的特点,本文研究微控制器硬件环境下静态资源任务分配问题的求解算法本文针对广告投放问题与工程应用中的两类需求,分别建立了两类静态资源任务分配问题模型。通过微控制器性能与应用领域的调研,采用一款主流微控制器作为算法的求解计算机,设计了三类改进求解算法,并选取两类国际标准算例集对各类算法进行测试,最后根据当前文献最优解做改进效果的对比,验证了改进方法的有效性与实用性本文的研究成果包括（1）提出了基于直接枚举算法改进的剪枝枚举算法,通过分部枚举与松弛贪婪上界的方式改进直接枚举算法,结果表明该算法适用于小规模问题的精确求解（2）提出了基于贪婪求解算法改进的贪婪交换算法,将贪婪解与循环交换算法结合,并对比了两层循环交换与三层循环交换的求解效果,结果表明该算法适用于实时性要求高的较大规模问题近似最优求解（3）提出了基于模拟退火的贪婪交换算法,在贪婪求解的交换改进算法基础上做了模拟退火改进。加入模拟退火决策能进一步提升贪婪交换算法的求解效果,结果表明该算法适用于实时性要求低而精确度要求高的近似最优问题求解（4）运用三类改进求解算法针对广告投放问题的具体应用做了分配方案的求解,分析结果表明,三类改进求解算法分别适用于具体工程应用中不同规模的场合。本文提出的求解方法能很好地应用于微控制器求解情况下的资源任务分配问题,测试覆盖了国际标准测试集中所有规模的算例,可根据规模来选择这类硬件条件下适用的求解算法。改进算法在求解各类规模静态资源任务分配问题的精确解和近似最优解时具有一定优势,对微控制器硬件环境下的资源任务分配问题求解方法研究具备很好的参考价值。
明月伟[6]（2018）在《可扩展机器学习关键技术研究》文中进行了进一步梳理近年来,数据量的激增迫切需要对可扩展机器学习关键技术的研究,而当前丰富的计算资源又为可扩展机器学习提供了机遇。为实现可扩展机器学习,本文从高效算法设计和并行与分布方法两条技术途径入手,对机器学习如何有效应对大数据挑战展开深入研究。基于算法与系统的协同设计,在保证精度的前提下,有效提高了机器学习的速度,增强了机器学习在计算和内存方面的扩展性,取得了以下几个方面的研究成果:1.提出了两种数据和模型并行极限学习机,即LDMP-ELM和GDMP-ELM。LDMP-ELM运行更快且更易实现,而GDMP-ELM能够支持更大模型,二者优势互补,统称为DMP-ELMs。DMP-ELMs因解决了现有方法中存在的计算和内存瓶颈而具有更好的可扩展性,能够处理大规模数据集、支持大量隐层节点。这得益于DMP-ELMs同时使用数据并行和模型并行方法来提高ELM的并行性,主要是利用矩阵分块与分布矩阵计算实现,并充分利用了ELM随机生成隐层参数的特性。DMP-ELMs完全基于超级计算机的软件栈,如MPI等进行开发。在实验中我们将算法成功扩展到128个节点,能有效处理数据和模型大到无法载入单机内存的情况。尽我们所知,这是第一次成功地在有着810万个样本和784维特征的mnist8m数据集上训练出一个具有5万个隐层神经元的大ELM模型。目前多数并行与分布机器学习研究集中于商用计算集群,基于超算系统的研究还较少,该工作是完全基于超算软硬件系统进行并行与分布机器学习的一项探索研究。2.提出了一种基于方差缩减的分布异步随机梯度下降方法,即DisSVRG。DisSVRG将方差缩减技术和异步通信协议有机结合,采用方差缩减梯度更新模型参数,并使用异步通信协议在集群节点间共享新学到的参数。另外,我们提出带有加速因子的自适应学习率,加速DisSVRG。同时,提出一种自适应采样策略,大大减少了迭代过程中由straggler问题引起的等待。另一方面,在发现超算软件栈进行并行与分布机器学习研究抽象层次过低的问题后,我们使用兴起于商用计算集群的参数服务器计算框架,将其迁移到超算生态圈,而参数服务器底层又使用MPI通信,这样两种计算框架得以融合。实质上参数服务器此时可看作是在MPI基础上又进行了一层封装,提供适于机器学习的抽象层次更高且更简洁的编程模型。而通过对参数服务器的分析、使用、再开发,极大简化了DisSVRG的实现。3.提出了两种分布可扩展的k-means聚类方法,即Scalable Lloyd’s K-Means和Scalable Mini-Batch K-Means。两者都能基于数据并行技术和参数服务器系统扩展超越单节点的计算和内存限制。前者能够找到更高质量的解,而后者能够更快收敛到一个合适的解。它们都具有良好的可扩展性并完全进行内存计算。此外,我们为Scalable Mini-Batch K-Means提出了一个新的聚合方法使得分布聚类能够收敛。大量实验表明我们提出的算法具有良好的收敛性能并能达到几乎线性的加速比,例如使用分布在4个计算节点上的16个CPU核进行计算时,可以达到14倍左右的加速比。在此项研究中,我们将前述研究的并行与分布随机梯度下降优化算法用于求解k-means聚类问题,仍然在超算系统中基于参数服务器实现,进一步证明了这种软件栈融合的通用性。4.提出了两种基于方差缩减的k-means聚类方法,即VRKM和VRKM++。具体来说,我们首先提出了一种位置校正机制来校正在基于方差缩减优化k-means问题时的聚类中心漂移问题,并使用常数学习率来更新k-means中的参数。在此基础上,我们提出了方差缩减k-means,即VRKM。进一步,我们通过理论推导优化VRKM,降低其计算成本,进而提出一种新的方差缩减k-means,即VRKM++。与VRKM相比,VRKM++可以避免计算批量梯度,减少计算量,因而效率更高。两种方法都在超算系统的单节点上串行实现。大量实验表明,我们提出的VRKM和VRKM++方法性能优于当前水平,并分别获得大约2倍和4倍的大规模聚类加速。在本项工作中,我们从高效算法设计角度入手,在不占用更多计算资源的情况下,增加k-means聚类的可扩展性。5.提出了一种基于局部敏感哈希的近似k-means方法,即LSH k-means。其在样本点上建立局部敏感哈希（Locality-Sensitive Hashing,LSH）索引,而不是在聚类中心上建立索引。具体而言,LSH k-means首先建立LSH哈希表,使得相互靠近的样本点有更大可能被哈希到相同的桶中。然后将聚类中心作为查询,从LSH表中查询其潜在近邻样本点。之后LSH k-means引入一个指示矩阵,其能将聚类中心的潜在近邻样本点转换为样本点的潜在近邻聚类中心。最后,各样本点可以在指示矩阵的引导下不用与所有聚类中心计算距离就能找到其最近聚类中心。此外,我们提出了一个自动调参策略,在构建于指示矩阵的两个指标的帮助下自动地确定LSH k-means的超参数。在三个数据集上进行的大量实验表明我们所提算法具有良好的收敛性能并实现了显着的加速。该项工作在工作站上串行实现,继续从高效算法设计角度入手,研究低资源占用高可扩展的方法。
龚涛[7]（2018）在《基于外包服务的调度策略与优化算法》文中进行了进一步梳理制造业作为我国的支柱产业,近三十年得到了快速发展,但同时也面临了许多突出的问题。一方面现如今全球信息技术快速发展,产品的易模仿性逐渐降低,产品的生命周期越来越短,企业必须不断加快生产速度,才能保持市场的竞争力。据调查数据统计,产品在其生产工期中等待被加工的时间和运输的时间大致占总工期的85%,因此制定一个有效的生产调度策略对于优化企业生产流程至关重要。另一方面,现如今顾客需求愈加多样化,从而导致企业的生产环节愈加繁多和复杂,企业若采用纵向一体化的生产模式不可避免会产生资源浪费和成本上涨的问题,因此部分企业选择了业务外包作为其拓展内部产能的一种有效方式。基于制造业中这些现实的生产问题,我们建立合理的生产调度模型并为其设计优化算法,从理论研究的角度和现实的角度都具有重要的意义。本文首先对生产调度问题的研究背景和意义做了介绍,从生产调度问题的提出到如今一些热门的研究课题和研究方法,我们对国内外一些主要的生产调度相关文献做了总结。其次本文结合企业实际的生产情况,研究了工作可外包的生产调度问题。首先针对企业的内部生产情况,我们提出了两个工作加工时间依赖位置变化的统一调度新模型,这两个模型首次将学习效应和老化效应融入到了同一模型中。然后基于这两个统一调度新模型提出了两类考虑工作可外包的生产调度模型,即选择单一外包商的调度模型和选择多外包商的调度模型。第一类模型适用于中小型企业,其希望在外包过程中获得规模经济,往往选择与固定的单一外包商合作,从而有效降低成本。第二类模型适用于大型企业,其生产过程有知识资产专用性,选择与单一外包商合作,往往会面临较大的机会主义行为危险,所以往往与多个外包商合作。接着针对以上两类模型,我们分别研究了多台机环境下极小化最大完工期与外包成本和,以及极小化完成时间和与外包成本和的问题。针对每个问题,我们需要作出的决策包括外包工作的选择,外包工作的生产调度方案以及内部加工生产调度方案。首先我们对每个问题的复杂度进行分析,主要将问题划分为P问题和NP-难问题两类,针对前一类问题,我们给出了多项式算法解决,对于后一类问题我们设计了完全多项式时间近似算法（FPTAS）,并证明了算法的近似性和可行性。最后我们针对文章所有设计的算法进行算例分析,首先我们利用MATLAB工具对算法进行程序实现,对于设计思路与程序较相似的问题,只选取一个模型进行举例分析。我们对设计的FPTAS算法进行了数据实验分析进而也从实践的角度验证了其可行性与有效性。
魏凤生[8]（2016）在《认知网络中继节点选择与信道分配算法研究》文中研究指明认知无线电被认为是缓解无线频谱资源稀缺问题的一个行之有效的技术,在认知无线电上发展而来的认知网络,是目前的研究热点。本文针对认知网络的中继选择与信道分配问题进行了研究,通过将该问题建模为一个三维指派问题,并使用拉格朗日松弛与次梯度算法给出了求解近似最优值的方法,进而得出了求解多源节点下的联合中继选择与信道分配问题的JRSCA（Joint Relay Selection and Channel Allocation,JRSCA）算法;在信道少于信源的场景中,为了兼顾网络的公平性,将JRSCA算法进行了适当的扩展,提出了解决一类变权二维指派问题的算法,并用该算法替换JRSCA算法中调用的Kuhn-Munkres算法,最终得到了能够保证认知网络公平性的FJRSCA（Fair Joint Relay Selection and Channel Allocation,FJRSCA）算法;考虑到功率分配能够大幅提升系统的吞吐量,因此本文研究了在认知网络中只有单源节点需要传输数据时的中继、信道、功率联合分配问题,给出了解决此问题的SJRCP（Single source Joint Relay,Channel and Power allocation,SJRCP）算法;另外,在得出SJRCP算法的过程中,本文给出了解决一类凸优化问题的一个算法,该算法可以有效地解决SJRCP中的功率分配问题以及其他类似的多载波优化问题。与内点法相比,该算法的运行时间与迭代次数均不受问题规模的影响。仿真结果表明,JRSCA算法、FJRSCA算法以及SJRCP算法均优于已知的同类算法:在多源节点的认知网络中,与目前已知的同类算法GRC（Greedy based Relay selection and Channel allocation,GRC）算法相比,JRSCA算法可以提高10%左右的吞吐量;当认知网络中信道数少于信源时,FJRSCA算法不但能在吞吐量上超出GRC算法约5%,而且可以达到比GRC算法更好的公平性;在单源节点的认知网络中,使用SJRCP算法获得的吞吐量优于已知的同类算法约10%左右。
夏小云[9]（2015）在《随机启发式搜索算法的性能分析》文中进行了进一步梳理随机启发式搜索算法如演化算法、蚁群算法及人工免疫算法等是通过模拟大自然现象、过程及一些生物特性等提出的一类通用算法。实践证明,这类随机启发式搜索算法在科学研究及工程实际问题中获得了极大的成功,尤其是针对一些结构不清晰的复杂优化问题,以及在计算资源有限的情况下表现出了卓越的性能。为了更好的理解随机启发式搜索算法的工作机制,进一步指导算法设计及应用,研究人员迫切希望为这类算法建立严密的理论基础。然而,由于随机启发式搜索算法的随机性、群体性等特点,使得算法在运行过程中表现出非常复杂的动态随机行为,增加了理论研究的难度。当前,理论研究成果相对偏少。本文从随机启发式搜索算法的理论研究角度出发,关注随机启发式搜索算法求解优化问题的时间复杂性,以及在NP-完全（难）优化问题上的近似性能;研究问题类型与算法特征之间的关系;进一步探索随机启发式搜索算法求解典型优化问题的有效性,以期完善和增强随机启发式搜索算法的理论基础。本文的主要工作如下:（1）研究了演化算法求解最多叶子生成树问题（MLST）的性能。最多叶子生成树问题是NP完全理论中一个经典的组合优化问题,在网络设计及电路布局等实际问题上有较强的应用背景。该问题是在一个无向连通图中找出一棵生成树,使得生成树中所含叶子节点最多。许多启发式算法如演化算法用于求解该问题。然而,对于演化算法在NP难问题的求解性能方面我们仍知之甚少。本文从理论上研究了演化算法求解MLST问题的近似性能。指出对于MLST问题,算法（1+1）EA能够分别在期望多项式时间2O（nm）和4O（nm）内获得5近似比和3近似比,其中n为无向连通图中的节点数,m为边数。同时,我们研究了（1+1）EA算法在两个MLST问题实例上的性能,并且指出局部搜索算法在该实例上容易陷入局部最优,而（1+1）EA算法能够逃脱局部最优并最终获得最优解。（2）研究了蚁群算法在二次指派问题（QAP）上的性能。二次指派问题是最具挑战性的组合优化问题之一。该问题在物流运输和选址等许多实际问题中有着广泛的应用。理论上研究了ACO算法在极其难的QAP问题上的性能。给出了一个简单的（1+1）MMAA算法在QAP问题上的最坏情况界。并指出对于QAP问题,（1+1）MMAA算法能够获得一定的近似保证。最后,通过构建一个QAP实例,表明蚁群优化算法在该实例上要优于2-exchange局部搜索算法,进一步证实了蚁群算法的有效性。（3）分析比较了基于免疫的超变异算子与标准位变异算子在优化问题上的性能。人工免疫系统在许多复杂的真实优化问题中获得了广泛的应用并取得了极大成功。然而,人工免疫算法的理论研究远远滞后于其在许多领域的应用研究。对于人工免疫算法的运行机制以及其有效性研究还处于探索的初级阶段,当前也迫切需要为这类算法建立坚实的理论基础。本文从理论上分析了一种被用于免疫算法中的连续高频变异算子在优化问题上的性能,并在两个拟布尔函数及两个真实组合优化问题的实例上分析比较了连续高频变异算子与标准位变异算子、局部变异算子的性能,证明了连续高频变异算子在这些实例上要优于标准位变异算子及局部变异算子。也进一步揭示了问题类型与算法特征之间的关系,从理论上证实了连续高频变异算子的有效性。
王竹芳,潘雪[10]（2015）在《一种求解指派问题的进步算法》文中进行了进一步梳理通过对运筹学中的两类经典问题:指派问题和最短路问题的对比分析,发现并证明了两者之间存在一定的联系,并试着借用这种联系用解最短路的解法解决指派问题,最终证明了这种进步算法的有效性和效率性。
二、求解指派问题的一个算法（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、求解指派问题的一个算法（论文提纲范文）
（1）一些网络排序和路径优化问题的算法设计与性能分析（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 组合优化问题 |
| 1.2 算法和复杂性 |
| 1.3 NP完备性理论 |
| 1.4 背景知识及问题简介 |
| 1.4.1 背景知识 |
| 1.4.2 问题简介 |
| 1.5 文献综述 |
| 1.5.1 车辆路径规划问题 |
| 1.5.2 VSP问题及对应的VRP问题 |
| 1.5.3 CVRP问题 |
| 1.5.4 k-配送问题 |
| 1.6 论文概述 |
| 第2章 树形网络和环形网络上的网络排序问题 |
| 2.1 引言 |
| 2.2 问题描述和符号介绍 |
| 2.3 树形网络上的单机网络排序问题 |
| 2.3.1 返回型T-SVSP问题 |
| 2.3.2 不返回型T-SVSP问题 |
| 2.4 环形网络上的单机网络排序问题 |
| 2.4.1 返回型C-SVSP问题 |
| 2.4.2 不返回型C-SVSP问题 |
| 2.5 本章小结 |
| 第3章 最小化总行程的CVRP问题 |
| 3.1 引言 |
| 3.2 最小化总行程的UL-CVRP问题 |
| 3.2.1 问题描述及符号介绍 |
| 3.2.2 标准实例和实例标准化 |
| 3.2.3 准备工作 |
| 3.2.4 5/3-近似算法 |
| 3.3 最小化总行程的SC-CVRP问题 |
| 3.3.1 问题描述及符号介绍 |
| 3.3.2 最优解的性质 |
| 3.3.3 O(nC)的最优算法 |
| 3.4 本章小结 |
| 第4章 最小化最大行程的CVRP问题 |
| 4.1 引言 |
| 4.2 最小化最大行程的UL-CVRP问题 |
| 4.2.1 问题描述及近似比下界 |
| 4.2.2 2-近似算法 |
| 4.3 最小化最大行程的SC-CVRP问题 |
| 4.4 本章小结 |
| 第5章 2-配送问题 |
| 5.1 引言 |
| 5.2 问题描述 |
| 5.3 树形网络上的2-配送问题 |
| 5.4 一般网络上的2-配送问题 |
| 5.5 本章小结 |
| 第6章 结论与展望 |
| 参考文献 |
| 致谢 |
| 附录: 博士在读期间完成的论文 |
（2）基于效率提升的单机多任务调度相关问题研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景和意义 |
| 1.2 国内外研究现状 |
| 1.2.1 关于多任务及效率提升现象的国内外研究现状 |
| 1.2.2 关于学习/恶化效应的国内外研究现状 |
| 1.2.3 关于资源分配问题的国内外研究现状 |
| 1.2.4 关于交货时间窗的国内外研究现状 |
| 1.3 本文主要研究工作 |
| 1.4 本文的组织结构 |
| 1.4.1 结构安排 |
| 1.4.2 研究框架 |
| 第2章 基本理论 |
| 2.1 组合优化问题概述 |
| 2.2 算法及复杂度理论 |
| 2.2.1 算法概述及应用 |
| 2.2.2 算法复杂度理论 |
| 2.3 调度问题 |
| 2.3.1 概述 |
| 2.3.2 三参数表示法 |
| 2.3.3 调度问题求解 |
| 2.4 本文主要算法和工具 |
| 2.4.1 指派问题的模型介绍 |
| 2.4.2 匈牙利算法 |
| 2.4.3 实例解析 |
| 2.4.4 Lingo工具 |
| 2.5 本章小结 |
| 第3章 带有效率提升效应的多任务调度新模型 |
| 3.1 本章研究内容 |
| 3.2 符号说明 |
| 3.3 经典多任务模型及带有效率提升效应的多任务模型描述 |
| 3.3.1 经典多任务模型 |
| 3.3.2 带有效率提升效应的多任务模型描述 |
| 3.4 具有线性效率提升效应的多任务调度新模型 |
| 3.4.1 极小化制造期 |
| 3.4.2 极小化总完工时间 |
| 3.4.3 极小化完工时间差的绝对值之和 |
| 3.5 本章小结 |
| 第4章 分别考虑具有恶化、资源及松弛交货时间窗的多任务调度问题 |
| 4.1 本章研究内容 |
| 4.2 符号说明 |
| 4.3 加工时间与位置相关的多任务调度新模型 |
| 4.3.1 模型描述 |
| 4.3.2 极小化制造期 |
| 4.3.3 极小化总完工时间 |
| 4.4 加工时间依赖于资源分配的多任务调度新模型 |
| 4.4.1 模型描述 |
| 4.4.2 极小化制造期与线性资源分配问题 |
| 4.4.3 极小化制造期与凸资源分配问题 |
| 4.5 具有松弛交货期时间窗口的多任务调度新模型 |
| 4.5.1 模型描述 |
| 4.5.2 初步分析与结论 |
| 4.5.3 问题求解 |
| 4.5.3.1 一般性问题 |
| 4.5.3.2 特殊性问题 |
| 4.6 本章小结 |
| 第5章 融合考虑具有恶化、资源及松弛交货时间窗的多任务调度问题 |
| 5.1 本章研究内容 |
| 5.2 符号说明 |
| 5.3 模型描述 |
| 5.4 最优算法 |
| 5.4.1 线性资源分配的多任务调度模型 |
| 5.4.2 凸资源分配的多任务调度模型 |
| 5.5 本章小结 |
| 第6章 算例分析 |
| 6.1 算例介绍 |
| 6.2 算例求解 |
| 6.2.1 基于恶化效应和线性资源分配的松弛交货时间窗模型求解 |
| 6.2.2 基于恶化效应和凸资源分配的松弛交货时间窗模型求解 |
| 6.3 本章小结 |
| 第7章 总结与展望 |
| 7.1 研究工作总结 |
| 7.2 研究工作展望 |
| 参考文献 |
| 附录1 攻读硕士学位期间完成的论文 |
| 附录2 攻读硕士学位期间参加的项目 |
| 后记 |
（3）多约束条件下多目标双边装配线再平衡方法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 研究现状及分析 |
| 1.2.1 双边装配线平衡问题研究现状 |
| 1.2.2 双边装配线再平衡问题研究现状 |
| 1.2.3 现有研究不足 |
| 1.3 论文组织结构及主要研究内容 |
| 第二章 双边装配线任务再分配策略研究 |
| 2.1 引言 |
| 2.2 问题描述及数学模型 |
| 2.3 任务移动关联效应 |
| 2.4 吸入式策略 |
| 2.4.1 基于任务吸入式策略的启发式规则设计 |
| 2.4.2 基于任务吸入式策略的启发式改进 |
| 2.5 任务推入式策略 |
| 2.5.1 基于任务推入式策略的启发式规则设计 |
| 2.5.2 基于任务推入式策略的启发式改进 |
| 2.6 单工作站策略 |
| 2.7 算法验证与结果分析 |
| 2.7.1 标准案例及参数设定 |
| 2.7.2 标准案例结果分析 |
| 2.7.3 工程案例结果分析 |
| 2.8 本章小结 |
| 第三章 工艺变化下双边装配线再平衡方法研究 |
| 3.1 引言 |
| 3.2 工艺变化问题描述 |
| 3.3 数学建模 |
| 3.3.1 改进再平衡成本计算方法 |
| 3.3.2 工位内空闲时间控制约束 |
| 3.4 改进的多目标遗传算法 |
| 3.4.1 编码与解码 |
| 3.4.2 种群初始化 |
| 3.4.3 交叉操作 |
| 3.4.4 变异操作 |
| 3.4.5 选择操作与精英策略中的改进设计 |
| 3.4.6 算法整体流程 |
| 3.5 算法性能验证与分析 |
| 3.5.1 算法参数设计 |
| 3.5.2 算法性能验证 |
| 3.6 工程案例验证分析 |
| 3.6.1 求解质量分析 |
| 3.6.2 算法改进策略有效性分析 |
| 3.6.3 解码有效性分析 |
| 3.7 本章小结 |
| 第四章 任务再分配受限的双边装配线再平衡方法研究 |
| 4.1 引言 |
| 4.2 任务再分配受限问题描述及数学建模 |
| 4.3 改进的帝国竞争算法 |
| 4.3.1 算法中解的表达 |
| 4.3.2 算法初始化 |
| 4.3.3 帝国内同化 |
| 4.3.4 形成新的国家种群并更新帝国 |
| 4.3.5 帝国间竞争 |
| 4.3.6 算法终止条件 |
| 4.4 算法性能验证 |
| 4.5 数值实验 |
| 4.5.1 算法参数设计 |
| 4.5.2 算法框架有效性分析 |
| 4.5.3 同化方法有效性分析 |
| 4.5.4 解码方法有效性分析 |
| 4.5.5 模型有效性分析 |
| 4.5.6 工程案例验证分析 |
| 4.6 本章小结 |
| 第五章 时空约束下双边装配线再平衡方法研究 |
| 5.1 引言 |
| 5.2 时空约束下双边装配线再平衡问题 |
| 5.2.1 装配线再平衡系统数据模型 |
| 5.2.2 装配任务数据模型 |
| 5.2.3 数据与物理空间关联 |
| 5.2.4 问题数学模型 |
| 5.3 算法设计 |
| 5.3.1 算法初始化 |
| 5.3.2 解码 |
| 5.3.3 同化 |
| 5.4 空间参数设置 |
| 5.5 问题求解与分析 |
| 5.5.1 求解质量分析 |
| 5.5.2 算法性能稳定性分析 |
| 5.5.3 算法改进设计有效性分析 |
| 5.5.4 工程案例验证分析 |
| 5.6 本章小结 |
| 第六章 总结与展望 |
| 6.1 论文主要研究工作总结 |
| 6.2 论文创新点 |
| 6.3 未来工作展望 |
| 参考文献 |
| 符号与标记(附录 A) |
| 工程案例信息(附录 B) |
| Pareto 最优解集及其评价指标(附录 C) |
| 致谢 |
| 攻读博士学位期间学术成果 |
| 攻读博士学位期间参与的科研项目 |
（4）多机器人全覆盖问题的任务分配算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 研究背景和意义 |
| 1.1.1 全覆盖问题 |
| 1.1.2 多机器人全覆盖问题 |
| 1.1.3 多机器人任务分配 |
| 1.2 本文主要工作 |
| 1.2.1 本文主要研究内容 |
| 1.2.2 主要结果与贡献 |
| 1.3 本文组织架构 |
| 第二章 预备知识 |
| 2.1 机器人全覆盖问题的概况 |
| 2.2 数学规划 |
| 2.3 遗传算法 |
| 2.4 多目标优化 |
| 2.5 强化学习 |
| 2.6 小结 |
| 第三章 机器人数目恒定的全覆盖任务分配算法 |
| 3.1 问题描述与建模 |
| 3.2 相关工作 |
| 3.3 精确算法 |
| 3.3.1 思路原理 |
| 3.3.2 顶点标记 |
| 3.3.3 流量模型 |
| 3.4 近似算法 |
| 3.4.1 思路原理 |
| 3.4.2 算法 |
| 3.5 实验对比与讨论 |
| 3.5.1 milpflow的结果 |
| 3.5.2 STED的结果 |
| 3.5.3 集成应用 |
| 3.6 小结 |
| 第四章 带时限的最优机器人数目任务分配算法 |
| 4.1 问题描述和相关工作 |
| 4.2 多目标的方法 |
| 4.2.1 时间限制版本CCP的形式化 |
| 4.2.2 机器人数目的界 |
| 4.2.3 多目标的转化式 |
| 4.3 Mofint算法 |
| 4.3.1 编码 |
| 4.3.2 两个优化目标 |
| 4.3.3 初始化 |
| 4.3.4 交叉算子 |
| 4.3.5 变异算子 |
| 4.3.6 协同进化适应度值 |
| 4.3.7 算法伪代码 |
| 4.4 数值结果 |
| 4.4.1 小示例结果 |
| 4.4.2 数据集 |
| 4.4.3 实验对比与讨论 |
| 4.5 Mucard的进一步研究与扩展应用 |
| 4.5.1 扩展应用到多机器人拓扑覆盖评估问题 |
| 4.5.2 扩展应用到3-目标优化问题 |
| 4.6 小结 |
| 第五章 非确定性环境下基于强化学习的均衡任务分配算法 |
| 5.1 问题 |
| 5.2 相关工作 |
| 5.3 问题的数学建模与算法实现 |
| 5.4 实验与讨论 |
| 5.4.1 算法 |
| 5.4.2 参数的设置 |
| 5.4.3 确定性环境结果与讨论 |
| 5.4.4 非确定性环境结果与讨论 |
| 5.5 小结 |
| 第六章 总结和展望 |
| 6.1 总结 |
| 6.2 下一步研究展望 |
| 致谢 |
| 参考文献 |
| 作者在学期间取得的学术成果 |
（5）微控制器硬件环境下的静态资源任务分配问题求解方法研究（论文提纲范文）
| 致谢 |
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 研究背景及意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.2.1 应用研究 |
| 1.2.2 算法研究 |
| 1.2.3 研究现状总结 |
| 1.3 论文内容与章节结构 |
| 2 相关概念及技术准备 |
| 2.1 静态资源任务分配问题的描述与数学建模 |
| 2.2 微控制器的选型与求解算法指标 |
| 2.3 微控制器硬件环境下的求解方法可行性分析 |
| 2.4 本章小结 |
| 3 微控制器硬件环境下的精确求解方法研究 |
| 3.1 直接枚举求解算法设计 |
| 3.1.1 直接枚举算法步骤 |
| 3.1.2 标准算例集说明 |
| 3.1.3 标准算例集测试 |
| 3.2 贪婪求解算法设计 |
| 3.2.1 当前加权任务剩余率 |
| 3.2.2 贪婪求解算法步骤 |
| 3.2.3 标准算例集测试 |
| 3.3 基于剪枝的枚举算法改进设计 |
| 3.3.1 分部枚举策略 |
| 3.3.2 松弛上界值的贪婪寻优过程 |
| 3.3.3 标准算例集测试 |
| 3.4 求解方法效果的总体对比 |
| 3.5 本章小节 |
| 4 微控制器硬件环境下的启发求解方法研究 |
| 4.1 基于贪婪求解的交换改进算法设计 |
| 4.1.1 基于贪婪求解的多次交换策略 |
| 4.1.2 标准算例集测试 |
| 4.2 基于模拟退火的贪婪交换算法设计 |
| 4.2.1 模拟退火策略 |
| 4.2.2 基于模拟退火算法的改进流程 |
| 4.2.3 标准算例集测试 |
| 4.3 实例分析与总体效果对比 |
| 4.3.1 分配方案举例与分析 |
| 4.3.2 求解时间对比 |
| 4.3.3 求解目标函数值相对误差对比 |
| 4.4 本章小节 |
| 5 总结与展望 |
| 5.1 全文总结 |
| 5.2 研究展望 |
| 参考文献 |
| 附录A |
| 作者简历及攻读硕士学位期间取得的研究成果 |
| 学位论文数据集 |
（6）可扩展机器学习关键技术研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.1.1 大数据推动可扩展机器学习研究 |
| 1.1.2 丰富的计算资源为可扩展机器学习提供机遇 |
| 1.1.3 可扩展机器学习研究面临的挑战 |
| 1.2 研究现状 |
| 1.2.1 高效机器学习算法设计 |
| 1.2.2 并行与分布机器学习 |
| 1.2.3 面向机器学习的计算框架 |
| 1.3 研究内容 |
| 1.3.1 本文主要工作 |
| 1.3.2 本文主要创新点 |
| 1.4 论文结构 |
| 第二章 面向大规模学习任务的数据和模型并行极限学习机 |
| 2.1 引言 |
| 2.2 相关工作 |
| 2.2.1 极限学习机 |
| 2.2.2 并行ELM |
| 2.3 数据和模型并行极限学习机 |
| 2.3.1 LDMP-ELM方法 |
| 2.3.2 GDMP-ELM方法 |
| 2.4 实验结果与分析 |
| 2.4.1 数据集和实验环境 |
| 2.4.2 时间性能 |
| 2.4.3 可扩展性 |
| 2.4.4 准确率 |
| 2.4.5 两种方法对比分析 |
| 2.5 本章小结 |
| 第三章 基于方差缩减的分布异步随机梯度下降方法 |
| 3.1 引言 |
| 3.2 相关工作 |
| 3.3 预备知识 |
| 3.3.1 参数服务器和数据并行 |
| 3.3.2 方差缩减SGD |
| 3.4 Dis SVRG算法及系统实现 |
| 3.4.1 Dis SVRG总体描述 |
| 3.4.2 Dis SVRG分布实现 |
| 3.5 Dis SVRG的优化 |
| 3.5.1 带有加速因子的学习率 |
| 3.5.2 自适应采样策略 |
| 3.6 Dis SVRG的优势 |
| 3.7 实验结果与分析 |
| 3.7.1 收敛性 |
| 3.7.2 加速比 |
| 3.7.3 等待时间 |
| 3.8 本章小结 |
| 第四章 面向大规模聚类的分布可扩展K-Means方法 |
| 4.1 引言 |
| 4.2 预备知识 |
| 4.2.1 K-Means聚类 |
| 4.2.2 Mini-Batch K-Means |
| 4.3 分布可扩展K-Means算法 |
| 4.3.1 Scalable Lloyd’s K-Means算法 |
| 4.3.2 Scalable Mini-Batch K-Means算法 |
| 4.4 实验结果与分析 |
| 4.4.1 数据集和实验环境 |
| 4.4.2 实现细节 |
| 4.4.3 收敛性能 |
| 4.4.4 加速比 |
| 4.5 本章小结 |
| 第五章 基于方差缩减的大规模K-Means聚类方法 |
| 5.1 引言 |
| 5.2 相关工作 |
| 5.3 预备知识 |
| 5.3.1 数据结构和基本定义 |
| 5.3.2 K-Means的优化视角 |
| 5.3.3 SVRG:基于方差缩减技术的SGD |
| 5.4 方差缩减K-Means聚类 |
| 5.4.1 位置校正 |
| 5.4.2 常数学习率 |
| 5.5 方差缩减K-Means的优化 |
| 5.5.1 VRKM++:不带批量梯度的VRKM |
| 5.5.2 参数设置 |
| 5.6 实验结果与分析 |
| 5.6.1 收敛性能 |
| 5.6.2 聚类性能 |
| 5.7 本章小结 |
| 第六章 基于局部敏感哈希的K-Means聚类方法 |
| 6.1 引言 |
| 6.2 相关工作 |
| 6.2.1 FLANN K-Means |
| 6.2.2 局部敏感哈希 |
| 6.3 LSH K-Means方法 |
| 6.3.1 LSH K-Means算法流程 |
| 6.3.2 自动调参 |
| 6.3.3 LSH K-Means与 FLANN K-Means对比 |
| 6.4 实验结果与分析 |
| 6.4.1 数据集与环境 |
| 6.4.2 实验设置 |
| 6.4.3 收敛性能和加速比 |
| 6.4.4 可扩展性 |
| 6.4.5 参数调节分析 |
| 6.4.6 聚类性能 |
| 6.5 本章小结 |
| 第七章 结论与展望 |
| 7.1 工作总结 |
| 7.2 研究展望 |
| 致谢 |
| 参考文献 |
| 作者在学期间取得的学术成果 |
（7）基于外包服务的调度策略与优化算法（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.3 本文主要研究工作 |
| 1.4 本文组织架构 |
| 第2章 基本理论介绍 |
| 2.1 组合优化问题概述 |
| 2.2 算法 |
| 2.2.1 概述及算法应用 |
| 2.2.2 计算复杂度理论 |
| 2.3 调度问题 |
| 2.3.1 概述 |
| 2.3.2 三参数表示法 |
| 2.3.3 调度问题求解 |
| 2.4 本文主要算法和工具 |
| 2.4.1 近似算法 |
| 2.4.2 指派问题 |
| 2.4.3 MATLAB工具 |
| 2.5 本章小结 |
| 第3章 加工时间依赖位置变化的统一调度新模型 |
| 3.1 本章研究内容 |
| 3.2 符号说明 |
| 3.3 模型描述 |
| 3.4 极小化最大完工期 |
| 3.5 极小化完成时间和 |
| 3.6 本章小结 |
| 第4章 基于单外包商的生产调度问题 |
| 4.1 本章研究内容 |
| 4.2 符号说明 |
| 4.3 问题描述 |
| 4.4 前期研究成果 |
| 4.5 极小化最大完工期和外包成本加权和 |
| 4.5.1 基于指数函数型生产调度问题 |
| 4.5.2 基于Pegels'函数型生产调度问题 |
| 4.6 极小化完工时间和与外包成本加权和 |
| 4.6.1 基于指数函数型生产调度问题 |
| 4.6.2 基于Pegels'函数型生产调度问题 |
| 4.7 本章小结 |
| 第5章 基于多外包商的生产调度问题 |
| 5.1 本章研究内容 |
| 5.2 符号说明 |
| 5.3 问题描述 |
| 5.4 极小化最大完工期与外包成本加权和 |
| 5.4.1 基于指数函数型生产调度问题 |
| 5.4.2 基于Pegels'函数型生产调度问题 |
| 5.5 极小化完成时间和与外包成本加权和 |
| 5.5.1 基于指数函数型生产调度问题 |
| 5.5.2 基于Pegels'函数型生产调度问题 |
| 5.6 本章小结 |
| 第6章 实验分析 |
| 6.1 引言 |
| 6.2 FPTAS实验分析 |
| 6.2.1 算法实现 |
| 6.2.2 算例分析 |
| 6.3 多项式算法实验分析 |
| 6.3.1 算法实现 |
| 6.3.2 算例分析 |
| 6.4 本章小结 |
| 第7章 总结与展望 |
| 7.1 研究工作总结 |
| 7.2 研究工作展望 |
| 参考文献 |
| 附录1 攻读硕士学位期间完成的论文 |
| 附录2 攻读硕士学位期间参加的项目 |
| 致谢 |
（8）认知网络中继节点选择与信道分配算法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究工作的背景与意义 |
| 1.1.1 认知无线电和认知网络简介 |
| 1.1.2 认知网络中继选择与信道分配的研究现状 |
| 1.2 本文的研究内容 |
| 1.3 本文的主要贡献与创新点 |
| 1.4 本文的结构安排 |
| 第二章 多源节点的中继选择与信道分配算法 |
| 2.1 引言 |
| 2.2 问题建模 |
| 2.2.1 系统模型 |
| 2.2.2 系统建模 |
| 2.3 三维指派问题的强制分离算法 |
| 2.3.1 强制分离算法的思想 |
| 2.3.2 强制分离算法的性能 |
| 2.4 JRSCA算法 |
| 2.4.1 拉格朗日松弛与对偶间隙 |
| 2.4.2 最大化原问题的下界 |
| 2.4.3 JRSCA算法 |
| 2.4.4 次梯度算法步长的选择 |
| 2.5 仿真与结果分析 |
| 2.5.1 信道对吞吐量的影响 |
| 2.5.2 信源对吞吐量的影响 |
| 2.5.3 中继对吞吐量的影响 |
| 2.6 本章小结 |
| 第三章 兼顾公平性的多源节点中继选择与信道分配算法 |
| 3.1 引言 |
| 3.2 认知网络中的公平性 |
| 3.3 最大化激活的源节点数 |
| 3.3.1 问题建模 |
| 3.3.2 求解变权二维指派问题的算法 |
| 3.3.3 FJRSCA算法 |
| 3.4 仿真与结果分析 |
| 3.4.1 信道对吞吐量的影响 |
| 3.4.2 信源与中继对吞吐量的影响 |
| 3.4.3 公平性的对比 |
| 3.5 本章小结 |
| 第四章 单源节点的中继选择与信道分配算法 |
| 4.1 引言 |
| 4.2 一类凸优化问题的算法 |
| 4.3 单源节点网络模型 |
| 4.4 单源节点下的中继选择准则 |
| 4.4.1 不同信道组合下的功率分配 |
| 4.4.2 联合中继选择与信道、功率分配算法 |
| 4.5 仿真与结果分析 |
| 4.6 本章小结 |
| 第五章 总结与展望 |
| 5.1 本文结论 |
| 5.2 研究展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间取得的成果 |
（9）随机启发式搜索算法的性能分析（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 主要符号表 |
| 第一章 绪论 |
| 1.1 引言 |
| 1.2 随机启发式搜索算法 |
| 1.2.1 演化算法 |
| 1.2.2 蚁群算法 |
| 1.2.3 人工免疫系统 |
| 1.2.4 其它随机搜索算法 |
| 1.3 相关工作 |
| 1.3.1 演化算法时间复杂度和近似性能研究相关工作 |
| 1.3.2 蚁群优化算法性能研究相关工作 |
| 1.3.3 基于免疫的B细胞算法性能研究相关工作 |
| 1.3.4 其它研究成果 |
| 1.4 本文概述和主要工作 |
| 第二章 随机启发式搜索算法理论研究基础 |
| 2.1 引言 |
| 2.2 随机启发式搜索算法的计算复杂度 |
| 2.3 随机启发式搜索算法理论研究方法 |
| 2.3.1 偏差不等式 |
| 2.3.2 标准变异 |
| 2.3.3 适应值划分 |
| 2.3.4 期望倍增距离减少 |
| 2.4 小结 |
| 第三章 演化算法求解最多叶子生成树问题的性能分析 |
| 3.1 引言 |
| 3.2 最多叶子生成树问题及(1+1) EA算法 |
| 3.3 (1+1) EA算法求解MLST问题的近似保证 |
| 3.4 (1+1) EA算法在两个MLST问题实例上的性能分析 |
| 3.4.1 在一个MLST实例上(1+1) EA算法优于 1-change邻域局部搜索方法 |
| 3.4.2 在一个MLST实例上(1+1) EA算法优于 2-change邻域局部搜索方法 |
| 3.5 小结 |
| 第四章 蚁群优化算法在二次指派问题上的性能分析 |
| 4.1 引言 |
| 4.2 问题和算法 |
| 4.2.1 二次指派问题 |
| 4.2.2 ACO算法 |
| 4.3 (1+1) MMAA算法求解QAP问题的近似性能分析 |
| 4.4 (1+1) MMAA算法求解QAP实例的分析 |
| 4.5 小结 |
| 第五章 基于免疫的超变异算子与标准位变异算子的性能比较 |
| 5.1 引言 |
| 5.2 基本定义及相关算法介绍 |
| 5.2.1 基本定义 |
| 5.2.2 算法 |
| 5.3 基于免疫的超变异算子在一些人工函数上优于标准位变异算子 |
| 5.3.1 TRAP函数 |
| 5.3.2 H-IFF函数 |
| 5.4 基于免疫的超变异、标准位变异及局部变异算子在最大割问题实例上的性能比较 |
| 5.4.1 最大割问题 |
| 5.4.2 不同变异算子在实例MC(s, p) 上的行为分析 |
| 5.5 基于免疫的超变异算子在最小S-T割问题的一个实例上优于标准位变异算子 |
| 5.5.1 最小s-t割问题 |
| 5.5.2 变异算子CHM2在实例ST(k, l) 上的分析 |
| 5.6 小结 |
| 结论 |
| 参考文献 |
| 攻读博士学位期间取得的研究成果 |
| 致谢 |
（10）一种求解指派问题的进步算法（论文提纲范文）
| 引言 |
| 1 问题及数学模型 |
| 1.1 指派问题 |
| 1.2 最短路问题 |
| 1.3 关系 |
| 2 算例 |
| 2.1 人数与任务数相等的指派问题 |
| 2.2 人数与工作数不等的指派问题 |
| 3 结语 |
四、求解指派问题的一个算法（论文参考文献）
- [1]一些网络排序和路径优化问题的算法设计与性能分析[D]. 吴元霄. 华东理工大学, 2020(08)
- [2]基于效率提升的单机多任务调度相关问题研究[D]. 张迎春. 浙江工商大学, 2020(08)
- [3]多约束条件下多目标双边装配线再平衡方法研究[D]. 张亚辉. 上海交通大学, 2020(01)
- [4]多机器人全覆盖问题的任务分配算法研究[D]. 周星. 国防科技大学, 2019(01)
- [5]微控制器硬件环境下的静态资源任务分配问题求解方法研究[D]. 彭欣炜. 北京交通大学, 2019(01)
- [6]可扩展机器学习关键技术研究[D]. 明月伟. 国防科技大学, 2018(01)
- [7]基于外包服务的调度策略与优化算法[D]. 龚涛. 浙江工商大学, 2018(05)
- [8]认知网络中继节点选择与信道分配算法研究[D]. 魏凤生. 电子科技大学, 2016(02)
- [9]随机启发式搜索算法的性能分析[D]. 夏小云. 华南理工大学, 2015(04)
- [10]一种求解指派问题的进步算法[J]. 王竹芳,潘雪. 现代工业经济和信息化, 2015(21)