Fast heuristic scheduling based on neural networks for real-time systems

As most of the real-time scheduling problems are known as hard problems, approximate or heuristic scheduling approaches are extremely required for solving these problems. This paper presents a new heuristic scheduling approach based on a modified Hopfield-Tank neural network to schedule tasks with deadlines and resource requirements in a multiprocessor system. In this approach, fast heuristic scheduling is achieved by performing a heuristic scheduling policy in conjunction with backtracking on the neural network. The results from our previous work, using the same neural network architecture without backtracking, are included here as a case with zero backtracking. Extensive simulation, which includes comparison with the conventional heuristic approach, is used to validate the effectiveness of our approach.     

A high-performance exact method for the resource-constrained project scheduling problem

This paper describes an efficient exact algorithm for project scheduling with resource constraints. The procedure consists of creating partial schedules which are always feasible with respect to both precedence and resource constraints. These partial schedules are connected through a tree, and a lower bound on the completion of the uncompleted activities is associated with each partial schedule. The branching process takes place from a partial schedule with the minimum lower bound and continues until the optimal schedule is created. Despite branching from a partial schedule with the minimum lower bound, the algorithm does not need large memory for keeping partial schedules as independent data, and does not require large comparability time for selecting a partial schedule to branch from. These make it possible to solve test problems each involving up to 100 activities and six different resource types. The computational results of the performance of the algorithm are reported.Scope and purposeThe resource-constrained project scheduling (RCPS) problem occurs in industrial organizations, and has been of a particular interest to industrial engineers. Current branch-and-bound procedures to find optimal solutions to this problem are based on either best-first or backtracking schemes. Best-first methods avoid redundant calculation but need a large amount of memory, which makes them impractical for solving large-sized problems. On the other hand, backtracking methods do not require a large amount of memory, but require extensive duplicating searching. This paper develops a procedure which integrates the positive features of both best-first and backtracking methods to solve the RCPS problem. The computational results show that the procedure has the advantages of being practical in the sense of memory requirements as well as ability to avoid a great deal of duplicating searching.     

A static scheduling algorithm for distributed hard real-time systems

A static scheduling algorithm is presented for off-line scheduling of tasks in distributed hard real-time systems. The tasks considered are instances of periodic jobs and have deadlines, resource requirements and precedence constraints. Tasks are divided into nonpreemptable blocks and all task characteristics are known a priori. The algorithm orders the tasks and iteratively schedules the tasks according to the order. Each task is scheduled globally by selecting a node to which it is assigned. Then, the task is scheduled locally by adding the task to the schedule of the selected node. Heuristics are used for both task ordering and node selection in order to guide the algorithm to a feasible schedule. Whenever local scheduling leads to an infeasible schedule, backtracking is used.Results of simulation studies of randomly generated task sets are presented. Although the scheduling problem is NP-hard, the results show that time performance is acceptable for off-line scheduling, except for extremely difficult task sets which make extensive use of the available resources.     

Backtracking-Based Instruction Scheduling to Fill Branch Delay Slots

Conventional schedulers schedule operations in dependence order and never revisit or undo a scheduling decision on any operation. In contrast, backtracking schedulers may unschedule operations and can often generate better schedules. This paper develops and evaluates the backtracking approach to fill branch delay slots. We first present the structure of a generic backtracking scheduling algorithm and prove that it terminates. We then describe two more aggressive backtracking schedulers and evaluate their effectiveness. We conclude that aggressive backtracking-based instruction schedulers can effectively improve schedule quality by eliminating branch delay slots with a small amount of additional computation.     

Adapting the behavior of a job-shop scheduling system

Factory scheduling consists in assigning resources (e.g. machines) and start and end times to operations. Our work is concerned with the problems of schedule generation and schedule revision when unanticipated events occur on the factory floor. SONIA is a knowledge-based scheduling system provided with a blackboard architecture for coordinating the activation of various scheduling and analyzing knowledge sources. In this paper, we focus on the various behaviors these knowledge sources can have and we gather a collection of conclusions regarding the use of various backtracking strategies and the control of constraint propagation.     

