1,721,055 research outputs found
Scheduling Preemptive Multiprocessor Tasks on Dedicated Processor
No full textIn this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented
Preemptive Multiprocessor Tasks Scheduling with Release Times and Time Windows
No full textClassical scheduling theory assumed that a task may require for its processing only one processor at a time. This assumption is not obvious in the context of new parallel computer systems and parallel algorithms. In this work, we consider preemptive deterministic scheduling of multiprocessor tasks, each of which may require a set of processors at a time. In general, tasks may appear in the system in different moments of time. We will also consider the problem of scheduling such tasks in time windows on particular processors. The existence of low-order polynomial time algorithms for the above problems with Cmax and Lmax criteria will be analyzed. The general case of the problem can be solved using a linear programming approach
Deconvolution and Identification of Mass Spectra from mixed and pure colonies of bacteria
No full textSimmuteit S, Simmuteit J, Schleif F-M, Villmann T. Deconvolution and Identification of Mass Spectra from mixed and pure colonies of bacteria. In: Blazewicz J, Ecker K, Hammer B, eds. ICOLE 2009. IfI-09-12. Clausthal-Zellerfeld, Germany: Technical University of Clausthal; 2009: 104-112
Scheduling multiprocessor tasks on two parallel processors
No full textIn this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed
Extended Targeted Profiling to Identify and Quantify Metabolites in 1-H NMR measurements
No full textSchleif F-M, Riemer T, Boerner U, Cross M. Extended Targeted Profiling to Identify and Quantify Metabolites in 1-H NMR measurements. In: Blazewicz J, Ecker K, Hammer B, eds. ICOLE 2009. IfI-09-12. Clausthal-Zellerfeld, Germany: Technical University of Clausthal; 2009: 89-103
Linear Algorithms for Preemptive Scheduling of Multiprocessor Tasks Subject to Minimal Lateness
No full textn scheduling theory it is widely assumed that a task is to be processed on one processor at a time. This assumption is not so obvious in the context of recently emerging parallel computer systems and parallel algorithms. In this work we consider tasks requiring more than one dedicated processor at a time, i.e. sets of processors simultaneously. Linear time algorithms will be given for the case of two, three and four processors and the Lmax criterion. The algorithms are based on the same simple paradigm. In some cases they deliver optimal solutions. In other cases, optimality is not guaranteed but they can still be used as fast approximation algorithms for which the worst case performance bounds are given. Results of the computational experiments involving four processors are reported
- …
