Preemptive parallel‐machine scheduling with a common server to minimize makespan

We consider parallel‐machine scheduling with a common server and job preemption to minimize the makespan. While the non‐preemptive version of the problem is strongly NP‐hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP‐hard even if there is a fixed number of machines. We give a pseudo‐polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP‐hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017     

天基预警系统资源调度问题分析

在介绍天基预警系统作战流程,以及天基预警系统资源和任务的分析和描述的基础上,提出天基预警系统资源调度问题,给出其输入输出结构,并以五元组的形式对该问题进行形式化描述。 关键词：天基预警系统、资源调度、形式化描述     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

基于改进LMS算法的复合材料超声检测缺陷识别

在径向基函数（RBF）神经网络实现无人机复合材料超声检测脱粘缺陷识别时,针对最小均方（LMS）算法在确定网络输出权值时存在稳态失调误差和收敛速度相矛盾的问题,提出一种改进的自适应的变步长LMS算法．该算法根据反馈误差自适应确定步长,通过引进动量项加快收敛速度．将改进LMS算法应用到RBF网络缺陷识别中,结果表明该方法在稳态失调误差较小的情况下,能快速确定RBF网络的权值．改进的RBF网络能够较好地识别超声检测脱粘缺陷．     

Review of the ordered and proportionate flow shop scheduling research

Ordered flow shop models have appeared in the literature since the mid‐1970s and proportionate flow shop models have appeared since the early 1980s. We provide a detailed review of these models along with some analysis and potential topics for future research. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

一种由条件确定导引时机的线导鱼雷导引方案

基于对水下平台获取目标信息客观实际的分析,指出以固定的导引周期、自动实现线导鱼雷整个过程的导引是难以实现的.为此,线导鱼雷导引方案设计必须综合利用各种渠道所获得的目标信息资源和鱼雷的高速制资源,才能大幅提高线导鱼雷的使用性能.通过仿真研究提出:“由条件确定导引时机”的概念,给出利用“依赖条件调度的管理器”对来自各方面的目标方位进行优先级排序并控制导引算法调度时机的技术方法;利用“间断导引”兼顾导引平台听测与鱼雷快速接近目标之矛盾的技术方案,给出了确定“听测速度”、转换方法和转换时间间隔的技术方法和途径.     

An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

We study a deterministic two‐machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP‐hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n⁵/ε⁴) time complexity. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Proactive release procedures for just‐in‐time job shop environments,subject to machine failures

In this paper, we consider just‐in‐time job shop environments (job shop problems with an objective of minimizing the sum of tardiness and inventory costs), subject to uncertainty due to machine failures. We present techniques for proactive uncertainty management that exploit prior knowledge of uncertainty to build competitive release dates, whose execution improves performance. These techniques determine the release dates of different jobs based on measures of shop load, statistical data of machine failures, and repairs with a tradeoff between inventory and tardiness costs. Empirical results show that our methodology is very promising in comparison with simulated annealing and the best of 39 combinations of dispatch rules & release policies, under different frequencies of breakdowns. We observe that the performance of the proactive technique compared to the other two approaches improves in schedule quality (maximizing delivery performance while minimizing costs) with increase in frequency of breakdowns. The proactive technique presented here is also computationally less expensive than the other two approaches. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

不确定环境下装备采购项目组织结构评估研究

首先分析了装备采购项目组织结构柔性的概念、环境不确定性的主客观因素及组织结构柔性与环境不确定性匹配的涵义;其次提出了装备采购项目组织结构柔性与环境不确定性的评价指标体系和测度方法,并在此基础上设计了组织结构柔性与环境不确定性匹配度的计算方法及判断准则;最后给出了算例。     

某特种车辆TTCAN网络的静态调度设计

针对某特种车辆计算机控制系统对实时性的高要求,采用了TTCAN总线系统,为实现TTCAN系统的静态调度问题,提出了基于AL算法的改进算法——谐波周期算法,并通过MATLAB建立了系统的调度表。针对谐波周期算法的不足,结合该计算机控制系统的工作原理、信息传输的重要程度对静态调度表进行了适当的修改。通过与AL算法的对比分析,证实了改进的谐波周期算法在保证系统中周期型消息实时性能前提下,为非周期型信息获得了更大的传输带宽,又使系统信息传输的时间分配更加合理。