An algorithm to schedule aircraft to sorties

An algorithm is presented which provides Air Force schedulers the capabilit alternative schedules rapidly. This capability enhances the schedulers' ability to obtain “good” schedules by: (1) providing for rapid rescheduling in the event of inevitable changeswhich routinely occur during the period of the schedule, (2) presenting a specific quantifiable set of objectives to be met by the schedule.The algorithm is designed specifically for use by B-52 and KC-135 schedulers in the Strategic Air Command. The objective function includes a term for minimizing hours remaining to phase inspections, where hours remaining to phase inspection refers to the number of flying hours an aircraft is permitted to accrue prior to being grounded for the maintenance action referred to as a phase inspection.Another term in the objective function is to maximize the number of turn-around flights, where a turn-around flight occurs when the same aircraft flys more than one sortie in a 48 hr time period. A turn-around sortie requires less pre-flight maintenance and thus results in a cost savings.A very favorable comparison is presented of algorithm schedules with schedules manually prepared in an operational environment.     

边失效情形下一类供应链系统的可靠性分析

以基于最大覆盖选址模型的供应链系统为对象,研究了边设施失效对其可靠性的影响。建立了以系统效率最大或最小化为目标的确定性边失效和随机性边失效两种情形下的优化模型,由此给出了解决这类可靠性分析问题的一般方法。实例求解结果表明模型合理,有一定推广和应用价值。     

Solving a stochastic single machine problem with initial idle time and quadratic objective

We study a static single machine scheduling problem in which processing times are stochastic, due-dates and penalties for not completing jobs on time are deterministic, and an initial fixed idle time is allowed to be inserted before the processing of the first job begins on the machine. The objective is to determine the optimal sequence and the optimal initial idle time that jointly minimize the expected value of the sum of a quadratic cost function of idle time and the weighted sum of a quadratic function of job lateness. The problem is NP-hard to solve; however, we develop an exact algorithm based on a precedence relation structure among adjacent jobs. Our extensive computational results show that the algorithm can solve large problem instances quickly. We also demonstrate that the proposed problem is general in the sense that its special cases reduce to new stochastic models while its limiting cases simplify to some deterministic models.     

A decision support system for the single-depot vehicle rescheduling problem

Disruptions in trips can prevent vehicles from executing their schedules as planned. Mechanical failures, accidents, and traffic congestion often hinder a vehicle schedule. When a vehicle on a scheduled trip breaks down, one or more vehicles need to be rescheduled to serve the passengers/cargo (if there are any) on that trip. The main objective of the vehicle rescheduling problem (VRSP) is to minimize operation and delay costs, while serving the passengers/cargo on the disrupted trip and completing all remaining trips that include the disrupted one. We report on a prototype decision support system (DSS) that recommends solutions for the single-depot rescheduling as well as vehicle scheduling (VSP) problems, since VRSP is closely related to VSP. The system was designed for human schedulers to obtain optimal vehicle assignments and reassignments. An experimental study, using randomly generated data, shows the efficiency of the developed algorithm. A real world problem, which involves the solid waste collection operational planning for a Brazilian city, is selected as the case study to illustrate the effectiveness of the developed DSS.     

不确定离散时间马尔可夫切换时滞系统的保成本控制

研究了一类不确定具有模式依赖时滞马尔可夫切换系统的保成本控制问题.首先将系统变换为等价的奇异系统,并对等价的奇异系统,构造出一个新型随机Lyapunov泛函.然后运用此Lyapunov泛函,基于线性矩阵不等式,得到了无记忆状态反馈保成本控制器存在的与时滞相关的充分条件.举例结果表明,与现有方法相比,用本文方法可以使成本指标取得较小的成本上界.     

A calculus for stochastic QoS analysis

The issue of Quality of Service (QoS) performance analysis in packet-switched networks has drawn a lot of attention in the networking community. There is a lot of work including an elegant theory under the name of network calculus, which focuses on analysis of deterministic worst case QoS performance bounds. In the meantime, researchers have studied stochastic QoS performance for specific schedulers. However, most previous works on deterministic QoS analysis or stochastic QoS analysis have only considered a server that provides deterministic service, i.e. deterministically bounded rate service. Few have considered the behavior of a stochastic server that provides input flows with variable rate service, for example wireless links. In this paper, we propose a stochastic network calculus to analyze the end-to-end stochastic QoS performance of a system with stochastically bounded input traffic over a series of deterministic and stochastic servers. We also prove that a server serving an aggregate of flows can be regarded as a stochastic server for individual flows within the aggregate. Based on this, the proposed framework is further applied to analyze per-flow stochastic QoS performance under aggregate scheduling.     

