一、极小化总加权完工时间的Dial-a-Ride问题的在线随机算法(英文)（论文文献综述）
王婷[1]（2018）在《机器调度问题和二维向量装箱问题的精确算法研究》文中进行了进一步梳理随着经济全球化的发展,企业之间的竞争越发激烈。在能源储备不足日益凸显的今天,高效分配和使用稀缺资源的技术优势无疑是企业的核心竞争力之一。生产调度问题是制造企业在日常运作中面临的主要问题,单一机器是制造产业的基本生产单元,在机械科技水平的限制和购入机器投入资金的限制下,如何通过排序和统筹调度方面的技术去提高机器产能是企业首要解决的问题。打包装箱方法是影响物流运输的一个关键技术,跟物流运输的自动化水平、装载效率和业务流程的规范都有着重要的关系。因此,本文针对生产调度和打包装箱问题展开研究,基于列生成的思想为问题设计有效的精确算法。首先,基于制造企业实际的生产场景,我们提出了一个考虑柔性周期维护和恶化效应的单机调度问题,并设计了有效的分支定价精确算法。通过推导问题最优解中所使用批次数目的上界,我们提出了该问题的混合整数规划模型,并将此模型通过Dantzig-Wolfe分解得到集合划分问题的整数规划模型。由于集合划分问题所对应的定价问题是带有资源约束的最短路问题,我们设计了高效的标签设定算法来求解此问题。在标签设定算法中,为了加速标签的搜索过程,我们针对定价问题的特性和结构设计了标签支配规则。同时,考虑到最优解的特性,我们还提出了一个能够有效减少集合划分模型中变量数目的批次支配规则。限制性主问题的线性松弛求得的最优解有可能不是整数。为了得到问题的最优整数解,我们为精确算法设计了两种分支策略:对批次的数目进行分支和对最短路中的前向弧进行分支。在分支定界树中,全局上界的更新是通过构造式的启发式算法来实现的。在计算实验中,我们结合相关文献随机生成了 1440个算例,用来验证算法的求解性能。通过对分支定价算法的多个子模块进行对比实验和分析,实验结果表明我们所设计的分支定价算法是高效的。我们还给出了该问题在线版本下的一个最优策略。其次,我们以一个物流运输行业实际的打包装箱收费问题为背景,提出了一个与体积重量相关的一般价格函数的二维向量装箱问题。我们在论文中介绍了知名物流企业对包裹的标准收费流程,据我们所知,这是第一篇考虑体积重量的装箱问题的论文。由于价格函数的原因,我们所考虑的问题要比经典的二维向量装箱问题复杂很多。为了求解这一问题,我们在分支定价算法的基础上往限制性主问题里面加入两种有效不等式,因此我们所设计的算法是一个分支定价切割精确算法。用于加速全局下界的提升速度和减少结点的求解个数的两种有效不等式分别为:取整不等式和Subset-row不等式。因为Subset-row不等式会改变定价问题的结构使得定价问题的复杂性增加,我们仅在根结点添加Subset-row不等式。为了求解定价问题,我们设计了标签设定算法,同时推导出了考虑Subset-row不等式下的标签支配规则。为了求得问题的最优整数解,我们采用了两种分支策略:对使用的箱子的数目进行分支和对成对的物品进行分支。我们基于一种最短路解码算法来更新分支定界树中每个结点的上界。我们随机生成了 360个算例来测试我们所设计算法的性能。我们将原问题的混合整数规划模型带入CPLEX求解器求解,所得到的结果与分支定价切割算法的实验结果进行了比较,结果显示我们的算法远比CPLEX求解高效。另外,我们还对算法的几个关键子模块做了测评实验和分析。最后,我们为一个抗癌静脉注射针剂的运输存储问题设计了一个分支定价切割精确算法。此问题实际上是一个不确定尺寸的二维向量装箱问题,我们将存储抗癌静脉注射针剂的容器看成是具有体积维度和加工时长维度的箱子,那么在体积维度上箱子的体积是确定的,但是在加工时长这一维度上箱子的大小是不确定的。在加工时长维度上,我们只需考虑的问题是针剂的延迟时长不超过给定的时间限制即可。为了减少求解分支定界树中结点的数目,我们在限制性主问题里面添加了取整不等式。为了求解定价问题,我们设计了标签设定算法和标签支配规则。另外,我们还设计了对定价问题中的前向弧进行分支的分支策略。通过随机生成420个算例来测试我们算法的性能。我们用CPLEX求解器来求解原问题的0,1整数规划模型,将得到的结果与分支定价切割算法的实验结果进行比较,结果显示我们的算法远比CPLEX求解高效。另外,我们还对加入取整不等式的BPC算法与不加取整不等式的BP算法做了比较实验,实验结果显示取整不等式能够极大地提升我们算法的性能。
贺聪[2]（2018）在《连续多阶段带并行加工单元的自动柔性生产线平衡与调度问题研究》文中认为客户需求多样化、个性化,以及市场竞争的激烈化,迫使制造企业不断提升其生产制造系统的柔性化、智能化。如何规划设计出满足企业需求的柔性制造系统,实现高效、均衡的产出,是当前企业发展数字化车间、智能制造的关键问题之一。柔性生产线,作为柔性制造系统中至关重要的组成部分,通过合理的配置生产资源,以实现柔性生产线的平衡优化,最大限度地挖掘生产线潜能,降低单位产品的生产成本,已成为学术界和工业界广泛关注的热点研究课题。本文围绕某新型自动柔性生产线的设计规划需求,围绕其自动柔性生产线平衡优化问题展开研究,在针对两类基本问题的研究基础上,深入研究探讨了考虑机台故障和维修时间不确定情况下的自动柔性生产线平衡问题、考虑加工时间不确定下的自动柔性生产线多目标鲁棒性平衡问题、客户需求不确定下的自动柔性生产线平衡与批量调度问题,从问题的特点、数学建模、优化算法等方面进行了深入的研究,具体包括:（1）研究了一种新型连续多阶段带并行加工单元的自动柔性生产线,分析了该自动柔性生产线的构造与生产特点,建立了自动柔性生产线与生产阶段、加工单元之间的节拍关系。针对自动柔性生产线平衡问题-I,考虑生产线中待分配处理的操作之间的优先约束关系、互斥约束关系以及包含约束关系,以最小化生产线配置成本为目标,建立了相应的数学模型,并阐述了该问题的计算复杂度等同于NP-hard问题。同时提出了基于分支定界法的启发式方法,最终通过基于企业实际情况设计的生产线平衡试验的验证,证明所提出的算法能在有效的时间内给出生产线平衡优化结果。（2）基于自动柔性生产线平衡问题-I,研究了机床故障频次和故障维修恢复时间两方面的双重不确定性的自动柔性生产线平衡问题,建立了对应的机会约束规划模型,提出一种基于分解启发式的求解算法,借助线性化变换,实现对于约束规划模型的有效分解。通过设计不同规模算例,引入随机模拟方法,对比验证表明本文所提分解启发式（DH）算法与随机模拟方法两者结果质量的一致性,并同时揭示其相比于后者具有更好的计算速度有效性。此外,通过分析生产线增加机台后的可靠性变化,实现了对所提算法的灵敏度分析;围绕自动柔性生产线规划设计中的机床供应商选择,对所提模型及算法进行了初步的实际应用。（3）针对新型自动柔性生产线,研究了生产线平衡问题-II,在已知生产线机台数量等设备配置情况下,以最小化生产线节拍时间为目标,建立了相应的混合整数规划模型。此外,对自动柔性生产线中的系统参数进行灵敏度分析,以了解机器数量和加工时间如何影响生产线的节拍时间及利用率。进而设计了一种基于集合划分的启发式算法,并将该算法分别与分支定界法和禁忌搜索算法进行对比,针对不同问题规模与系统参数,设计了相应的基准试验。最终结果表明所提出的基于集合划分的启发式算法在求解质量和计算效率等方面均优于其它算法。（4）基于自动柔性生产线平衡问题-II,研究了加工时间的不确定环境下的自动柔性生产线多目标平衡问题,考虑了包括最小化生产线节拍时间、最小化生产线平滑指数,同时最大化期望生产线节拍的稳定性三个目标,提出了基于场景规划的三种新的多目标鲁棒性支配标准,并结合支配标准设计了基于分支定界的启发式方法和基于人工蜂群的启发式方法。通过对不同规模自动柔性生产线平衡问题的求解,并综合考虑平衡结果在所有场景下的支配比例,结果证明,基于人工蜂群的启发式结果相比于基于分支定界的启发式方法,求解结果前者优于后者,而求解速度前者不如后者。总体上两类方法均能有效求解自动柔性生产线多目标鲁棒性平衡问题。（5）在多条自动柔性生产线中,不同需求与交付期的订单连续到达工厂,很难在每个计划期内将订单需求做到合理、有效、均衡地分配到每条生产线上。针对多线生产环境下,本文研究考虑了混合产品种类在多条自动柔性生产线环境下的动态批量调度问题,同时考虑了客户需求和机台故障的不确定性。此外,在制定调度计划时,同时也考虑混合产品种类批次之间的切换时间。针对自动柔性生产线多线、混合品种调度问题,提出了一种混合整数规划模型,其目的是在每个规划期的交付期内尽可能完成来自不同客户订单的产品。为解决当前的问题,提出了解决动态批量调度问题的构造型启发式算法。所提出构造型启发式算法涉及在多条生产线路中分配不同客户订单的引导规则,并基于平衡生产线彼此之间的完工时间来进行分配。通过设计不同规模的测试实验,并基于的测试实验算例,与文献中着名的启发式方法得到的结果进行比较。结果表明,与其它典型启发式启发式算法相比,所提出的构造型启发式方法在绝大多数问题实例中得到了更好的结果。（6）基于课题组自主研发的高级计划排程系统Xplanner,将本文相关理论和研究成果集成到高级计划排程系统中。针对本文提出的优化算法,形成了面向生产线配置优化的“架机系统”子模块,同时丰富了高级计划排程系统的优化算法库。最后,基于高级计划排程系统,有效解决了智能制造新模式下的H企业的实际问题,充分阐明了本文的研究与应用价值。本文的研究成果在一定程度上丰富了自动柔性生产线平衡与优化问题研究,所研究的新型自动柔性生产线以及提出的关键技术不仅在理论方面有所突破,同时还能有效的提升企业的资源利用率和决策管理能力。
李竹林[3]（2018）在《云环境下基于负载均衡感知的任务调度算法研究》文中提出云计算作为一种新的高速网络计算服务受到越来越多的青睐,云计算技术广泛应用于通讯、交通、金融、制造等领域。通过实施任务的最优调度,充分利用现有资源实现任务的最快完成,是云计算中任务调度算法研究的目标。随着云计算的高速发展,云系统底层技术构架发生了明显变化,云系统结构越来越复杂,资源节点数量越来越多,不同云之间的差异性越来越明显。同时,用户数量多、行业普及、服务需求多、时效性期望高、数据海量且多样化等特点日益明显。已有的任务调度算法难以满足新形势下任务调度的需求,迫切需要研发更优的任务调度算法。为此,本文遵循实现系统负载均衡的基本原则,提出了适于云环境面向负载均的任务调度算法,以适应新形势下云环境及用户的需求。本文针对云环境复杂程度不同,分别提出负载评估和负载预测的算法,并对云计算中具有差异性的资源节点和任务进行聚类分析,在此基础上提出了新的任务调度算法,取得以下主要创新成果:（1）针对私有云节点异构等原因产生的负载不均衡现象,提出了节点负载评估的SARIMA算法。该算法以提高私有云系统资源利用率为目标,采用基于时间序列的两步法预测CPU工作负载。算法使用WPD法将原始序列转化为更稳定的子序列,通过SVM拟合提高ARIMA模型预测的精度,得到资源节点负载情况。SARIMA算法得到的资源节点负载评估结果,可作为任务调度的基础,也可用于资源节点负载监测。（2）针对公有云多数据中心、多资源节点等特点,提出了适用于公有云的GFCEM资源节点负载预测算法。为提高负载预测结果的准确性,GFCEM算法允许考虑可能影响节点负载的主要指标。算法引入三角模糊权重对各个资源节点的指标进行赋值,应用模糊综合评价与灰色关联理论相结合的方法,预测公有云环境下的资源节点负载情况。GFCEM算法预测的负载结果可作为任务调度算法的初始参数,也可作为虚拟机迁移的依据。（3）针对云计算技术在实际应用中动态性强、时效性高,资源节点和云任务数量大,且往往具有数值型、分类型多属性的特点,为优化任务调度算法,提出了可实现高维混合属性对象聚类的MATC算法。算法首先度量对象与类之间的相异性,计算属性的类模糊质心,结合改进的欧氏距离模型计算对象与类质心的欧氏距离;然后利用熵的理论,计算类的内部熵和类的外部熵,得到基于信息熵的混合属性对象的聚类结果。MATC聚类算法可以对混合属性对象进行较为准确的聚类,聚类结果可作为任务调度的基本初始参数。（4）针对现有任务调度算法不能很好满足云计算系统规模差异性大和资源节点异构性突出的问题,提出面向负载均衡的任务调度算法IAACO和IAPSO,两种算法均较好的考虑了资源节点负载均衡的因素。IAACO算法在满足负载均衡的前提下,重点解决了传统算法中出现局部最优解的弊端。IAPSO算法考虑了节点的多属性且差异性明显的问题,在较好预测节点负载情况的基础上完成任务的调度,最终得到理想的任务完成时间。通过以上研究,就新形势下云环境中的任务调度问题提出了新的解决方案。经系统测试实验表明,本文提出的任务算法在保持系统负载均衡、提高系统资源利用率和执行效率方面优势明显,可广泛应用于云系统中。
包晓光[4]（2012）在《一些路线问题的算法设计与分析》文中研究指明本学位论文旨在从算法设计与分析的角度研究车辆调度问题（Vehicle Scheduling Problem, VSP）、分群旅行商问题（Clustered Traveling Salesman Problem, CTSP）和在线旅行商问题（Online Traveling Salesman Problem, OLTSP）等一些路线问题。全文共分五章。第一章首先介绍本文问题的研究背景,其次引入本文涉及的一些基本概念,然后给出本文问题的数学描述,最后综述本文问题及相关问题的研究现状。第二章考虑树形和圈形网络上含释放时间和服务时间约束的单机VSP问题,目标为极小化时间表长。探讨该问题的两种形式：返回型和不返回型。返回型时间表长定义为机器服务完所有客户后返回其初始出发位置的时间,不返回型时间表长则定义为所有客户的最大完工时间。当网络结构为树时,对返回型和不返回型单机VSP问题分别给出了一个9/5和一个27/14一近似算法；当网络结构为圈时,对单机VSP问题的两种形式分别给出了一个12/7一近似算法。第三章考虑线形网络上含释放时间和服务时间约束的单机分群VSP问题。若干客户分布在一条直线上,它们被划分成若干个连续子集,每个子集称为一个群。一台机器服务所有客户,且要求每个子集内的客户连续服务。问题目标亦为极小化时间表长。对每个客户服务时间为零的情形,证明了两种形式均可在O（n2）时间内解决。对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了一个16/9和一个13/7一近似算法。第四章考虑CTSP问题。给定一个完全无向图,其顶点集被划分成若干个子集。探讨该问题的两种形式：返回型和不返回型,其目标分别是计算一条最短环游和一条最短路,使得该环游和该路经过所有顶点,且每个子集内的顶点连续经过。对旅行商进入和离开每个子集的顶点均可以在其内任意选择的情形,就返回型和不返回型形式,分别给出了一个13/6和一个33/14一近似算法。第五章考虑在线QATSP （Quota Asymmetric TSP）和在线MATSP （Multiple Asymmetric TSP）（?）司题。问题的输入由一个拟度量空间和一个以在线形式出现的请求序列组成,其中每个请求由释放时间、空间位置和权重唯一指定。在线QATSP问题的目标是,极小化机器服务了某些请求,使得它们的权重之和至少为预先给定的某个配额,且返回到其初始出发位置的时间；在线MATSP问题（此时有多台机器,且每个请求仅由释放时间和空间位置指定）的目标是,极小化所有请求均被服务完且所有机器都已返回到其初始出发位置的时间。探讨这两个问题的下界与在线算法。对在线QATSP问题,证明了其下界为2,并给出了一个（1+ρ）一竞争比算法,其中ρ为求解相应无释放时间离线问题的近似比；对在线MATSP问题,证明了其下界为3+（?）/2≈2.618,并给出了一个竞争比算法,其中ρ如前定义。
王成飞[5]（2011）在《几类新型在线分批排序问题》文中研究表明本文提出并研究一些新型的排序问题，其模型是经典排序问题和现有的排序问题的推广。经典排序问题中，工件的加工时间是不变的，我们研究工件的加工时间依赖开工时间或者开工位置变化的模型；目前几乎没有研究在线与恶化效应结合的排序问题文献，我们提出相关模型并研究；经典的在线问题（over time模型）是指工件只有到达后才知道信息，也就是说要做决策必须要等到工件到达，我们研究的在线模型是提前一段时间就知道工件的信息。本文研究的工件信息到达时间是依时间（over time）的，分批模型是指平行批模型，即工件同一时刻最多加工B个工件，B为机器的容量，批的加工时间为该批工件中最大的加工时间。本文主要由四个部分组成。第一章，我们介绍排序问题和算法复杂性的一些基本知识，并对在线排序、分批排序、带恶化效应的排序的研究进行了综述。第二章研究加工时间是一般函数的排序问题，主要考虑了两类有一般加工时间函数的排序问题，工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和。对于加工时间依赖开工时间的模型，证明一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的。对于加工时间依赖开工位置的模型，给出极小化最大完工时间和总完工时间的最优序，同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法。第三章研究加工时间是具有线性恶化效应的在线排序问题，工件Jj的实际加工时间为Pj=bj+αt,其中bj为基本加工时间, α>0为恶化率, t是开工时间，目标为极小化最大完工时间。证明不分批的单机在线问题的下界至少为；对批容量无限的单机在线问题给出一个在线算法βH∞,并证明其竞争比和问题的下界相同,为（1+α）β+1，其中进而算法是最优的；对于批容量无限的同型机排序问题，给出在线算法并证明其竞争比为（1+α）βm+1，其中第四章研究工件具有提前预知信息的在线排序问题，从预知时间到工件可加工的时间之间间隔为a,还知道工件的最大加工是为pmax，目标为极小化最大完工时间，对于批容量无限的单机（在线问√题给出一个）在线算法γH∞,并证明其竞争比和问题的下界相同,为其中pmax+a/2，进而算法是最优的；对于（批容量无√限的同型机排）序问题，给出在线算法γmH∞并证明其竞争比为1+γm，其中最后，我们对本文研究的问题进行了总结和展望。
张树霞[6]（2007）在《延误与离散可控排序》文中研究说明排序理论是组合优化这门学科的一个重要组成部分，有着深刻的实际背景和广阔的应用前景，随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷，离散可控排序就是发展最为迅速的新方向之一。经典排序模式中的工件之间带有前后约束的延误排序问题是NP困难的。本文就离散加工时间的可控排序、离散到达时间的可控排序和延误排序中的五个模型做了如下工作。一．离散可控排序1．本文首次研究了离散加工时间的可控排序中，目标函数是有限的总压缩费用（总压缩费用约束）下极小化最大完工时间，单机，工件有不同到达时间，即1|rj，dm|Cmax／TPC问题，我们设计了伪多项式时间的动态规划算法，并给出了相应的FPTAS算法。2．本文首次研究了离散加工时间的可控排序中，目标函数是有限的总压缩费用（总压缩费用约束）下极小化最大完工时间，同型机，工件到达时间都相同，即Pm|dm|Cmax／TPC问题，我们设计了伪多项式时间的动态规划算法，并给出了相应的FPTAS算法。3．本文首次研究了离散到达时间的可控排序中，目标函数是极小化总压缩费用与最大完工时间之和，单机，即1|rj，dr|Cmax+TRC问题，我们指明了其强NP-困难性，并且我们设计了在给定任意序下如何选择到达时间的一个最优算法，从而得出这个问题存在最差性能比是2的近似算法。二．延误排序1．虽然对于不带前后约束的延误排序已经有许多近似算法，其中包括后移算法。然而，迄今为止，对于带有前后约束的延误排序的近似算法在国内外还没有见过报道。对问题1|prec|∑Tj，我们把不带前后约束的延误排序的后移算法移植到工件之间带有前后约束的情况，提出一个多项式时间的近似算法。这个算法可以快速地得到这种延误问题的近似解。2．Emmons条件在求解单台机器延误问题中起着十分重要的作用，本文对陶霖和唐国春提出的弱于Emmons条件的所谓改进的Emmons条件的证明再进一步改进，简化，并完善了相应的预排序算法。
曹志刚[7]（2006）在《分批排序、可拒绝排序及离散可控排序中的若干问题》文中提出排序理论一直是组合优化领域的一个热门方向,有坚实的应用背景和深刻的理论意义。分批排序、可拒绝排序及离散可控排序都是比较新的排序模型,本文就这三个模型做了以下一些工作: 1.本文指明了单台机器上工件有不同到达时间极小化总完工时间的无穷批量问题在一种新的编码下是NP-难的;就有任意多个到达时间极小化最大完工时间的分批排序问题,本文给出了一致不相关机上的PTAS算法;对于工件有尺寸极小化最大完工时间的分批排序问题,在工时与工件尺寸成比例且比例系数为常数时,我们给出了问题的一个下界3/2,设计出了渐进PTAS算法。 2.本文首次研究了可拒绝排序的约束模型以及工件不同时到达的可拒绝排序.对于在总惩罚费用的约束下极小化加权总完工时间的问题,证明了其NP-难性,设计出了FPTAS算法;对于极小化总惩罚费用与最大完工时间之和的问题,证明了其NP-难性,设计出了PTAS算法,并对只有两个到达时间的情形设计出了竞争比为(52/1+1)/2的最有竞争性的在线算法。 3.本文证明了在总压缩费用的约束下极小化最大完工时间的离散可控排序问题是Np-难的,设计出了FPTAS算法;我们指明了极小化总压缩费用与加权总完工时间之和的离散可控排序问题是Np-难的,给出了一个在一定条件下具有有限近似比的启发式算法。大量的数值试验表明,此算法的平均性能是很好的。
鲁习文[8]（2004）在《极小化总加权完工时间的Dial-a-Ride问题的在线随机算法（英文）》文中研究表明讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为（2+2）/ln（1+2）的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.
二、极小化总加权完工时间的Dial-a-Ride问题的在线随机算法(英文)（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、极小化总加权完工时间的Dial-a-Ride问题的在线随机算法(英文)（论文提纲范文）
（1）机器调度问题和二维向量装箱问题的精确算法研究（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2. 相关问题算法预备知识和文献综述 |
| 1.2.1 调度问题预备知识 |
| 1.2.2 带有柔性周期维护和恶化效应的调度问题综述 |
| 1.2.3 二维向量装箱问题综述 |
| 1.2.4 列生成算法文献综述 |
| 1.3 研究方法和创新 |
| 1.3.1 研究方法 |
| 1.3.2 研究创新 |
| 1.4 本文的技术路线 |
| 1.5 全文结构 |
| 第二章 带有恶化效应和柔性周期维护的单机调度问题 |
| 2.1 引言 |
| 2.2 问题描述和数学规划模型 |
| 2.2.1 问题描述 |
| 2.2.2 数学规划模型 |
| 2.3 支配规则 |
| 2.4 分支定价算法 |
| 2.4.1 分支策略 |
| 2.4.2 限制性主问题 |
| 2.4.3 定价问题 |
| 2.4.4 标签设定算法 |
| 2.5 启发式算法 |
| 2.6 计算实验 |
| 2.6.1 实验算例生成 |
| 2.6.2 分支定价算法性能分析 |
| 2.7 在线版本问题 |
| 2.8 本章小结 |
| 第三章 与体积重量相关的一般价格函数的二维向量装箱问题 |
| 3.1 引言 |
| 3.2 问题描述和数学规划模型 |
| 3.2.1 问题描述 |
| 3.2.2 整数规划模型 |
| 3.3 分支定价切割算法 |
| 3.3.1 集合划分问题 |
| 3.3.2 有效不等式 |
| 3.3.3 分支策略 |
| 3.3.4 限制性主问题 |
| 3.3.5 初始化限制性主问题 |
| 3.4 列生成 |
| 3.4.1 定价问题 |
| 3.4.2 标签设定算法 |
| 3.4.3 标签支配规则 |
| 3.5 启发式算法 |
| 3.6 计算实验 |
| 3.6.1 实验算例生成 |
| 3.6.2 分支定价切割算法性能分析 |
| 3.7 本章小结 |
| 第四章 带有二维向量约束的单机调度问题 |
| 4.1 引言 |
| 4.2 问题描述和数学规划模型 |
| 4.2.1 问题描述 |
| 4.2.2 数学规划模型 |
| 4.3 分支定价切割算法 |
| 4.3.1 集合划分问题 |
| 4.3.2 有效不等式 |
| 4.3.3 限制性主问题 |
| 4.3.4 分支策略 |
| 4.3.5 初始化限制性主问题 |
| 4.4 列生成 |
| 4.4.1 定价问题 |
| 4.4.2 标签设定算法 |
| 4.4.3 标签支配规则 |
| 4.5 启发式算法 |
| 4.6 计算实验 |
| 4.6.1 实验算例生成 |
| 4.6.2 算法性能分析 |
| 4.7 本章小节 |
| 第五章 问题总结和展望 |
| 5.1 问题总结 |
| 5.2 展望 |
| 参考文献 |
| 博士在读期间的论文和科研情况 |
| 致谢 |
（2）连续多阶段带并行加工单元的自动柔性生产线平衡与调度问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 研究背景 |
| 1.2 课题来源 |
| 1.3 课题目的及意义 |
| 1.4 国内外研究现状 |
| 1.5 论文的研究思路与组织结构 |
| 2 自动柔性生产线平衡问题-I研究 |
| 2.1 引言 |
| 2.2 连续多阶段带并行加工单元的自动柔性生产线 |
| 2.3 自动柔性生产线平衡问题-I描述及建模 |
| 2.4 基于分支定界法的启发式方法 |
| 2.5 算例结果与分析 |
| 2.6 本章小结 |
| 3 双重不确定下的自动柔性生产线平衡问题-I研究 |
| 3.1 引言 |
| 3.2 双重不确定下的自动柔性生产线平衡问题-II描述与建模 |
| 3.3 基于分解启发式的解决方法 |
| 3.4 算例结果与分析 |
| 3.5 本章小结 |
| 4 自动柔性生产线平衡问题-II研究 |
| 4.1 引言 |
| 4.2 自动柔性生产线平衡问题-II描述及建模 |
| 4.3 基于集合划分的启发式方法 |
| 4.4 算例结果与分析 |
| 4.5 本章小结 |
| 5 基于多目标鲁棒性的自动柔性生产线平衡问题-Ⅱ研究 |
| 5.1 引言 |
| 5.2 加工时间不确定下的自动柔性生产线平衡问题-II |
| 5.3 加工时间不确定的自动柔性生产线多目标优化问题 |
| 5.4 启发式算法 |
| 5.5 算例结果与分析 |
| 5.6 本章小结 |
| 6 需求不确定下的自动柔性生产线批量调度问题研究 |
| 6.1 引言 |
| 6.2 需求不确定下的自动柔性生产线调度问题描述与建模 |
| 6.3 构造型启发式算法 |
| 6.4 算例结果与分析 |
| 6.5 本章小结 |
| 7 智能制造新模式下的初步应用 |
| 7.1 企业应用背景介绍 |
| 7.2 自动柔性生产线车间APS实施与应用 |
| 7.3 本章小结 |
| 8 总结与展望 |
| 8.1 全文总结 |
| 8.2 创新点 |
| 8.3 研究展望 |
| 致谢 |
| 参考文献 |
| 附录1 攻读博士学位期间发表的学术论文和学术成果 |
| 附录2 攻读博士学位期间参加的科研项目 |
| 附录3 H企业车间A部分相关数据 |
（3）云环境下基于负载均衡感知的任务调度算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究背景 |
| 1.1.1 云计算分类 |
| 1.1.2 云平台承载的大数据 |
| 1.1.3 云计算平台 |
| 1.2 存在的问题与挑战 |
| 1.3 研究的目标、内容和创新点 |
| 1.3.1 研究目标 |
| 1.3.2 研究内容 |
| 1.3.3 主要创新点 |
| 1.4 论文组织结构 |
| 第2章 云计算中任务调度关键技术研究 |
| 2.1 典型任务调度算法 |
| 2.1.1 传统任务调度算法 |
| 2.1.2 启发式任务调度算法 |
| 2.2 任务调度的研究进展 |
| 2.2.1 负载均衡感知的任务调度 |
| 2.2.2 成本感知的任务调度 |
| 2.2.3 效率感知的任务调度 |
| 2.2.4 能量感知的任务调度 |
| 2.2.5 服务质量感知的任务调度 |
| 2.3 服务于任务调度的负载预测研究 |
| 2.3.1 时间序列线性预测模型 |
| 2.3.2 指数平滑法预测模型 |
| 2.3.3 神经网络预测模型 |
| 2.4 小结 |
| 第3章 私有云节点负载评估SARIMA算法 |
| 3.1 研究意义 |
| 3.2 私有云负载评估模型建立 |
| 3.3 SARIMA评估算法 |
| 3.3.1 负载序列处理 |
| 3.3.2 负载评估 |
| 3.3.3 算法流程与代码实现 |
| 3.4 实验与结果分析 |
| 3.4.1 仿真实验与结果分析 |
| 3.4.2 真实数据测试与结果分析 |
| 3.5 小结 |
| 第4章 公有云环境GFCEM负载预测算法 |
| 4.1 预备理论 |
| 4.2 模型建立 |
| 4.3 GFCEM评价算法 |
| 4.3.1 指标数据处理 |
| 4.3.2 三角模糊权重计算 |
| 4.3.3 三角模糊相似度计算 |
| 4.3.4 灰色关联度计算 |
| 4.3.5 GFCEM算法伪代码 |
| 4.4 实验与结果分析 |
| 4.4.1 测度指标选取 |
| 4.4.2 节点负载预测 |
| 4.4.3 结果分析 |
| 4.5 小结 |
| 第5章 面向云任务调度的MATC聚类算法 |
| 5.1 研究的意义 |
| 5.2 模型构建 |
| 5.3 MATC聚类算法 |
| 5.3.1 属性对象间相异性计算 |
| 5.3.2 数值型属性对象聚类 |
| 5.3.3 分类型属性对象聚类 |
| 5.3.4 混合属性对象聚类 |
| 5.4 任务调度中MATC的应用 |
| 5.4.1 节点属性处理 |
| 5.4.2 任务属性处理 |
| 5.4.3 算法伪代码实现 |
| 5.5 算法性能测试 |
| 5.6 小结 |
| 第6章 云环境中面向负载均衡的任务调度算法 |
| 6.1 研究的意义 |
| 6.2 任务调度模型构建 |
| 6.3 IAACO任务调度算法 |
| 6.3.1 算法基础 |
| 6.3.2 初始负载评估 |
| 6.3.3 IAACO算法 |
| 6.3.4 IAACO算法伪代码 |
| 6.4 IAPSO任务调度算法 |
| 6.4.1 IAPSO算法 |
| 6.4.2 IAPSO算法优化 |
| 6.4.3 IAPSO算法实现 |
| 6.5 实验与结果分析 |
| 6.5.1 IAACO算法实验 |
| 6.5.2 IAPSO算法实验 |
| 6.5.3 IAACO与IAPSO算法对比实验 |
| 6.6 小结 |
| 第7章 结论与展望 |
| 7.1 主要结论 |
| 7.2 工作展望 |
| 参考文献 |
| 致谢 |
| 攻读博士学位期间取得的学术成果 |
| 作者从事科学研究和学习经历的简历 |
（4）一些路线问题的算法设计与分析（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究背景 |
| 1.2 基本概念 |
| 1.2.1 算法和复杂性 |
| 1.2.2 离线问题和在线问题 |
| 1.2.3 算法评价 |
| 1.3 本文问题描述 |
| 1.3.1 VRP和VSP问题 |
| 1.3.2 CTSP问题 |
| 1.3.3 在线TSP问题 |
| 1.4 应用实例 |
| 1.5 文献综述 |
| 1.5.1 VRP、VSP和相关问题 |
| 1.5.2 CTSP和相关问题 |
| 1.5.3 在线TSP和相关问题 |
| 1.6 论文概述 |
| 第2章 树和圈形网络上单机VSP问题 |
| 2.1 引言 |
| 2.2 问题描述和符号 |
| 2.3 树形网络上单机VSP问题(T-VSP) |
| 2.3.1 返回型T-VSP问题 |
| 2.3.2 不返回型T-VSP问题 |
| 2.4 圈形网络上单机VSP问题(C-VSP) |
| 2.4.1 返回型C-VSP问题 |
| 2.4.2 不返回型C-VSP问题 |
| 2.5 总结 |
| 第3章 线形网络上单机分群VRP和分群VSP问题 |
| 3.1 引言 |
| 3.2 问题描述和符号 |
| 3.3 分群L-VRP问题 |
| 3.4 分群L-VSP问题 |
| 3.4.1 近似算法 |
| 3.4.2 返回型 |
| 3.4.3 不返回型 |
| 3.5 总结 |
| 第4章 CTSP问题 |
| 4.1 引言 |
| 4.2 预备知识 |
| 4.2.1 TSPP问题 |
| 4.2.2 RPP问题 |
| 4.3 近似算法 |
| 4.4 性能比分析 |
| 4.5 总结 |
| 第5章 在线QATSP和在线MATSP问题 |
| 5.1 引言 |
| 5.2 问题描述和符号 |
| 5.3 在线QATSP问题 |
| 5.4 在线MATSP问题 |
| 5.5 总结 |
| 参考文献 |
| 致谢 |
| 博士在读期间完成的论文 |
（5）几类新型在线分批排序问题（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 排序问题 |
| 1.2 算法复杂性 |
| 1.3 文献综述 |
| 1.3.1 在线排序 |
| 1.3.2 分批排序 |
| 1.3.3 带恶化效应的排序 |
| 第二章 加工时间是一般函数的排序问题 |
| 2.1 引言 |
| 2.2 加工时间依赖开工时间的单机模型 |
| 2.3 加工时间依赖开工位置的单机模型 |
| 2.4 同型机排序问题模型 |
| 2.5 分批排序问题模型 |
| 第三章 具有线性恶化效应的在线排序问题 |
| 3.1 引言 |
| 3.2 问题1|online, r_j, p_j= bj+ αt|C_max |
| 3.2.1 问题下界 |
| 3.2.2 贪婪算法及其竞争比 |
| 3.3 问题1|online, r_j, p-batch, B = ∞, p_j= b_j+ αt|C_max |
| 3.3.1 问题的下界 |
| 3.3.2 在线算法及其竞争比 |
| 3.4 问题Pm|online, r_j, p-batch, B = ∞, pj= bj+ αt|Cmax |
| 3.4.1 在线算法 |
| 3.4.2 竞争比分析 |
| 第四章 提前预知信息的在线分批排序问题 |
| 4.1 引言 |
| 4.2 问题1|online, p-batch, r_j= r′_j+ a, p_max|C_max |
| 4.2.1 问题下界 |
| 4.2.2 在线算法及其竞争比 |
| 4.3 问题Pm|online, p-batch, r_j= r′_j+ a, p_max|C_max |
| 4.3.1 在线算法 |
| 4.3.2 竞争比分析 |
| 第五章 总结与展望 |
| 参考文献 |
| 在校期间发表的学术论文 |
| 致谢 |
（6）延误与离散可控排序（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 应用背景及问题描述 |
| 1.2 预备知识 |
| 1.3 本文主要结果及创新点 |
| 第二章 离散可控排序中的若干问题 |
| 2.1 问题描述及研究概况 |
| 2.2 工件有不同到达时间的离散加工时间的单机可控排序 |
| 2.3 工件到达时间都相同的离散加工时间的同型机可控排序 |
| 2.4 离散到达时间的可控排序 |
| 2.5 小结 |
| 第三章 延误排序中的若干问题 |
| 3.1 带有前后约束的延误排序问题的近似算法 |
| 3.2 关于延误问题改进的Emmons条件 |
| 3.3 小结 |
| 参考文献 |
| 作者发表的主要论文 |
| 后记 |
（7）分批排序、可拒绝排序及离散可控排序中的若干问题（论文提纲范文）
| 第一章 绪论 |
| 1.1 应用背景及问题描述 |
| 1.1.1 应用背景 |
| 1.1.2 历史起源及研究概况 |
| 1.1.3 经典排序与现代排序 |
| 1.1.4 排序问题的表示 |
| 1.2 预备知识 |
| 1.2.1 排序问题的求解 |
| 1.2.2 基本方法和技巧 |
| 1.2.3 离线与在线 |
| 1.2.4 目标排序的四种模型及基本关系 |
| 1.2.5 几个常见的NP-难问题 |
| 1.2.6 几个经典算法 |
| 1.3 本文主要结果及创新点 |
| 第二章 分批排序中的若干问题 |
| 2.1 问题背景及描述 |
| 2.2 研究概况 |
| 2.3 一致不相关机上的分批排序 |
| 2.3.1 到达时间个数为常数以及输入数据为整数的情形 |
| 2.3.2 输入为一般有理数的情形 |
| 2.3.3 一般情形 |
| 2.4 工件有尺寸的分批排序 |
| 2.4.1 问题PBSM的下界 |
| 2.4.2 BSM的一个多项式可解的特殊情形 |
| 2.4.3 一般情形 |
| 2.5 小结 |
| 第三章 可拒绝排序和离散可控排序中的若干问题 |
| 3.1 问题描述及研究概况 |
| 3.1.1 问题描述 |
| 3.1.2 研究概况 |
| 3.2 工件不同时到达极小化最大完工时间的可拒绝排序 |
| 3.2.1 离线情形 |
| 3.2.2 在线情形 |
| 3.3 压缩费用约束下极小化最大完工时间的离散可控排序 |
| 3.4 惩罚费用约束下极小化总完工时间的可拒绝排序 |
| 3.5 极小化压缩费用与加权总完工时间之和的离散可控排序 |
| 3.5.1 一个启发式算法 |
| 3.5.2 数值试验 |
| 3.6 小结 |
| 参考文献 |
| 附录一 附表 |
| 附录二 硕士生期间发表或完成的论文 |
| 附录三 致谢 |
四、极小化总加权完工时间的Dial-a-Ride问题的在线随机算法(英文)（论文参考文献）
- [1]机器调度问题和二维向量装箱问题的精确算法研究[D]. 王婷. 南京大学, 2018(04)
- [2]连续多阶段带并行加工单元的自动柔性生产线平衡与调度问题研究[D]. 贺聪. 华中科技大学, 2018(05)
- [3]云环境下基于负载均衡感知的任务调度算法研究[D]. 李竹林. 东北大学, 2018(01)
- [4]一些路线问题的算法设计与分析[D]. 包晓光. 华东理工大学, 2012(02)
- [5]几类新型在线分批排序问题[D]. 王成飞. 曲阜师范大学, 2011(10)
- [6]延误与离散可控排序[D]. 张树霞. 华东师范大学, 2007(03)
- [7]分批排序、可拒绝排序及离散可控排序中的若干问题[D]. 曹志刚. 曲阜师范大学, 2006(09)
- [8]极小化总加权完工时间的Dial-a-Ride问题的在线随机算法（英文）[J]. 鲁习文. 高校应用数学学报A辑（中文版）, 2004(S1)