The effectiveness of the longest delivery time rule for the flow shop delivery time problem

In the flow shop delivery time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize maximum delivery completion time over all the jobs, where the delivery completion time of a job is the sum of its completion time, and the delivery time associated with that job. In this paper, we prove the asymptotic optimality of the Longest Delivery Time algorithm for the static version of this problem, and the Longest Delivery Time among Available Jobs (LDTA) algorithm for the dynamic version of this problem. In addition, we present the result of computational testing of the effectiveness of these algorithms. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

Mean sojourn times in multiclass feedback queues with gated disciplines

In this paper, we investigate multiclass feedback queues with gated disciplines. The server selects the stations by a nonpreemptive priority scheduling algorithm and serves customers in the selected station by either a gated FCFS discipline or a gated priority discipline. We take a rather systematic approach to their mean sojourn times. We define conditional expected sojourn times for all customers and derive their expressions from an analysis of busy periods. Since they are shown to be linear in some components of the system states, their steady state mean values can be derived from simple limiting procedures. These mean values can be obtained from a set of linear equations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 719–741, 2003.     

面向I/O优化调度器的磁盘特征提取

外存I/O一直是影响I/O密集型应用系统性能的决定性因素。在系统分析I/O优化调度策略及其对磁盘特征参数的需求的基础上,提出了一组面向I/O优化调度器的磁盘特征抽取方法。这些抽取方法已经被证明是高效的,并且在Traxtents Cello调度器的实现中得到采用。     

Minimizing weighted earliness and tardiness penalties in single‐machine scheduling with idle time permitted

In this paper, a single‐machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch‐and‐bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 760–780, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10039     

具有吞吐量和时延约束的软件无线电波形部署决策算法

针对当前具有吞吐量和时延约束的软件无线电波形部署决策算法在内存开销方面考虑的不足,提出一个更为通用的波形部署决策系统模型,将波形的处理开销、内存开销和通信带宽开销都纳入到波形部署决策过程中,并设计了一种基于动态规划的波形部署决策算法以最小化波形对平台各种计算资源的占用总和。仿真结果表明,内存对波形部署决策具有重要影响,与未考虑内存开销的解决方案相比,平台支持的平均最大波形数目和平均处理资源利用率均下降40%左右。     

A decomposition heuristic for the twin robots scheduling problem

This article provides an efficient heuristic based on decomposition for the twin robots scheduling problem (TRSP). TRSP concerns two moving robots executing storage and retrieval requests in parallel along a shared pathway. The depots are located at both ends of the line and a dedicated robot is assigned to each of them. While moving goods between their respective depots and some storage locations on the line, noncrossing constraints among robots need to be considered. Our heuristic uses a dynamic programming framework to determine the schedule of one robot while keeping the other one's fixed. It finds near‐optimal solutions even for large problem instances with hundreds of jobs in a short time span. © 2014 Wiley Periodicals, Inc. 62:16–22, 2015     

指定目标不延误条件下的拦截决策算法

从现有的拦截排序准则出发,根据实际作战中进袭目标的特点,应用现代排序理论,分别建立了动态目标拦截排序模型和总损失最小化模型,给出相应的求解算法。最后实例计算得出模型既体现了现有的拦截准则,又对现有的准则进行了推广。     

舰载机多机一体化机务保障调度研究

针对舰载机多机一体化机务保障调度问题,以出树、入树的形式描述实际保障过程中并行工序的约束关系,以最大保障完工时间和资源负载均衡性为目标,构建了舰载机多机一体化机务保障非线性多目标混合流水车间调度模型,并设计了一种结合基于Insert的动态邻域爬山搜索策略和并行工序的同步化修正的Memetic算法求解该模型。最后通过实例仿真验证了模型和所提算法的可行性和有效性。     

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