According to Askin and Standridge, "the purpose ofmanufacturing, at least idealistically, is to enrich society through the production of functionally de sirable, aesthetically pleasing, environmentally safe, economically affordable, highly reliable, top-quality products" [AS93]. A less pointed and more prag matic description ofmanufacturing purposes is to satisfy customer's demand (function, reliability, quality of products) while considering management's objectives (minimum of costs). In this context, the organization of manu facturing systems has become an increasingly important factor, stimulated by impressive productivity gains that have been observed in the japanese industry in the 80s. The boost of efficiency especially became apparent in the automobileindustry which experienced a "second revolution" as has been demonstrated in the famous study of the International Motor Vehicle Pro gram (IMVP) of Womack et al. [WJR92]. Due to this study and other re search initiated by this work, the opinion eventually has gained acceptance that competitive advantages offirms can be considerably influenced by inno vations in the organization of manufacturing systems [Laz90, AD94]. Manufacturing systems cover the following functions [AS93]: (a) product de sign and development, (b) process planning, (c) manufacturing operations, (d) facilities layout and (e) production planning. Product design and devel opment is responsible for analyzing the information provided by marketing and sales regarding customer's demands. Its task is to transform these in formation into the description of products that both satisfy the customer's needs and can be efficiently manufactured.

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.