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

Título inglés	Strategies for LP-based solving a general class of scheduling problems.
Título español	Estrategias basadas en LP para solucionar una clase general de problemas de planificación.
Autor/es	Escudero, Laureano F. ; Pérez Sáinz de Rozas, Gloria
Organización	IBM T. J. Watson Res. Cent., Yorktown Heights (New York), Estados Unidos;Fac. Cienc. Secc. Mat. Univ. País Vasco, Lejona (Vizcaya), España
Revista	0213-8204
Publicación	1990, 5 (1): 3-33, 21 Ref.
Tipo de documento	articulo
Idioma	Inglés
Resumen inglés	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.
Clasificación UNESCO	120707
Palabras clave español	Programación lineal ; Optimización
Código Z-Math	Zbl 0693.90051
Acceso al artículo completo