Skip to main content
main-content

Über dieses Buch

This book is the outcome of my research in the field of multi­ levellot sizing and scheduling which started in May 1993 at the Christian-Albrechts-University of Kiel (Germany). During this time I discovered more and more interesting aspects ab out this subject and I had to learn that not every promising idea can be thoroughly evaluated by one person alone. Nevertheless, I am now in the position to present some results which are supposed to be useful for future endeavors. Since April 1995 the work was done with partial support from the research project no. Dr 170/4-1 from the "Deutsche For­ schungsgemeinschaft" (D FG). The remaining space in this preface shaH be dedicated to those who gave me valuable support: First, let me express my deep gratitude towards my thesis ad­ visor Prof. Dr. Andreas Drexl. He certainly is a very outstanding advisor. Without his steady suggestions, this work would not have come that far. Despite his scarce time capacities, he never rejected proof-reading draft versions of working papers, and he was always willing to discuss new ideas - the good as weH as the bad ones. He and Prof. Dr. Gerd Hansen refereed this thesis. I am in­ debted to both for their assessment. I am also owing something to Dr. Knut Haase. Since we al­ most never had the same opinion when discussing certain lot sizing aspects, his comments and criticism gave stimulating input.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Lot sizing1 certainly belongs to the most established production planning problems.2 As first scientific reports of this subject date from the beginning of the 20th century [And29, Har13] and at least one chapter about lot sizing can be found in almost every good textbook about production research issues, it seems to be hard to justify yet another publication focusing on lot sizing. Especially a monograph appears to be of no further relevance at first glance.
Alf Kimms

Chapter 2. Literature Review

Abstract
This chapter contains the most comprehensive review of the multilevel lot sizing literature available today. First, in Section 2.1 the scope of the review is defined. In Section 2.2 we then list some contributions of general interest. Models and methods for dynamic demand and no capacity constraints are discussed in Section 2.3. In Section 2.4 our concern is about dynamic demand and capacity restrictions. In both sections we refer to methods, e.g. dynamic programming or simulated annealing without further comment, because their basic working principles are more or less standard. Readers who are not familiar with these may start with [ZaEvVa89] for an overview of heuristics and with any good operations research textbook (e.g. [DoDr95, HiLi88, Win93]) for exact methods. Finally, in Section 2.5 intermediate conclusions from the review are given.
Alf Kimms

Chapter 3. Problem Specifications

Abstract
Until now, we have gained our understanding from informal statements only. To give a more precise definition of what is the focus of our attention, this chapter contains MIP—model formulations. In Section 3.1 we concisely describe the underlying model assumptions. Then, in Section 3.2 a MIP—model for lot sizing and scheduling with multiple machines is presented. Since the bulk of this book is about certain aspects related to this model. Section 3.3 gives some more insight and shows that the problem is indeed a non—trivial one. Sections 3.4, 3.5, and 3.6 introduce parallel machines, multiple resources, and partially renewable resources, respectively, and contain MIP-models. Remembering the literature review it becomes evident that today there are no multi—level lot sizing models and methods that rely on such general assumptions as we do below.
Alf Kimms

Chapter 4. Instance Generation

Abstract
As we have learned, the problem that we are concerned about has not been treated elsewhere. Hence, there is neither an established multi—level test—bed nor an instance generator available. Section 4.1 therefore introduces a parameter controlled instance generator (APCIG) which allows to create multi—level lot sizing (and scheduling) instances systematically. Due to preliminary computational experience, we know that certain parameters of the PLSP have an impact on the performance of solution methods. This is not a very surprising result, of course. But, to gain a better understanding in what makes instances hard to solve and what method should be chosen for what instance, a (full) factorial design is used rather than a randomized design. For a guideline for designing test—beds, performing computational studies, and reporting the results1 we refer to [BaGoKeReSt95, Hoo95]. Section 4.2 presents an experimental design for the PLSP-MM. Section 4.3 relates the speed of different computers to allow fair comparisons with other platforms than those used for our tests.
Alf Kimms

Chapter 5. Lower Bounds