On the Expressive Power of Schedulers in Distributed Probabilistic Systems

In this paper, we consider several subclasses of distributed schedulers and we investigate the ability of these subclasses to attain worst-case probabilities.Based on previous work, we consider the class of distributed schedulers, and we prove that randomization adds no extra power to distributed schedulers when trying to attain the supremum probability of any measurable set, thus showing that the subclass of deterministic schedulers suffices to attain the worst-case probability. Traditional schedulers are a particular case of distributed schedulers. So, since our result holds for any measurable set, our proof generalizes the well-known result that randomization adds no extra power to schedulers when trying to maximize the probability of an ω-regular language. However, non-Markovian schedulers are needed to attain supremum probabilities in distributed systems.We develop another class of schedulers (the strongly distributed schedulers) that restricts the nondeterminism concerning the order in which components execute. We compare this class against previous approaches in the same direction, showing that our definition is an important contribution. For this class, we show that randomized and non-Markovian schedulers are needed to attain worst-case probabilities.We also discuss the subclass of finite-memory schedulers, showing the intractability of the model checking problem for these schedulers.     

Combining model reference adaptive controllers and stochastic self-tuning regulators

The similarities between model reference adaptive controllers (MRAC) for minimum phase plants where the control objectives are specified by reference models and stochastic self-tuning regulators (S-STURE) for minimum phase plants where the control objectives are specified by autoregressive moving average (ARMA) stochastic models are investigated.These similarities permit the extension, for these two classes of adaptive systems, of the duality existing in the linear case with known parameters between modal control and minimum variance control. The convergence analysis of these schemes in a combined deterministic and stochastic environment allows one finally to define schemes which behave as a desired MRAC in a deterministic environment and as a desired S-STURE in a stochastic environment. The problem of removing the positive real conditions for convergence in deterministic and stochastic environment is also discussed.     

Artificial Neural Network support to monitoring of the evolutionary driven security aware scheduling in computational distributed environments

Monitoring of the system performance in highly distributed computing environments is a wide research area. In cloud and grid computing, it is usually restricted to the utilization and reliability of the resources. However, in today’s Computational Grids (CGs) and Clouds (CCs), the end users may define the special personal requirements and preferences in the resource and service selection, service functionality and data access. Such requirements may refer to the special individual security conditions for the protection of the data and application codes. Therefore, solving the scheduling problems in modern distributed environments remains still challenging for most of the well known schedulers, and the general functionality of the monitoring systems must be improved to make them efficient as schedulers supporting modules.In this paper, we define a novel model of security-driven grid schedulers supported by an Artificial Neural Network (ANN). ANN module monitors the schedule executions and learns about secure task–machine mappings from the observed machine failures. Then, the metaheuristic grid schedulers (in our case—genetic-based schedulers) are supported by the ANN module through the integration of the sub-optimal schedules generated by the neural network, with the genetic populations of the schedules.The influence of the ANN support on the general schedulers’ performance is examined in the experiments conducted for four types of the grid networks (small, medium, large and very large grids), two security scheduling modes—risky and secure scenarios, and six genetic-based grid schedulers. The generated empirical results show the high effectiveness of such monitoring support in reducing the values of the major scheduling criteria (makespan and flowtime), the run times of the schedulers and the grid resource failures.     

Scheduling with compressible and stochastic release dates

In this work we study a one-machine scheduling problem which is featured by: (a) the release date of each job is compressible and stochastic, (b) each job has to be delivered before its due date (deadline) and (c) the manufacturer can expedite the production through overtime at an extra cost. The objective function of the scheduling problem is to minimize the total cost which includes the compressing cost and the overtime production cost. We propose a heuristic algorithm in which the stochastic problem is converted to the deterministic problem by a release-time “converting policy”. We coin a concept of a job's late-release-impact factor (LRIF) and we propose a LRIF based converting policy. We compare the LRIF based converting policy with the ones used in practice, and the numerical test shows that the LRIF based converting policy can obtain the schedule with the lowest actual total cost.     

Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms

This paper deals with the reliability of task graph schedules with transient and fail-stop failures. While computing the reliability of a given schedule is easy in the absence of task replication, the problem becomes much more difficult when task replication is used. We fill a complexity gap of the scheduling literature: our main result is that this reliability problem is #P??-Complete (hence at least as hard as NP-Complete problems), both for transient and for fail-stop processor failures. We also study the evaluation of a restricted class of schedules, where a task cannot be scheduled before all replicas of all its predecessors have completed their execution. Although the complexity in this case with fail-stop failures remains open, we provide an algorithm to estimate the reliability while limiting evaluation costs, and we validate this approach through simulations.     

