导读:本文包含了加权总完工时间论文开题报告文献综述及选题提纲参考文献，主要关键词:重新排序,错位,最大加权完工时间,NP-困难
加权总完工时间论文文献综述
臧西杰,李士生,王曦峰[1]（2017）在《最小化最大加权完工时间重新排序研究》一文中研究指出重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.(本文来源于《系统科学与数学》期刊2017年11期）
李金权[2]（2017）在《一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究》一文中研究指出本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.(本文来源于《计算数学》期刊2017年04期）
王杜娟,刘锋,王建军,王延章[3]（2016）在《加工时间可控单机加权总完工时间Pareto优化研究》一文中研究指出针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。(本文来源于《运筹与管理》期刊2016年01期）
农庆琴,范国强,赵婷[4]（2015）在《最大加权完工时间排序博弈问题的协调机制》一文中研究指出研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有m台平行机和n个工件,工件j的加工时间为pj,权重为ωj。每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间。本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m。(本文来源于《中国海洋大学学报(自然科学版)》期刊2015年07期）
柴幸[5]（2015）在《最小化最大加权完工时间的平行分批在线排序问题》一文中研究指出在经典的离线排序问题中,在排序之前已经知道工件的所有信息.本文主要研究的是按时在线排序.也就是指工件的各种信息在加工之前并不清楚,而是随着时间推移逐个到达之后才被了解.在本文中,主要研究平行分批在线排序的若干问题.平行分批排序是排序研究领域中一类非常重要的问题.平行机排序模型中共有m台机器.一台分批机器可以一批同时加工至多b个工件.批的加工时长由该批中的最长工件决定.按照批的容量,可以分为两类平行分批排序：有界的情形和无界的情形.在第二章中,对单机上最小化最大加权完工时间的分批在线排序问题,当批容量为1时,给出竞争比为2的最好可能的在线算法.在第叁章中,考虑平行机上单位长度工件最小化最大加权完工时间的分批在线排序问题.对批容量有界情形,引用叁参数表示法可以表示为：Pm|online,p-batch,b<∞,Pj= 1|WCmax我们给出竞争比为攀#≈1.618的最好可能的在线算法.同时证明了该问题稠密算法竞争比的下界为2,给出了达到该竞争比的稠密算法.批容量无界时,对问题Pm|online,p-batch,prec,b=∞,Pj=1|WCmax和Pm|online,p-batch,prec,b=∞,Pj=1|∑wjcj,我们给出竞争比为(?)的最好可能的稠密算法,这个结果在工件间无序约束关系时同样成立.在第四章中,考虑平行机上权重相同的单位工件具有不相容工件组和前瞻区间的无界分批在线排序问题.具有前瞻区间表示,在时刻t,在线算法可以看到在㈦t+序]时间内到达的工件信息.不相容工件组表示来自不同工件组的工件不可以在同一批次加工.当所有工件的权重相同时,最大加权完工时间即转化为最大完工时间.对问题Pm|online,p-batch,b= ∞,Pj=1,LKβ,f-families,β≥[f/m]Cmax,我们给出最优的在线算法.对问题Pm|online, p-batch,b=∞,Pj=1,LKβk,f_families,f=km,βk∈[k-1,k)|Cmax,我们给出竞争比为1+α七的最好可能的在线算法,其中α七是方程kαk2+αk(βk+1)+βk-k=0的正根.对更一般的情形,我们证明了稠密算法的下界,并给出了最好可能的稠密算法.(本文来源于《郑州大学》期刊2015-05-01）
马冉[6]（2015）在《最小化加权完工时间和的在线排序研究》一文中研究指出在线排序研究具有重要的理论意义和实际应用价值。近二十年来,在线排序得到国内外同行的广泛关注和深入研究,并促使其成为现代排序领域中发展最为迅速的方向之一。本文所说的“在线”是指时间在线(online over time)。也就是说,工件是随着时间依次到达的,并且事先不知道它的一切信息。求解在线问题的算法称为在线算法。对一个最小化目标函数的在线排序问题,在线算法A的竞争比定义为ρA=sup{A(I)/OPT(I):I是满足OPT(I)>0的任一实例}.由此可见,竞争比越接近于1,就表明在线算法的性能越优良。如果不存在其他的竞争比小于A的竞争比的在线算法,就称在线算法A是最好可能的(best possible)。工件的加权完工时间和是排序的主要优化指标之一。本学位论文研究了若干与最小化工件的加权完工时间和相关的在线排序问题。学位论文共有六章:第一章主要介绍了一些与组合最优化以及排序问题相关的概念,并介绍了在线排序的研究现状,特别是最小化加权完工时间和的在线排序的研究现状。第二章研究了工件可拒绝的在线排序,其中每个工件Jj或者被拒绝加工并支付拒绝费用ej,或者被机器接收并加工。目标是最小化接收工件的加权完工时间和加上被拒绝工件的拒绝费用和。?对于一台机器工件有相同的权重且加工时间和拒绝费用满足一致性条件的情形,给出了一个竞争比为2的最好可能的在线算法DSPTR。?对于一台机器上问题的一般情形,给出了一个竞争比为2的最好可能的在线算法DSWPTR,推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。该结果也是本章上一个结果的推广,但是论证技巧上截然不同。我们首先将在线算法柔性化,然后采用实例归结的技巧进行论证。?在多台恒同机(identical machines)上,我们给出了一个竞争比至多为4+的在线算法,在多台无关机(unrelated machines)上,我们给出了一个竞争比至多为8的在线算法。第叁章研究了一台机器最小化时间表长和加权完工时间和的在线折衷排序问题。我们引入了最小化f1和f2的在线折衷排序。称一个在线算法A是(ρ1,ρ2)-竞争的,如果最小化f1时A是ρ1-竞争的而最小化f2时A是ρ2-竞争的。对于一个(ρ1,ρ2)-竞争的在线算法A,如果不存在(ρ1,ρ2)-竞争的在线算法A满足(ρ1,ρ2)≤(ρ1,ρ2)并且有ρ1<ρ1或者ρ2<ρ2,则在线算法A被称为是不可支配的(nondominated).?对于该问题,我们给出了一个参数在线算法,并利用两种不同的方法分别证明了该算法对于满足0<α≤1的任意α是一个竞争比为(1+α,1+1/α)的不可支配的在线算法。此结果推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。第四章研究了多台平行批机器上批容量有限目标函数为最小化加权完工时间和的在线排序问题。?在一致机(uniform machines)上,当机器台数m为常数时,我们得到了一个竞争比至多为4+的在线算法。?在恒同机上,当机器台数m任意时,我们也得到了一个竞争比至多为4+的在线算法。该项工作改进了Zhang等人发表于《Journal of Industrial and Management Optimization,2007》对此问题给出的竞争比至多为8的在线算法。第五章研究了一台机器上工件加工时间可退化的最小化加权完工时间和的在线排序问题。在该问题中,工件Jj的加工时间为pj=αj(A+Bsj),其中A≥0,B≥0,A和B至少有一个非零,αj≥0是工件Jj的退化率,sj≥0是工件Jj的开工时间。?我们给出了一个竞争比为1+λ(A)+αmaxB的最好可能的在线算法,其中αmax=max1≤j≤nαj,而λ(A)=0或λ(A)=1取决于A=0或A>0。该项工作将Liu等人发表于《Theoretical Computer Science,2012》的简单线性退化并且工件权重都相等时的结果推广到了线性退化并且工件权重不同的更一般的情形。第六章总结了本学位论文所研究的主要内容和取得的一些主要结果,并指出了存在的一些问题以及未来的一些研究方向。(本文来源于《郑州大学》期刊2015-03-01）
闫力君,赵玉芳[7]（2015）在《极小化加权总完工时间的可拒绝单机排序问题》一文中研究指出在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。(本文来源于《沈阳师范大学学报(自然科学版)》期刊2015年01期）
邱言玲,高淑萍,张宝玉[8]（2014）在《基于加权总完工时间的两人合作排序博弈》一文中研究指出现实活动中,往往存在一方无法独自完成一个项目中全部工件加工任务的情况,这就需要双方或者多方合作共同完成任务。假设每人有一台用于加工工件的机器,通过确定这批工件的一个恰当划分,把工件分配给两台机器,使得双方合作收益最大。本文研究当工件加工时间是其开工时间线性恶化函数,以最小的加权总完工时间作为加工成本,建立两人合作排序博弈模型。通过运用Matlab软件,分析不同的盈利能力和机会成本对最优解的影响,并与以总完工时间作为加工成本的模型进行比较,表明本文模型在盈利能力不强以及恶化因子小的情况下都可以求得最优解。(本文来源于《重庆师范大学学报(自然科学版)》期刊2014年06期）
何程,林浩,豆俊梅,慕运动[9]（2014）在《同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题(英文)》一文中研究指出It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time.(本文来源于《数学季刊(英文版)》期刊2014年02期）
臧西杰,李士生[10]（2014）在《两类极小化最大加权完工时间排序问题研究》一文中研究指出研究两个单机排序问题,目标函数均是最大加权完工时间。对于问题1‖maxwjcj,证明了LW规则序是最优排序,而问题1|rj|maxwjcj,用3-划分问题归结,证明是强NP困难的。(本文来源于《佛山科学技术学院学报(自然科学版)》期刊2014年03期）
加权总完工时间论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
加权总完工时间论文参考文献
[1].臧西杰,李士生,王曦峰.最小化最大加权完工时间重新排序研究[J].系统科学与数学.2017
[2].李金权.一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究[J].计算数学.2017
[3].王杜娟,刘锋,王建军,王延章.加工时间可控单机加权总完工时间Pareto优化研究[J].运筹与管理.2016
[4].农庆琴,范国强,赵婷.最大加权完工时间排序博弈问题的协调机制[J].中国海洋大学学报(自然科学版).2015
[5].柴幸.最小化最大加权完工时间的平行分批在线排序问题[D].郑州大学.2015
[6].马冉.最小化加权完工时间和的在线排序研究[D].郑州大学.2015
[7].闫力君,赵玉芳.极小化加权总完工时间的可拒绝单机排序问题[J].沈阳师范大学学报(自然科学版).2015
[8].邱言玲,高淑萍,张宝玉.基于加权总完工时间的两人合作排序博弈[J].重庆师范大学学报(自然科学版).2014
[9].何程,林浩,豆俊梅,慕运动.同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题(英文)[J].数学季刊(英文版).2014
[10].臧西杰,李士生.两类极小化最大加权完工时间排序问题研究[J].佛山科学技术学院学报(自然科学版).2014