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

[学位论文] 李诠娜青岛大学 2008年硕士导师: 海进科共35页

摘要 : Basil Gordon在1960年为了研究完备Latin方首次引入可排序群的概念，并对有限的可排序交换群进行了完全分类，随后的几十年中，人们致力于对有限非交换群可排序性分类问题的研究，为了更好的研究这一问题，又先后引入了R-可排序群、对称排序、2-排序和... 展开

关键词 : 排序个数对称排序 2-排序超可排序群

2. 总和型目标排序问题及相关问题研究

[学位论文] 严羽洁浙江大学 2017年博士导师: 谈之奕共84页

摘要 : 排序问题是组合优化的一个重要分支，近年来经典排序与博弈论相结合而形成的排序博弈受到了学者的关注。本文主要研究排序博弈中的若干问题及部分有较强应用背景的排序问题，其中多数问题的目标函数为总和型目标，全文共分六章。第一章介绍了排... 展开排序问题是组合优化的一个重要分支，近年来经典排序与博弈论相结合而形成的排序博弈受到了学者的关注。本文主要研究排序博弈中的若干问题及部分有较强应用背景的排序问题，其中多数问题的目标函数为总和型目标，全文共分六章。第一章介绍了排序问题，排序博弈的基本概念与重要结果。第二章中，研究两个不同类机以极小化最大完工时间为社会费用的排序博弈模型Price of Anarchy(PoA)和Strong Price of Anarchy(SPoA)的下界。在第一个模型中机器遵循Shortest First规则，证明了对m台不同类机，PoA至少为m，并说明了界为紧界。在第二个模型中机器遵循EQUI规则，证明了对m台不同类机，SPoA至少为m。我们同时证明了任意不可中断，满足无关选择独立性和强局部性的规则的PoA和SPoA的下界至少为m，从而说明了Shortest First在这一类规则中的最优性。第三章研究两台同类机以极小化总完工时间为目标函数的排序问题Q2‖∑Cj，给出了机器数为2，且s≥2时SPT算法最坏情况界的参数上界与下界，且上界和下界均较已有结果有较大改进。第四章研究工件有不同大小的批排序问题。证明了m台平行机，即使所有工件加工时间均相等，以极小化最大完工时间为目标的批排序问题不可能有最坏情况界小于2的多项式时间近似算法，除非P=NP。对两台机，工件大小总和大于2这一特殊情形，给出了最坏情况界为1.95的改进算法。对单台机，工件具有相等加工时间，以极小化工件总完工时间为目标的批排序问题，给出了一个最坏情况界不超过9+√3/6的多项式时间近似算法，并证明了即使工件总大小不超过2，该问题也不存在FPTAS，除非P=NP。第五章研究了不可靠工件排序问题。主要考虑工件成功概率和收益满足一定关系的特殊情形，对目标为极大化总期望收益问题，我们给出一个新的双重排序算法DLS。借助求解凸规划，证明了对m台机，DLS算法的最坏情况界至多为1.1054;对两台机，最坏情况界至多为2+4√2/7，至少为1.0094。我们还考虑了瓶颈型目标，即目标为极小化所有机器的最大期望收益和极大化所有机器的最小期望收益的排序问题，证明了DLS算法的最坏情况界分别为4m-1/3m和4m-2/3m-1。第六章总结了本文的研究成果，给出了待研究的问题。收起

关键词 : 排序博弈总和型目标批排序双重排序算法

3. 具有约束关系的三类单机排序问题的研究

[学位论文] 成龙西北工业大学 2004年硕士导师: 刘小冬共71页

摘要 : 排序问题研究的是若干个任务要在一些机器上进行加工,如何安排机器和任务使得某些要求(目标函数)达到最优的问题.按处理机个数将排序问题分为:单机排序问题和多处理机排序问题;根据任务加工时间和到达时间以及处理机的工作环境等数据是确定的或服从某... 展开

关键词 : 排序最优排序在线最优排序 &rho 因子中断模型

4. 若干单机在线排序问题研究

[学位论文] 杨斌鑫西北工业大学 2004年硕士导师: 刘小冬共65页

摘要 : 该文选择单机排序问题为研究对象,并且研究单机排序问题的动态在线情况.首先建立了一般化中断模型,然后在此基础上研究了几类单机排序问题的动态在线最优排序问题.该文所做的工作如下:首先,我们一般化了任务中断模型.讨论了定义在更一般意义下的可中断... 展开

