面向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     

卫星数传调度模型研究

卫星数传调度问题是一个具有多时间窗口、多资源约束的优化问题。针对该问题,建立了卫星数传需求模型、任务模型和调度模型。在建模过程中,采用了框架模型形式,把问题中的主要约束封闭于每个数传任务中,这在降低调度模型复杂度的同时,也降低了调度算法设计难度。还提出了调度算法设计思想,并设计了一基于灵活度的调度算法。仿真表明,所建立的模型及算法对解决卫星数传调度问题是可行的。     

An absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 ? 1/m)p_max, p} is presented, where p_max is the largest job processing time and p is the mth element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p_max. The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm²) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines

We consider the problem of maximizing the number of on‐time jobs on two uniform parallel machines. We show that a straightforward extension of an algorithm developed for the simpler two identical parallel machines problem yields a heuristic with a worst‐case ratio bound of at least . We then show that the infusion of a “look ahead” feature into the aforementioned algorithm results in a heuristic with the tight worst‐case ratio bound of , which, to our knowledge, is the tightest worst‐case ratio bound available for the problem. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A note on combined job selection and sequencing problems

We investigate the solvability of two single‐machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single‐machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n²) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single‐machine total‐weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n²) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013     

非周期不完全检测下的维修优化

针对gamma退化型单部件系统,基于更新和半更新过程理论建立了以期望费用率最小为目标的非周期不完全检测下的维修优化模型。利用检测规划函数使系统的检测间隔期可以依据系统的状态进行调整。为更加贴近实际,模型考虑了测量误差对维修优化的影响。通过计算可以得到最优预防性维修阈值和检测方案。给出了模型的应用算例,通过对退化速率和费用参数的灵敏度分析说明了模型的有效性。与不考虑检测误差的优化结果进行对比,证明了考虑检测误差的重要性。     

Interval scheduling: A survey

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process

This paper finds the optimal integrated production schedule and preventive maintenance plan for a single machine exposed under a cumulative damage process, and investigates how the optimal preventive maintenance plan interacts with the optimal production schedule. The goal is to minimize the total tardiness. The optimal policy possesses the following properties: Under arbitrary maintenance plan when jobs have common processing time, and different due dates, the optimal production schedule is to order the jobs by earliest due date first rule; and when jobs have common due date and different processing times, the optimal production schedule is shortest processing time first. The optimal maintenance plan is of control limit type under any arbitrary production schedule when machine is exposed under a cumulative damage failure process. Numerical studies on the optimal maintenance control limit of the maintenance plan indicate that as the number of jobs to be scheduled increases, the effect of jobs due dates on the optimal maintenance control limit diminishes. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007