Partitioned scheduling of multimode systems on multiprocessor platforms: when to do the mode transition?

Systems composed of distinct operational modes are a common necessity for embedded applications with strict timing requirements. With the emergence of multi-core platforms protocols to handle these systems are required in order to provide this basic functionality.In this work a description on the problems of creating an effective mode-transition protocol are presented and it is proven that in some cases previous single-core protocols can not be extended to handle the mode-transition in multi-core.

On the implementation of real-time slotbased task-splitting scheduling algorithms for multiprocessor systems

In this paper we discuss challenges and design principles of an implementation of slot-based tasksplitting algorithms into the Linux 2.6.34 version. We show that this kernel version is provided with the required features for implementing such scheduling algorithms. We show that the real behavior of the scheduling algorithm is very close to the theoretical. We run and discuss experiments on 4-core and 24-core machines.

A 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources

We present a 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources.

A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained- deadline sporadic tasks on a uniprocessor

Compositional real-time scheduling clearly requires that ”normal” real-time scheduling challenges are addressed but challenges intrinsic to compositionality must be addressed as well, in particular: (i) how should interfaces be described? and (ii) how should numerical values be assigned to parameters constituting the interfaces? The real-time systems community has traditionally used narrow interfaces for describing a component (for example, a utilization/bandwidthlike metric and the distribution of this bandwidth in time). In this paper, we introduce the concept of competitive ratio of an interface and show that typical narrow interfaces cause poor performance for scheduling constrained-deadline sporadic tasks (competitive ratio is infinite). Therefore, we explore more expressive interfaces; in particular a class called medium-wide interfaces. For this class, we propose an interface type and show how the parameters of the interface should be selected. We also prove that this interface is 8-competitive.

A synchronous transition protocol with periodicity for global scheduling of multimode real-time systems on multiprocessors

We consider the global scheduling problem of multimode real-time systems upon identical multiprocessor platforms. During the execution of a multimode system, the system can change from one mode to another such that the current task set is replaced with a new task set. Thereby, ensuring that deadlines are met requires not only that a schedulability test is performed on tasks in each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. In this paper, we extend the synchronous transition protocol SM-MSO in order to take into account mode-independent tasks [1], i.e., tasks of which the execution pattern must not be jeopardized by the mode changes.

Two protocols without periodicity for the global and preemptive scheduling problem of multi-mode real-time systems upon multiprocessor Platforms

We consider the problem of scheduling a multi-mode real-time system upon identical multiprocessor platforms. Since it is a multi-mode system, the system can change from one mode to another such that the current task set is replaced with a new task set. Ensuring that deadlines are met requires not only that a schedulability test is performed on tasks in each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. We propose two protocols which ensure that all the expected requirements are met during every transition between every pair of operating modes of the system. Moreover, we prove the correctness of our proposed algorithms by extending the theory about the makespan determination problem.

Conjecture about global fixed-priority preemptive multiprocessor scheduling of implicit-deadline sporadic tasks: the utilization bound of SM-US(sqrt(2)-1) is sqrt(2)-1

Consider global fixed-priority preemptive multiprocessor scheduling of implicit-deadline sporadic tasks. I conjecture that the utilization bound of SM-US(√2−1) is √2-1.

Runtime CRPD management for rate-based scheduling

Temporal isolation is an increasingly relevant con- cern in particular for ARINC-351 and virtualisation- based systems. Traditional approaches like the rate- based scheduling framework RBED do not take into account the impact of preemptions in terms of loss of working set in the acceleration hardware (e.g. caches). While some improvements have been suggested in the literature, they are overly heavy in the presence of small high-priority tasks such as interrupt service routines. Within this paper we propose an approach enabling adaptive assessment of this preemption delay in a tem- poral isolation framework with special consideration of capabilities and limitations of the approach.

Collision-free beacon scheduling mechanisms for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks

The recently standardized IEEE 802.15.4/Zigbee protocol stack offers great potentials for ubiquitous and pervasive computing, namely for Wireless Sensor Networks (WSNs). However, there are still some open and ambiguous issues that turn its practical use a challenging task. One of those issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes two collision-free beacon frame scheduling schemes. We strongly believe that the results provided in this paper trigger a significant step towards the practical and efficient use of IEEE 802.15.4/Zigbee cluster-tree networks.

Implementation details of the time division beacon scheduling approach for ZigBee cluster-tree networks

This technical report describes the implementation details of the Time Division Beacon Scheduling Approach in IEEE 802.15.4/ZigBee Cluster-Tree Networks. In this technical report we describe the implementation details, focusing on some aspects of the ZigBee Network Layer and the Time Division Beacon Scheduling mechanism. This report demonstrates the feasibility of our approach based on the evaluation of the experimental results. We also present an overview of the ZigBee address and tree-routing scheme.

Beacon scheduling in cluster-tree IEEE 802.15.4/ZigBee wireless sensor networks