关键词 : 运筹学排序单机动态排序问题在线最优排序中断

5. 两种新型排序问题的近似算法——分批排序和柔性流水车间排序问题的研究

[学位论文] 任建锋曲阜师范大学 2003年硕士导师: 张玉忠共27页

摘要 : 论文主要内容包括两部分.第一部分针对m台同型机,工件具有到达时间的情况,研究了分批排序问题P<,m>|r<,j>,B|ΣC<,j>.由于1|r,B|ΣC<,j>为NP-hard的,因而P<,m>|r<,j>,B|ΣC<,j>也是NP-hard的.给出了当机器台数m及批容量B均为常数情况下的PTAS算法.第二部分研究了具有可用时间限制的... 展开

关键词 : 排序问题分批排序柔性流水车间排序

6. 在线排序与博弈排序研究

[学位论文] 成夏炎湖南师范大学 2020年博士导师: 李荣珩共111页

摘要 : 排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域出现了许多新的模... 展开排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域出现了许多新的模型和研究方法.作为现代排序中的在线排序和博弈排序,也取得了相当丰富的成果.本文研究了在平行机环境下的这两类排序问题.全文分为三章. 第一章简要介绍了组合优化以及排序问题,特别是在线排序和博弈排序的相关内容作了较为系统简洁地阐述,同时综述了在线排序和博弈排序的有关研究成果.另外,对我们取得的主要研究成果进行了梳理. 第二章讨论了同类平行机环境下工件有到达时间,目标函数为极小化最大完工时间的在线排序问题Qm|online,rj|Cmax(m≥2),分析了LS算法的竞争比.得到了机器环境为2台和不少于3台同类平行机时竞争比的紧界,分别是5+√5/2,4?4/m?1.另外给出了比LS算法的竞争比要好的算法MLS算法,并分析了其竞争比. 第三章主要研究的是相同平行机环境下机器和工件均具有自私性的二元平衡博弈排序问题Pm||Cmax(m≥2).此模型中,工件和机器因自私性,均为各自的目标函数而相互进行博弈.当博弈形成一种稳定的平衡状态时,均不会使工件和机器各自的决策发生改变,这种平衡状态被称为二元平衡状态,简写成DE.本章采用权函数的方法,通过对比DE状态下和最优状态下的工件排序情况确定最大完工时间来分析PoA.首先讨论了2台机器的情况,得到了8/7这个PoA的紧界,并给出了以工件长度相似系数r为参数的PoA结果,是一个关于r的分段函数.接着,讨论了机器数3≤m≤9时,4/3为DE状态PoA的一个上界,且是紧界.当m≥10时,得到7/5?9/5(5m-3)为PoA的一个上界.这比此前该模型仅有的结果7/5要好. 收起

关键词 : 在线排序博弈排序竞争比

7. 关于重新排序问题的研究

[学位论文] 慕运动郑州大学 2007年博士导师: 原晋江共112页

