1996 | OriginalPaper | Buchkapitel
A local search approach to job grouping
verfasst von : Dr. Yves Crama, Dr. Alwin G. Oerlemans, Dr. Frits C. R. Spieksma
Erschienen in: Production Planning in Automated Manufacturing
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In Chapters 6 and 7, lower and upper bounding procedures were proposed for the job grouping problem. It appeared that, in many cases, sequential heuristic procedures were not sufficient to provide an optimal solution. A column generation approach was also developed to compute a strong lower bound, based on the linear relaxation of the set covering formulation of the job grouping problem. In the course of this procedure, it was sometimes possible to derive improved upper bounds. Notice, however, that solving the job grouping problem may be done faster if a better upper bound is known from the start. For instance, execution of the column generation procedure can be avoided if simple lower bounds like LB SW and LB MSW (see Chapters 6 and 7) are optimal and an optimal upper bound is also available. Alternatively, improved solutions provide additional columns to be included in the set covering formulation, which may speed up the column generation procedure.