Optimal Time-Critical Scheduling via Resource Augmentation

We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

Optimal Time-Critical Scheduling via Resource Augmentation

Abstract. We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

Feature selection based on artificial bee colony and gradient boosting decision tree

Data from many real-world applications can be high dimensional and features of such data are usually highly redundant. Identifying informative features has become an important step for data mining to not only circumvent the curse of dimensionality but to reduce the amount of data for processing. In this paper, we propose a novel feature selection method based on bee colony and gradient boosting decision tree aiming at addressing problems such as efficiency and informative quality of the selected features. Our method achieves global optimization of the inputs of the decision tree using the bee colony algorithm to identify the informative features. The method initializes the feature space spanned by the dataset. Less relevant features are suppressed according to the information they contribute to the decision making using an artificial bee colony algorithm. Experiments are conducted with two breast cancer datasets and six datasets from the public data repository. Experimental results demonstrate that the proposed method effectively reduces the dimensions of the dataset and achieves superior classification accuracy using the selected features.     

Fisher’s decision tree

Univariate decision trees are classifiers currently used in many data mining applications. This classifier discovers partitions in the input space via hyperplanes that are orthogonal to the axes of attributes, producing a model that can be understood by human experts. One disadvantage of univariate decision trees is that they produce complex and inaccurate models when decision boundaries are not orthogonal to axes. In this paper we introduce the Fisher’s Tree, it is a classifier that takes advantage of dimensionality reduction of Fisher’s linear discriminant and uses the decomposition strategy of decision trees, to come up with an oblique decision tree. Our proposal generates an artificial attribute that is used to split the data in a recursive way.The Fisher’s decision tree induces oblique trees whose accuracy, size, number of leaves and training time are competitive with respect to other decision trees reported in the literature. We use more than ten public available data sets to demonstrate the effectiveness of our method.     

Competitive distributed decision-making

We study several natural problems in distributed decision-making from the standpoint of competitive analysis; in these problems incomplete information is a result of the distributed nature of the problem, as opposed to the on-line mode of decision making that was heretofore prevalent in this area. In several simple situations of distributed scheduling, the competitive ratio can be computed exactly, and the different ratios can be used as a measure of the value of information and communication between decision-makers. In a more general distributed scheduling situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal randomized algorithm with a much better competitive ratio.The research of Xiaotie Deng was supported by an NSERC grant and that of C. H. Papadimitriou was supported by an NSF grant.     

Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning

We address an unrelated parallel machine scheduling problem with R-learning, an average-reward reinforcement learning (RL) method. Different types of jobs dynamically arrive in independent Poisson processes. Thus the arrival time and the due date of each job are stochastic. We convert the scheduling problems into RL problems by constructing elaborate state features, actions, and the reward function. The state features and actions are defined fully utilizing prior domain knowledge. Minimizing the reward per decision time step is equivalent to minimizing the schedule objective, i.e. mean weighted tardiness. We apply an on-line R-learning algorithm with function approximation to solve the RL problems. Computational experiments demonstrate that R-learning learns an optimal or near-optimal policy in a dynamic environment from experience and outperforms four effective heuristic priority rules (i.e. WSPT, WMDD, ATC and WCOVERT) in all test problems.     

Many Plans: Multidimensional Ensembles for Visual Decision Support in Flood Management

Uncertainties in flood predictions complicate the planning of mitigation measures. There is a consensus that many possible incident scenarios should be considered. For each scenario, a specific response plan should be prepared which is optimal with respect to criteria such as protection, costs, or realization time. None of the existing software tools is capable of creating large scenario pools, nor do they provide means for quick exploration and assessment of the associated plans. In this paper, we present an integrated solution that is based on multidimensional, time‐dependent ensemble simulations of incident scenarios and protective measures. We provide scalable interfaces which facilitate and accelerate setting up multiple time‐varying parameters for generating a pool of pre‐cooked scenarios. In case of an emergency, disaster managers can quickly extract relevant information from the pool to deal with the situation at hand. An interactive 3D‐view conveys details about how a response plan has to be executed. Linked information visualization and ranking views allow for a quick assessment of many plans. In collaboration with flood managers, we demonstrate the practical applicability of our solution. We tackle the challenges of planning mobile water barriers for protecting important infrastructure. We account for real‐world limitations of available resources and handle the involved logistics problems.     

