Space communications scheduler: A rule-based approach to adaptive deadline scheduling

Job scheduling is a deceptively complex subfield of computer science. The highly combinatorial nature of the problem, which is NP-complete in nearly all cases, requires a scheduling program to intelligently traverse an immense search tree to create the best possible schedule in a minimal amount of time. In addition, the program must continually make adjustments to the initial schedule when faced with last-minute user requests, cancellations, unexpected device failures, etc. A good scheduler must be quick, flexible, and efficient, even at the expense of generating slightly less-than-optimal schedules.

The Space Communications Scheduler (SCS) is an intelligent rule-based scheduling system developed at GE's Advanced Technology Laboratories. SCS is an adaptive deadline scheduler, which allocates modular communications resources to meet an ordered set of user-specified job requests on board the NASA Space Station. SCS uses pattern-matching techniques to detect potential conflicts within a schedule, then resolves these conflicts through algorithmic and heuristic means. As a result, the system generates and maintains high-density schedules without relying heavily on backtracking or blind search techniques. SCS was designed to allocate communication devices on board the Space Station, but its general-purpose scheduling strategy is suitable for many common real-world applications.     

Segment-based approach for real-time reactive rescheduling forautomatic manufacturing control

We propose a new segment-based approach for a real-time reactive rescheduling method. The approach is applicable to actual large-scale manufacturing systems, such as fully automated semiconductor wafer fabrication lines. The proposed method can efficiently (in terms of computation time) schedule processing operations at equipment units by dividing a wide scheduling range into small segments and by using a greedy scheduling algorithm. It can also reactivate infeasible schedules without sacrificing the quality of schedules in terms of productivity as much as possible. From the simulation results obtained, we experimentally confirmed that the proposed method reactivates, without significant productivity loss caused by the rescheduling algorithm itself, infeasible schedules faster than a comparative method commonly in use today. Consequently, the proposed method manages to keep schedules at each equipment unit executable in terms of processing performance and schedule quality     

Integrated resource scheduling in a distributed scheduling environment

The Space Station era presents a highly complex multimission planning and scheduling environment exercised over a highly distributed system. In order to automate the scheduling process, customers require a mechanism for communicating their scheduling requirements to NASA. An expressive scheduling notation that captures a wide range of customer requirements and scheduling options is one solution to this problem. This article describes a request language that a remotely located customer can use to specify his scheduling requirements to a NASA scheduler, thus automating the customer-scheduler interface. Additionally, this article describes a scheduler that can accept these requests, process them, generate schedules, and return schedule and resource availability information to the requester.     

An approach to rescheduling activities based on determination of priority and disruptivity

A constraint-based scheduling system called SPIKE is being used to create long-term schedules for the Hubble Space Telescope. Feedback from the spacecraft or from other ground support systems may invalidate some scheduling decisions and those activities concerned must be reconsidered. A function rescheduling priority is defined, which for a given activity performs a heuristic analysis and produces a relative numerical value that is used to rank all such entries in the order that they should be rescheduled. A function disruptivity is also defined that is used to place a relative numeric value on how much a preexisting schedule would be changed to reschedule an activity. Using these functions, two algorithms (a stochastic neural network approach and an exhaustive search approach) are proposed to find the best place to reschedule an activity. Prototypes have been implemented and preliminary testing reveals that the exhaustive technique produces only marginally better results at much greater computational cost.     

Hardware-software partitioning and pipelined scheduling of transformative applications

Transformative applications are computation intensive applications characterized by iterative dataflow behavior. Typical examples are image processing applications like JPEG, MPEG, etc. The performance of embedded hardware-software systems that implement transformative applications can be maximized by obtaining a pipelined design. We present a tool for hardware-software partitioning and pipelined scheduling of transformative applications. The tool uses iterative partitioning and pipelined scheduling to obtain optimal partitions that satisfy the timing and area constraints. The partitioner uses a branch and bound approach with a unique objective function that minimizes the initiation interval of the final design. We present techniques for generation of good initial solution and search-space limitation for the branch and bound algorithm. A candidate partition is evaluated by generating its pipelined schedule. The scheduler uses a novel retiming heuristic that optimizes the initiation interval, number of pipeline stages, and memory requirements of the particular design alternative. We evaluate the performance of the retiming heuristic by comparing it with an existing technique. The effectiveness of the entire tool is demonstrated by a case study of the JPEG image compression algorithm. We also evaluate the run time and design quality of the tool by experimentation with synthetic graphs.     

A design space exploration scheme for data-path synthesis

In this paper, we examine the multicriteria optimization involved in scheduling for data-path synthesis (DPS). The criteria we examine are the area cost of the components and schedule time. Scheduling for DPS is a well-known NP-complete problem. We present a method to find nondominated schedules using a combination of restricted search and heuristic scheduling techniques. Our method supports design with architectural constraints such as the total number of functional units, buses, etc. The schedules produced have been taken to completion using GABIND as written by Mandal et al., and the results are promising     

