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算法的对比分析,证实了改进的谐波周期算法在保证系统中周期型消息实时性能前提下,为非周期型信息获得了更大的传输带宽,又使系统信息传输的时间分配更加合理。     

履带车辆转向性能指标分析及实验研究

转向性能是评价履带车辆机动性的重要指标之一.文中针对转向角速度、转向半径和转向消耗功率3个指标,分别在不考虑履带滑转滑移的理想条件下和考虑履带滑转滑移的实际情况下,对履带车辆的转向性能进行了讨论和分析,对2种条件下履带车辆的转向性能的变化进行了比较.为了对履带车辆在转向过程中履带的滑转和滑移程度进行定量的分析,定义了履带的滑转和滑移系数.通过实车实验,对分析结果进行了验证.     

Manpower allocation with time windows and job‐teaming constraints

In this work, we study manpower allocation with time windows and job‐teaming constraints. A set of jobs at dispersed locations requires teams of different types of workers where each job must be carried out in a preestablished time window and requires a specific length of time for completion. A job is satisfied if the required composite team can be brought together at the job's location for the required duration within the job's time window. The objective is to minimize a weighted sum of the total number of workers and the total traveling time. We show that construction heuristics used with simulated annealing is a good approach to solving this NP‐hard problem. In experiments, this approach is compared with solutions found using CPLEX and with lower bounds obtained from a network flow model. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Single machine scheduling with a restricted rate‐modifying activity

In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost

In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines, where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

舰艇辐射噪声仿真信号应用风险评估模型

为了克服传统风险评估中定性分析方法客观性较差等缺点,定义了与仿真信号特征参数一致性相关联的后果系数,对仿真信号风险事件所导致的后果进行了定量分析,并在此基础上提出了基于一致性分析的仿真信号应用风险评估模型,最后给出了该模型应用于舰艇辐射噪声仿真的评估实例。评估实例表明,该模型不仅有助于充分挖掘信号仿真中阶段性数据的有用信息,同时也能为仿真信号的风险评估提供实用工具。     

Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

维修任务调度的多目标决策模型

通过对维修调度问题进行分析,考虑到战斗力相关的多种目标因素,针对目前研究的目标单一,又未考虑武器的先进程度、配置等缺陷,就修复后的加权作战时间和装备尽可能少的延误数量双重目标加以研究,并给出了调度算法。从而弥补了这些缺陷,使调度更加合理。最后,算例表明模型的求解方法简单,计算时间较短,可有效地实现维修任务调度。