Expert systems tools for hubble space telescope observation scheduling

Construction of an efficient yearlong observing program for the Hubble Space Telescope (HST) requires the ordering of tens of thousands of proposer-specified exposures on a timeline while satisfying numerous coupled constraints. Although manually optimized planning can be performed for short time periods, routine operations will clearly require that most of the planning be done by software. This paper discusses the utility of expert systems techniques for HST planning and scheduling and describes a plan for development of expert system tools which will augment the existing ground system. Additional capabilities provided by these tools will include graphics-oriented plan evaluation, long-range analysis of the observation pool, analysis of optimal scheduling time intervals, constructing sequences of spacecraft activities which minimize operational overhead, and optimization of linkages between observations. Initial prototyping of a scheduler used the Automated Reasoning Tool (ART) running on a Texas Instruments Explorer Lisp workstation.     

Online Scheduling of Integrated Single-Wafer Processing Tools With Temporal Constraints

This paper addresses the issues of online scheduling for integrated single-wafer processing tools with temporal constraints. The integrated single-wafer processing tool is an integrated processing system consisting of single-wafer processing modules and transfer modules. Certain chemical processes require that the wafer flow satisfies temporal constraints, especially, postprocessing residency constraints. This paper proposes an online scheduling method that guarantees both logical and temporal correctness for the integrated single-wafer processing tools. First, mathematical formulation of the scheduling problem using temporal constraint sets is presented. Then, an online, noncyclic scheduling algorithm with polynomial complexity is developed. The proposed scheduling algorithm consists of two subalgorithms: FEASIBLE_SCHED_SPACE and OPTIMAL_SCHED. The former computes the feasible solution space in the continuous time domain, and the latter computes the optimal solution that minimizes the completion time of the last operation of a newly inserted wafer.     

Effect of Clock Skew in Event Driven,Delay Constrained Heterogeneous WSN with Anycast

In time critical event driven data gathering, anycasting technique is considered as one of the best methods that minimizes delay and maximizes lifetime. Moreover, asynchronous sleep/wake scheduling techniques like anycasting, is energy efficient compared to synchronous sleep/wake scheduling in rare event detection. However, asynchronous techniques incur additional delay during the event reporting as a result of the clock skew which may violate the delay constraint for a large number of packets. In this paper, we find the critical wake-up rate to constrain the increase in end-to-end delay, as a result of clock-skew, within given delay constraint \(\xi\), by estimating the expected increase in end-to-end delay using a stochastic approach. We verify our mathematical analysis using Monte-carlo simulation. Further simulation results in network simulator 2.34 (ns2) confirm the effectiveness of our approach.     

STEAC: A Platform for Automatic SOC Test Integration

The lack of electronic design automation tools for system-on-chip (SOC) test integration increases SOC development time and cost, so SOC test integration tools are important in the success of promoting SOC. We have stressed practical SOC test integration issues, including real problems found in test scheduling, test input/output (I/O) reduction, timing of functional test, scan I/O sharing, etc. In this paper, we further consider the requirement of integrating at-speed testing of embedded cores - to detect timing-related defects, our test architecture is equipped with at-speed test capability. Test scheduling is done based on our test architecture and test access mechanism, considering I/O resource constraints. Detailed scheduling further reduces the overall test time of the system chip. All these techniques are integrated into an automatic flow to facilitate SOC test integration. The test integration platform has been applied to both academic and industrial SOC cases. The chips have been designed and fabricated. The measurement results justify the approach - simple and efficient, i.e., short test integration cost, short test time, and small hardware and pin overhead.     

Transformation reborn: A new generation expert system for planning HST operations

