Scheduling multiple part-types in an unreliable single-machinemanufacturing system

Quadratic approximations to the differential cost-to-go function, which yield linear switching curves, have been extensively studied in the literature. In this paper, we provide solutions to the partial differential equations associated with the components of the steady-state probability density function of the buffer levels for two part-type, single-machine flexible manufacturing systems under a linear switching curve (LSC) policy. When there are more than two part-types, we derive the probability density function, under a prioritized hedging point (PHP) policy by decomposing the multiple part-type problem into a sequence of two part-type problems. The analytic expression for the steady-state probability density function is independent of the cost function. Therefore, for average cost functions, we can compute the optimal PHP policy or the more general optimal LSC policy for two part-type problems     

Optimal control structure of an unreliable manufacturing systemwith random demands

This paper considers an unreliable manufacturing system with random processing times and random product demands. The system can produce many part types and its total capacity is constrained by a fixed constant. The objective is to find an optimal service-rate allocation policy between different part types by minimizing the expected discounted inventory and backlog cost. Structural properties of the optimal control policy are investigated. It is shown that the optimal policy is of a switching structure. For producing a one part type case, the optimal control is a threshold policy. For producing a two part types case, the optimal control can be described by three monotone switching curves and its asymptote properties are derived. Numeric examples are given to illustrate the results     

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.     

Multi-armed bandits with switching penalties

The multi-armed bandit problem with switching penalties (switching cost and switching delays) is investigated. It is shown that under an optimal policy, decisions about the processor allocation need to be made only at stopping times that achieve an appropriate index, the well-known “Gittins index” or a “switching index” that is defined for switching cost and switching delays. An algorithm for the computation of the “switching index” is presented. Furthermore, sufficient conditions for optimality of allocation strategies, based on limited look-ahead techniques, are established. These conditions together with the above-mentioned feature of optimal scheduling policies simplify the search for an optimal allocation policy. For a special class of multi-armed bandits (scheduling of parallel queues with switching penalties and no arrivals), it is shown that the aforementioned property of optimal policies is sufficient to determine an optimal allocation strategy. In general, the determination of optimal allocation policies remains a difficult and challenging task     

Production rate control for failure-prone production systems withno backlog permitted

In this paper, we consider systems in which backlog is not allowed. We show that the hedging point policy is still optimal. For systems with backlog, it is usually quite straightforward to show that their optimal cost-to-go functions are convex-a key property that is needed for the hedging point policy to be optimal. With no backlog permitted, it becomes much more difficult to establish the convexity property, and the explicit formulas for the optimal hedging point and the optimal cost-to-go functions have to be obtained, based on which the convexity property can then be verified. The method we use in this paper to derive these explicit formulas is mainly based on an interesting relationship between the inventory process of the system under the hedging point policy and some stochastic processes which are well studied in queueing theory     

Value function-based approach to the scheduling of multiple controllers

Both gain scheduling and multiple model based control approaches are considered to be practical approaches for control of industrial nonlinear processes. However, the former ignores system dynamics and the latter is specific to the type of controller design and limited in its scope of application as practiced in industry. This paper proposes a value function-based strategy for switching among local controllers, thereby providing an effective global control policy for the entire operating regions. The suggested method selects the best one among a set of available control policies at each time step by evaluating the “value” function associated with the successive state when a particular control action instructed by a candidate policy is taken for a give state. The value function, which maps a state to its associated discounted infinite horizon cost-to-go, is obtained by solving the dynamic programming in an approximate way using closed-loop simulation or operational data and a function approximator. The proposed approach has the advantages that candidate controllers are general and the switching is performed not by a fixed heuristic rule but rigorously via dynamic programming. From the viewpoint of dynamic programming, the approach helps alleviate the curse of dimensionality with respect to the state space and action space. Optimal or approximately optimal switching rules can be learned without a model, which defines the state transitional rule. The approach is demonstrated on several different nonlinear control examples.     

Optimal control of two interacting service stations

Optimal controls described by switching curves in the two-dimensional state space are shown to exist for the optimal control of a Markov network with two service stations and linear cost. The controls govern routing and service priorities. Finite horizon and long run average cost problems are considered and value iteration is a key tool. Nonconvex value functions are shown to exist for slightly more general networks. Nonconvex value functions are also shown to arise for a simple single station control problem in which the instantaneous cost is convex but not monotone. Nevertheless, optimality of threshold policies is established for the single station problem. The proof is based on a novel use of stochastic coupling and policy iteration.     