Time‐selective integrated scheduling algorithm with backtracking adaptation strategy

Currently, integrated scheduling algorithms schedule processes using fixed rules, making it difficult to balance serial and parallel processes in product craftsmanship trees while conducting complicated single product scheduling. To solve this problem, we propose a time‐selective integrated scheduling algorithm with a backtracking adaptation (TISAWBA) strategy. The proposed process sequence sorting strategy aims to determine process scheduling sequences based on the overall structure of the machining craftsmanship tree. The proposed time‐selective scheduling strategy aims to select the process portfolio with the minimum total elapsed time for machining from a process portfolio set based on craftsmanship tree structure. The proposed backtracking adaptation strategy conducts backtracking adaptation to find process portfolios having a total elapsed machining time greater than the “scheduling reference time.” Finally, illustrative use cases verify that TISAWBA guarantees parallel processing for parallel processes and elevates the proximity of serial processes, generating optimized integrated scheduling results.     

I/O scheduling for digital continuous media

A growing set of applications require access to digital video and audio. In order to provide playback of such continuous media (CM), scheduling strategies for CM data servers (CMS) are necessary. In some domains, particularly defense and industrial process control, the timing requirements of these applications are strict and essential to their correct operation. In this paper we develop a scheduling strategy for multiple access to a CMS such that the timing guarantees are maintained at all times. First, we develop a scheduling strategy for the steady state, i.e., when there are no changes in playback rate or operation. We derive an optimal Batched SCAN (BSCAN) algorithm that requires minimum buffer space to schedule concurrent accesses. The scheduling strategy incorporates two key constraints: (1) data fetches from the storage system are assumed to be in integral multiples of the block size, and (2) playback guarantees are ensured for frame-oriented streams when each frame can span multiple blocks. We discuss modifications to the scheduling strategy to handle compressed data like motion-JPEG and MPEG. Second, we develop techniques to handle dynamic changes brought about by VCR-like operations executed by applications. We define a suite of primitive VCR-like operations that can be executed. We show that an unregulated change in the BSCAN schedule, in response to VCR-like operations, will affect playback guarantees. We develop two general techniques to ensure playback guarantees while responding to VCR-like operations: passive and active accumulation. Using user response time as a metric we show that active accumulation algorithms outperform passive accumulation algorithms. An optimal response-time algorithm in a class of active accumulation strategies is derived. The results presented here are validated by extensive simulation studies.     

基于回溯算法的实验室排课系统的分析与设计

在实践教学场所有限的条件下,研究实验室排课问题,有助于提高教学的有序性及资源得利用率。文章根据实际需求设计出了一种基于优先级回溯算法的实验室排课系统。文中根据约束条件得到了具体的排课算法,在此基础上,采用B/S结构进行了系统设计,实现了教师申报、查询、排课、实验室应用分析等功能,运行以来效果良好,具有一定的实用价值。     

Performance analysis of active schedules in identical parallel machine

Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs’ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.     

Supporting rescheduling using CSP, RMS and POB—an example application

This paper introduces an innovative approach to the problem of rescheduling within manufacturing industry. An example of a manufacturing context that requires rescheduling capability is given (tyre production). The meaning of rescheduling, possible metrics for assessment of rescheduling and the advantages of applying the new techniques are reviewed. Of particular importance is the notion that the technology for providing rescheduling and explanation capabilities is to a large degree problem and context insensitive. The manner in which an original schedule has been created is irrelevant to the use of the technology described, allowing the advantages of the approach to be realized as an add-on facility to any existing scheduling system that fulfills a minimal set of requirements. These advantages are due to the use of a constraint based approach to new schedule creation used in tandem with dependency analysis techniques based on reason maintenance systems (de Kleer, 1986) and partial order backtracking (Ginsberg and McAllister, 1995; Spragg and Kelleher, 1996).     

Scheduling Independent Multiprocessor Tasks

Abstract. We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.     

A multi-agent based approach to dynamic scheduling with flexible processing capabilities

