关于同顺序m×n排序问题消去法的两点注记

本文对[1,2]中指出的一类同顺序m×n排序问题有关的消去法提出两点注记。这里补充提出了一种不涉及下界计算并且检验方法简单的消去准则,同时,对[2]中给出的下界B(S…S′)的算法做了改进,从而使下界B(S…S′)的估值精度有所提高。 一、一个消去准则 首先说明,文中运用的术语和记号除特殊说明外均与[2]的定义相同,不再另述。 同顺序m×n排序问题是指:设有n个零件J_1,J_2,…,J_n和m台机床M_1,M_2,     

n个零件在m台机床上的加工顺序问题(Ⅰ)

在工厂的零件加工车间,设有n个零件要在m台机床上加工,各零件根据工艺上的要求,按一定顺序通过这些机床,如何安排这些零件顺序使预先给定的指标达到最优,这就是运筹学中所谓的排序问题。本文所考虑的排序问题:假设1)各零件皆依同一顺序通过这些机床;2)每个零件的加工时间为已知;3)每个机床在同一时间。只能加工一个零件。目的是要寻求一个顺序,使总的加工时间为最短。我们所得到的主要结果如下:1.设ω为(1…n)的某一排列,ω’为从ω经交换相邻两数字i和′的位置后的排列,T(ω)和T(ω′)分别表示在ω和ω’之下总加工时间,则当时,有T(ω)≤T(ω′)。2.我们所给出的条件比Nabeshima所给出的条件要弱。3.从推广Johnson法则这一角度看,本文定理4的结果已是最好的结果。     

P-J型的一类最优服务的排序问题

排序问题自Johnson提出后,长期以来对于多台机床的情形,一直进展不大。直到1975年越民义、韩继业才把这一问题大大向前推进了一步。到目前为止,关于同顺序的排序问题,越-韩条件算是最好的结果了。对于n个零件于单台机床上加工的最优排序问题,越民义、韩继业在文献[3]中作了系统的整理。Lawler在分段与加权之后,也得到了一些较好的结果。然而,上述作者所研究的问题,均以单位时间内诸零件     

同顺序M×N排序问题的动态规划方法

排序论(Scheduliny Theory)是组合最优化理论中一个应用十分广泛的领域;而同顺序m×n排序问题则是众多的排序模型中一个成果较多的模型.1954年,S.M.Johson给出m=2情形的解法,揭开排序问题研究的序幕.一些动态规划、组合最优化和图论文献都以此作为有趣的例子竞相引用.嗣后,许多作者企图把Johnson算法推广到m≥3的情形.但1976年Garey等人证明了m≥3情形是一个“NP完全问题”.这样,要想找到“好算法”几乎是没有希望的了.近年来,m≥3的m×n排序问题的研究,主要在如下几个方面:     

机器维修的排序问题

研究了机器维修的排序问题,假设第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(σ)最小.     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.     

一类排序问题的最优解

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

一致条件下具学习因子的几个单机排序问题

n个工件需在同台机器上依次加工，工件j,j=1，2，…，n所需的正常加工时间为pj,如在某序中工件j第r个加工，则机器对其实际加工的时间为pjr^α，其中α≤0为一学习因子．要求适当排列这n个工件的加工顺序，使某目标函数达最小．本文对加权完工时间之和，最大迟后，延误工件数这三个目标函数，给出了在相应的一致条件下，对应的WSPT规则，EDD规则，修正Moore-Hodgson算法可获最优序，并估计了在一般情况下由该三规则所获序的误差．     

工件加工可拒绝的无界批量分批排序问题的几点探讨

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.     

无关机上极小化求和问题的平行分批排序(英文)

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.     

无关机上极小化求和问题的平行分批排序（英）

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对$p_{ij}\leq p_{ik}$ $(i=1, \cdots, m; 1\leq j\neq k\leq n)$这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了$p_{ij}=p_{i}$ $(i=1, \cdots, m; j=1,\cdots, n)$这种情况, 当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.     

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.     

m×n排序问题在实际中的应用

本文对某工厂生产实际中的一个零件加工顺序问题(m=12,n=45)建立了两个模型,并应用在计算机上易实现的一个排序问题的算法进行了计算,两个模型都使该厂每年的生产时间缩短至少100天,模型二还大大增加了生产量,从而提高了生产效率。     

关于欧氏空间正交变换的存在性问题

给出无限维欧氏空间上正交变换存在性问题的两个结论:设V1,V2是欧氏空间V的两个有限维子空间,且dimV1=dimV2,则存在V的正交变换σ,使得σ(V1)=V2;设α1,α2,…,αr和β1,β2,…,βr为欧氏空间V中两个向量组,则存在V的正交变换σ,使得σ(αi)=βi(i=1,2,…,r)的充要条件是(αi,αj)=(βi,βj)(i,j=1,2,…,r).     

单机排序中一个极小最大绝对迟后问题

本文考虑n个工件在单机上加工的排序问题,工作j的预期开始加工时间和所需加工时间分别为αj,pj,应交工时间为dj=αj kpj d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。     

排序原理与排序思想

排序原理已为广大读者所熟悉,在不等式的证明和最优化设计方面有广泛的用途,同时与排序原理相关的排序思想,在解某些组合问题时,也很有用。兹各举一例。例1 已知a,b∈R~ ,a≠b;求证: a~n b~n≥a~(n-k)b~k a~kb~(n-k)(n>k,n、k∈N)。本例可用比较法证,但用排序原理证也甚简单。证明不妨设a>b>0,则a~(n-k)>b~(n-k),a~k>b~k,由排序原理知,同序最大,即a~n b~n=a~(n-k)。a~k b~(n-k)·b~k≥a~(n-k)b~n a~nb~(n-k)。例2 三个工人同时到同一车床加工零件,每个工人加工零件的时间互不相同;问怎样安排加工零件的顺序,使三个工人互相等待的总时间最短? 这是一个最优化问题,用排序原理处理简     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力,用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达,每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.     

一类资源约束排序问题

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

一个单台机器排序问题的下界

本文考虑下述n个工件在一台机器上加工的排序问题。其中d_i,C_i,w_i和h_i分别为工件i的应交工时间、完工时间、延误权因子和成本权因子。工件i所需的加工时间为p_i,所有工件在时间t=0时同时到达机器旁,机器不允许空转,工件被加工时不允许中断。本文用一O(n)快速方法给出(P)的一个下界。对问题(P),当取O≤u_i≤w_i,i=1,2,…,n时,