排序问题

写些短文的动机是想用一个更浅显的例子(跟组合群试比较 )解释“优化问题”中的组合概率论方法 ,包括不确定性的数量刻画、信息下界等概念 ,顺便纠正组合群试一文中的打印错误 .问题的提法 :ｎ个重量互不相同的球 ,通过在天平上比较可以确定两个球谁轻谁重 ,问立足于最坏可能 ,把它们按从最轻到最重的次序排列出来 ,需要使用几次天平 ?一个完整的方案遇到不同的中间结果 ,所需要使用天平的次数可能是不同的 ,但我们只关注这个方案遇到最倒霉的情形所需要的使用天平的(最大 )次数 .两个不同的方案 ,当然是那个这一(最大 )次数小的方案好 .问…     

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

排序问题中的一些数学问题

一、绪言§1.什么是排序问题在某一加工机器零件的车间里有若干台机器,它们的工作是随时对一些输送进来的零件进行加工.各个零件依照工艺技术上的要求,按一定的加工次序通过这些机器.我们设一台机器同时只能加工一个零件.若现在有许多个零件等着要进行加工,这时就可能出现这样的现象:有好些零件同时都需要在某一台机器上进行加工,但因为这台机器     

一类资源约束排序问题

引入与研究 1| pj=fj( uj) ,∑uj U| ∑ ( wj Cj+ uj)型资源约束排序问题 .针对系统中加工顺序确定的情况 ,给出三个寻求最优资源分配的算法 ;就 fj=f和 fj=bj+ g,wj=w等情况研究系统的最优排序 .     

机器维修的排序问题

研究了机器维修的排序问题,假设第i台机器的维修起始日期为第αi天(i=1,2,…,n)．n台机器的维修起始日期简记为(α1,α2,…,αn),得到一系列(α1,α2,…,αn)存在的充分或必要条件。     

并行分批排序问题综述

并行分批排序是兴起于上世纪末的一类新型排序问题，它最初来源于半导体生产中的芯片测试过程，有重要的应用价值，在理论上也有重要的意义．因此，并行分批排序问题近年来受到了越来越广泛的关注，新的研究成果不断涌现．本文就并行分批排序问题的最新进展作了全面的介绍，指出了许多尚未解决的问题和许多新的研究方向，给出了丰富的参考文献，旨在把感兴趣的读者迅速带到此研究领域的前沿．     

排序问题中的凸性

凸性在连续性最优化理论中起着重要的作用，它在离散性最优化中的相应概念尚待研究，本文运用差分和次梯度的概念给出排序问题中离散凸性的描述，并指出凸性在构造最优排序中的重要性。     

一类新的可控排序问题

本文讨论了一类新的加工时间可控的单机排序问题,我们所考虑的目标函数由所有工件的加权完工时间之和与对所有工件的实际加工时间偏离额定加工时间的最大满意程度这两部分组成,对此问题,我们提出了一个多项式算法。     

一类排序问题及其求解

我们研究如下的排序问题:有 n 批“顾客”(零件、原料、…),它们的批号为1,2,…,n.分别进入 m 个“服务台”(机器,仓库,…)接受服务(加工,处理,…).只要 m 个服务台有一个空闲,那么一批顾客便同时到达,排队等侯服务.设每个顾客所需的服务时间是相同的,而第 i 个服务台需要接纳第 j 批顾客的数量为 q_(ij),试确定 n 批顾客的输入顺序σ,使最大队长总和 f_1(σ)最小.     

运筹学中的一个排序问题

设有n个零件J_1,…,J_n要在一台机器上加工,它们的加工时间p_1,…,p_n和应交工时间d_1,…,d_n事先已知.试将J_1,…,J_n安排一个加工顺序,使得总的延误时间最少.     

一类资源分配与排序问题

给出与研究1 rj=bj-ajuj,∑uj U-∑uj+Cm ax型资源分配与排序问题.对于系统中加工顺序确定的情况给出并证明一个寻求其最优资源分配的多项式算法;就系统参量的某些特殊情况研究系统的最优排序.     

一类排序问题的最优解

本文讨论了将多个零件分派给多台机床加工的一类排序问题,机床的工效可以不一样,但假设零件在不同机床上的加工时间成比例.给出了使总花费时间最小的计算方法,这是一种多项式算法.当零件在所有机床上的加工时间与在其中某一机床上的加工时间之比均 为正整数时,进一步给出一种更为简便的算法——标号法.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

货物装卸中的一个排序问题

本文考虑货物装卸管理中船主和港口之间的下述相互制约关系：有n条船在时刻零同时抵达同一码头装卸货物,因而也希望在同一时刻守成装卸货物。如某船的货物不能如期装卸守而延误了该船的离港,船主会向港方索取赔偿,反之如货物提前装卸完而使该船河提前投入运输,则船主会向港方付取奖金,加上正常装卸费用,从港方来说要适当考虑n条船的一个装卸顺序,使总费用减少,对这一NP-困难的排序问题,文中给出了几个多项式可解的特殊情形,一般情况下的一个快速下界估计方法以及相应的分支定界算法。     

颤振分析中的特征值排序问题

颤振分析中判断颤振临界速度的重要依据是系统V-g和V-f图,即系统特征值随参数的变化曲线.在几乎所有商用软件及自编程序的输出结果中,有时会出现所谓的"窜支"现象,这给颤振临界速度和颤振穿越分支及耦合形式的判断带来很大不便.通过隐函数定理可以证明,除重特征值点以外,系统特征值连续依赖于系统参数变化.依据多元向量值函数连续性,建立对特征值的排列算法,给出系统特征根轨迹的正确曲线,再输出V-g和V-f图数据,从而避免"窜支"现象.编制应用程序,通过几个典型算例对算法进行了验证.该工作能够有效简化颤振分析的后处理工作,提高分析效率.     

机器加工能力受限制的排序问题

本文研究上海港长江口深水航道大型重载船舶的通行问题.利用排序论的理论和方法,把这个问题转换成机器加工能力受到限制的新型排序问题,提出解决这个问题的两个算法,并证明其中一个算法的最优性.     

排序问题的一个判别条件和一类特殊的m×n排序问题

一、引言 在排序理论的一篇开创性的文章中,Johnson给出了2×n排序问题(二台“机床”,n个“零件”的同顺序排序问题,这里机床和零件被理解成广义的)的最优顺序的算法。在导出这算法时,Johnson给出的判别两个相邻零件的先后次序的一个条件起着关键作用。这判别条件是:设i,j是相邻的两个零件,α_i和b_i(α_j,b_j)是i(j)分别在机床M_1和M_2上的加工时间,如     

排序问题的线性规划松弛方法

本文研究排序问题的线性规划松弛方法，对单台机器排序问题1｜prec｜∑wjCj介绍基于三个确定性线性规划松弛的2一近似算法，对平行机排序问题R｜rij｜（wjCj）介绍基于随机线性规划松弛的2-近似算法。这后一个算法对排序问题R｜（wjCj｜是3／2-近似算法．     

装配系统的供应链排序问题

在装配系统中,有多个供应商向同一个制造商提供零部件,仅当一个产品的所有零部件都送到后,制造商才进行最后的组装与发送.假设制造商为非瓶颈式生产.研究目标为工件带权完工时间和及最大延误的装配系统供应链排序问题,利用排序的理论和方法,分别设计多项式时间算法,并分析算法的性能比.