导读:本文包含了总加权完工时间论文开题报告文献综述及选题提纲参考文献，主要关键词:重新排序,错位,最大加权完工时间,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]（2015）在《最大加权完工时间排序博弈问题的协调机制》一文中研究指出研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有m台平行机和n个工件,工件j的加工时间为pj,权重为ωj。每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间。本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m。(本文来源于《中国海洋大学学报(自然科学版)》期刊2015年07期）
柴幸[3]（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）
马冉[4]（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）
臧西杰,李士生[5]（2014）在《两类极小化最大加权完工时间排序问题研究》一文中研究指出研究两个单机排序问题,目标函数均是最大加权完工时间。对于问题1‖maxwjcj,证明了LW规则序是最优排序,而问题1|rj|maxwjcj,用3-划分问题归结,证明是强NP困难的。(本文来源于《佛山科学技术学院学报(自然科学版)》期刊2014年03期）
卫志刚[6]（2011）在《可自由离线批处理机最小化加权完工时间和排序》一文中研究指出批处理排序是排序领域中一类重要问题.批处理是指处理机可以同时将b个工件作为一批,在相同的批开工时间同时加工.对于输入的n个工件,要求将n个工件安排到若干批中,并且决定这些批的开始加工时间：使得给定的目标函数值最小在本文中,工件具有自由离线的性质,目标函数是总加权完工时间.工件可自由离线(item-availability)是指,同一批中的每个工件完工时间等于该批的开工时间与该工件的加工时间之和.本文对完工工件可自由离线的单台批处理机最小化加权完工时间和排序的在线和离线情况分别做了研究.在线情形下,对于批容量无限(b=+∞)的模型,给出了一个竞争比是2+α的柔性算法(α=(?)-1/2),并证明了该竞争比是紧的(tight)对于容量有限(b<n)的模型,给出了一个(4+ε)近似的在线算法.离线情形下,首先证明了批容量无限(b=+∞),且工件到达时间(release-date)不全相同的批排序问题是NP-困难的,然后给出一个全多项式近似方案(FPTAS)对于工件加工时间的种类为固定常数的情形,给出了一个多项式时间的动态规划算法.对于批容量有限的模型,对工件到达时间不全相同且所有的工件加工时间都相同的情形,证明了可在多项式时间找到一个最优排序.对工件到达时间相同且工件权重全相同的情形：设计出一个2-近似的算法.(本文来源于《郑州大学》期刊2011-05-01）
吴志德,冯荣权[7]（2010）在《具有禁用区间的单机最小化加权完工时间和排序问题》一文中研究指出研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重迭.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.(本文来源于《数学的实践与认识》期刊2010年06期）
原晋江,王勤[8]（2010）在《单可变资源最小化加权完工时间和排序问题的强NP-困难性(英文)》一文中研究指出Baker和Nuttle提出了下述单可变资源排序问题:n个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.(本文来源于《运筹学学报》期刊2010年01期）
慕运动,谷存昌,周伟,程瑶[9]（2010）在《反相容工件系统的加权完工时间和的重新排序问题(英文)》一文中研究指出重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。(本文来源于《工程数学学报》期刊2010年01期）
马英,左春荣,杨善林[10]（2009）在《带不可用时间段的两台同类机加权完工时间和调度》一文中研究指出研究了两台同类机加权完工时间和调度,其中一台机器在一个固定的时间段内不可用,并且被不可用时间段中断的工件是部分可续的,即被中断工件在机器不可用之前已加工的部分在机器重新可用之后需进行部分重新加工.首先简单说明了此问题的NP难性,然后证明了最优调度的一个性质,并在此基础上提出了一种动态规划算法来求得小规模问题的最优解,另外还提出了一种启发式算法来求得中大规模问题的近优解.实验结果表明了这两种算法的有效性.(本文来源于《中国科学技术大学学报》期刊2009年06期）
总加权完工时间论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有m台平行机和n个工件,工件j的加工时间为pj,权重为ωj。每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间。本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
总加权完工时间论文参考文献
[1].臧西杰,李士生,王曦峰.最小化最大加权完工时间重新排序研究[J].系统科学与数学.2017
[2].农庆琴,范国强,赵婷.最大加权完工时间排序博弈问题的协调机制[J].中国海洋大学学报(自然科学版).2015
[3].柴幸.最小化最大加权完工时间的平行分批在线排序问题[D].郑州大学.2015
[4].马冉.最小化加权完工时间和的在线排序研究[D].郑州大学.2015
[5].臧西杰,李士生.两类极小化最大加权完工时间排序问题研究[J].佛山科学技术学院学报(自然科学版).2014
[6].卫志刚.可自由离线批处理机最小化加权完工时间和排序[D].郑州大学.2011
[7].吴志德,冯荣权.具有禁用区间的单机最小化加权完工时间和排序问题[J].数学的实践与认识.2010
[8].原晋江,王勤.单可变资源最小化加权完工时间和排序问题的强NP-困难性(英文)[J].运筹学学报.2010
[9].慕运动,谷存昌,周伟,程瑶.反相容工件系统的加权完工时间和的重新排序问题(英文)[J].工程数学学报.2010
[10].马英,左春荣,杨善林.带不可用时间段的两台同类机加权完工时间和调度[J].中国科学技术大学学报.2009