Explore the vast range of titles available.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, along with complexity results, and proofs of optimal priority assignment policies. The MRSS task model is underpinned by a proof-of-concept industrial case study. The problem of task allocation is considered in the context of the MRSS task model, with Simulated Annealing shown to provide an effective solution.

Currently, autonomous vehicles, non-autonomous vehicles, and VIP (emergency) autonomous cars are using intelligent road management techniques to interact with one another and enhance the effectiveness of the traffic system. All sorts of vehicles are managed and under control using the intersection management unit approach. This study focuses on transportation networks where VIP cars are a major disruption, accounting for 40% of accidents and 80% of delays. Intelligent Mobility (IM) is a strategy promoted in this study that proposes setting up intelligent channels for all vehicle communication. As part of its function, the IM unit keeps tabs on how often each junction is used so that it may notify drivers on traffic conditions and ease their workload. The suggested layout may drastically cut average wait times at crossings, as shown in SUMO simulations. The entrance of a VIP car should disrupt all traffic, but the IM (intersection management) unit effectively manages all traffic by employing preemptive scheduling and non-preemptive scheduling techniques for all types of vehicles. We are employing Nishtar roads, the M4 motorway, Mexico, and Washington roads in our scenario. In comparison to all other routes, the simulation results demonstrate that the Washington road route is better able to manage all vehicle kinds. Washington’s traffic delays for 50 cars of all sorts are 4.02 s for autonomous vehicles, 3.62 s for VIP autonomous vehicles, and 4.33 s for non-autonomous vehicles.

Mixed criticality systems are one of the relatively new directions of development for the classical real-time systems. As the real-time embedded systems become more and more complex, incorporating different tasks with different criticality levels, the continuous development of mixed criticality systems is only natural. These systems have practically entered every field where embedded systems are present: avionics, automotive, medical systems, wearable devices, home automation, industry and even the Internet of Things. While scheduling techniques have already been proposed in the literature for different types of mixed criticality systems, the number of papers addressing multiprocessor platforms running in a time-triggered mixed criticality environment is relatively low. These algorithms are easier to certify due to their complete determinism and isolation between components of different criticalities. Our research has centered on the problem of real-time scheduling on multiprocessor platforms for periodic tasks in a time-triggered mixed criticality environment. A partitioned, non-preemptive, table-driven scheduling algorithm was proposed, called Partitioned Time-Triggered Own Criticality Based Priority, based on a uniprocessor mixed criticality method. Furthermore, an analysis of the scheduling algorithm is provided in terms of success ratio by comparing it against an event-driven and a time-triggered method.

Restricted preemption plays a crucial role in reducing total completion time while controlling preemption overhead. A typical version of restricted preemptive models is k -restricted preemptive scheduling, where preemption is only allowed after a task has been continuously processed for at least k units of time. Though solving this problem of minimizing the makespan on parallel machines is NP-hard in general, it is of vital importance to obtain the optimal solution for small-sized problems, as well as for evaluation of heuristics. This paper proposes optimal strategies to the aforementioned problem. Motivated by the dramatic speed-up of Boolean Satisfiability (SAT) solvers, we make the first step towards a study of applying a SAT solver to the k -restricted scheduling problem. We set out to encode the scheduling problem into propositional Boolean logic and determine the optimal makespan by repeatedly calling an off-the-shelf SAT solver. Moreover, we move one step further by encoding the problem into Partial Maximum Satisfiability (PMS), which is an optimized version of SAT, so that the explicit successive calls of the solver can be eliminated. The optimal makespan of the problem and the performance of the proposed methods are studied experimentally. Furthermore, an existing heuristic algorithm is evaluated by the optimization methods.

We consider online preemptive scheduling of jobs arriving one by one, to be assigned to two identical machines, with the goal of makespan minimization. We study the effect of selecting the best solution out of two independent solutions constructed in parallel in an online fashion. Two cases are analyzed, where one case is purely online, and in the other one jobs are presented sorted by non-increasing sizes. We show that using two solutions rather than one improves the performance significantly, but that an optimal solution cannot be obtained for any constant number of solutions constructed in parallel. Our algorithms have the best possible competitive ratios out of algorithms for each one of the classes.

This paper presents an efficient SAT-solving approach for addressing the NP-hard problem of non-preemptive task scheduling on multiple identical resources. This problem is relevant to various application domains, including automotive, avionics, and industrial automation where tasks compete for shared resources. The proposed approach, called CSE, incorporates several novel optimizations, including a Block encoding technique for efficient continuity constraint representation and specialized symmetry-breaking constraints to prune the search space. We evaluate the performance of CSE compared to state-of-the-art SAT encoding schemes and leading optimization solvers like Google OR-Tools, IBM CPLEX, and Gurobi through extensive experiments across diverse datasets. Our method achieves substantial reductions in solving time and exhibits superior scalability for large problem instances.

We propose two modeling approaches to solve single machine preemptive scheduling problems with tardiness related objectives. Employing the conventional time-indexed formulation, we first build a model that explicitly identifies completion times of jobs with varying release times, due dates, and processing times. The second model adopts the aggregate planning view and eliminates binary constraints. Under this approach, each job is seen as a unit demand while its due date is mapped to a period where this unit is demanded. With this mapping, the periodic job allocation decisions are transformed into periodic production decisions that are measured by fraction of demand. Consequently, instead of explicit representation of the job completion times, this model tracks the amounts of production completed and backlogged via inventory and shortage variables and conservation of units constraints. We establish that the latter model provides tighter bounds and demonstrate that it provides a more efficient platform for optimization via computational analysis employing four commonly used tardiness related criteria and a case study from a real life application. Numerical computations reveal that aggregate planning view becomes more dominant in terms of computational performance as the problem size grows.

Non-preemptive tasks with strict periods are usually adopted in practical real-time systems where missing deadlines may lead to catastrophic situations. Their schedulability analysis plays a crucial role in guiding the design and development of such real-time systems. In this paper, we study the schedulability analysis problem of partitioned non-preemptive scheduling for strictly periodic tasks on multiprocessors. We propose a set of schedulability conditions, which determines whether a new task can be scheduled on a processor without changing the offsets of the existing tasks and identifies all valid start time offsets for the new task if it is schedulable. Based on these conditions, we present a task assignment algorithm, which is not optimal, but provides an upper bound on the number of cores required by a periodic task set. We illustrate this algorithm with a practical example and conduct stimulation experiments with randomly generated task sets to evaluate the performance of our approach from several aspects.

The car of the future will be driven by software and offer a variety of customisation options. Enabling these customisation options forces modern automotive manufacturers to update their standardised scheduling concepts for testing and commissioning cars. A flexible scheduling concept means that every chosen customer configuration code must have its own testing procedure. This concept is essential to provide individual testing workflows where the time and resources are optimised for every car. Manual scheduling is complicated due to constraints on time, predecessor-successor relationships, mutual exclusion criteria, resources and status conditions on the car engineering and assembly line. Applied methods to handle the mathematical formulation for the corresponding industrial optimisation problem and its implementation are not yet available. This paper presents a procedure for automated and non-preemptive scheduling in the testing and commissioning of cars, which is built on a Boolean satisfiability problem on parallel and identical machines with temporal and resource constraints. The presented method is successfully implemented and evaluated on a variant assembly line of an automotive Original Equipment Manufacturer. This paper is the starting point for an automated workflow planning and scheduling process in automotive manufacturing.