实时磁盘调度算法研究

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

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

仿真模型调度决策是实现仿真结果合理、可信、可用的重要环节。界定了模型调度决策问题域,引入了模型调度序列表示决策结果,提出了基于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     

基于协商的Agent资源冲突消解算法研究

针对分布式规划系统中Agent计划的资源冲突问题,研究了资源冲突的分类;基于Agent协商理论,从资源最优配置的角度,论证了最优的协商策略,提出了可重复利用的不可分享型资源的冲突消解算法,较好地解决了Agent分布式规划中出现的一类资源冲突问题。算例表明,给出的冲突消解算法是有效的。     

分布式到达时间控制器装备维修任务实时调度方法

战时装备维修企业的生产环境呈现出更多的不确定性,合理安排维修任务来适应这种不确定性使实际修复时间与计划时间偏差最小是什么重要的.为此,提出了一种面向准时制造的实时生产调度方法,这种生产调度系统有多个独立的智能体,每个智能体通过到达时间控制器和仿真系统的反馈来调整对应维修任务的到达时间,然后通过先来先服务的调度规则确认维...     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

Relaxed sequencing games have a nonempty core

We study sequencing situations with a fixed initial order and linear cost functions. Cost savings can be obtained by rearranging jobs. Next to finding an optimal order, an additional issue is formed by the division of these savings. Cooperative game theory studies this issue. A common assumption states that cooperation between players is restricted to groups that are connected according to the initial order. The value of disconnected groups is defined additively over their connected components. In this paper we allow players in disconnected coalitions to switch places as long as they do not hurt the players not in the coalition under consideration. The resulting games are called relaxed sequencing games. Although they have been studied before, no general results on stable profit divisions have been derived so far. In this paper we prove that relaxed sequencing games have a nonempty core, i.e., they all have stable profit divisions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

基于距离加权Bloom filter的网络路由算法

基于分布式哈希表(DHT)的P2P查找经常受到在底层网络中路由时无必要的路径长度增加的影响.另外,DHT在处理复制方面也有一定的缺陷.文中探讨了解决这些问题的方法.对使用Bloom filters作为资源路由的方法做了简要回顾,并较为详细地阐述了在资源分散的覆盖网络中使用距离加权Bloom filter的网络路由算法.对该算法进行了仿真测试,证明了其有效性.