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

Page 1

Displaying 1 – 12 of 12

Showing per page

A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays

Aziz Moukrim, Djamal Rebaine, Mehdi Serairi (2014)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be 𝒩 P x1d4a9;x1d4ab; -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide...

A Branch-and-Bound method for solving Multi-Skill Project Scheduling Problem

Odile Bellenguez-Morineau, Emmanuel Néron (2007)

RAIRO - Operations Research

This paper deals with a special case of Project Scheduling problem: there is a project to schedule, which is made up of activities linked by precedence relations. Each activity requires specific skills to be done. Moreover, resources are staff members who master fixed skill(s). Thus, each resource requirement of an activity corresponds to the number of persons doing the corresponding skill that must be assigned to the activity during its whole processing time. We search for an exact solution that...

A branch-and-cut algorithm for a resource-constrained scheduling problem

Renaud Sirdey, Hervé L. M. Kerivin (2007)

RAIRO - Operations Research

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance,...

A branch-and-cut for the Non-Disjoint m-Ring-Star Problem

Pierre Fouilhoux, Aurélien Questel (2014)

RAIRO - Operations Research - Recherche Opérationnelle

In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a Branch-and-Cut...

A branch-and-price-and-cut algorithm for the pattern minimization problem

Cláudio Alves, J. M. Valério de Carvalho (2008)

RAIRO - Operations Research - Recherche Opérationnelle

In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the Pattern Minimization Problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature....

A branch-and-price-and-cut algorithm for the pattern minimization problem

Cláudio Alves, J.M. Valério de Carvalho (2009)

RAIRO - Operations Research

In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the Pattern Minimization Problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature....

A new relaxation in conic form for the euclidean Steiner problem in ℜ n

Marcia Fampa, Nelson Maculan (2001)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in ℜ n . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ -optimal solution for this latter problem using interior-point algorithm.

A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ

Marcia Fampa, Nelson Maculan (2010)

RAIRO - Operations Research

In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ-optimal solution for this latter problem using interior-point algorithm.

Acyclic orientations with path constraints

Rosa M. V. Figueiredo, Valmir C. Barbosa, Nelson Maculan, Cid C. de Souza (2008)

RAIRO - Operations Research - Recherche Opérationnelle

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency...

Acyclic Orientations with Path Constraints

Rosa M. V. Figueiredo, Valmir C. Barbosa, Nelson Maculan, Cid C. de Souza (2009)

RAIRO - Operations Research

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency...

Currently displaying 1 – 12 of 12

Page 1