Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

基于遗传算法的信息系统安全技术方案

组织如何制定优化的信息安全技术方案以降低脆弱性对其信息系统的威胁,是信息安全管理领域的关键问题。在描述信息系统安全技术方案决策模型的基础上,提出了一种求解信息系统安全技术方案优化问题的自适应遗传算法,使得组织能以最少的方案实施费用最大限度地处置脆弱性,并以实例说明了该算法的有效性。     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

基于不完全信息演化博弈模型的网络舆情传播羊群行为

以网络舆情传播过程中大部分人对事实不了解为前提,在这部分群体内构建基于不完全信息环境的两人对称演化博弈模型。提出了两人对称博弈矩阵来决定个体策略的选择,建立了复制动态方程说明不同策略群体比例的演化方向,演化时引入个体的记忆长度,根据设定的交互规则更新各自的观点值及记忆列表。仿真分析模型表明,在此环境中很容易产生羊群行为,群体内的个体都选择盲从并且观点保持一致。此外,羊群行为的集聚产生受多种因素影响,主要与采取分析策略的交互利益、成本系数以及记忆长度有关。本文对科学分析引导网络舆情的传播有一定实际意义。     

巨型机通用数学库软件与并行算法

本文介绍了巨型机通用数学库软件的概念和意义,指出了巨型机数学软件开发的技术途径与发展趋势,讨论了并行算法在其中的关键性作用,结合实例分析了巨型机通用数学库软件研制中的并行算法设计与实现。     

分段线性凸费用网络流的两个算法

本文讨论了分段线性凸费用网络流问题,推广了线性费用网络流中的负回路方法和最小费用路方法,从而得到了求分段线性凸费用网络的最小费用流的两个算法。     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

C2组织的通信结构优化设计与分析

指挥控制(Command and Control,C2)组织的通信结构设计是解决网络中心战条件下指控信息高效交互的核心问题.围绕C2组织通信结构的延时、可靠性及成本进行建模,在虚拟全连通网络中采用路由随机搜索的方法避免路由及拓扑的局部搜索,并基于遗传算进行全局搜索求解.实验分析表明该方法可以实现优化目标和效果.     

电视侦察弹侦察效力的演化仿真优化研究

为了保证电视侦察弹能到达目标区域的上空并发挥最优的侦察效力,采用了基于遗传算法的启发式仿真优化方法来解决炮射电视侦察弹的优化使用问题.分析了电视侦察弹的主要影响因素,建立了用于计算目标侦察效力的仿真模型,引入了演化策略,实现了基于进化计算的启发式仿真优化系统,并求取了电视侦察弹的最大侦察效力及其主要影响因素的最优搭配....