The Transformation expert system (TRANS) converts proposals for astronomical observations with the Hubble Space Telescope (HST) into detailed observing plans. It encodes expert knowledge to solve problems faced in planning and commanding HST observations to enable their processing by the Science Operations Ground System (SOGS). Among these problems are determining an acceptable order of executing observations, grouping of observations to enhance efficiency and schedulability, inserting extra observations when necessary, and providing parameters for commanding HST instruments. TRANS is currently an operational system and plays a critical role in the HST ground system. It was originally designed using forward-chaining provided by the OPS5 expert system language, but has been reimplemented using a procedural knowledge base. This reimplementation was forced by the explosion in the amount of OPS5 code required to specify the increasingly complicated situations requiring expert-level intervention by the TRANS knowledge base. This problem was compounded by the difficulty of avoiding unintended interaction between rules. To support the TRANS knowledge base, XCL, a small but powerful extension to Common Lisp was implemented. XCL allows a compact syntax for specifying assignments and references to object attributes. XCL also allows the capability to iterate over objects and perform keyed lookup. The reimplementation of TRANS has greatly diminished the effort needed to maintain and enhance it. As a result of this, its functions have been expanded to include warnings about observations that are difficult or impossible to schedule or command, providing data to aid SPIKE, an intelligent planning system used for HST long-term scheduling, and providing information to the Guide Star Selection System (GSSS) to aid in determination of the long-range availability of guide stars.     

Asymptotic Throughput Analysis for Channel-Aware Scheduling

In this paper, we provide an asymptotic performance analysis of channel-aware packet scheduling based on extreme value theory. We first address the average throughput of systems with a homogeneous average signal-to-noise ratio (SNR) and obtain its asymptotic expression. Compared with the exact throughput expression, the asymptotic one, which is applicable to a broader range of fading channels, is more concise and easier to get insights. Furthermore, we confirm the accuracy of the asymptotic results by theoretical analysis and numerical simulation. For a system with heterogeneous SNRs, normalized-SNR-based scheduling needs to be used for fairness. We also investigate the asymptotic average throughput of the normalized-SNR-based scheduling, and prove that the average throughput in this case is less than that in the homogeneous case with a power constraint.     

Opportunistic packet scheduling algorithm for non-real-time service with a soft QoS requirement in a mobile broadband wireless access system

In this paper, we present a packet scheduling algorithm for a non-real-time service, with soft QoS requirements, which allows for degrading the QoS level, e.g., typically the packet delay, whenever necessary, in mobile broadband wireless Internet access systems. This algorithm is designed to properly trade off system throughput and delay performance, which can improve the system capacity by relaxing the delay constraint with respect to the underlying soft QoS requirement. This is as opposed to most of the existing packet scheduling algorithms for non-real-time service which are simply designed to maximize the system throughput without a delay constraint. The proposed adaptive exponential scheduling algorithm intentionally introduces additional delay to some users, especially under bad channel conditions, opportunistically allowing for serving users only under good channel conditions, as long as the resulting QoS degradation is acceptable for non-real-time service users. The results from a system-level simulation demonstrate that the system capacity can be significantly increased over existing algorithms, by as much as 65%, using the adaptive exponential scheduling algorithm while satisfying the given QoS-level requirements.     

Real-Time Dynamic Voltage Loop Scheduling for Multi-Core Embedded Systems

In this brief, we propose a novel real-time loop-scheduling technique to minimize energy consumption via dynamic voltage scaling (DVS) for applications with loops considering transition overhead. One algorithm, dynamic voltage loop scheduling (DVLS), is designed integrating with DVS. In DVLS, we repeatedly regroup a loop based on rotation scheduling and decrease the energy by DVS as much as possible within a timing constraint. We conduct the experiments on a set of digital signal processing benchmarks. The experimental results show that DVLS achieves big energy saving compared with the traditional time-performance-oriented scheduling algorithm     

Using C to build a satellite scheduling expert system: Examples from the explorer platform planning system

Recently, many expert systems have been developed in a LISP environment and then ported to the real world C environment before the final system is delivered. This situation may require that the entire system be completely rewritten in C and may actually result in a system that is put together as quickly as possible with little regard for maintainability and further evolution. With the introduction of high-performance UNIX and X-windows-based workstations, a great deal of the advantages of developing a first system in the LISP environment have become questionable. This paper describes a C-based artificial intelligence (AI) development effort based on a software tools approach with emphasis on reusability and maintainability of code. The discussion starts with simple examples of how list processing can easily be implemented in C and then proceeds to the implementations of frames and objects that use dynamic memory allocation. The implementation of procedures that use depth first search, constraint propagation, context switching, and a blackboard-like simulation environment are described. Techniques for managing the complexity of C-based AI software are noted, especially the object-oriented techniques of data encapsulation and incremental development. Finally, all these concepts are put together by describing the components of planning software called the Planning And Resource Reasoning (PARR) shell. This shell has been successfully utilized for scheduling services of the Tracking and Data Relay Satellite System for the Earth Radiation Budget Satellite since May of 1987 and will be used for operations scheduling of the Explorer Platform in November of 1991.     

