中国科学技术信息研究所--国家工程技术数字图书馆

[学位论文] 谈之奕浙江大学 2001年博士导师: 姚恩瑜;何勇共92页

摘要 : 该文主要研究平行机在线半在线排序问题及其相关问题.论文首先简要介绍了排序问题、竞争比分析和随机算法的基本概念,总结了近年来出现的各个半在线模型及有关结果.对多个不同机器环境下部分在线半在线排序问题,讨论了问题的下(上)界,设计了相应的近似... 展开该文主要研究平行机在线半在线排序问题及其相关问题.论文首先简要介绍了排序问题、竞争比分析和随机算法的基本概念,总结了近年来出现的各个半在线模型及有关结果.对多个不同机器环境下部分在线半在线排序问题,讨论了问题的下(上)界,设计了相应的近似算法,通过对它们的竞争比与问题的下(上)界进行比较,可知在大多数情况下文章得到了最好算法或接近最好的算法.第二章研究两台同类平行机半在线排序问题.对ordinal半在线模型,我们给出了算法QOrdinal,其参数竞争比与问题的参数下界在绝大部分情况下是相等的,最大差距不大于0.053.对已知工作总加工时间,已知工件最大加工时间两个半在线模型,近似算法的竞争比与它们的下界的差距均不大于0.01.第三章研究带机器准备时间的平行机排序问题.论文介绍了与完工时间相关的两种不同目标函数及其实际意义,证明了LS算法解在线问题的竞争比仍为2-1/m.对ordinal半在线模型,我们指出此时两个目标函数相对应的排序问题的下界有显著差异,对其中一个目标,我们给出了对任意m台机均为最好的算法,而对另一个目标,我们给出的算法当机器数m≤4时为最好的.该章最后讨论了已知工件加工时间非增,已知工件总加工时间和已知工件最大加工时间半在线排序问题,在两台机情形均给出了最好算法.第四章研究以极大化最小机器负载为目标的平行机排序问题.我们给出了求解两台机在线和已知工件加工时间非增半在线排序问题的最好随机算法.对ordinal半在线模型,我们给出了任意m台机时的上界及算法Harmonic,其竞争比与上界有相同的渐近阶.当机器数m≤16时,我们给出了另一族算法MIN(m),其竞争比与上界的差距不大于0.013.第五章研究机器有维修时段的两台同型机不中恢复在线排序问题.我们证明了问题的下界为5/2,而LS算法的竞争比为3,进一步我们给出了竞争比为5/2因而也是最好的算法CLS.第六章研究与排序问题有密切关系的k-分划和k<,i>-分划问题.在极大化最小负载目标时,我们证明了Folding算法解k-分划的最坏情况界,给出了分别求解k-分划问题和k<,i>-分划问题的新算法Harmonic_k和Harmonic_k<,i>,在应用范围和近似程度上改进了已有的结果. 收起

关键词 : 排序问题算法设计

2. 工件加工时间非恒定且工件可拒绝的排序问题

[学位论文] 程予绍上海大学 2008年硕士导师: 孙世杰共51页

摘要 : 排序问题是一类重要的组合优化问题。本文提出一类新型的排序问题--工件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体分为以下几方面； 1. 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工时间... 展开排序问题是一类重要的组合优化问题。本文提出一类新型的排序问题--工件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体分为以下几方面； 1. 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工时间非恒定排序问题及工件可拒绝的排序问题的相关结果做了简要的介绍。同时，阐述了研究加工时间非恒定且工件可拒绝的排序问题理论意义与应用价值。 2.工件加工时间是其开始加工时间的线性函数且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，最小化加权总完工时间与拒绝惩罚和的问题以及最小化最大延迟/延误与拒绝惩罚和的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。 3.工件加工时间是其基本加工时间和开始加工时间的线性函数且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。对于最小化加权总完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并对它的一个特例设计了多项式时间的最优算法。 4.工件加工时间是其正常加工时间和开始加工时间的线性函数且工件可拒绝的带优势关系流水作业问题。对于最小化最大完工时间与拒绝惩罚和的问题，最小化总完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。 5.工件加工时间与工件所排位置有关且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。此外，本文还研究了以下加工时间恒定的问题。 1.证明了加工时间恒定的最小化误工工件个数与拒绝惩罚和的排序问题是NP-困难的。 2.约束条件下加工时间恒定的工件可拒绝的排序问题。对于在拒绝惩罚和的约束条件下最小化最大完工时间的问题，在拒绝惩罚和的约束条件下最小化最大延迟/延误的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。收起

关键词 : 工件加工时间排序问题

3. 平行机上的在线排序问题研究

[学位论文] 刘培海华东理工大学 2008年博士导师: 鲁习文共100页

