Batching and Scheduling: Models and Methods for Several Problem Classes

ISBN-13: 9783540611141 / Angielski / Miękka / 1996 / 178 str.

Carsten Jordan

Opis

This work presents a problem classification in the area of batching (including multi-level and parallel machine problems) and develops several exact and heuristic algorithms to solve them.

Spis treści

1 Introduction.- 1.1 Motivation of the Planning Problem.- 1.2 Background and Related Work.- 1.3 Case Description.- 1.4 Chapter Synopsis.- 2 Description of the Problems.- 2.1 Batching Types and Literature Review.- 2.2 Notation, Basic Definitions and [?/?/?] Descriptor.- 2.3 Single-Machine Case.- 2.4 Multi-Level Product Structures and Parallel Machines.- 2.5 Complexity Analysis.- 2.6 Structural Properties.- 2.7 Instance Generator.- 3 Single-Machine Case.- 3.1 Basic Enumeration Scheme.- 3.2 Item Availability — Preemptive Batching.- 3.2.1 Branch&Bound.- 3.2.2 Dynamic Programming.- 3.2.3 Construction and Improvement.- 3.2.4 Computational Results.- 3.3 Item Availability — Nonpreemptive Batching.- 3.3.1 Branch&Bound.- 3.3.1.1 Minimum Cost Schedule of a Sequence.- 3.3.1.2 Dominance Rules.- 3.3.2 Genetic Algorithm for Sequence Independent Setups.- 3.3.3 Computational Results.- 3.4 Batch Availability.- 3.4.1 Branch&Bound.- 3.4.1.1 Late Schedule of a Sequence.- 3.4.1.2 Dominance Rule.- 3.4.2 Genetic Algorithm for Sequence Independent Setups.- 3.4.3 Computational Results.- 3.4.4 Genetic Algorithm for the Flow-Shop Case.- 4 Discrete Lotsizing and Scheduling.- 4.1 Discrete Lotsizing and Scheduling Problem.- 4.2 Equivalence of DLSP and BSP.- 4.3 Comparison with Variants of the DLSP.- 4.3.1 Sequence Independent Setup Times and Costs (SISTSC).- 4.3.2 Sequence Dependent Setup Costs (SDSC).- 4.3.3 Sequence Dependent Setup Times and Costs (SDSTSC).- 4.3.4 Single-Level Batch Availability (BA).- 4.3.5 Two-Level Batch Availability (BA2LV).- 4.4 Conclusions.- 5 Multi-Level and Parallel Machine Case.- 5.1 Multi-Level Case.- 5.1.1 Single-Machine.- 5.1.2 Multi-Machine.- 5.1.3 Preliminary Computational Results.- 5.2 Parallel Machines.- 6 Artificial Intelligence Approaches.- 6.1 Introduction.- 6.2 Model Formulations.- 6.3 Performance Comparison.- 6.4 Conclusions.- 7 Summary and Future Work.- Appendix A Setup Matrices for the Instance Generator.- List of Notation.- List of Abbreviations.- List of Figures.- List of Tables.