Quality-driven cross-layer optimized video delivery over LTE

3GPP Long Term Evolution is one of the major steps in mobile communication to enhance the user experience for next-generation mobile broadband networks. In LTE, orthogonal frequency- division multiple access is adopted in the downlink of its E-UTRA air interface. Although cross-layer techniques have been widely adopted in literature for dynamic resource allocation to maximize data rate in OFDMA wireless networks, application-oriented quality of service for video delivery, such as delay constraint and video distortion, have been largely ignored. However, for wireless video delivery in LTE, especially delay-bounded real-time video streaming, higher data rate could lead to higher packet loss rate, thus degrading the user-perceived video quality. In this article we present a new QoS-aware LTE OFDMA scheduling algorithm for wireless real-time video delivery over the downlink of LTE cellular networks to achieve the best user-perceived video quality under the given application delay constraint. In the proposed approach, system throughput, application QoS constraints, and scheduling fairness are jointly integrated into a cross-layer design framework to dynamically perform radio resource allocation for multiple users, and to effectively choose the optimal system parameters such as modulation and coding scheme and video encoding parameters to adapt to the varying channel quality of each resource block. Experimental results have shown significant performance enhancement of the proposed system.     

基于混合算法的智能排课系统

传统采用单一排课算法设计的排课系统,编排出的课程表总是与期望结果相差太大。为了使课表编排结果能满足教学要求,在此对排课约束条件进行了详细分析,采用基于遗传算法和贪婪算法的混合算法进行排课系统设计,将排课分为时间安排和地点安排2部分进行,时间安排采用遗传算法设计,地点安排采用贪婪算法设计,时间安排和地点安排过程可以人工干预,编排的课程表基本符合教务管理需求。混合算法设计的智能排课系统编排的课程表更加科学化、合理化和人性化。     

Formal Approach of FMS Cyclic Scheduling

This correspondence is related to the determination of both control and scheduling of flexible manufacturing systems under cyclic command. Different approaches can be found in the literature, but we focus on those which respect the optimal throughput while minimizing the work in process. So, we recall methods of performance evaluation developed during the last 20 years. The last part is devoted to a new approach of cyclic scheduling using a Petri net. This method uses algebraic tools (dioids) developed for the study of marked graphs. In this way, the problem of the scheduling is progressively transformed into a problem of the search of solution(s) on a system of equations     

Constrained Codes as Networks of Relations

We address the well-known problem of determining the capacity of constrained coding systems. While the one-dimensional case is well understood to the extent that there are techniques for rigorously deriving the exact capacity, in contrast, computing the exact capacity of a two-dimensional constrained coding system is still an elusive research challenge. The only known exception in the two-dimensional case is an exact (however, not rigorous) solution to the -run-length limited (RLL) system on the hexagonal lattice. Furthermore, only exponential-time algorithms are known for the related problem of counting the exact number of constrained two-dimensional information arrays. We present the first known rigorous technique that yields an exact capacity of a two-dimensional constrained coding system. In addition, we devise an efficient (polynomial time) algorithm for counting the exact number of constrained arrays of any given size. Our approach is a composition of a number of ideas and techniques: describing the capacity problem as a solution to a counting problem in networks of relations, graph-theoretic tools originally developed in the field of statistical mechanics, techniques for efficiently simulating quantum circuits, as well as ideas from the theory related to the spectral distribution of Toeplitz matrices. Using our technique, we derive a closed-form solution to the capacity related to the Path-Cover constraint in a two-dimensional triangular array (the resulting calculated capacity is ). Path-Cover is a generalization of the well known one-dimensional -RLL constraint for which the capacity is known to be .     

Traffic and Interference Adaptive Scheduling for Internet Traffic in UMTS

In this paper we propose a scheduling strategy for the radio resources management when transmitting Internet traffic over third-generation systems. More precisely, we consider the UMTS Terrestrial Radio Access Network (UTRAN) Time Division Duplex (TDD) mode standardized by ETSI. UTRAN TDD uses a hybrid solution of code and time division multiple access, called TD-CDMA. In UMTS systems a key issue in developing access methodologies for the available spectrum is an optimal management of the rare radio resources. In this paper we present a fair and efficient scheduling algorithm that adapts its behavior to traffic and interference conditions. Specifically, our scheduling algorithm is able to manage the radio resources taking into account both the traffic fluctuations in the uplink and downlink direction and the variations of the system interference. The goal of our scheduler is the data-throughput maximization for an efficient utilization of available radio resources. The effectiveness of our scheduling algorithm is shown by exploiting analytical tools.     