The incremental benefits of changes in the timeliness of information

The managers of all purposeful organizations rely on historical information as an aid to decision making. Information enables managers to formulate expectations about the future. Less timely information is generally inferior because the manager's expectations will contain greater error; and the operating results obtained may therefore be less satisfactory. The timeliness of information often can be improved by incurring incremental systems costs. However, the degree to which such improvements will produce benefits is uncertain. This research uses modeling to explore the relationship between information timeliness and the benefits derived by implementing optimal decisions based upon the information. The most significant finding is that the shape of this relationship is dependent upon the scope of the action set available to the decision maker. If a continuous range of options is available (such as a pricing decision), then the relationship is linear. If only a few discrete options are present (as in linear programming) the relationship is more complex but describable. The decision maker is therefore found to be in a position to offer guidance to the systems designer which will facilitate enhancement of the benefit/cost characteristics of the organization's information resource.     

Advanced step nonlinear model predictive control for air separation units

Cryogenic air separation units constitute an integral part of many industrial processes and next generation power plants. These units are characterized by fluctuating operating conditions to respond to changing product demands. The dynamics of these transitions are highly nonlinear and energy-intensive. Consequently, nonlinear model predictive control (NMPC) based on rigorous dynamic models is essential for high performance in these applications. Currently, the implementation of NMPC controllers is limited by the computational complexity of the associated on-line optimization problems. In this work, we make use of the so-called advanced step NMPC controller to overcome these limitations. We demonstrate that this sensitivity-based strategy reduces the on-line computational time to just a single CPU second, while incorporating a highly detailed dynamic air separation unit model. Finally, we demonstrate that the controller can handle nonlinear dynamics over a wide range of operating conditions.     

On-Line Dial-a-Ride Problems Under a Restricted Information Model

In on-line dial-a-ride problems servers are traveling in some metric space to serve requests for rides which are presented over time. Each ride is characterized by two points in the metric space, a source, the starting point of the ride, and a destination, the endpoint of the ride. Usually it is assumed that at the release of a request, complete information about the ride is known. We diverge from this by assuming that at the release of a ride, only information about the source is given. At visiting the source, the information about the destination will be made available to the servers. For many practical problems, our model is closer to reality. However, we feel that the lack of information is often a choice, rather than inherent to the problem: additional information can be obtained, but this requires investments in information systems. In this paper we give mathematical evidence that for the problem under study it pays to invest.     

AN ESTIMATOR ALGORITHM FOR LEARNING AUTOMATA WITH CHANGING NUMBER OF ACTIONS

In many problems of decision making under uncertainty the system has to acquire knowledge of its environment and learn the optimal decision through its experience. Such problems may also involve the system having to arrive at the globally optimal decision, when at each instant only a subset of the entire set of possible alternatives is available. These problems can be successfully modelled and analysed by learning automata. In this paper an estimator learning algorithm, which maintains estimates of the reward characteristics of the random environment, is presented for an automaton with changing number of actions. A learning automaton using the new scheme is shown to be e-optimal. The simulation results demonstrate the fast convergence properties of the new algorithm. The results of this study can be extended to the design of other types of estimator algorithms with good convergence properties.     

多声传感器异步融合算法

声探测定位技术是利用声传感器接收特定声波信号以确定声源的一种无源定位技术,它具有隐蔽性好、不易受干扰等优点.本文研究了仅能提供方位角信息的异步多声传感器无源探测系统数据融合问题,提出了一种适用于声传感器的在线估计可变周期融合算法.该算法首先采用伪线性算法,将非线性量测方程线性化;然后通过采用参数在线估计和基于运动模型向前追溯确保时间同步的方法,解决了目标跟踪时信号传输时延和传感器异步的问题.通过Monte Carlo仿真表明,在参数在线估计中,步长选取适当时,该算法可以满足声探测系统的精度要求,并且具有收敛快、精度高、稳定的特点.     

