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

本文考虑下述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时,     

有准备时间的最小带权误工工件数问题的最优解

设有工件集合N={J_1,…,J_n}要在一台机器上加工,已知J_i的准备时间、加工时间、应交工期和权分别为r_i、p_i、d_i和w_i(i=1,…,n)。问如何安排工件的加工顺序,使带权的误工工件数最小? 加工顺序确定了J_i的完工时间C_i(i=1,…,n)。当C_i≤d_i定义U_i=0,否则U_i=1本文假定r_i满足:对于我们的问题记为: (P) 当w_i≡1时,Kise等给出O(n~2)的算法求其最优解。当r_i≡0时该问题已被证明是完全的。Lawler曾用动态规划方法求其最优解。我们对r_i不为零的(P),建立了消去准则,构造了分支定界算法求其最优解,并在微机上进行了试算。     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

最小化最大加权完工时间重新排序研究

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是: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-困难的.     

带批运输的两台同型机排序问题的改进算法

研究带批运输的两台同型机排序问题. 在该问题中,工件在两台同型机上加工,完工的工件由一辆容量为z的车运输到客户. 这里假设工件有不同的物理大小,目标是求一个时间表使得所有工件送达客户且车回到机器所在位置的时间最小,给出了一个(14/9+ε)-近似算法     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

同时加工排序问题的分支定界法和启发式算法

同时加工机器或者称为批加工机器是可以同时加工多个工件的机器．本文研究使带权总完工时间为最小的同时加工排序问题1|B|∑wjGj.这个问题的计算复杂性还没有解决．我们给出这个问题的精确解法——分支定界法和几个启发式算法，并且用较多实例对启发式算法的性能进行了比较．     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

H-矩阵的实用判定及谱分布

1引言及记号因为非奇异H-矩阵主对角元非零,所以本文总假定所涉及矩阵主对角元非零,并且设A=(aij)∈Cn×n为n阶复方阵,N={1,2,…,n}．记N1={i∈N |Pi(A)<|aii|Pi(A)}, N4={i∈N | |aii|≥Pi(A)>Ri(A)}, N5={i∈N | |aii|>Pi(A)=Ri(A)},N0={i∈N | |aii|≤Ri(A),|aii|≤Pi(A)},即N=N1∪N2∪N3∪N4∪N5∪N0．     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

分支定界法求解最小带权误工工件数排序

设有n个工件J_1,J_2,…,J_n要在一台机器上加工。已知工件J_i的工时(加工时间)是Pi,工期(预定交付期限)是d_i,权(工件误工时,即在工期之后完工所造成的损失)是w_i.记s=(s(1),…,s(n))为1,2,…,n的一个排列(置换),并记S为1,2,…,n所有排列的全体。如何在S中寻找一个排列s,使在按照次序J_(s(1)),J_(s(2))…,J_(s(n))进行加     

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

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

一类带机器准备时间的排序复杂性及算法

1引言文[2-4]中考虑了如下定义的一个排序模型：m台同型机器加工n个工件，每个工件在零时刻到达，第i个工件需加工时间pi,而各机器有各自的准备时间Tj≥0,怎样安排工件加工顺序，使机器总完工时间（makespan）尽可能早．这是一个强NP-完全问题．本文考虑增加这样一个约束，即每     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

具有学习效应的非同类机资源约束排序问题研究

研究具有学习效应和资源约束的非同类平行机排序,即工件的加工时间与所排机器,所排位置和所用资源都有关系.目地是确定每台机器所分配的工件及其排序和所用的资源量,使所有工件的总完工时间和总资源消耗费用的加权和最小.在非同类机的数量给定的情况下,证明了这个问题能够在多项式时间内解决,并给出了一个例子来说明问题是如何求解的.