摘要 : 本文主要研究平行机上的几个在线排序问题以及半在线排序问题。我们主要研究这些排序问题的下界、设计算法并分析算法的竞争比。全文主要分为六部分内容。第一章主要介绍了组合优化、排序问题相关的一些概念，并介绍了在线排序以及半在线排序的... 展开本文主要研究平行机上的几个在线排序问题以及半在线排序问题。我们主要研究这些排序问题的下界、设计算法并分析算法的竞争比。全文主要分为六部分内容。第一章主要介绍了组合优化、排序问题相关的一些概念，并介绍了在线排序以及半在线排序的研究现状。第二章研究了同型机上的在线排序问题，目标为极小化所有工件的完工时间之和。这是在线排序中一个非常重要的问题，已经有了很多的研究成果。Vestjens证明了此问题的任何在线算法的竞争比不可能小于1.309，对具体的机器数m，这个结果可以做进一步改进。本文给出了此问题的一个在线算法DSPT，证明了这个算法的竞争比为2。这是目前最好的结果，也是大家一直希望得到的结果。第三章主要研究了两台同类机上的在线排序问题。两台同类机的速度分别为1和s(s≥1)。我们分别研究了不可中断和可中断两个排序模型。对不可中断的情形，我们研究目标函数为极小化完工时间之和的在线排序问题。我们证明了此问题的任何在线算法的竞争比不可能小于1.5，同时我们给出了一个2＋min(s/s＋1，1/s)—competitive的在线算法。而对可中断的情形，我们研究目标函数为极小化加权完工时间之和的在线排序问题，我们给出了一个竞争比为2的在线算法。第四章研究了同型机上带配送时间的在线排序问题，最优化准则是极小化所有工件最迟配送时间，即极小化Lmax。Vestjens[1]证明了此问题的任何在线算法的竞争比都不可能小于1.5。利用LDT(Largest Delivery Time)算法的思想，对机器数为2的情形，我们给出了此问题的一个在线算法，并证明了这个算法的竞争比为1.618。第五章主要研究了两台同类同型机上的半在线排序问题，目标函数为极小化最大完工时间。两台同类机，假设它们的速度分别为1和s(s≥1)。工件是从一个列表中逐个释放的(over list)。我们首先研究了一个带buffer的半在线问题。对带buffer的两台同类平行机上的半在线排序问题，我们给出了任意确定性在线算法的竞争比的下界，同时当s≥√2时，我们给出了一个竞争比为s＋2/s＋1等的最好可能的半在线算法，当1≤s≤√2，我们给出了一个2s＋2/s＋2-competitive的半在线算法。接下来，我们研究了已知工件最大加工时间的半在线排序问题。当1≤s≤1＋√17/4时，Cai和Yang给出了已知工件最大加工时间的半在线排序问题的一个2s＋2/2s＋1-competitive的半在线算法，同时他们证明了当1≤s≤1.192时，此问题不存在竞争比小于2s＋2/2s＋1的半在线算法。当s≥3.777时，他们证明了LS算法就是最优的在线算法。我们给出了一个更简单的算法，同时证明了当1≤s≤1＋√17/4时，这个算法都是最优的半在线算法。第六章研究了同型批处理机在线排序问题。一台批处理机一次可以把B个工件作为一批加工，批的加工时间由批中最长工件的加工时间决定。同一批中的工件具有相同的开工时间和完工时间。我们只考虑B=∞的情形。目标函数为极小化最大完工时间。我们给出了这个排序问题的下界1＋√m2＋4－m/2，同时我给出了一个最优的在线算法。收起

关键词 : 平行机排序问题在线算法

4. Ip范数下两台同类机在线排序问题的若干研究

[学位论文] 刘卯北京邮电大学 2013年硕士导师: 帅天平共51页

摘要 : 本文主要研究了Ip范数下两台同类机的几种半在线排序问题。该类问题可以描述为:给定两台同类机（两台机器速度不同但恒定）和一个按列表到达的工件序列，每个到达的工件必须实时的分配给两台同类机中的一个，且只有在当前工件被分配后后续工件才会到达... 展开

关键词 : 排序问题在线算法 Ip范数

5. 面向对象的排序问题方法研究

[学位论文] 席成新上海交通大学 1999年硕士导师: 田澎共45页

摘要 : 该文在回顾排序问题研究历史与现状的基础上,针对人们对排序认识的局限和求解方法上的重复劳动,采用面向对象方法来描述排序问题和排序求解方法,以实现对排序问题的扩展和排序求解方法的重用.围绕这一主线,该文首先对排序问题归纳分类,并以工件排序问... 展开

关键词 : 排序问题工件排序问题面向对象方法迭代启发式方法

6. 两类加工时间可变的现代排序问题

