Search results for "scheduling."
showing 10 items of 270 documents
Two Job Cyclic Scheduling with Incompatibility Constraints
2001
The present paper deals with the problem of scheduling several repeated occurrences of two jobs over a finite or infinite time horizon in order to maximize the yielded profit. The constraints of the problem are the incompatibilities between some pairs of tasks which require a same resource.
Time and work generalised precedence relationships in project scheduling with pre-emption: An application to the management of Service Centres
2012
Abstract In this paper we present an application of project scheduling concepts and solution procedures for the solution of a complex problem that comes up in the daily management of many company Service Centres. The real problem has been modelled as a multi-mode resource-constrained project scheduling problem with pre-emption, time and work generalised precedence relationships with minimal and maximal time lags between the tasks and due dates. We present a complete study of work GPRs which includes proper definitions, a new notation and all possible conversions amongst them. Computational results that show the efficiency of the proposed hybrid genetic algorithm and the advantages of allowi…
Exact Response Time Analysis of Hierarchical Fixed-Priority Scheduling
2009
Hierarchical scheduling has recently been used to provide temporal isolation to embedded virtualised systems. Response time analysis is a common way to derive a schedulability test for these systems. This paper points out that response time analysis for hierarchical fixed-priority scheduling found in the literature is only exact for tasks of the highest priority domain. For the rest of the tasks is an upper bound. In our work, we provide the exact analysis and we compare it with previously published works.
HEURISTIC PROCEDURES FOR GROUP SCHEDULING
1989
ABSTRACT The group scheduling problem is investigated, solving numerous small and large sized examples with eight sequencing algorithms. A new approach, basically consisting in the definition of real machines' idles for each group, utilizing allowed shifting of non critical activities, is proposed. Moreover the CDS multi-shot algorithm is extended to group scheduling.
Integrated Production and Predictive Maintenance Planning based on Prognostic Information
2019
International audience; This paper address the problem of scheduling production and maintenance operation in predictive maintenance context. It proposes a contribution in the decision making phase of the prognostic and health management framework. Theprognostics and decision processes are merged and an ant colony optimization approach for finding the sequence of decisions that optimizes the benefits of a production system is developed. A case study on a single machine composed of several components where machine can have several usage profiles. The results show thatour approach surpasses classical condition based maintenance policy.
Performance Analysis in Spatially Correlated IEEE 802.11 Networks
2012
Wireless mesh networks are difficult to be characterized, especially under multi-hop traffic streams. The problem is that the local view of the channel and the correlation between the buffers of consecutive nodes in a stream path make complicated the identification of the contention level perceived by each station along the time. Such a figure is used in the models based on the so called decoupling assumption for evaluating the final scheduling of simultaneous channel access grants. In this paper we propose a simplified mesh network model focused on capturing the correlation due to the network topology and traffic routes rather than the access protocol state at each node. To this purpose, w…
Reliable Coverage with Circumferential WMSNs
2021
This work tackles the closed peripheral coverage issue. Such circumferential surveillance is essential in numerous realistic applications where the goal is to ensure rapid detection of any unauthorized entry/exit of the monitored area. To respond to these requirements, peripheral WMSNs can be rapidly deployed around areas of interest (e.g., temporary military camps, natural or nuclear disasters, etc.). While it seems simple, this solution raises two major challenging issues. First, checking whether the deployed peripheral WMSN forms a closed shape around the monitored region. That is, any object trying to leave or access this area must be instantaneously detected by at least one multimedia …
VarySched: A Framework for Variable Scheduling in Heterogeneous Environments
2016
Despite many efforts to better utilize the potential of GPUs and CPUs, it is far from being fully exploited. Although many tasks can be easily sped up by using accelerators, most of the existing schedulers are not flexible enough to really optimize the resource usage of the complete system. The main reasons are (i) that each processing unit requires a specific program code and that this code is often not provided for every task, and (ii) that schedulers may follow the run-until-completion model and, hence, disallow resource changes during runtime. In this paper, we present VarySched, a configurable task scheduler framework tailored to efficiently utilize all available computing resources in…
Checkpointing Workflows for Fail-Stop Errors
2017
International audience; We consider the problem of orchestrating the exe- cution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge,…
Pre-emption in resource-constrained project scheduling
2008
Abstract The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discrete activity pre-emption, and the papers dealing with this issue have reached the conclusion that it has little effect on project length when constant resource availability levels are defined. In this paper we show how three basic elements of many heuristics for the RCPSP – codification, serial SGS and double justification – can be adapted to deal with interruption. The paper is mainly foc…