Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

Note: On the two‐machine no‐idle flowshop problem

In this short note we study a two‐machine flowshop scheduling problem with the additional no‐idle feasibility constraint and the total completion time criterion function. We show that one of the few papers which deal with this special problem contains incorrect claims and suggest a way how these claims can be rectified. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:353–358, 2000     

并串联系统设计优化

建立了并串联系统设计优化的两类模型,提出了遗传算法与模式搜索、启发式算法相结合的求解方法．     

高精度分数时延滤波器设计的边界拟合Remez算法

在卫星星间测距模拟信号仿真及实际测试中,为提高测距模拟信号精度和系统可用带宽,提出基于边界拟合Remez算法的高精度分数时延滤波器的设计算法。该算法利用Farrow结构的多项式近似思想,采用多项式拟合Remez算法设计滤波器的冲激响应边界系数,通过多相分解实现分数时延滤波器组。该算法改善了当设计的滤波器阶数较高时冲激响应边界的不连续现象,进而降低了群时延误差,提高了精度。仿真结果表明,该算法设计的滤波器的分数时延精度得到了提高,同时系统可用带宽提高近一倍,实现时需使用的乘法器数目也有明显降低。     

Local search methods for the discrete time/resource trade-off problem in project networks

In this paper we consider the discrete time/resource trade-off problem in project networks. Given a project network consisting of nodes (activities) and arcs (technological precedence relations), in which the duration of the activities is a discrete, nonincreasing function of the amount of a single renewable resource committed to it, the discrete time/resource trade-off problem minimizes the project makespan subject to precedence constraints and a single renewable resource constraint. For each activity, a work content is specified such that all execution modes (duration/resource requirement pairs) for performing the activity are allowed as long as the product of the duration and the resource requirement is at least as large as the specified work content. We present a tabu search procedure which is based on a decomposition of the problem into a mode assignment phase and a resource-constrained project scheduling phase with fixed mode assignments. Extensive computational experience, including a comparison with other local search methods, is reported. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 553–578, 1998     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Heuristic procedures for scheduling job families with setups and due dates

This paper examines heuristic solution procedures for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. It reviews the state of knowledge about the solution of this problem, which is known to be difficult to solve in general, and examines natural solution approaches derived from some of the underlying theory. The emphasis is on the design and computational evaluation of new heuristic procedures. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 978–991, 1999     

动圈式永磁直线直流电机的精英保留多种群遗传优化算法

为了实现陆基无人机电磁弹射器高机动性及其直线弹射电机的高功率密度,针对动圈式永磁直线直流电机,提出精英保留的多种群遗传算法(Multi-Population Genetic Algorithm with Elite Retention, MPGAER)的电机最大功率密度优化方法。以磁通密度和电流密度为约束条件,利用其搜索能力强、收敛速度快的特点优化电机的结构参数,并与磁路法初始设计结果和传统遗传算法优化结果进行比较。结果表明:与磁路法初始设计相比,MPGAER能使电机质量减少6.25%,功率密度提高10%,电机动态性能得到提高;MPGAER优化设计的电机功率密度高于遗传算法设计结果,所提方法有效地解决了在优化过程中出现易收敛于局部最优点和寻优效果差的问题。     

基于蚁群算法的防空C3I系统火力分配模型研究

针对当前火力分配问题实现难度大的特点,分析各种火力分配优化方法的优缺点,运用新型蚁群算法尝试解决WTA问题。建立了基于蚁群算法的火力分配优化模型,描述了解火力分配问题的一般步骤,通过实例给出了算法,解决了WTA问题。并与匈牙利法相比较,结果表明该方法的合理性和有效性,特别是在武器—目标数较大时,其效率要高于常用的匈牙利法。     

改进的蚁群算法及其在卫星网络路由计算中的应用

介绍了蚁群算法的原理,然后对现有蚁群算法进行了一些改进,使它能够快速地收敛以满足高速变化的卫星网络拓扑结构.采用改进的虚拟拓扑策略解决了卫星网络拓扑高速变换的问题,将改进的蚁群算法应用于其上,并给出了相应的性能评估.所提出的改进的虚拟拓扑策略,能够大大减少一个系统周期内卫星网的时间片个数.应用于此基础上的改进的蚁群算法也体现了较好的性能.