Constraint Propagation in Flexible Manufacturing

by Toan Phan Huy

Overview

This book provides a thorough analysis of scheduling problems that arise in a flexible manufacturing environment with scarce resource supply. Generalizations of the famous job shop scheduling problem are discussed. As a basic and common technique for solving these problems constraint propagation is applied in various solution methods. The effectiveness of constraint propagation is demonstrated by the solution of a high number of benchmark problem instances.

Product Details

ISBN-13:	9783540679134
Publisher:	Springer Berlin Heidelberg
Publication date:	10/13/2000
Series:	Lecture Notes in Economics and Mathematical Systems , #492
Edition description:	Softcover reprint of the original 1st ed. 2000
Pages:	258
Product dimensions:	6.10(w) x 9.25(h) x (d)

Table of Contents

1 Introduction.- 2 General Solution Methods.- 2.1 Constraint Satisfaction and Optimization.- 2.2 Constraint Propagation.- 2.3 Exhaustive Search.- 2.4 Local Search.- 3 The Disjunctive Scheduling Problem.- 3.1 The Disjunctive Scheduling Model.- 3.2 Disjunctive Clique Decompositions.- 4 Constraint Propagation and the DSP.- 4.1 Some Basic Definitions.- 4.2 Conjunctive Consistency Tests.- 4.3 Lower-Level Bound-Consistency.- 4.4 Input/Output Consistency Tests.- 4.5 Input/Output Negation Consistency Tests.- 4.6 Input-or-Output Consistency Tests.- 4.7 Energetic Reasoning.- 4.8 Shaving.- 4.9 A Comparison of Disjunctive Consistency Tests.- 4.10 Conjunctive vs. Disjunctive Consistency Tests.- 4.11 Bound-Consistency Revisited.- 5 A Branch-and-Bound Algorithm.- 5.1 The Block Branching Scheme.- 5.2 Lower Bound Calculation.- 5.3 Upper Bound Calculation.- 5.4 Putting Things Together: The Algorithm.- 5.5 Computational Results.- 6 A Decomposition Based Heuristic.- 6.1 Edge-Guessing.- 6.2 A Parallel Strategy.- 6.3 A Sequential Strategy.- 6.4 Computational Results.- 7 A Local Search Based Heuristic.- 7.1 Neighbourhood Structures.- 7.2 Makespan Approximations.- 7.3 A Tabu Search Approach.- 7.4 Edge-Guessing and Local Search.- 7.5 Computational Results.- 8 Some Concluding Remarks.- List of Symbols.