Loading [MathJax]/extensions/MathZoom.js
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 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...
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...
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,...
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...
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....
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....
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.
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.
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...
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