Classifying the multi robot path finding problem into a quadratic competitive complexity class

We explore two motion planning problems where a group of mobile robots has to reach a target located in an a priori unknown environment while on-line planning the next step. In the first problem the target position is unknown and should be found by the robots, while in the second problem the target position is known and only a path to it should be found. We focus on optimizing the cost of the task in terms of motion time, which, under the assumption of uniform velocity of all the robots, correlates to the path length passed by the robot which reaches the target. The performance of an on-line algorithm is usually expressed in terms of Competitiveness, the constant ratio between the on-line and the optimal off-line solutions. Specifically, the ratio between the lengths of the actual path made by the robot which reached the target to the shortest path to the target. We use generalized competitiveness, i.e., the ratio is not necessarily constant, but could be any function. Classification of a motion planning task in the sense of performance is done by finding an upper and a lower bounds on the competitiveness of all algorithms solving that task. If the two bounds belong to the same functional class this is the Competitive Complexity Class of the task. We find the two bounds for the aforementioned common on-line motion planning problems, and classify them into competitive classes. It is shown that in general any on-line motion planning algorithm that tries to solve these problems must have at least a quadratic competitive performance. This is a lower bound of the problems. This paper describes two new on-line navigation algorithm which solve the problems under discussion. The first is called MRSAM, short for Multi-Robot Search Area Multiplication, and the second is called MRBUG, short for Multi-Robot BUG which extends Lumelsky famous BUG algorithm. Both algorithms have quadratic upper bounds, which prove that the problems they solve have quadratic upper bounds. Thus it is shown that navigation in an unknown environment by a group of robots belongs to a quadratic competitive class. MRSAM and MRBUG have a quadratic competitive performance and thus have optimal competitiveness. The algorithms’ performance is simulated in office-like environments.     

Regret bounds for sleeping experts and bandits

We study on-line decision problems where the set of actions that are available to the decision algorithm varies over time. With a few notable exceptions, such problems remained largely unaddressed in the literature, despite their applicability to a large number of practical problems. Departing from previous work on this “Sleeping Experts” problem, we compare algorithms against the payoff obtained by the best ordering of the actions, which is a natural benchmark for this type of problem. We study both the full-information (best expert) and partial-information (multi-armed bandit) settings and consider both stochastic and adversarial rewards models. For all settings we give algorithms achieving (almost) information-theoretically optimal regret bounds (up to a constant or a sub-logarithmic factor) with respect to the best-ordering benchmark.     

改进DMC在远程网络化过程测控系统中的应用研究

针对Internet网络测控系统的网络延时、时序错乱和数据丢包现象,引入时间序列分析方法,构建了DMC多步预测控制模型;采用时间序列排序与插值,解决时序错乱和数据丢包问题;对于系统的反馈通道延时,提出基于信息缺失下的改进DMC多步预测控制,减小其影响;对于系统的前向通道延时,在新的控制信息未到时,利用多步预测的第N步信息顺序控制。整个系统通过TRU-ETIME仿真,当网络延时在20倍采样周期内时,系统控制实时。结果表明改进DMC在减小网络延时、时序错乱和数据丢包对系统的影响是可行的。     

Efficient On-Line Frequency Allocation and Call Control in Cellular Networks

In this paper we consider communication issues arising in cellular (mobile) networks that utilize frequency division multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of available frequencies is limited; thus, efficient solutions to the frequency-allocation and the call-control problems are essential. In the frequency-allocation problem, given users that wish to communicate, the objective is to minimize the required spectrum of frequencies so that communication can be established without signal interference. The objective of the call-control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users served. We consider cellular, planar, and arbitrary network topologies. In particular, we study the on-line version of both problems using competitive analysis. For frequency allocation in cellular networks, we improve the best known competitive ratio upper bound of 3 achieved by the folklore Fixed Allocation algorithm, by presenting an almost tight competitive analysis for the greedy algorithm; we prove that its competitive ratio is between 2.429 and 2.5 . For the call-control problem, we present the first randomized algorithm that beats the deterministic lower bound of 3 achieving a competitive ratio between 2.469 and 2.651 for cellular networks. Our analysis has interesting extensions to arbitrary networks. Also, using Yao's Minimax Principle, we prove two lower bounds of 1.857 and 2.086 on the competitive ratio of randomized call-control algorithms for cellular and arbitrary planar networks, respectively.     