Optimal and suboptimal control policies for a solar collector system

An optimal control problem to maximize the net energy gathered by a flat-plate solar collector system by controlling the collector fluid flow rate is investigated. The problem is formulated in terms of a distributed parameter system and solved using the method of characteristics. It is shown that if the pump of the collector loop is such that its pumping power is greater than a linear function of the fluid velocity, then the optimal control policy is one in which the fluid flow is instantly switched between zero and maximum rates. Necessary conditions that determine the optimal switching times are derived. Because the resultant switching function of the optimal policy is shown to be decomposable into two parts, one that depends on the state of the system and another that requires a priori knowledge of the solar intensity over the entire period of operation, a suboptimal control policy that can be implemented by an on/off feedback controller with hysteresis is proposed. When this suboptimal policy is compared with the optimal policy, it is shown that on a clear day with sufficient solar insolation to dictate a two-switch optimal policy, the two policies are identical. Under other weather conditions, the feedback suboptimal controller will keep the pump off for a slightly shorter period of time than the time dictated by the optimal control.     

随机需求不可靠制造系统的最优服务率分配策略

本文讨论了一类随机需求不可靠制造系统的最优服务率控制问题。所研究的系统能同时生产多类产品，但生产能力受常数限制。目标是通过最小化库顾和欠缺的期望折扣费用，寻找最优服务率分配策略，本文证明了最优策略具有开关结构，并针对生产单类和两类产品的系统详细研究了最优控制策略的结构性质，最后以数值例子验证了本文的结论。     

Self-balancing dynamic scheduling of electrical energy for energy-intensive enterprises

Balancing production and consumption with self-generation capacity in energy-intensive enterprises has huge economic and environmental benefits. However, balancing production and consumption with self-generation capacity is a challenging task since the energy production and consumption must be balanced in real time with the criteria specified by power grid. In this article, a mathematical model for minimising the production cost with exactly realisable energy delivery schedule is formulated. And a dynamic programming (DP)-based self-balancing dynamic scheduling algorithm is developed to obtain the complete solution set for such a multiple optimal solutions problem. For each stage, a set of conditions are established to determine whether a feasible control trajectory exists. The state space under these conditions is partitioned into subsets and each subset is viewed as an aggregate state, the cost-to-go function is then expressed as a function of initial and terminal generation levels of each stage and is proved to be a staircase function with finite steps. This avoids the calculation of the cost-to-go of every state to resolve the issue of dimensionality in DP algorithm. In the backward sweep process of the algorithm, an optimal policy is determined to maximise the realisability of energy delivery schedule across the entire time horizon. And then in the forward sweep process, the feasible region of the optimal policy with the initial and terminal state at each stage is identified. Different feasible control trajectories can be identified based on the region; therefore, optimising for the feasible control trajectory is performed based on the region with economic and reliability objectives taken into account.     

不完全柔性制造系统的最优控制

考虑具有随机需求的不完全柔性制造系统的最优控制，系统在各种产品间的切换时间是不可忽略的。运用马尔可夫最优决策过程归纳方法，导出机器服务率的最优控制策略。通过分析最优值函数的性质，证明最优策略具有简单的阈值结构，从而可得到次优生产策略--阈值控制策略。     

Optimal allocation of a server between two queues with due times

Two queues share a single server. Arrivals to each queue have individual target due times for service completion (their due times are known to the controller) and a penalty is incurred when they stay in the system after the expiration of these due times. The two classes have different service requirements and incur penalty at different rates. The problem of dynamic priority assignment so as to minimize the discounted and average tardiness per customer is considered. The problem is formulated in discrete time where it is shown that, under the assumptions of geometric arrivals and geometric services, there is a nonidling stationary optimal preemptive policy. Within each class, the policy chooses, if at all, the customer with the smallest due time. A partial order on the space of the set of residual times is introduced. It is shown that the optimal choice of the customer class is monotonic with respect to this partial order; this implies a switchover-type property in the appropriate space. A combination of stochastic dominance and dynamic programming ideas is used to establish the results     

计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.     

Modeling and analysis of a communication switching processor

A communication switching processor is modeled as an M/G/1 queueing system with a processor sharing service discipline. Messages arrive at the processor according to a Poisson stochastic process. The service requirements of a message consist of various communication functions performed at the processor and are organized into a set of tasks. Each task service time is a random variable from a general distribution. Tasks are assigned prescribed priorities. The tasks of a message are served sequentially. The processor serves tasks according to their priority and tasks of the same priority on a FCFS basis.This paper analytically derives the average delay of an arbitrary task in the system. The use of the results in the design of communication processors is illustrated.     

