工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

工件加工时间是开工时间线性函数的单机排序问题

研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <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/α.     

各机器具有相同加工时间的Flow Shop 成组排序问题

本文讨论了m台机器的Folw Shop成组排序问题，工件在不同机器上的加工时间相同，目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。     

具有截断学习效应和工件带准备时间的单机排序问题

研究工件加工时间具有截断学习效应且带有准备时间的单机排序问题。截断学习效应指的是工件的加工时间是它所排位置和一个控制参数的函数,其中,“截断”是一个控制参数。由于在现实生活中,与工件的排列位置有关的“学习”不可能无止境的进行下去,所以给定了一个参数来进行控制,使得工件的学习效应随着排列位置的靠后而逐渐趋于稳定。目标函数为最小化总完工时间,这个问题是NP-难的,进而结合几个优势性质和下界给出了分支定界算法来求此问题的最优解。     

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

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

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax     

加工时间可控和恶化的单机最大完工时间排序

本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩;加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.     

基于判别超图和非负矩阵分解的人脸识别方法

非负矩阵分解是一种流行的数据表示方法,已广泛应用于图像处理和模式识别等问题.但是非负矩阵分解忽略了数据的几何结构. 而现有的基于简单图的学习方法只考虑了图像的成对信息,并且对计算相似度时的参数选择非常敏感. 超图学习方法可以有效地解决这些问题. 超图利用超边将多个顶点相连接用以表示图像的高维结构信息. 然而, 现有的大部分超图学习方法都是无判别的学习方法.为了提高识别效果, 提出了基于具有判别信息的超图和非负矩阵分解方法的新模型, 利用交替方向法进行迭代求解新模型, 并结合最近邻方法进行人脸识别. 在几个常用标准人脸图像数据库上进行实验, 实验结果表明提出的方法是有效的.     

Updating and downdating an upper trapezoidal sparse orthogonal factorization{dagger}

^** Email: santos{at}ctima.uma.es^*** Corresponding Author. Email: pablito{at}ctima.uma.es We describe how to update and downdate an upper trapezoidalsparse orthogonal factorization, namely the sparse QR factorizationof A_k^T, where A_k is a ‘tall and thin’ full columnrank matrix formed with a subset of the columns of a fixed matrixA. In order to do this, we have adapted Saunders' techniquesof the early 1970s for square matrices, to rectangular matrices(with fewer columns than rows) by using the static data structureof George and Heath of the early 1980s but allowing row downdatingon it. An implicitly determined column permutation allows usto dispense with computing a new ordering after each update/downdate;it fits well into the LINPACK downdating algorithm and ensuresthat the updated trapezoidal factor will remain sparse. We giveall the necessary formulae even if the orthogonal factor isnot available, and we comment on our implementation using thesparse toolbox of MATLAB 5.     

Strictly nonnegative tensors and nonnegative tensor partition

We introduce a new class of nonnegative tensors—strictly nonnegative tensors.A weakly irreducible nonnegative tensor is a strictly nonnegative tensor but not vice versa.We show that the spectral radius of a strictly nonnegative tensor is always positive.We give some necessary and su?cient conditions for the six wellconditional classes of nonnegative tensors,introduced in the literature,and a full relationship picture about strictly nonnegative tensors with these six classes of nonnegative tensors.We then establish global R-linear convergence of a power method for finding the spectral radius of a nonnegative tensor under the condition of weak irreducibility.We show that for a nonnegative tensor T,there always exists a partition of the index set such that every tensor induced by the partition is weakly irreducible;and the spectral radius of T can be obtained from those spectral radii of the induced tensors.In this way,we develop a convergent algorithm for finding the spectral radius of a general nonnegative tensor without any additional assumption.Some preliminary numerical results show the feasibility and effectiveness of the algorithm.     

Linear convergence of an algorithm for largest singular value of a nonnegative rectangular tensor

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284–294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption.     

Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor

An iterative method for finding the largest eigenvalue of a nonnegative tensor was proposed by Ng, Qi, and Zhou in 2009. In this paper, we establish an explicit linear convergence rate of the Ng–Qi–Zhou method for essentially positive tensors. Numerical results are given to demonstrate linear convergence of the Ng–Qi–Zhou algorithm for essentially positive tensors. Copyright © 2011 John Wiley & Sons, Ltd.     

A CLASS OF FACTORIZATION UPDATE ALGORITHM FOR SOLVING SYSTEMS OF SPARSE NONLINEAR EQUATIONS

ＡＣＬＡＳＳＯＦＦＡＣＴＯＲＩＺＡＴＩＯＮＵＰＤＡＴＥＡＬＧＯＲＩＴＨＭＦＯＲＳＯＬＶＩＮＧＳＹＳＴＥＭＳＯＦＳＰＡＲＳＥＮＯＮＬＩＮＥＡＲＥＱＵＡＴＩＯＮＳＢＡＩＺＨＯＮＧＺＨＩ（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔａｔｉｏｎａｌＭａｔｈｅｍａｔｉｃ...     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

An iterative algorithm for low-rank tensor completion problem with sparse noise and missing values

Robust low-rank tensor completion plays an important role in multidimensional data analysis against different degradations, such as sparse noise, and missing entries, and has a variety of applications in image processing and computer vision. In this paper, an optimization model for low-rank tensor completion problems is proposed and a block coordinate descent algorithm is developed to solve this model. It is shown that for one of the subproblems, the closed-form solution exists and for the other, a Riemannian conjugate gradient algorithm is used. In particular, when all elements are known, that is, no missing values, the block coordinate descent is simplified in the sense that both subproblems have closed-form solutions. The convergence analysis is established without requiring the latter subproblem to be solved exactly. Numerical experiments illustrate that the proposed model with the algorithm is feasible and effective.     

A lifting and recombination algorithm for rational factorization of sparse polynomials

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.