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

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为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/α.     

一类带核的平行机排序问题

研究了一类工件具有相似加工时间的带核的平行机排序问题,运用ＬＰＴ算法求解,得到ＬＰＴ算法界的精确估计并对问题的某些情形,给出了界紧的例子。     

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。     

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

同类机下的供应链排序及转包策略

研究了一类工件排序与转包关联的模型,即工件既可以在制造商的同类机上加工,也可以较高费用转包给某个承包商加工.需要确定被转包的工件集,以及未转包工件的加工顺序,使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小.证明了该问题的NP困难性,用数学规划方法构造多项式时间近似算法,并分析算法性能比.     

提前预知信息的在线分批排序问题

研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{\rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$\gamma H^\infty$, 并证明其竞争比和问题的下界都为~$1+\gamma$, 其中~$\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$, 进而算法是最优的.     

可拒绝的同类机在线排序(英文)

考虑了带拒绝费用的在线同类机排序模型.工件一个一个的到达,到达后或被接受,或以一定的费用被拒绝,目标是最小化最大完工时间与总的拒绝费用之和.我们提供了一个在线算法和分析了算法的竞赛比.     

两台可拒绝同类机在线排序问题近似算法的参数性能比

讨论两台可拒绝同类机在线排序问题的近似算法。设两台机器的速度之比为ｓ（≥１）。工件逐个到位,可以被加工,也可以被拒绝,但要付出相应的罚值ｐｊ。并且只有在安排完当前工件之后,下一个工件才到达。目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小。文中设计出线性时间的ＲＬＳ（α）算法,并证明了其关于ｓ的参数紧界,这个界于ｓ＝１以及ｓ≥（５＋１）／２均是不可改进的。     

排序问题中优化准则关于基本参数的正则性及其应用

本文提出了优化准则关于加工时间、准备时间、应交工时间的正则性，利用这种正则性对寻找参数可控排序问题中的有效值、有效解给出了一直观算法，并指出对一些具体的参数可控排序问题，其有效值、有效解的寻找可通过对这一直观算法加以具体化而得．文中还对平均流程问题给出了这样一个具体化算法．     

一类新的分批排序问题的NP完备性证明

本文研究了加权的延迟工作和的排序问题,即极小化的批处理问题, 其中.本文主要考虑了B≥n的情形,即 证明了这个问题是NP-完备的.     

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

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

THE SINE TRANSFORM OPERATOR IN THE BANACH SPACE OF SYMMETRIC MATRICES AND ITS APPLICATION IN IMAGE RESTORATION

In this paper, we study an operator s which maps every n-by-n symmetric matrix A, to a matrix s(A_n) that minimizes || B_n-A_n || F over the set of all matrices B_n, that can be diagonalized by the sine transform. The matrix s(A_n), called the optimal sine transform preconditioner, is defined for any n-by-n symmetric matrices A_n. The cost of constructing s(A_n) is the same as that of optimal circulant preconditioner c(A_n) which is defined in [8], The s(A_n) has been proved in [6] to be a good preconditioner in solving symmetric Toeplitz systems with the preconditioned conjugate gradient (PCG) method. In this paper, we discuss the algebraic and geometric properties of the operator s, and compute its operator norms in Banach spaces of symmetric matrices. Some numerical tests and an application in image restoration are also given.     

在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。     

预知工件大小上界的平行机排序问题

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡,大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:C_(max)(极小化机器最大负载makespan)和C_(min)(极大化机器最小负载).在不同的目标下,针对m台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.     

关于具有主次指标的单机排序的注记

本文讨论具有主次指标的单机同工期排序问题,其主指标和次指标取为:最大误时、总流程、误时工件数、总误时、加权总流程、加权误时工件数以及加权总误时。     

平行机的实时到达on-line算法下界的改进

本文考虑了平行机实时到达的在线问题,模型中,工件是陆续到达的,工件的个数,到达时间是事先未知的,而且只有当工件到达,才知其加工时间,目标是使所有工件都加工完成的时间达到最小。     

SUMUDU TRANSFORM IN BICOMPLEX SPACE AND ITS APPLICATIONS

In this paper, we define Sumudu transform with convergence conditions in bicomplex space. Also, we derive some of its basic properties and its inverse. Applications of bicomplex Sumudu transform are illustrated to find the solution of differential equation of bicomplex-valued functions and find the solution for Cartesian transverse electric magnetic (TEM) waves in homogeneous space.