Cooperative scheduling and its application to steelmaking processes

A cooperative approach to scheduling problems is proposed, and its application to creating daily schedules for steelmaking processes is described. In cooperative scheduling, procedures, rules, and the user cooperate to make a feasible schedule efficiently. The procedures, collectively called a scheduling engine, work as a local constraint satisfier to solve general primitive constraints. Rules that represent domain-dependent knowledge then solve the domain-specific constraints by means of a pattern-matching function. The user evaluates the schedule and modifies it by means of a user-friendly interface with direct-manipulation functions. The user interaction is therefore included in the system architecture as a global constraint satisfier. The iteration of this cycle improves the schedule until it becomes feasible. Experimental results obtained with Scheplan, the scheduling environment that applies this approach to scheduling steelmaking processes, show that the daily scheduling time is much less than in manual scheduling and the quality of the schedule is much improved     

一种基于资源约束的工作流建模及分析方法

资源约束是工作流正确实施的一个瓶颈问题,因此工作流系统的资源建模及模型正确性验证方法显得非常重要.为此,基于Petri网和工作流建模方法,提出了一种资源约束的工作流系统的形式化建模和分析技术,定义了资源空间(RS)、资源子网、资源工作流网和资源工作流网完整性(soundness)的概念,建立了资源调用视图以及Petri网影射模型,得到了资源工作流网保持完整性判定的一个充要条件.该方法将系统资源建模和过程建模合成到一个模型中,解决了工作流系统资源和过程分别建模给系统的正确性验证带来的困难,为工作流系统资源状态的可视化和进行有效的系统验证提供了模型依据.给出的实例验证了模型的有效性.     

Quasi-Static Scheduling of CAL Actor Networks for Reconfigurable Video Coding

The upcoming Reconfigurable Video Coding (RVC) standard from MPEG (ISO / IEC SC29WG11) defines a library of coding tools to specify existing or new compressed video formats and decoders. The coding tool library has been written in a dataflow/actor-oriented language named CAL. Each coding tool (actor) can be represented with an extended finite state machine and the data communication between the tools are described as dataflow graphs. This paper proposes an approach to model the CAL actor network with Parameterized Synchronous Data Flow and to derive a quasi-static multiprocessor execution schedule for the system. In addition to proposing a scheduling approach for RVC, an extension to the well-known permutation flow shop scheduling problem that enables rapid run-time scheduling of RVC tasks, is introduced.     

复杂真实约束条件下的多星测控资源调度

测控资源调度是卫星调度研究领域的关键问题之一,其在多星条件下面临着因约束信息来源不同、结构差异大、表达模糊而难以建立统一的约束模型,以及求调度问题的最优解是NP-hard的且不易得到较优解的问题。为此,首先将多星测控问题表达为组合优化模型,再将复杂的约束信息归纳为一套约束,最后提出了一种双层并行约束匹配算法求解问题。与用户现有算法对比,所提算法的周期测控调度成功率提升了9%左右,且可以处理更多约束信息类型。     

Energy efficient transmission scheduling for delay constrained wireless networks

In this paper, we address the problem of energy efficient packet scheduling in a wireless environment. We consider a wireless transmitter which is limited by its finite battery resource. Our objective is to design a transmission schedule that maximizes battery lifetime subject to some delay constraints. To achieve this, we exploit two previously unconnected ideas: (i) channel coding can be used to conserve energy by transmitting at reduced power levels over longer durations; (ii) electro-chemical mechanisms in batteries allow them to recover energy during idle periods. While the first idea favors extending transmission durations, the second idea requires the transmitter to be idle to allow for recovery. In other words, bursty packet transmissions interspersed with idle periods extend battery life. Therefore, a strategy which is based entirely on either one or the other idea is not optimal. We provide a framework to merge the two ideas. We consider two kinds of delay constraints, one a deadline constraint and the other an average delay constraint and show that energy aware scheduling strategies for both these scenarios can result in significant energy savings.