[学位论文] 刘春来沈阳师范大学 2012年硕士导师: 赵传立共52页

摘要 : 排序论是当前发展非常快速，研究十分活跃，成果相当丰硕的学科之一。经典排序问题中工件的加工时间是一个固定不变的常数。但是在某些实际生产生活中，工件的实际加工时间可能是某些因素的具体函数。本文讨论两类工件加工时间可变的现代排序问题。 ... 展开

关键词 : 工件加工时间可变排序问题

7. 开工时间不同的平行机排序问题的MULTIFIT算法更紧界的证明

[学位论文] 杨慧兰州大学 1999年硕士导师: 李志斌;王海明共19页

摘要 : 该文考虑开工时间不同的平行机排序问题,简记为NMSP.对于这类问题Soo Y.Chang和Hark-Chin Hwang证明了MULTIFTT的一个性能界指标为R(MF(k))≤9/7+1/2... 展开

关键词 : 平行机排序问题 MULTIFIT算法紧界

8. 若干新型排序问题的复杂性与算法研究

[学位论文] 李大伟华东理工大学 2019年博士导师: 鲁习文共125页

摘要 : 本文研究了若干新型排序问题，主要包括工件可拒绝的平行机代理排序问题、工件带退化和拒绝的分批排序问题、工件带退化和拒绝的多代理排序问题、带有人员不可用区间的两台机器流水车间排序问题以及工件可拒绝的供应链排序问题五个方面。针对不同的问... 展开本文研究了若干新型排序问题，主要包括工件可拒绝的平行机代理排序问题、工件带退化和拒绝的分批排序问题、工件带退化和拒绝的多代理排序问题、带有人员不可用区间的两台机器流水车间排序问题以及工件可拒绝的供应链排序问题五个方面。针对不同的问题，我们分别给出了相应的算法，并对一些问题的计算复杂性进行了分析。第一章首先给出了组合优化和排序论方面的一些基本概念和定义，然后介绍了与本文内容相关方向的研究现状，最后介绍了本文的主要研究成果。第二章研究了工件可拒绝的平行机代理排序问题。给定两个代理A和B以及两台平行机，每个代理有一批工件需要在机器上加工，两个代理的工件互不相同。对于任意一个工件，可以被拒绝并支付一定的拒绝费用，或者被接受并安排在机器上加工。目标是在代理B的接受工件对应的目标函数fB与拒绝B-工件的总拒绝费用之和不超过一给定上界的情况下，极小化代理A的接受工件对应的目标函数fA与拒绝A-工件的总拒绝费用之和，其中fA和fB分别是关于代理A和代理B的接受工件的完工时间的正则函数。我们研究了四种不同的目标函数组合，fA=∑CAj，fB∈{CBmax,LBmax,∑CBj，∑WBjUBj}。当(fA,fB)=(∑CAj，CBmax)，我们给出了两个伪多项式时间算法和一个(1+ε)-近似算法。对于其它三种情形，我们分别给出了伪多项式时间算法。第三章研究了工件带退化和拒绝的两代理单机排序问题。给定两个竞争关系的代理A和代理B，每个代理有一批T件需要在机器上加工，每个工件JXj的实际加工时间是其开工时间的线性增函数，目pXj=bXj(a+bt)，X∈{A B}，工件可以被拒绝。目标是在代理B的接受工件对应曰标函数fB与拒绝B-工件的总拒绝费用之和不超过一给定上界的情况下，极小化代理A的接受工件的总完工时间与拒绝A-工件的总拒绝费用之和，其中fB∈{CBmax，∑JBj∈ABCBj｝。对于这两种情形，我们分别基于动态规划的思想给出了算法和(1+ε)-近似算法。第四章研究了工件带退化和拒绝的分批排序问题。给定n个工件需要在一台无容量约束平行批处理机上加工，每个工件的实际加工时间是其开工时间的线性增函数，即pj=bjt，工件可以被拒绝。我们主要研究了下面的五种情形:(1)在拒绝工件的总拒绝费用不超过一给定上界的情况下，极小化接受工件的最大完工时间;(2)在接受工件的最大完工时间不超过一给定上界的情况下，极小化拒绝工件的总拒绝费用;(3)在拒绝工件的总拒绝费用不超过一给定卜界的情况下，极小化接受工件的总完工时间:(4)在接受工件的总完工时间不超过一给定上界的情况下，极小化拒绝工件的总拒绝费用:(5)在拒绝工件的总拒绝费用不超过一给定上界的情况下，极小化接受工件的最大延误。对于前两种情形，我们假设工件具有不同的到达时间;而对于后面三种情形，所有工件同时在t0时刻到达。我们证明了所有的情形都是NP-困难的，并且对于前四种情形，分别给出了动态规划算法和完全多项式时间近似方案（FPTAS）。第五章研究了带有人员不可用区间的两台机器流水作业排序问题。给定n个工件需要在两台机器上加工，每个工件Jj包含两道工序O1j，和O2j，加工时间分别为aj和bj，J=1.2，…,n。每个工件的工序相同，只有当第一道工序加工完成后，第二道工序才可以在第二台机器上加工。目标是极小化工件的最大完工时间，其中在第一道工序加工过程中存在一个人员不可用区间(s，s+L)，每道工序既不能在该区间内开工，也不能在该区间内完工。我们首先证明了，即使人员不可用区间的长度小于任意一个工件的第一道工序的加工时间，即aj＞L，j=1，2,…n，该问题仍是NP-困难的。然后我们证明了Johnson算法的最坏情形下的性能比是2并且界是紧的。最后我们给出了一个3/2-近似算法。第六章研究了工件可拒绝的供应链排序问题。给定n个工件和m台平行机，每个工件可以被拒绝并支付一定的拒绝费用，或者被接受并安排在m台平行机中的一台上加工，工件加工完成后需要分批配送给客户。不考虑配送时间，每批的配送费用是f，目标是极小化接受工件的最大完工时间与拒绝工件的总拒绝费用以及接受工件的总配送费用的加权和。我们首先指出了历史文献中存在的错误，然后给出了一个2-近似算法。收起

关键词 : 排序问题复杂性近似算法

9. 平行机半在线排序问题

[学位论文] 罗润梓上海大学 2005年博士导师: 孙世杰共105页

摘要 : 本文主要考虑平行机半在线排序问题.本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结果. 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负载.主要讨论两个问题：... 展开本文主要考虑平行机半在线排序问题.本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结果. 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负载.主要讨论两个问题：1三台同类机的情形，我们给出min3算法并且证明此算法的竞争比为max{r+1，3s+r+11+r+s}.min3算法是紧的且当1≤s≤2、r=1时是最优的.2m台特殊同类机问题，我们给出Cmin算法及其竞争比max{m-1，ms+m-1}，并证明Cmin算法是紧的且当1≤s≤(m-1)(m-2)(m≥3)时是最优的. 第三章考虑已知工件最大加工时间的半在线问题，目标为极小化机器最大负载.主要讨论四个问题：1对于两台同类机的问题，我们给出竞争比分别为2(s+1)s+2(1≤s≤2)和s+1(s＞2)的Qmax2算法，并且证明此算法是紧的且相应某些s的特殊值是最优的.2对于三台同类机半在线问题，我们给出Qmax3算法并证明此算法的竞争比不大于2(r+s+1)2r+s(1＜s≤2)和r+2s+1(s＞2)且严格小于2.3对于三台特殊同类机问题，给出Qmax3t算法并证明其竞争比不大于s+2(1≤s≤2)和s+2s(s＞2)且恒小于2.4最后我们考虑m台同型机问题，给出一个竞争比为2m-3的Cmax算法并证明此算法对任何m≥3是紧的. 第四章中，我们考虑已知工件总加工时间的两台同类机半在线问题，目标为极大化最小机器负载.我们给出Q2min算法并证明此算法的竞争比小于2+√22，而此问题竞争比的下界为1+√52.同时证明当s=1+√52时Q2min算法最优的. 在第五章中，我们考虑带机器准备时间的已知工件总加工时间的半在线问题.第一节考虑P2，ri｜sum｜Cmin问题，给出Prsum算法并证明此算法的竞争比为32且是最优算法.在第二节则考虑Q2，ri｜sum｜Cmax问题，给出Qrmax算法并证明此算法的竞争比为√2；同时给出此问题的一个下界. 第六章我们首先引进一个新的半在线术语：半在线模型的松弛，然后我们介绍一个新的半在线模型：已知工件最大加工时间在某一区域内，即knownlargestjobinterval模型.第一节考虑P2｜knownlargestjobinterval｜Cmax问题，我们给出Pinterval算法及其竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过433.第二节考虑P2｜knownlargestjobinterval｜Cmin问题，我们给出Pinterval算法的竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过14. 收起

关键词 : 排序问题半在线竞争比平行机

10. 若干MapReduce排序问题的算法研究

[学位论文] 周维浙江理工大学 2016年硕士导师: 蒋义伟共46页

摘要 : MapReduce是Google提出的一种编程模型，一个处理和生成大数据集的相关实现。本文主要研究了MapReduce平行机排序问题，对极小化最大完工时间(makespan)，论文研究了m台同类机离线和两台机在线排序模型。对极大化最小完工时间，文中研究了同型机离线排... 展开

关键词 : MapReduce编程排序问题完工时间