A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

光学系统的副像及其消除方法的探讨

视准式光学系统瞄准具的成像有主像和副像两种情形,主像是对目标瞄准的必要标志,副像则对目标的瞄准产生不良影响,为消除或减弱光学系统所成的副像对瞄准精度的影响,主要分析了光学系统中中心反射镜的反射和有无平行差时产生副像的原因.提出了消除或减弱副像的多项措施,并针对中心反射镜提出了两种截然相反地改进方法.可有效地消除或减弱副像所引起的不良干扰对飞行人员视觉的影响,有效地提高了观察效果和瞄准精度.     

Solution algorithms for the parallel replacement problem under economy of scale

We consider the parallel replacement problem in which machine investment costs exhibit economy of scale which is modeled through associating both fixed and variable costs with machine investment costs. Both finite- and infinite-horizon cases are investigated. Under the three assumptions made in the literature on the problem parameters, we show that the finite-horizon problem with time-varying parameters is equivalent to a shortest path problem and hence can be solved very efficiently, and give a very simple and fast algorithm for the infinite-horizon problem with time-invariant parameters. For the general finite-horizon problem without any assumption on the problem parameters, we formulate it as a zero-one integer program and propose an algorithm for solving it exactly based on Benders' decomposition. Computational results show that this solution algorithm is efficient, i.e., it is capable of solving large scale problems within a reasonable cpu time, and robust, i.e., the number of iterations needed to solve a problem does not increase quickly with the problem size. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 279–295, 1998     

Server scheduling on parallel dedicated machines with fixed job sequences

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial‐time algorithm to solve the two‐machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP‐hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.     

网格方程组并行计算预条件迭代若干性质及应用

对网格方程组作区域分裂并行计算 ;分析了预条件迭代谱条件的若干性质及其对算法收敛性的影响 ,为构造预处理提供了理论依据 ,并应用于区域分裂并行计算     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

结合峰值检测的高噪声图像快速聚类分割方法

针对高噪声污染图像,提出一种结合峰值检测算法的快速聚类分割方法(FC-ImSeg)。根据平行线投影分割算法将二维直方图映射到一维空间,利用峰值检测算法检测图像像素点的聚类结果,调整映射模型的平行线宽度,使直方图符合双峰分布特性,最后利用加权模糊c均值聚类算法实现图像的分割。实验结果证明了该方法是快速有效的。     

基于粒度计算的指控系统效能测度的探索性建模方法

分析了探索性分析模型的粒度原理,建立了基于粒度计算的指控系统效能测度的探索性分析模型,重点研究了探索性分析模型的建立,属性函数的构造和探索因子集的粒度获取方法,并结合多兵种联合作战案例,对使命完成时间测度进行了探索性分析,实验表明,基于粒度计算的探索性建模方法能够通过粒度的转换降低问题的复杂度,并在不同粒度层次上实现对问题描述的一致性。     

液体火箭发动机非线性燃烧不稳定过程的并行仿真

采用计算燃烧学方法对火箭发动机非线性燃烧不稳定工作过程进行了并行数值模拟。气相控制方程组用欧拉坐标系下的Navier Stokes方程组描述 ,液相控制方程组在Lagrangian坐标系下进行描述。气、液两相作用通过方程组的源项互相耦合。编制了串行和并行程序 ,并在并行计算环境下进行了测试。从计算结果可以看出并行计算的效率较高。     

运动舰船上任意分布的磁偶极子的感应电场计算

基于电磁场的坐标变换和线性叠加原理 ,导出了舰船上任意分布的磁偶极子感应电场的计算方法 .与积分方法相比 ,该方法具有普遍性 ,对任意磁化的舰船感应的磁场都适用 .