分布式文件系统副本一致性检测研究

在大规模分布式文件系统中,副本一致性的实现既需要一致性协议模型的保障,也需要系统能够及时检测出已产生的不一致并予以修复.这里主要研究副本一致性的在线检测技术,全面分析了基于对象存储的大规模分布式文件系统中副本不一致的所有可能情况,深入阐述了在线一致性检测所面临的3个关键问题,即如何减小检测过程对系统性能的影响、保证检测的及时性、以及保证检测的准确性.针对这3个关键问题,总结提出了相应的解决方法.其中,模拟存储状态的方法,减轻了检测过程给系统带来的负荷;预检测的方法,增强了检测出系统不一致错误的及时性;检测静态数据的方法,有效避免了误检和漏检,保证了在线检测的准确性.     

An stochastic multiattribute acceptability analysis‐based method for the multiattribute project portfolio selection problem with rank‐level information

In many cases of practical multiattribute project portfolio selection problems, it is hard to obtain accurate measurements of attributes and precise preference information. Even after a long and costly information gathering, the attribute measurements and the preference information can still be uncertain or inaccurate. Considerable cost saving will be obtained if the selection of an optimal project portfolio can be done using rank‐level information based on some or all the attributes, without knowing the preference information. In this paper, we propose a stochastic multiattribute acceptability analysis‐based method that can deal with mixed rank and cardinal attribute measurements and uses little or no weight information. In the proposed stochastic multiattribute acceptability analysis‐based method, the decision makers need not to express their preferences explicitly or implicitly, so it is particularly useful when no weight information is available at all. A numerical example involving selection of photovoltaic plants in an industrial province in Eastern China is provided to demonstrate the proposed method.     

On the competitiveness of on-line real-time task scheduling

With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of clairvoyancy, i.e., the power of possessing knowledge of various task parameters of future events. Specifically, we consider the problem of preemptively sheduling sporadic task requests in both uni- and multi-processor environments. If a task request is successfuly scheduled to completion, a value equal to the task's execution time is obtained; otherwise no value is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than 1/4th the value obtainable by a clairvoyant scheduler; i.e., we prove a 1/4th upper bound on the competitive factor of on-line real-time schedulers. We present an online uniprocessor scheduling algorithm TD ₁ that actually has a competitive factor of 1/4; this bound is thus shown to be tight. We further consider the effect of restricting the amount of overloading permitted (the loading factor), and quantify the relationship between the loading factor and the upper bound on the competitive factor. Other results of a similar nature deal with the effect of value densities (measuring the importance of type of a task). Generalizations to dual-processor on-line scheduling are also considered. For the dual-processor case, we prove an upper bound of 1/2 on the competitive factor. This bound is shown to be tight in the special case when all the tasks have the same density and zero laxity.     

Optimal resource allocation for time-reservation systems

This paper studies the optimal resource allocation in time-reservation systems. Customers arrive at a service facility and receive service in two steps; in the first step information is gathered from the customer, which is then sent to a pool of computing resources, and in the second step the information is processed after which the customer leaves the system. A central decision maker has to decide when to reserve computing power from the pool of resources, such that the customer does not have to wait for the start of the second service step and that the processing capacity is not wasted due to the customer still being serviced at the first step. The decision maker simultaneously has to decide on how many processors to allocate for the second processing step such that reservation and holding costs are minimized. Since an exact analysis of the system is difficult, we decompose the system into two parts which are solved sequentially leading to nearly optimal solutions. We show via dynamic programming that the near-optimal number of processors follows a step function with as an extreme policy the bang-bang control. Moreover, we provide new fundamental insights in the dependence of the near-optimal policy on the distribution of the information gathering times. Numerical experiments demonstrate that the near-optimal policy closely matches the performance of the optimal policy of the original problem.