A multi-agent based system is proposed to simultaneous scheduling of flexible machine groups and material handling system working under a manufacturing dynamic environment. The proposed model is designed by means of \(\hbox {Prometheus}^{\mathrm{TM}}\) methodology and programmed in \(\hbox {JACK}^{\mathrm{TM}}\) agent based systems development environment. Each agent in the model is autonomous and has an ability to cooperate and negotiate with the other agents in the system. Due to these abilities of agents, the structure of the system is more suitable to handle dynamic events. The proposed dynamic scheduling system is tested on several test problems the literature and the results are quite satisfactory because it generates effective schedules for both dynamic cases in the real time and static problem sets. Although the model is designed as an online method and has a dynamic structure, obtained schedule performance parameters are very close to those obtained from offline optimization based algorithms.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

A Complete 4-parametric complexity classification of short shop scheduling problems

We present a comprehensive complexity analysis of classical shop scheduling problems subject to various combinations of constraints imposed on the processing times of operations, the maximum number of operations per job, the upper bound on schedule length, and the problem type (taking values ??open shop,?? ??job shop,?? ??mixed shop??). It is shown that in the infinite class of such problems there exists a finite basis system that allows one to easily determine the complexity of any problem in the class. The basis system consists of ten problems, five of which are polynomially solvable, and the other five are NP-complete. (The complexity status of two basis problems was known before, while the status of the other eight is determined in this paper.) Thereby the dichotomy property of that parameterized class of problems is established. Since one of the parameters is the bound on schedule length (and the other two numerical parameters are tightly related to it), our research continues the research line on complexity analysis of short shop scheduling problems initiated for the open shop and job shop problems in the paper by Williamson et?al. (Oper. Res. 45(2):288?C294, 1997). We improve on some results of that paper.     

DESH: overhead reduction algorithms for deferrable scheduling

Although the deferrable scheduling algorithm for fixed priority transactions (DS-FP) has been shown to be a very effective approach for minimizing real-time update transaction workload, it suffers from its on-line scheduling overhead. In this work, we propose two extensions of DS-FP to minimize the on-line scheduling overhead. The proposed algorithms produce a hyperperiod from DS-FP so that the schedule generated by repeating the hyperperiod infinitely satisfies the temporal validity constraint of the real-time data. The first algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Construction (DESH-SC), searches the DS-FP schedule for a hyperperiod. The second algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Adjustment (DESH-SA), adjusts the DS-FP schedule in an interval to form a hyperperiod. Our experimental results demonstrate that while both DESH-SC and DESH-SA can reduce the scheduling overhead of DS-FP, DESH-SA outperforms DESH-SC by accommodating significantly more update transactions in the system. Moreover, DESH-SA can also achieve near-optimal update workload.     

Controlling the data space of tree structured computations

We study the problem of scheduling a parallel computation so as to minimize the maximum number of data items extant at any point in the execution. Computations are expressed as directed graphs, where nodes represent primitive operations and arcs represent data dependences. The result of an operation is extant after the operation executes and until all immediate successors have begun execution. Our goal is to schedule computations so as to minimize both the maximum space required for extant data and the overall completion time.The classical problem of multiprocessor scheduling with precedence constraints is a special case of our problem, obtained by disregarding the data-space constraint. This special case is NP-complete for general graphs; a time-optimal multiprocessor scheduling algorithm is known only for the class of arbitrary trees. For this same class of arbitrary trees we present a multiprocesssor scheduling algorithm where the completion time is optimal within a constant factor, while the data-space size exceeds the optimal by a factor not greater than the number of processors.For an arbitrary n-node precedence tree T of in-degree Δ, we present:

(1)an algorithm for evaluating the lower bound on the size of data space required for executing T, regardless of the completion time or number of processors;

(2)a proof that the lower bound of Part 1 may be as large as (Δ−1)lgn but not larger;

(3)a single-processor schedule that executes T in time that equals the optimal, while creating the data space of size equal to the lower bound of Part 1;

(4)an ω-processor schedule that executes T in time not exceeding three times the optimal, while creating the data space of size that exceeds the lower bound of Part 1 by a factor not greater than ω.