Optimal scheduling of two competing queues with blocking

Consideration is given to the problem of optimal scheduling for two queues for service at a single station, where the queues have finite capacities and the service rate is class-dependent. The cost structure is linear in the number of holding customers in the queues, combined with blocking costs incurred whenever arrivals encounter a full queue. The authors derive the optimal policy minimizing this criterion when the blocking cost is larger than the holding cost for each queue. Then they show that the optimal policy is of the switching type. Numerical results are included to support the analytical findings     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

Joint admission,production sequencing,and production rate control for a two-class make-to-order manufacturing system

Today's manufacturing industry faces a number of challenges related to the rapid delivery of products with a high degree of variety. Striking a balance between the effectiveness in capacity utilization and the rapidness in order-fulfillment is a substantial challenge for manufacturing companies. This work aims to provide a theoretical basis from which to address this practical question. To this end, we address the problem of coordinating the admission, production sequencing, and production rate controls for a two-class make-to-order manufacturing system. Formulating the problem as a Markov decision process model, we identify the structural properties of optimal control policies under both discounted and average profit criteria. We show that the cμ rule is optimal for production sequencing and the optimal admission and production rate control policies can be characterized by the state-dependent threshold levels, provided that the production times are not associated with customer class. We also show that the optimal production rates are monotone in the system state, as in the case of a single class queueing system, and that the lower priority class can be preferred to the higher priority class in order admission under a certain condition on the system parameters. Our numerical study demonstrates that a considerable economic benefit can be achieved if the production rate is dynamically controlled between the minimum and maximum rates rather than fixed to the mean rate of these values. Finally, we present a heuristic policy that is described by linear switching functions for the control of order admission and a selection rule for the control of production rate. We compare the performance of our heuristic to the optimal policy using a numerical experiment, revealing that the heuristic provides near optimal solutions to test example problems and is robust to the system parameters.     

多处理器全局单调比率的可调度性分析

针对全局单调比率(RM)调度的多处理器系统中最高优先级任务数量少于处理器数量时,Bertogna等给出的最坏情况计算任务受到的干涉过于悲观,证明了任务受到最高优先级任务的干涉不会出现最坏情况,它受到非最高优先级任务干涉仍可能出现最坏情况。分析得出了任务受到最高优先级任务干涉的最大可能值,由此得到了一个更紧的可调度性判断条件。实验结果表明,提出的方法提高了判为可调度的任务集数量。     

Evaluation of Guidance Performance in Urban Terrains for Different UAV Types and Performance Criteria Using Spatial CTG Maps

Unmanned aerial vehicles (UAVs) present in a wide range of scales, airframe types and possible systems configurations. Assessing how these different systems perform, therefore, should be an essential part of their design. This task, however, is particularly difficult due to the complex, dynamic interactions these vehicles are capable of, and the often complex operational conditions. In this paper we describe and apply an evaluation framework based on spatial cost-to-go (SCTG) maps. These maps describe the spatial distributions of optimal state and cost-to-go for a given geographical environment, and are computed using a finite-state approximation of the vehicle dynamics. The SCTG maps embed the interaction effects between vehicle dynamics and environment, and thus provide a rigorous basis for the evaluation of the airframe, various system and environment factors. The paper describes the results obtained applying this framework to a basic goal-directed guidance task taking place in an urban environment. Three small-scale UAV types are compared: a fixed-wing aircraft, a standard helicopter, and a quad-rotorcraft. Both minimum-time and minimum-energy performance criteria are analyzed to determine overall performance characteristics and highlight the basic features of the proposed framework.     

Optimal and heuristic policies for dynamic server allocation

We examine a system where the servers in a cluster may be switched dynamically and preemptively from one kind of work to another. The demand consists of M job types joining separate queues, with different arrival and service characteristics, and also different relative importance represented by appropriate holding costs. The switching of a server from queue i to queue j incurs a cost which may be monetary or may involve a period of unavailability. The optimal switching policy is obtained numerically by solving a dynamic programming equation. Two simple heuristic policies—one static and one dynamic—are evaluated by simulation and are compared to the optimal policy. The dynamic heuristic is shown to perform well over a range of parameters, including changes in demand.