A periodic scheduling problem in flow control for datacommunication networks

The scheduling of user-session transmission-priority time slots in time-periodic frames on links in a network is considered from an algorithmic standpoint. Priority slot schedules with low schedule delays can be used in a flow control scheme to lower limits on packet intranetwork delay. An NP-completeness result is proved, showing that for general networks the scheduling of priority slots to obtain a minimum sum of schedule delays is algorithmically hard. Minimum-delay scheduling algorithms for special classes and a scheduling heuristic for general networks are presented     

Power-efficient and interference-free link scheduling algorithms for connected wireless sensor networks

A fundamental aspect in performance engineering of wireless sensor networks (WSN) is optimizing the set of links that can be concurrently activated to meet a given signal-to-interference-plus-noise ratio (SINR) threshold. The solution of this combinatorial problem is a key element in wireless link scheduling. Another key architectural goal in WSN is connectivity. The connectivity of sensor nodes is critical for WSN, as connected graphs can be used for both data collection and data dissemination. In this paper, we investigate the joint scheduling and connectivity problem in WSN assuming the SINR model. We propose algorithms to build connected communication graphs with power-efficient links to be scheduled simultaneously in one time slot. The algorithms aiming at minimizing the number of time slots needed to successfully schedule all the given links such that the nodes can communicate without interference in the SINR model. While power-efficient and interference-free schedules reduce energy consumption, minimization of the schedule length (shortest link scheduling) has the effect of maximizing network throughput. We propose one greedy randomized constructive heuristic, two local search procedures, and three greedy randomized adaptive search procedures metaheuristics. We report computational experiments comparing the effectiveness of the proposed algorithms. Our simulation also shows the trade-off between power consumption and schedule length and the results indicate that not only the overall performance of our algorithms, but also show that the total power and schedule length value of its solutions are better than the existing work.

     

Robust Packet Scheduling in Wireless Cellular Networks

This paper addresses the following robust scheduling problem: Given that only coarse-grained channel state information (i.e., bounds on channel errors, but not the fine-grained error pattern) is available, how to design a robust scheduler that ensures worst-case optimal performance? To solve this problem, we consider two coarse-grained channel error models and take a zero-sum game theoretic approach, in which the scheduler and the channel error act as non-cooperative adversaries in the scheduling process. Our results show that in the heavy channel error case, the optimal scheduler adopts a threshold form. It does not schedule a flow if the price (the flow is willing to pay) is too small, in order to maximize the system revenue. Among the scheduled flows, the scheduler schedules a flow with a probability inversely proportional to the flow price such that the risk of being caught by the channel error adversary is minimized. We also show that in the mild channel error model, the robust scheduling policy exhibits a balanced trade-off between a greedy decision and a conservative policy. The scheduler is likely to take a greedy decision if it evaluates the risk of encountering the channel error adversary now to be small. Therefore, robust scheduling does not always imply conservative decision. The scheduler is willing to take “risks” to expect higher gain in some scenarios. Our solution also shows that probabilistic scheduling may lead to higher worst-case performance compared to traditional deterministic policies. Finally, the current efforts show the feasibility to explore a probabilistic approach to cope with dynamic channel error conditions.     

Optimal Burst Scheduling in Optical Burst Switched Networks

Optical burst switching (OBS) is an emerging technology that allows variable size data bursts to be transported directly over dense wavelength division multiplexing links. In order to make OBS a viable solution, the burst-scheduling algorithms need to be able to utilize the available wavelengths efficiently, while being able to operate fast enough to keep up with the burst incoming rate. For example, for a 16-port OBS router with 64 wavelengths per link, each operating at 10 Gb/s, we need to process one burst request every 78 ns in order to support an average burst length of 100 kB. When implemented in hardware, the well-known horizon scheduler has O(1) runtime for a practical number of wavelengths. Unfortunately, horizon scheduling cannot utilize the voids created by previously scheduled bursts, resulting in low bandwidth utilization. To date, minimum starting void is the fastest scheduling algorithm that can schedule wavelengths efficiently. However, while its complexity is O(log m), it requires 10 log m memory accesses to schedule a single burst. This means that it can take up to several microseconds for each burst request, which is still too slow to make it a practical solution for OBS deployment. In this paper, we propose an optimal burst scheduler using constant time burst resequencing (CTBR), which has O(1) runtime. The proposed CTBR scheduler is able to produce optimal burst schedules while having processing speed comparable to the horizon scheduler. The algorithm is well suited to high- performance hardware implementation.     

Incremental scheduling algorithms for WDM/TDM networks with arbitrary tuning latencies