Abstract
Where standard MIP-solvers fail to compute optimum objective function values for PLSP-instances, lower bounds may be used as a point of reference for evaluation purposes. In this chapter, we compute lower bounds for the PLSP-MM. Solving the LP—relaxation of a PLSP—MM—model optimally is a straightforward idea. Section 5.1 deals with this approach and discusses a network reformulation of the model. Another way to get lower bounds is to ignore some of the constraints and to solve the remaining problem optimally. This path is followed in Section 5.2 where a B&B- procedure is used to attack the uncapacitated, multi—level, multi—machine lot sizing and scheduling problem.1 On the basis of this. Section 5.3 introduces a method to solve a Lagrangean relaxation of the capacity constraints. Finally, Section 5.4 summarizes the lower bounds obtained.
Alf Kimms

Chapter 6. Multiple Machines

Abstract
This chapter discusses several heuristic solution procedures for the PLSP-MM. We briefly report about some unsuccessful attempts in Section 6.1. A backward oriented construction scheme is underlying all methods described in here. Hence, in Section 6.2 we provide those construction principles that are common to all heuristics. Afterwards, we refine the presented concept to give a randomized regret based sampling procedure in Section 6.3, a cellular automaton in Section 6.4, a genetic algorithm in Section 6.5, a disjunctive arc based tabu search method in Section 6.6, and a so—called demand shuffle heuristic in Section 6.7. Section 6.8 provides a summary of the computational studies and compares the procedures. In Section 6.9 we run some tests with large instances to reveal the applicability to real—world instances.
Alf Kimms

Chapter 7. Parallel Machines

Abstract
While we have spent much effort to discuss the PLSP—MM on isolation, we will now outline solution procedures for extensions of the lot sizing and scheduling problem. To begin with, the PLSP—PM is considered in this chapter. The PLSP—MR and the PLSP–PRR are the subjects of interest in the two chapters that will follow.
Alf Kimms

Chapter 8. Multiple Resources

Abstract
In this chapter we deal with the PLSP—MR. Although some lot sizing models are with multiple resources (e.g. [Der95, He194, Sta88, Sta94]), for solution procedures other than LP—based techniques the single—or multi—machine case is assumed. In Section 8.1 we give an introduction into the resource constrained project scheduling problem (RCPSP) where multiple resources are standard. Then, in Section 8.2, we show how the demand shuffle heuristic can be modified in order to be able to solve the PLSP—MR. Preliminary computational tests are provided in Section 8.3.
Alf Kimms

Chapter 9. Partially Renewable Resources

Abstract
In this chapter the PLSP—PRR is tackled. The notion of partially renewable resources is new and thus there exists no literature for lot sizing and scheduling with such resources. Section 9.1 shortly draws the attention to course scheduling which is the application field for which this kind of resource was invented. Then, in Section 9.2 we present the modifications of the demand shuffle heuristic that allow us to solve the PLSP—PRR. Finally, in Section 9.3 some preliminary computational tests are done.
Alf Kimms

Chapter 10. Rolling Planning Horizon

Abstract
All methods described thus far are tailored to construct a production plan for T periods. Since the lifetime of a firm is supposed to last beyond the planning horizon, lot sizing and scheduling is not a single event. A quick and dirty approach to meet that situation would be to plan for the T periods 1,..., T, to implement that plan, to plan for the next T periods T+1,..., 2T, afterwards, and so on. This would make short—term production planning being a process running a lot sizing and scheduling method every T periods. Beside the fact that the final setup state of one production plan defines the initial setup state for the next, these runs would be independent.
Alf Kimms

Chapter 11. Method Selection Guidelines

Abstract
Given a particular PLSP—instance, a question that arises is which method should be chosen to get a production plan with low objective function value. Running all known methods to select the best result afterwards is annoying, if there are hints available which help to make the decision what method to apply. In Section 11.1 we discuss the basic ideas of how to do the method selection. Section 11.2 refines these ideas.
Alf Kimms

Chapter 12. Research Opportunities

Abstract
In this chapter we give some hints for future work. Clearly, one should pursuit to find more methods for the presented models in order to improve the current bounds. Beside this, effort should be spent to extend the models and the methods for further real—world requirements. Section 12.1 summarizes some of these extensions. To be integrated into a real—world environment with harmony, one must take into account that lot sizing and scheduling interacts with other planning tasks. Hence, Section 12.2 reveals some links to other planning problems.
Alf Kimms

Chapter 13. Conclusion

Abstract
This book deals with multi–level lot sizing and scheduling and most chapters are devoted to present methods for capacitated, dynamic and deterministic models.
Alf Kimms

Backmatter

Weitere Informationen