Constraint Propagation in Flexible Manufacturing

ISBN-13: 9783540679134 / Angielski / Miękka / 2000 / 258 str.

Huy Toan Phan; Toan Phan Huy; Toan Phan Huy

Opis

This text provides an analysis of scheduling problems that arise in a flexible manufacturing environment with scarce resource supply. As a basic and common technique for solving these problems constraint propagation is applied in various solution methods.

Spis treści

Introduction.- General Solution Methods.- Constraint Satisfaction and Optimization; Constraint Propagation; Exhaustive Search; Local Search; The Disjunctive Scheduling Problem.- The Disjunctive Scheduling Model; Disjunctive Clique Decompositions; Constraint Propagation and the DSP.- Some Basic Definitions; Conjunctive Consistency Tests; Lower-Level Bound-Consictency; Input/Output Consistency Tests; Input/Output Negation Consistency Tests; Input-or-Output Consistency Tests; Energetic Reasoning.- Shaving; A Comparison of Disjunctive Consistency Tests; Conjunctive vs. Disjunctive Consistency Tests; Bound-Consistency Revisited; A Branch-and-Bound Algorithm.- The Block Branching Scheme; Lower Bound Calculation; Upper Bound Calculation; Putting Things Together: The Algorithm; Computational Results; A Decomposition Based Heuristic.- Edge-Guessing; A Parallel Strategy; A Sequential Strategy; Computational Results; A Local Search Based Heuristic.- Neighbourhood Structures; Makespan Approximations; A Tabu Search Approach; Edge-Guessing and Local Search; Computational Results; Some Concluding Remarks