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     

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

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

Machine scheduling with pickup and delivery

The coordination of production, supply, and distribution is an important issue in logistics and operations management. This paper develops and analyzes a single‐machine scheduling model that incorporates the scheduling of jobs and the pickup and delivery arrangements of the materials and finished jobs. In this model, there is a capacitated pickup and delivery vehicle that travels between the machine and the storage area, and the objective is to minimize the makespan of the schedule. The problem is strongly NP‐hard in general but is solvable in polynomial time when the job processing sequence is predetermined. An efficient heuristic is developed for the general problem. The effectiveness of the heuristic is studied both analytically and computationally. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A logistics scheduling model: Inventory cost reduction by batching

Logistics scheduling refers to the problems where the decisions of job scheduling and transportation are integrated in a single framework. In this paper, we discuss a logistics scheduling model where the raw material is delivered to the shop in batches. By making the batching and scheduling decisions simultaneously, the total inventory and batch setup cost can be reduced. We study different models on this issue, present complexity analysis and optimal algorithms, and conduct computational experiments. Some managerial insights are observed. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

实时磁盘调度算法研究

总结分析了现阶段流行的实时磁盘调度算法,针对磁盘的存储特性,在对任务请求的磁盘访问时间精确预估的基础上,提出了一种新的调度算法-DSJIT(diskjustintime).该算法通过对请求文件在磁盘上分布的预分析得出处理请求所需时间的一个精确预估值,然后根据此预估值再对任务队列进行调度调整,它在保证应用程序对磁盘工作实时要求的同时,尽可能地提高磁盘的吞吐量.最后通过模拟试验,验证了算法的有效性.     

LEO/MEO双层卫星网络设计及仿真

针对单层卫星网络功能单一、可靠性较低以及三重卫星网络链路冗余度过高、实现复杂的问题,提出了利用LEO/MEO卫星构建双层网络的构想.基于"最坏观察点"与"覆盖带"理论设计了"弱连接"的LEO/MEO双层卫星网络星座,给出了星际链路建立原则.仿真结果表明,所设计的卫星网络具有全天时全球覆盖能力,有利于星际链路的建立.     

基于概念模型的仿真模型调度决策法

仿真模型调度决策是实现仿真结果合理、可信、可用的重要环节。界定了模型调度决策问题域,引入了模型调度序列表示决策结果,提出了基于UML(unified modeling language)概念模型的模型调度决策法,分析了防空作战仿真模型调度决策示例,为解决舰艇作战仿真模型的调度决策提供可行办法,对复杂军事问题仿真模型调度决策具有一定的理论意义。     

Scheduling with centralized and decentralized batching policies in concurrent open shops

This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The batching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo‐polynomial time algorithms for some problems that are NP‐hard in the ordinary sense. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17–27, 2011