(5)a proof that for every number of processors ω and for every 0<ε1, there exist infinitely many trees such that every ω-processor schedule that executes any of these trees in time not exceeding (2−ε) times the optimal requires a token space as large as that created by the schedule of Part 4, while the schedule of Part 4 executes every such tree in optimal time.

The family of complete binary trees provides an example where our schedule achieves an exponential improvement in the size of the data space, compared to that of the classical time-optimal schedule.     

Improved algorithms for latency minimization in wireless networks

In the interference scheduling problem, one is given a set of n communication requests described by source-destination pairs of nodes from a metric space. The nodes correspond to devices in a wireless network. Each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.We introduce an instance-based measure of interference, denoted by I, that enables us to improve on previous results for the interference scheduling problem. We prove the upper and lower bounds in terms of I on the number of steps needed for scheduling a set of requests. For general power assignments, we prove a lower bound of Ω(I/(logΔlogn)) steps, where Δ denotes the aspect ratio of the metric. When restricting to the two-dimensional Euclidean space (as in the previous work) the bound improves to Ω(I/logΔ). Alternatively, when restricting to linear power assignments, the lower bound improves even to Ω(I). The lower bounds are complemented by an efficient algorithm computing a schedule for linear power assignments using only O(Ilogn) steps. A more sophisticated algorithm computes a schedule using even only O(I+log²n) steps. For dense instances in the two-dimensional Euclidean space, this gives a constant factor approximation for scheduling under linear power assignments, which shows that the price for using linear (and, hence, energy-efficient) power assignments is bounded by a factor of O(logΔ).In addition, we extend these results for single-hop scheduling to multi-hop scheduling and combined scheduling and routing problems, where our analysis generalizes the previous results towards general metrics and improves on the previous approximation factors.     

Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness

In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We assume a network router has m incoming queues, each corresponding to a single traffic stream, and must schedule at any time on-line from which queue to take the next packet to send out. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low over the entire scheduling period. We call this new on-line problem the balanced scheduling problem (BSP). By competitive analysis, we measure the power of on-line scheduling algorithms to prevent packet losses. We show that a simple greedy algorithm is Θ(log m)-competitive which is asymptotically optimal, while Round-Robin scheduling is not better than m-competitive, as actually is any deterministic on-line algorithm for BSP. We also give a polynomial time algorithm for solving off-line BSP optimally. We also study another on-line balancing problem that tries to balance the delay among the m traffic streams.     

Perfect periodic scheduling for three basic cycles

Periodic scheduling has many attractions for wireless telecommunications. It offers energy saving where equipment can be turned off between transmissions, and high-quality reception through the elimination of jitter, caused by irregularity of reception. However, perfect periodic schedules, in which each (of $n$ ) client is serviced at regular, prespecified intervals, are notoriously difficult to construct. The problem is known to be NP-hard even when service times are identical. This paper focuses on cases of up to three distinct periodicities, with unit service times. Our contribution is to derive a $O(n^4)$ test for the existence of a feasible schedule, and a method of constructing a feasible schedule if one exists, for the given combination of client periodicities. We also indicate why schedules with a higher number of periodicities are unlikely to be useful in practice. This methodology can be used to support perfect periodic scheduling in a wide range in real world settings, including machine maintenance service, wireless mesh networks and various other telecommunication networks transmitting packet size data.     

Performance and alertness on 8 h and 12 h rotating shifts at a natural gas utility

Abstract

An 8 h/5-7 day shift schedule was compared with a newly instituted 12 h/2-4 day schedule in this, our second worksite study of extended workshifts. Workers completed a performance/alertness test battery, and a questionnaire on sleep patterns and other personal habits, 2-4 times a week on all shifts. After 10 months adaptation to the 12 h shift schedule, there were decrements in performance/ alertness attributable to the extra 4 h on the extended shift. There were also reductions in sleep across the workweek which were most apparent on 12 h night shifts. The results are consistent with our first worksite study of 12 h shifts and indicate extra caution should be exercised when scheduling critical activities for extended workshifts, especially extended night shifts.