Parametric concavity in stochastic dynamic programs

e study a family of dynamic programs that are characterized by a deterministic vector of cost parameters. We show that if the single period cost function is concave with respect to this vector, then the optimal costs of the family of dynamic programs are also concave in the vector of costs. We also establish that the optimal cost inherits other properties, namely, super-additivity, +∞-star-shaped, 0-star-shaped, concavity-along-rays and monotonicity. When the vector of cost parameters evolves as a stochastic process and the single period cost is concave with respect to this vector, we show that the optimal cost is bounded above by the optimal cost for the dynamic program in which these stochastic cost parameters are replaced by their expectations in each period. We provide examples to illustrate how our results can be used to derive bounds which are either easy to compute or have analytical expressions. We also explain why such bounds are useful.     

Production planning optimization for manufacturing and remanufacturing system in stochastic environment

This article studies a single item dynamic lot sizing problem with manufacturing and remanufacturing provisions. The demands and returns are considered as both stochastic and deterministic. There are two inventories recoverable and serviceable inventory. We developed a dynamic programming based model with objective to determine the quantities that have to be manufactured or re-manufactured at each period in order to minimize the total cost, including production cost, holding cost for returns and finished goods, and backlog cost. Also, unit production cost is also taken as variable in case of deterministic case. Finally, a numerical example for each of deterministic and stochastic model is worked out to illustrate how the model is applied and to prove its feasibility.     

Matching and scheduling algorithms for minimizing execution timeand failure probability of applications in heterogeneous computing

In a heterogeneous distributed computing system, machine and network failures are inevitable and can have an adverse effect on applications executing on the system. To reduce the effect of failures on an application executing on a failure-prone system, matching and scheduling algorithms which minimize not only the execution time but also the probability of failure of the application must be devised. However, because of the conflicting requirements, it is not possible to minimize both of the objectives at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the reliability of the application. This goal is achieved by modifying an existing matching and scheduling algorithm. The reliability of resources is taken into account using an incremental cost function proposed in this paper and the new algorithm is referred to as the reliable dynamic level scheduling algorithm. The incremental cost function can be defined based on one of the three cost functions developed here. These cost functions are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. The simulation results confirm that the proposed incremental cost function can be incorporated into matching and scheduling algorithms to produce schedules where the effect of failures of machines and network resources on the execution of the application is reduced and the execution time of the application is minimized as well     

Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

In prior work on soft real-time (SRT) multiprocessor scheduling, tardiness bounds have been derived for a variety of scheduling algorithms, most notably, the global earliest-deadline-first (G-EDF) algorithm. In this paper, we devise G-EDF-like (GEL) schedulers, which have identical implementations to G-EDF and therefore the same overheads, but that provide better tardiness bounds. We discuss how to analyze these schedulers and propose methods to determine scheduler parameters to meet several different tardiness bound criteria. We employ linear programs to adjust such parameters to optimize arbitrary tardiness criteria, and to analyze lateness bounds (lateness is related to tardiness). We also propose a particular scheduling algorithm, namely the global fair lateness (G-FL) algorithm, to minimize maximum absolute lateness bounds. Unlike the other schedulers described in this paper, G-FL only requires linear programming for analysis. We argue that our proposed schedulers, such as G-FL, should replace G-EDF for SRT applications.     

An Lmi Approach To Non‐Fragile Guaranteed Cost Control Of Uncertain Discrete Time‐Delay Systems

This paper studies the non‐fragile Guaranteed Cost Control (GCC) problem via memoryless state‐feedback controllers for a class of uncertain discrete time‐delay linear systems. The systems are assumed to have norm‐bounded, time‐varying parameter uncertainties in the state, delay‐state, input, delay‐input and state‐feedback gain matrices. Existence of the guaranteed cost controllers are related to solutions of some linear matrix inequalities (LMIs). The non‐fragile GCC state‐feedback controllers are designed based on a convex optimization problem with LMI constraints to minimize the guaranteed cost of the resultant closed‐loop systems. Numerical examples are given to illustrate the design methods.     

Multi‐organization scheduling approximation algorithms

In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi‐Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives—makespan and average completion time—and show that MOSP is strongly NP‐Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives. Copyright © 2011 John Wiley & Sons, Ltd.     

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP^NP functions are not computable in polynomial-time with an NP oracle.