The recently standardized IEEE 802.15.4/Zigbee protocol stack offers great potentials for ubiquitous and pervasive computing, namely for Wireless Sensor Networks (WSNs). However, there are still some open and ambiguous issues that turn its practical use a challenging task. One of those issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This report tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes two collisionfree beacon frame scheduling schemes.

A hybrid genetic algorithm for the multi-mode resource-constrained project scheduling

A construction project is a group of discernible tasks or activities that are conduct-ed in a coordinated effort to accomplish one or more objectives. Construction projects re-quire varying levels of cost, time and other resources. To plan and schedule a construction project, activities must be defined sufficiently. The level of detail determines the number of activities contained within the project plan and schedule. So, finding feasible schedules which efficiently use scarce resources is a challenging task within project management. In this context, the well-known Resource Constrained Project Scheduling Problem (RCPSP) has been studied during the last decades. In the RCPSP the activities of a project have to be scheduled such that the makespan of the project is minimized. So, the technological precedence constraints have to be observed as well as limitations of the renewable resources required to accomplish the activities. Once started, an activity may not be interrupted. This problem has been extended to a more realistic model, the multi-mode resource con-strained project scheduling problem (MRCPSP), where each activity can be performed in one out of several modes. Each mode of an activity represents an alternative way of combining different levels of resource requirements with a related duration. Each renewable resource has a limited availability for the entire project such as manpower and machines. This paper presents a hybrid genetic algorithm for the multi-mode resource-constrained pro-ject scheduling problem, in which multiple execution modes are available for each of the ac-tivities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme. It is evaluated the quality of the schedules and presents detailed comparative computational re-sults for the MRCPSP, which reveal that this approach is a competitive algorithm.

Optimal scheduling of aircrafts’ engines repair process

We address a real world scheduling problem concerning the repair process of aircrafts’ engines by TAP - Maintenance & Engineering (TAP-ME). TAP-ME is the maintenance, repair and overhaul organization of TAP Portugal, Portugal’s leading airline, which employs about 4000 persons to provide maintenance and engineering services in aircraft, engines and components. TAP-ME is aiming to optimize its maintenance services, focusing on the reduction of the engines repair turnaround time.

Scheduling aircraft’s engines repair process: a mathematical model

In this talk, we discuss a scheduling problem that originated at TAP - Maintenance & Engineering - the maintenance, repair and overhaul organization of Portugal’s leading airline. In the repair process of aircrafts’ engines, the operations to be scheduled may be executed on a certain workstation by any processor of a given set, and the objective is to minimize the total weighted tardiness. A mixed integer linear programming formulation, based on the flexible job shop scheduling, is presented here, along with computational experiment on a real instance, provided by TAP-ME, from a regular working week. The model was also tested using benchmarking instances available in literature.

Vedolizumab as induction and maintenance therapy for Crohn's disease.

BACKGROUND: The efficacy of vedolizumab, an α4β7 integrin antibody, in Crohn's disease is unknown. METHODS: In an integrated study with separate induction and maintenance trials, we assessed intravenous vedolizumab therapy (300 mg) in adults with active Crohn's disease. In the induction trial, 368 patients were randomly assigned to receive vedolizumab or placebo at weeks 0 and 2 (cohort 1), and 747 patients received open-label vedolizumab at weeks 0 and 2 (cohort 2); disease status was assessed at week 6. In the maintenance trial, 461 patients who had had a response to vedolizumab were randomly assigned to receive placebo or vedolizumab every 8 or 4 weeks until week 52. RESULTS: At week 6, a total of 14.5% of the patients in cohort 1 who received vedolizumab and 6.8% who received placebo were in clinical remission (i.e., had a score on the Crohn's Disease Activity Index [CDAI] of ≤150, with scores ranging from 0 to approximately 600 and higher scores indicating greater disease activity) (P=0.02); a total of 31.4% and 25.7% of the patients, respectively, had a CDAI-100 response (≥100-point decrease in the CDAI score) (P=0.23). Among patients in cohorts 1 and 2 who had a response to induction therapy, 39.0% and 36.4% of those assigned to vedolizumab every 8 weeks and every 4 weeks, respectively, were in clinical remission at week 52, as compared with 21.6% assigned to placebo (P<0.001 and P=0.004 for the two vedolizumab groups, respectively, vs. placebo). Antibodies against vedolizumab developed in 4.0% of the patients. Nasopharyngitis occurred more frequently, and headache and abdominal pain less frequently, in patients receiving vedolizumab than in patients receiving placebo. Vedolizumab, as compared with placebo, was associated with a higher rate of serious adverse events (24.4% vs. 15.3%), infections (44.1% vs. 40.2%), and serious infections (5.5% vs. 3.0%). CONCLUSIONS: Vedolizumab-treated patients with active Crohn's disease were more likely than patients receiving placebo to have a remission, but not a CDAI-100 response, at week 6; patients with a response to induction therapy who continued to receive vedolizumab (rather than switching to placebo) were more likely to be in remission at week 52. Adverse events were more common with vedolizumab. (Funded by Millennium Pharmaceuticals; GEMINI 2 ClinicalTrials.gov number, NCT00783692.).