All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3

Displaying 41 – 58 of 58

Showing per page

On the power of randomization for job shop scheduling with k-units length tasks

Tobias Mömke (2008)

RAIRO - Theoretical Informatics and Applications

In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for d = o ( D ) jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation...

Online LIB problems : heuristics for bin covering and lower bounds for bin packing

Luke Finlay, Prabhu Manyem (2005)

RAIRO - Operations Research - Recherche Opérationnelle

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...

Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing

Luke Finlay, Prabhu Manyem (2006)

RAIRO - Operations Research

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...

On-line models and algorithms for max independent set

Bruno Escoffier, Vangelis Th. Paschos (2006)

RAIRO - Operations Research

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially...

Optimal Allocation of Renewable Energy Parks: A Two–stage Optimization Model

Carmen Gervet, Mohammad Atef (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Applied research into Renewable Energies raises complex challenges of a technological, economical or political nature. In this paper, we address the techno−economical optimization problem of selecting locations of wind and solar Parks to be built in Egypt, such that the electricity demand is satisfied at minimal costs. Ultimately, our goal is to build a decision support tool that will provide private and governmental investors into renewable energy systems, valuable insights to make informed short...

Parallel approximation to high multiplicity scheduling problems V I A smooth multi-valued quadratic programming

Maria Serna, Fatos Xhafa (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming

Maria Serna, Fatos Xhafa (2007)

RAIRO - Theoretical Informatics and Applications

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

Phenotype space and kinship assignment for the Simpson index

Bruce Litow, Dmitry Konovalov (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype...

Phenotype space and kinship assignment for the simpson index

Bruce Litow, Dmitry Konovalov (2007)

RAIRO - Theoretical Informatics and Applications

We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype...

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Simulation and design of extraction and separation fluidic devices

Bijan Mohammadi, Juan G. Santiago (2001)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

We present the combination of a state control and shape design approaches for the optimization of micro-fluidic channels used for sample extraction and separation of chemical species existing in a buffer solution. The aim is to improve the extraction and identification capacities of electroosmotic micro-fluidic devices by avoiding dispersion of the extracted advected band.

Simulation and design of extraction and separation fluidic devices

Bijan Mohammadi, Juan G. Santiago (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

We present the combination of a state control and shape design approaches for the optimization of micro-fluidic channels used for sample extraction and separation of chemical species existing in a buffer solution. The aim is to improve the extraction and identification capacities of electroosmotic micro-fluidic devices by avoiding dispersion of the extracted advected band.

Currently displaying 41 – 58 of 58

Previous Page 3