We focus on all-optical broadcast and select slotted WDM networks. Each network user is equipped with one tunable transmitter and one fixed receiver; full connectivity is achieved by tuning transmitters to all different wavelengths available in the optical spectrum. Tuning latencies are considered to be not negligible with respect to the slot time. A network controller allocates fixed size slots in a TDM/WDM frame according to requests issued by users via signalling procedures. User requests are accommodated in the frame incrementally, as soon as they are received by the network controller. Since we aim at an incremental solution, we impose a transparency constraint in the scheduling algorithm: new user requests may be accepted only without affecting existing allocations, otherwise they are refused. We propose a novel scheduling algorithm that may route some flows from source to destination through some intermediate nodes, following a multi-hop approach. A formal definition of an optimal transparent incremental scheduling algorithm is provided as an integer linear programming problem. The optimal incremental scheduling algorithm is NP-hard. Thus, a heuristic quasi-optimal scheduling algorithm is proposed, and its complexity is evaluated. Performance results show that significant benefits can be achieved with respect to traditional single-hop approaches and to other multi-hop approaches.     

Scheduling in Optical WDM Networks Using Hidden Markov Chain Based Traffic Prediction

This paper presents the design and performance analysis of a predictor-based scheduling algorithm for optical wavelength division multiplexed (WDM) networks. WDM technology provides multiple, simultaneous and independent gigabit-per-second channels on a single fiber. A reservation-based multiple access control (MAC) protocol is considered here for a local area WDM network based on the passive star topology. The MAC protocol schedules reservation requests from the network nodes on the multiple channels. In previous work, we have presented an on-line scheduling algorithm for such a network. We have shown earlier that schedule computation time can significantly affect performance and the scheduling algorithms should be simple for better performance. In this work, we further improve system performance by using a hidden Markov chain based prediction algorithm. The objective here is to reduce the amount of time spent in computing the schedule by predicting traffic requests. Performance analysis based on discrete-event simulation, varying parameters such as number of nodes and channels is presented. The results show that the error of prediction is reasonable for most cases: more than 70% of the time, the error between actual request and predicted request is less than 20%. Network throughput is higher with the proposed prediction algorithm due to pipelining of schedule computation.     

Process-Variation and Temperature Aware SoC Test Scheduling Technique

High temperature and process variation are undesirable phenomena affecting modern Systems-on-Chip (SoC). High temperature is a well-known issue, in particular during test, and should be taken care of in the test process. Modern SoCs are affected by large process variation and therefore experience large and time-variant temperature deviations. A traditional test schedule which ignores these deviations will be suboptimal in terms of speed or thermal-safety. This paper presents an adaptive test scheduling method which acts in response to the temperature deviations in order to improve the test speed and thermal safety. The method consists of an offline phase and an online phase. In the offline phase a schedule tree is constructed and in the online phase the appropriate path in the schedule tree is traversed based on temperature sensor readings. The proposed technique is designed to keep the online phase very simple by shifting the complexity into the offline phase. In order to efficiently produce high-quality schedules, an optimization heuristic which utilizes a dedicated thermal simulation is developed. Experiments are performed on a number of SoCs including the ITC’02 benchmarks and the experimental results demonstrate that the proposed technique significantly improves the cost of the test in comparison with the best existing test scheduling method.     

Integrated scheduling of flexible manufacturing systems employingautomated guided vehicles

Centralized and distributed automated guided vehicle system (AGVS) models for materials handling, and the model for part processing are integrated into a single coherent model. This formulation can be used to collectively schedule and control the entire flexible manufacturing system (FMS) as opposed to the traditional separate scheduling of part processing and material handling. The two AGVS models are based on Petri nets and can be directly used in the scheduling method that uses Petri nets for formulation and heuristic search for solution. This method employs a global search to seek the optimal operation of an entire FMS. Scheduling examples are presented and the method compares favorably with the results simulated using heuristic dispatch rules     

面向集成电路制造的基于Petri网的生产调度

本文提出了一个新的面向集成电路(IC)制造的调度方法,核心内容包括两方面:首先,用本文提出的扩展定时Petri 网对IC生产工艺进行描述;其次,对所得Petri 网模型的状态空间进行搜索,得到以Transition序列表示的最优或近似最优调度.该方法可以很好地描述IC制造系统中存在的多制造路径、资源共享、可变晶片组及并发等特性,通过引入测试弧增强Petri 网的建模能力,进而在调度模型上对设备维护、设备优先级以及操作优先级进行描述,而且支持多目标的评价函数,使得到的调度结果更具实用价值.文中给出试验结果表明了算法的有效性.     

Integrating Physical Constraints in HW-SW Partitioning for Architectures With Partial Dynamic Reconfiguration

