任务划分与处理机调度的递归-分治方法

本文介绍并实现了一种如何把一个顺序执行的任务集,根据其子任务之间潜在的并行性,划分成若干个可并发执行的任务子集,并把每个子集分配给一个处理机,使各处理机之间的数据通信量尽可能地少,同时兼顾各处理机之间负载平衡的算法。最后给出了几个典型例题的试算结果,为了满足用户的不同要求,文章还提出了几点改进方法。     

基于改进蚁群算法的云计算任务调度研究

把改进的蚁群算法应用到云计算任务调度中,通过将任务在虚拟机上的一次分配作为蚂蚁的一次成功搜索,实现了虚拟机的负载均衡和调度时间的优化,提高云计算资源分配的效率。通过在Cloud Sim平台下进行仿真测试,结果显示,改进蚁群算法在负载均衡性能和总的任务调度时间方面均优于基本的蚁群算法。     

向量巨型机高效程序设计技术

本文着重研究适应向量巨型机体系结构的高效程序设计技术。围绕减少指令流水线阻塞,提高多功能部件并行度,数据调度与局部化技术三个方面进行了深入的讨论,给出了一系列设计高效程序的方法和技巧。     

应用于流水时序调度的归一化定时数据流图理论

流水时序调度是专用数字信号处理器高层综合中的一个困难而急待解决的问题 ,文中提出了一种有着鲜明物理意义的归一化定时数据流图 ,基于节点移动研究了合法流水调度变换的内部机理 ,从而证明从任一合法的初始流水调度出发 ,通过合法的节点移动可以搜索到设计空间中任何一个合法的流水调度。一个合法、完备的变换集 ,为寻优搜索的算法应用于流水调度解决了理论和算法实现问题。文中还给出了一些实验结果。     

电力市场环境下发电厂机组检修计划

分析了传统的统一调度下和电力市场环境下发电厂机组检修计划的不同,在此基础上提出不同于以往的检修计划方法。以检修费用、电价收益损失和违约金之和最小为目标函数,然后采用0-1整数规划的直接枚举法求解。最后通过算例论证了该方法的可行性。     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

A comparative study of three tool replacement/operation sequencing strategies in a flexible manufacturing system

This paper studies three tool replacement/operation sequencing strategies for a flexible manufacturing system over a finite time horizon: (1) failure replacement—replace the tool only upon failure, (2) optimal preventive tool replacement for a fixed sequence of operations, and (3) joint scheduling of the optimal preventive tool replacement times and the optimal sequence of operations. Stochastic dynamic decision models are used for strategies 2 and 3. The optimization criterion for strategies 2 and 3 is the minimization of the total expected cost over the finite time horizon. We will show through numerical studies that, with the same amount of information, the total expected costs can be reduced considerably by choosing an optimal strategy. Our conclusion is that in flexible manufacturing, optimal tool replacement and optimal operations sequencing are not separate issues. They should be considered jointly to minimize the expected total cost. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 479–499, 2000     

A new appointment rule for a single-server,multiple-customer service system

This paper proposes a new appointment rule for the single-server, multiple-customer service system. Unlike previous appointment rules, which perform well only in specific service environments, the new rule can be parameterized to perform well in different service environments. The new appointment rule is presented as a mathematical function of four environmental parameters, namely, the coefficient of variation of the service time, the percentage of customers' no-shows, the number of appointments per service session, and the cost ratio between the server's idle and customers' waiting cost per unit time. Once the values of these environmental parameters are estimated, the new appointment rule can be parameterized to perform well. The results show that new rule performs either as well as or better than existing appointment rules in a wide range of service environments. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 313–326, 1998     

面向点及区域目标的遥感卫星任务调度

遥感应用需求中存在点目标和区域目标两类任务,遥感卫星对两类任务的调度方式存在很大区别,将二者统一调度困难.本文将点目标视为特殊的区域目标,将它们按照卫星观测机会分解,构建元任务,将两类目标在元任务层次进行统一;根据任务类型分别构建收益函数,兼顾了二者在收益计算上的差异,并建立了面向点及区域目标的遥感卫星任务调度模型,实现了对两类任务的综合调度.仿真实例证明,此方法能够提高卫星的观测效率.     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009