摘要 : 排序就是在一定的约束条件下对若干个要加工的工件或任务在指定的机器上按时间进度进行分配和调度，使某一个或某一些指标达到最优。重新排序问题是一种新型的排序模型．它有着重要的实际应用背景．生产部门根据自己的生产计划或是由客户提出的... 展开排序就是在一定的约束条件下对若干个要加工的工件或任务在指定的机器上按时间进度进行分配和调度，使某一个或某一些指标达到最优。重新排序问题是一种新型的排序模型．它有着重要的实际应用背景．生产部门根据自己的生产计划或是由客户提出的要求，在生产前一定时期内事先有一个作业方案，将已有的任务或订单按照某一规则安排好，使某一目标值最优．但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达．这时就要把新的任务和原有的还未加工的任务一起加工．为了不失信于对原客户的承诺或耽误原任务的完成，这就要求在原有的工件或任务的次序不至于打乱的过多的前提下，使得总的目标函数值达到最优．Hall和Potts(2004)在前人研究的基础上，系统地研究了重新排序问题．他们引入了序列错位(sequence disruption)和时间错位(time disruption)的概念，研究了在原来最优排序和任意排序的基础上重新排序，在原来排序的序列错位和时间错位不至于太大的情况下，使目标函数最优的问题。多目标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出现的复杂问题中起着越来越重要的作用．例如，在一个工厂的生产过程中，生产决策者不但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个数最少，以更好地满足顾客的要求．多目标排序包括字典序最优问题、Perato最优解问题和组合目标函数最优问题。在线排序是指每个工件的信息在该工件到达之前是未知的．在工件的到达时间得到该工件的所有信息并允许对该工件进行加工；而且一旦决定工件的安排就不允许改变．而离线排序在安排所有工件之前便知道所有工件的信息．衡量一个在线排序算法最常用的指标是它的竞争度(competitiveness)，即把在线排序算法的结果与对相同工件运用离线排序算法得到的最优排序的结果进行比较．更确切的说，我们用竞争比(competitive ratio)ρ来衡量一个在线排序算法的性能．对于使目标函数为最小的在线排序问题，竞争比ρ定义为对问题的所有实例的比值C/C<,0>的上确界，其中C和C<,0>分别表示由这个在线排序算法得到的目标函数值和相应的离线排序的最优值。本文的内容分四部分：第一部分研究了几种特殊情形的重新排序模型(第二章)．第二部分研究了一种新型重新排序模型(第三章)。第三部分研究了多目标的重新排序问题(第四章)．第四部分研究了在线的重新排序问题(第五章)。在第二章中，研究了几种特殊情形的重新排序模型，其主要结果如下：对一些未解问题和强NP-困难问题， (1)给出了当工件的加工时间与工期相容或原始工件保持其相对顺序时，使得最大延迟和加工时间和为最小的多项式或拟多项式时间算法；(2)给出了当工件具有相同的加工时间或具有相同的工期时，使得误工和为最小的多项式或拟多项式时间算法； (3)给出了当工件的加工时间与权重反相容时，使得加权完工时间和为最小的多项式或拟多项式时间算法。在第三章中，对于具有到达时间的最小化最大完工时间的重新排序问题，(1)给出了在最大序列错位约束下的最小化最大完工时间的重新排序问题的多项式时间算法； (2)给出了在总序列错位和约束下的最小化最大完工时间的重新排序问题的多项式时间算法； (3)证明了在最大时间错位或总时间错位约束下的最小化最大完工时间的重新排序问题是强NP-困难的。在第四章中，对于多目标的重新排序问题，本文将错位量作为第二目标来考察，研究了四种错位量(D<,max>(π)，∑D<,j>(π))与传统的目标函数(如C<,max>，L<,max>，∑w<,j>C<,j>)的相互组合问题，给出了多目标排序中字典序最优问题、Perato最优解问题和线性组合目标函数最优问题的多项式时间算法或拟多项式时间算法。在第五章中，主要研究了在线重新排序问题．即在原始工件已经按照某一规则排好，而新工件在原始工件的加工过程中是按时间顺序到达的．在此情形下，本文分别给出了在各种错位量约束下，目标函数为最小化最大延迟的竞争比为2的在线排序算法和最小化最大完工时间的竞争比为3/2的在线排序算法。收起

关键词 : 排序重新排序多目标排序在线排序错位量动态规划计算复杂性

8. 带运输的离线和半在线排序问题的研究

[学位论文] 张志敏华东理工大学 2006年硕士导师: 鲁习文共40页

摘要 : 本文研究的是离线和半在线情况下带运输的排序问题。工件先在机器上加工，然后由运输机运往同一个目的地。我们的目标是运输机运完最后一批工件回来的时间最早，其中加工机器为单机或者平行机，运输机为单台或者多台。对于离线情况下的带运输排... 展开

关键词 : 带运输排序问题近似算法离线排序半在线排序

9. 多排序者下排序集抽样的均值估计

[学位论文] 周焜华中师范大学 2013年硕士导师: 谢民育共25页

摘要 : 排序集抽样(Rankedsetsampling简称RSS)和后分层排序抽样(Judgmentpoststratified简称JPS)是两种比简单随机抽样(Simplerandomsampling简称SRS)更为有效的数据收集方式，在相同容量的样本下能包含更多的总体信息，因此基于RSS和JPS两种抽样方法的统计... 展开

关键词 : 多排序者排序集抽样后分层排序抽样总体均值

10. 在线排序和批排序问题研究

[学位论文] 李融奇浙江大学 2018年博士导师: 谈之奕共117页

摘要 : 排序问题是一类重要的组合优化问题，随着实际应用和理论研究的不断深入，产生了各种不同的排序问题模型.本文主要研究经典平行机在线、半在线排序问题和单台机上的批排序问题，侧重于不同模型下近似算法的设计以及最坏情况分析.本文共分为五章. ... 展开

关键词 : 在线排序批排序组合优化