Partial dynamic reconfiguration is a key feature of modern reconfigurable architectures such as the Xilinx Virtex series of devices. However, this capability imposes strict placement constraints such that even exact system-level partitioning (and scheduling) formulations are not guaranteed to be physically realizable due to placement infeasibility. We first present an exact approach for hardware-software (HW-SW) partitioning that guarantees correctness of implementation by considering placement implications as an integral aspect of HW-SW partitioning. Our exact approach is based on integer linear programming (ILP) and considers key issues such as configuration prefetch for minimizing schedule length on the target single-context device. Next, we present a physically aware HW-SW partitioning heuristic that simultaneously partitions, schedules, and does linear placement of tasks on such devices. With the exact formulation, we confirm the necessity of physically-aware HW-SW partitioning for the target architecture. We demonstrate that our heuristic generates high-quality schedules by comparing the results with the exact formulation for small tests and with a popular, but placement-uanaware scheduling heuristic for a large set of over a hundred tests. Our final set of experiments is a case study of JPEG encoding-we demonstrate that our focus on physical considerations along with our consideration of multiple task implementation points enables our approach to be easily extended to handle heterogenous architectures (with specialized resources distributed between general purpose programmable logic columns). The execution time of our heuristic is very reasonable-task graphs with hundreds of nodes are processed (partitioned, scheduled, and placed) in a couple of minutes     

Optimal broadcast scheduling in packet radio networks using meanfield annealing

We present an efficient broadcast scheduling algorithm based on mean field annealing (MFA) neural networks. Packet radio (PR) is a technology that applies the packet switching technique to the broadcast radio environment. In a PR network, a single high-speed wideband channel is shared by all PR stations. When a time-division multi-access protocol is used, the access to the channel by the stations' transmissions must be properly scheduled in both the time and space domains in order to avoid collisions or interferences. It is proven that such a scheduling problem is NP-complete. Therefore, an efficient polynomial algorithm rarely exists, and a mean field annealing-based algorithm is proposed to schedule the stations' transmissions in a frame consisting of certain number of time slots. Numerical examples and comparisons with some existing scheduling algorithms have shown that the proposed scheme can find near-optimal solutions with reasonable computational complexity. Both time delay and channel utilization are calculated based on the found schedules     

Synthesis of Hard Real-Time Application Specific Systems

This paper presents a system level approach for the synthesis of hard real-time multitask application specific systems. The algorithm takes into account task precedence constraints among multiple hard real-time tasks and targets a multiprocessor system consisting of a set of heterogeneous off-the-shelf processors. The optimization goal is to select a minimal cost multi-subset of processors while satisfying all the required timing and precedence constraints. There are three design phases: resource allocation, assignment, and scheduling. Since the resource allocation is a search for a minimal cost multi-subset of processors, we adopted an A* search based technique for the first synthesis phase. A variation of the force-directed optimization technique is used to assign a task to an allocated processor. The final scheduling of a hard-real time task is done by the task level scheduler which is based on Earliest Deadline First (EDF) scheduling policy. Our task level scheduler incorporates force-directed scheduling methodology to address the situations where EDF is not optimal. The experimental results on a variety of examples show that the approach is highly effective and efficient.     

Hybrid applications of constraint satisfaction and meta-heuristicsto railway timetabling: a comparative study

The paper provides a discussion on the train scheduling algorithms developed to create predictive schedules for a fleet of passenger trains which travel along a primarily single-track railway with some double-track stretches. The algorithms are an object oriented constraint based heuristic and two hybrid methods, which represent combinations of the heuristic with tabu search and simulated annealing search control strategies. The data of infrastructures and working timetables of passenger trains of Iran's railway system are used to evaluate and compare the generated schedules. Three delay based performance measures, i.e., sum of weighted waiting times (SWWTs), average of unit waiting time (AUWT), and maximum ratio of waiting time to journey time (MRWJ), are used to evaluate the schedules and compare algorithms, where AUWT and MRWJ are introduced by the authors. Simulation experiments show the success of the three methods and the relative advantages and disadvantages of the algorithms are discussed     

Engineering Dynamic Scheduler for Work Manager

Provision of service to business and residential customers, network maintenance and fault repair are core activities of large telecommunications companies which involve thousands of technicians every day. Managing a large-sized workforce efficiently in a highly dynamic environment is a challenge that BT has addressed by automating its work management processes within a single application known as Work Manager. For the most part, the success of Work Manager rests upon the ability of its work allocation component in determining the best assignments at any time and in any environment.This paper presents a scheduler for Work Manager which is both predictive and reactive and whose computational model reconciles genericity and efficiency. Coupling Constraint Satisfaction and Local Search, this scheduler can generate long-term schedules that satisfy the conflicting objectives of feasibility, productivity, quality of service and cost minimisation. It also provides the capability to adjust schedules before despatch through on-line heuristic repair/improvement. Equipped with a powerful interface, this system has been successfully trialled within the field and is now deployed nationally.