# Strategies for LP-based solving a general class of scheduling problems.

Laureano F. Escudero; Gloria Pérez Sáinz de Rozas

Trabajos de Investigación Operativa (1990)

- Volume: 5, Issue: 1, page 3-33
- ISSN: 0213-8204

## Access Full Article

top## Abstract

top## How to cite

topEscudero, Laureano F., and Pérez Sáinz de Rozas, Gloria. "Strategies for LP-based solving a general class of scheduling problems.." Trabajos de Investigación Operativa 5.1 (1990): 3-33. <http://eudml.org/doc/40609>.

@article{Escudero1990,

abstract = {In this work we describe some strategies that have been proved to be very efficient for solving the following type of scheduling problems: Assume a set of jobs is to be performed along a planning horizon by selecting one from several alternatives for doing so. Besides selecting the alternative for each job, the target consists of choosing the periods at which each component of the work will be done, such that a set of scheduling and technological constraints is satisfied. The problem is formulated as a large-scale pure 0-1 model. Three facts are observed: (1) The number of variables with nonzero value at each feasible solution is much smaller than the total number of variables; (2) For some types of objectives (e.g., makespan minimizing), each incumbent solution allows for a problem reduction without eliminating any better solution; (3) Initial feasible solutions can be found, by means of an heuristic procedure, without great difficulty.The three mentioned characteristics allow for a modification in the traditional using of the branch-and-bound methods and, hence, increase the problem dimensions that could be dealt with at a reasonable computer effort. Computational experience on a broad set of real-life problems is reported.},

author = {Escudero, Laureano F., Pérez Sáinz de Rozas, Gloria},

journal = {Trabajos de Investigación Operativa},

keywords = {Programación lineal; Optimización; coefficient reduction; special ordered sets; scheduling; large-scale pure 0-1 model; branch-and-bound},

language = {eng},

number = {1},

pages = {3-33},

title = {Strategies for LP-based solving a general class of scheduling problems.},

url = {http://eudml.org/doc/40609},

volume = {5},

year = {1990},

}

TY - JOUR

AU - Escudero, Laureano F.

AU - Pérez Sáinz de Rozas, Gloria

TI - Strategies for LP-based solving a general class of scheduling problems.

JO - Trabajos de Investigación Operativa

PY - 1990

VL - 5

IS - 1

SP - 3

EP - 33

AB - In this work we describe some strategies that have been proved to be very efficient for solving the following type of scheduling problems: Assume a set of jobs is to be performed along a planning horizon by selecting one from several alternatives for doing so. Besides selecting the alternative for each job, the target consists of choosing the periods at which each component of the work will be done, such that a set of scheduling and technological constraints is satisfied. The problem is formulated as a large-scale pure 0-1 model. Three facts are observed: (1) The number of variables with nonzero value at each feasible solution is much smaller than the total number of variables; (2) For some types of objectives (e.g., makespan minimizing), each incumbent solution allows for a problem reduction without eliminating any better solution; (3) Initial feasible solutions can be found, by means of an heuristic procedure, without great difficulty.The three mentioned characteristics allow for a modification in the traditional using of the branch-and-bound methods and, hence, increase the problem dimensions that could be dealt with at a reasonable computer effort. Computational experience on a broad set of real-life problems is reported.

LA - eng

KW - Programación lineal; Optimización; coefficient reduction; special ordered sets; scheduling; large-scale pure 0-1 model; branch-and-bound

UR - http://eudml.org/doc/40609

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.