Evolutionary production planning and scheduling - TU · PDF fileEvolutionary production planning and scheduling vorgelegt von Dipl.-Ing. Andreas Schöpperl aus Berlin von der Fakultät

Evolutionary production planning and scheduling

vorgelegt von

Dipl.-Ing.

Andreas Schöpperl

aus Berlin

von der Fakultät VII – Wirtschaft und Management

der Technischen Universität Berlin

zur Erlangung des akademischen Grades

Doktor der Ingenieurwissenschaften

- Dr.-Ing.-

genehmigte Dissertation

Promotionsausschuss:

Vorsitzender: Prof. Dr. H. Hirth

Berichter: Prof. Dr. H.-O. Günther

Berichter: Prof. Dr. C. Bierwirth

Tag der wissenschaftlichen Aussprache: 26. August 2013

Berlin 2013

D83

Evolutionary production planningand scheduling

eingereicht von:

Dipl.-Ing. Andreas Schöpperl

Dissertation

zur Erlangung des akademischen Grades

Doktor-Ingenieur

(Dr.-Ing.)

Doktor der Ingenieurwissenschaften

Fakultät VII

Wirtschaft und Management

Technische Universität Berlin

To my love.

To my son.

To my mother.

Acknowledgement

I wish to express my gratitude to Prof. Dr. Hans-Otto Günther

for his support, guidance and for providing valuable insights and advice.

Additionally, I would like to thank the PhD committee

for the assessment of this dissertation.

Furthermore, I offer my sincere thanks to Anna Barkhoff

for her friendship, support and precious advice.

Finally, I wish to thank my family and friends

for their on-going support and encouragement.

Contents

I. Concept 11

1. Introduction 121.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2. Object of study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3. Way of proceeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2. Production planning in a dynamic environment 172.1. Production planning environments . . . . . . . . . . . . . . . . . . . . . . 172.2. Uncertainty sources in production planning . . . . . . . . . . . . . . . . . 182.3. Common production planning approaches . . . . . . . . . . . . . . . . . . 20

2.3.1. Static and flexible planning . . . . . . . . . . . . . . . . . . . . . . 202.3.2. Rolling horizon planning . . . . . . . . . . . . . . . . . . . . . . . . 212.3.3. Robust planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3.4. Reactive planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4. Production plan evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4.1. Plan variation impacts . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.2. Measuring plan variations . . . . . . . . . . . . . . . . . . . . . . . 282.4.3. Combining multiple measures . . . . . . . . . . . . . . . . . . . . . 29

2.5. Planning policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.5.1. Periodical planning policies . . . . . . . . . . . . . . . . . . . . . . 312.5.2. Event-based planning policies . . . . . . . . . . . . . . . . . . . . . 322.5.3. Hybrid planning policies . . . . . . . . . . . . . . . . . . . . . . . . 32

2.6. Classification of an evolutionary production planning . . . . . . . . . . . . 33

3. Evolutionary production planning concept 363.1. Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1.1. Main characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . 363.1.2. Balancing evolutionary production planning goals . . . . . . . . . . 40

3.1.2.1. Plan efficiency & variation trade-off . . . . . . . . . . . . 403.1.2.2. Multi-step techniques . . . . . . . . . . . . . . . . . . . . 44

3.1.3. Responsive evolutionary production planning . . . . . . . . . . . . 463.1.4. Further characteristics . . . . . . . . . . . . . . . . . . . . . . . . . 503.1.5. Classification of evolutionary production planning applications . . 52

3.2. Evolutionary production planning system development . . . . . . . . . . . 543.3. Evolutionary production planning simulation framework (EPPSF) . . . . . 55

4

Contents

II. Case studies 60

4. Case 1 - Evolutionary scheduling of a beverages bottling facility 614.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.2. Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.3. Model formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.3.1. Representation of time . . . . . . . . . . . . . . . . . . . . . . . . . 664.3.2. Scheduling model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.3.3. Schedule efficiency & variation objectives . . . . . . . . . . . . . . 754.3.4. Compact scheduling model . . . . . . . . . . . . . . . . . . . . . . 794.3.5. Model extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.4. Experimental design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.5. Numerical study results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.5.1. Preliminary considerations and simulation excerpts . . . . . . . . . 884.5.2. Main results — strategy comparison . . . . . . . . . . . . . . . . . 924.5.3. Result details & parameter impacts . . . . . . . . . . . . . . . . . . 98

4.5.3.1. Schedule variation & production cost trade-off . . . . . . 984.5.3.2. Fixation of schedule elements . . . . . . . . . . . . . . . . 994.5.3.3. Two-step strategies with production cost bounds . . . . . 1034.5.3.4. Limited number of planning periods with schedule varia-

tion considerations . . . . . . . . . . . . . . . . . . . . . . 1054.5.3.5. Number of planning periods . . . . . . . . . . . . . . . . . 1064.5.3.6. Scheduling policies . . . . . . . . . . . . . . . . . . . . . . 1074.5.3.7. Demand characteristics . . . . . . . . . . . . . . . . . . . 108

4.6. Case summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5. Case 2 - Evolutionary scheduling of chemical commodity products 1155.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155.2. Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185.3. Model formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.3.1. Scheduling model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1195.3.2. Schedule efficiency & variation objectives . . . . . . . . . . . . . . 1295.3.3. Compact scheduling model . . . . . . . . . . . . . . . . . . . . . . 1315.3.4. Model extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

5.3.4.1. Inverse production sequences . . . . . . . . . . . . . . . . 1335.3.4.2. Variable production speed . . . . . . . . . . . . . . . . . . 136

5.4. Experimental design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1385.5. Numerical study results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

5.5.1. Preliminary considerations . . . . . . . . . . . . . . . . . . . . . . . 1455.5.2. Main results — strategy comparison . . . . . . . . . . . . . . . . . 1475.5.3. Detailed results & parameter impacts . . . . . . . . . . . . . . . . 152

5.5.3.1. Schedule variation & production cost trade-off . . . . . . 1535.5.3.2. Fixation of schedule elements . . . . . . . . . . . . . . . . 1535.5.3.3. Two-step strategies with production cost bounds . . . . . 156

5

Contents

5.5.3.4. Limited number of planning periods with schedule varia-tion considerations . . . . . . . . . . . . . . . . . . . . . . 157

5.5.3.5. Inverse production sequences . . . . . . . . . . . . . . . . 1585.5.3.6. Number of planning periods . . . . . . . . . . . . . . . . . 1595.5.3.7. Scheduling policies . . . . . . . . . . . . . . . . . . . . . . 1605.5.3.8. Demand characteristics . . . . . . . . . . . . . . . . . . . 161

5.6. Case summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

6. Concluding remarks and outlook 167

Bibliography 169

6

List of Figures

1.1. Dissimilarity of successive plans . . . . . . . . . . . . . . . . . . . . . . . . 131.2. Additional coordination and planning efforts and costs . . . . . . . . . . . 141.3. Case-specific planning system implementation . . . . . . . . . . . . . . . . 15

2.1. Categorization of production planning environments . . . . . . . . . . . . 182.2. Uncertainty causes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3. Rigid planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4. Rolling horizon planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.5. Robust planning for a worst case scenario . . . . . . . . . . . . . . . . . . 232.6. Robust planning for estimated plan realizations . . . . . . . . . . . . . . . 242.7. Robust planning for estimated disruptions . . . . . . . . . . . . . . . . . . 242.8. Reactive planning for a machine break-down . . . . . . . . . . . . . . . . . 262.9. Hierarchical grouping of plan variation measures . . . . . . . . . . . . . . 282.10. Plan variation measure example . . . . . . . . . . . . . . . . . . . . . . . . 292.11. Planning policy categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.12. Periodical planning policy . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.13. Event-based planning policy . . . . . . . . . . . . . . . . . . . . . . . . . . 322.14. Hybrid planning policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.15. Common production planning approaches & typical characteristics . . . . 34

3.1. Evolutionary production planning logic . . . . . . . . . . . . . . . . . . . . 383.2. Evolutionary production system planning information overview . . . . . . 403.3. High vs. low schedule variation . . . . . . . . . . . . . . . . . . . . . . . . 413.4. One dominant goal type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.5. One quantity unit for all objectives . . . . . . . . . . . . . . . . . . . . . . 433.6. Example trade-off curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.7. Example trade-off curves for different data sets . . . . . . . . . . . . . . . 443.8. Time-based goal balance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.9. Time dependent goal dominance . . . . . . . . . . . . . . . . . . . . . . . 453.10. Goal as constraint example . . . . . . . . . . . . . . . . . . . . . . . . . . 473.11. Normalization of goal elements . . . . . . . . . . . . . . . . . . . . . . . . 483.12. Periodical planning policies . . . . . . . . . . . . . . . . . . . . . . . . . . 493.13. Event-based planning policies . . . . . . . . . . . . . . . . . . . . . . . . . 503.14. Hybrid planning policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.15. Evolutionary planning system development . . . . . . . . . . . . . . . . . 553.16. Evolutionary production planning simulation framework (EPPSF) . . . . . 563.17. EPPSF-Planner example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

7

List of Figures

3.18. EPPSF-Planner example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.19. General EPPSF simulation logic . . . . . . . . . . . . . . . . . . . . . . . 59

4.1. Example of a beverage bottling production cycle . . . . . . . . . . . . . . 624.2. Time representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.3. EPPSF-Planner - beverages bottling case . . . . . . . . . . . . . . . . . . 824.4. Generation of demand orders . . . . . . . . . . . . . . . . . . . . . . . . . 854.5. Generation of order cancellations . . . . . . . . . . . . . . . . . . . . . . . 864.6. Simulation run excerpt — base demand . . . . . . . . . . . . . . . . . . . 884.7. Simulation run excerpt — demand change . . . . . . . . . . . . . . . . . . 894.8. Simulation run excerpt — production costs . . . . . . . . . . . . . . . . . 904.9. Simulation run excerpt — lot starting time variation costs . . . . . . . . . 904.10. Simulation run excerpt — schedule variation measures . . . . . . . . . . . 914.11. Average solution time per scheduling iteration . . . . . . . . . . . . . . . . 914.12. Cost strategy & deterministic planning comparison . . . . . . . . . . . . . 924.13. Strategy comparison — total production & schedule variation costs . . . 944.14. Strategy comparison — lot variation costs . . . . . . . . . . . . . . . . . . 954.15. Strategy comparison — sub-lot variation costs . . . . . . . . . . . . . . . 954.16. Strategy comparison — production costs . . . . . . . . . . . . . . . . . . 964.17. Schedule variation & production cost objective weighting . . . . . . . . . 964.18. Schedule variation & production cost trade-off (SlStSiCost strategy) . . . 994.19. Schedule variation & production cost trade-off (SlSiCost strategy) . . . . 1004.20. Schedule variation & production cost trade-off (SlStCost strategy) . . . . 1004.21. Schedule variation & production cost trade-off (LStCost strategy) . . . . 1014.22. Schedule variation & production cost trade-off (SlSeCost strategy) . . . . 1014.23. Schedule variation & production cost trade-off (LSeCost strategy) . . . . 1024.24. Sub-lot starting time & size variation cost trade-off (SlStSi strategy) . . . 1024.25. Schedule fixation strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 1034.26. Production cost bounds — schedule variation costs . . . . . . . . . . . . . 1044.27. Production cost bounds — production costs . . . . . . . . . . . . . . . . . 1044.28. Production cost bounds — SlStCb strategy . . . . . . . . . . . . . . . . . 1054.29. Limited number of planning periods with schedule variation consideration 1064.30. Planning horizon length & production costs . . . . . . . . . . . . . . . . . 1074.31. Planning horizon length & lot starting time variation costs . . . . . . . . . 1084.32. Scheduling policy & cost measures . . . . . . . . . . . . . . . . . . . . . . 1094.33. Demand level & production costs . . . . . . . . . . . . . . . . . . . . . . . 1104.34. Demand level & lot starting time variation costs . . . . . . . . . . . . . . 1104.35. Demand change offset impact . . . . . . . . . . . . . . . . . . . . . . . . . 1114.36. Demand change level impact . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.37. Demand granularity impact . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5.1. Exemplary changeover matrix . . . . . . . . . . . . . . . . . . . . . . . . . 1175.2. Changeover matrix excerpt — product cluster with sub-clusters . . . . . . 1175.3. EPPSF-Planner - chemical commodity case study . . . . . . . . . . . . . . 139

8

List of Figures

5.4. Generation of demand orders . . . . . . . . . . . . . . . . . . . . . . . . . 1425.5. Generation of order cancellations . . . . . . . . . . . . . . . . . . . . . . . 1435.6. Simulation run excerpt - schedule variation measures . . . . . . . . . . . . 1465.7. Average solution time per scheduling iteration . . . . . . . . . . . . . . . . 1465.8. Cost strategy & deterministic planning comparison . . . . . . . . . . . . . 1475.9. Strategy comparison — total production & schedule variation costs . . . . 1495.10. Strategy comparison — schedule variation costs . . . . . . . . . . . . . . . 1505.11. Strategy comparison — production costs . . . . . . . . . . . . . . . . . . 1505.12. Schedule variation & production cost objective weighting . . . . . . . . . . 1515.13. Schedule variation & production cost trade-off (LStSiCost strategy) . . . 1545.14. Schedule variation & production cost trade-off (LSiCost strategy) . . . . 1545.15. Schedule variation & production cost trade-off (LStCost strategy) . . . . 1555.16. Schedule variation & production cost trade-off (LSeCost strategy) . . . . 1555.17. Schedule fixation strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 1565.18. Production cost bounds — schedule variation costs . . . . . . . . . . . . . 1575.19. Production cost bounds — production costs . . . . . . . . . . . . . . . . . 1585.20. Limited number of planning periods with schedule variation consideration 1595.21. Product sequence impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1605.22. Planning horizon length & production costs . . . . . . . . . . . . . . . . . 1615.23. Scheduling policy & cost measures . . . . . . . . . . . . . . . . . . . . . . 1625.24. Demand level impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1635.25. Demand granularity impact . . . . . . . . . . . . . . . . . . . . . . . . . . 1645.26. Impact of demand change occurrence . . . . . . . . . . . . . . . . . . . . . 1645.27. Impact of demand change level . . . . . . . . . . . . . . . . . . . . . . . . 165

9

List of Tables

3.1. Case study classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.1. Model parameterization examples . . . . . . . . . . . . . . . . . . . . . . . 764.2. Production system parameters . . . . . . . . . . . . . . . . . . . . . . . . . 834.3. Demand data overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.1. Model parameterization examples . . . . . . . . . . . . . . . . . . . . . . . 1305.2. Production system parameters . . . . . . . . . . . . . . . . . . . . . . . . . 1405.3. Production system parameters — Product changeover . . . . . . . . . . . 1415.4. Demand data overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

10

Part I.

Concept

11

1. Introduction

This work arose from research activities investigating the possibilities of a more contin-uous development of plans in modern production planning and scheduling applications.The following section 1.1 states the underlying motivation for this research while section1.2 isolates the object of study and defines research goals. Finally, the last section 1.3 ofthis chapter describes the way of proceeding and the contents of the remaining chaptersof this work.

1.1. Motivation

Nowadays, companies often encounter highly competitive markets in very dynamic en-vironments. Indeed, companies in many industries are faced with an increased productvariety and complex, fast changing and ever more sophisticated environments, increas-ing demand variability as well as decreasing order timeframes, while the need to remaincompetitive results in an increased cost pressure.Furthermore, many companies are shifting from Make-To-Stock (MTS) to Make-To-

Order systems (cf. Kaminsky and Kaya (2009)), in order to reduce inventory holdingand associated costs. Production is thus based on actual customer demands instead ofdemand forecast. In consequence, a constant change in consumer behavior and demandvariations (often on short notice) result in a requirement of quick responses and frequentplanning decisions, while still remaining competitive. An on-going challenge is e.g. theneed to quickly respond to demand-related influences, such as short-term customer or-ders and order modifications. A further characteristic of these competitive markets andthe sophisticated customer side (cf. Adebanjo and Mann (2000)) is the need to quoteshort, reliable lead times (cf. Kaminsky and Kaya (2009)). Examples of markets withcharacteristics as described above may be found e.g. in the fast-moving consumer goodsindustry. It is a competitive industry, characteristic are low margins for relatively highvolumes, a high product variety, small order sizes, short lead times, cost pressure andhigh demand variability. Quick responses to changing consumer behavior are required,in terms of demand, quality, flexibility, service and price (cf. e.g. van Dam et al. (1993),Keh and Park (1997)).Classically, if cost (or time, respectively) efficient planning is pursued, in order to

produce with minimal costs, no attention is payed to previously released production plans.Respective planning processes typically result in a complete regeneration of productionplans without consideration of former plans. Furthermore, the outcome of correspondingplanning methods will usually react rather sensitive to even small data changes. Inconjunction with a high demand variability, necessitating frequent planning decisions,

12

1. Introduction

Arrival of a new order

Modification of an order

...

...

...

Scheduled production lots (colors indicate specific products)

SuccessiveProduction schedules

Figure 1.1.: Dissimilarity of successive plans

this leads to an increased variation in resulting planning decisions and rather dissimilaror unrelated seeming successive production plans (cf. figure 1.1).On the other hand, alterations between two successively released production plans do

not only concern the production system which is executing these plans but usually alsoinfluence further planning activities (e.g. material sourcing, personnel planning or financ-ing) within a company which rely on a released production plan. Thus, if alterations toan already released production plan are made, further coordination will usually arise(e.g. with other company departments) when an adjusted plan is verified and released.Furthermore, an altered plan then may necessitate the execution of other dependentplanning activities to incorporate the plan alterations, which in turn strains correspond-ing personnel and planning capacities (cf. figure 1.2). In consequence, additional costsarise, due to the occupation of planning capacities but also as a result of alterations tothe respective plans made by dependent planning activities (e.g. additional costs for ma-terial delivery on short notice). In turn, alterations to these plans of dependent planningactivities influence further dependent planning activities as well, resulting in even moreadditional planning, coordination and planning efforts and costs. In fact, some of theseplan alterations may again affect the validity of released production plans and requirefurther coordination and potentially renewed production planning activities.For these reasons the described interdependencies have to be considered in produc-

tion planning considerations as well. Ideally an integrated planning might encompass allrelevant coherences in order to accomplish an integrated efficient planning of all respec-tive planning activities within a company. However, such integrated planning modelsare usually far too complex to allow for an integrated approach. Furthermore, not allof the required information regarding these interdependencies and resulting costs willbe available or even ascertainable in a specific planning case. Thus, it may not even bepossible to completely assess realistic costs as a result of specific plan adjustments. Com-monly, this information deficit is countered by the estimation and application of penaltycosts to plan alterations, by the fixation of plan components or by focusing solely onthe minimization of certain plan alterations or costs. The estimation quality of penaltycosts is important in the first type of approaches, as respective planning methods mayreact rather sensitive to penalty cost variations. A fixation of plan components restrictsrespective plan alterations without the need for cost estimations, though the time periodin which plan components may be fixed is limited by the due dates and occurrence of

13

1. Introduction

��

��

��

��

��

��

��

��

��

��

��

��

Figure 1.2.: Additional coordination and planning efforts and costs

(short-term) demand variations to be planned. While a focus on cost minimization doesnot consider described interdependencies in planning and perhaps implicitly assumes ahandling of occurring demand variation events during plan execution, the exclusive min-imization of plan alterations focuses on plan repairs and may not be very cost efficient iffrequent plan adaptions become necessary.In practical applications, it is e.g. not uncommon to focus solely on the reduction of

plan alterations, as reliable plans are desired in order to reduce coordination efforts. Thisrepair of production plans is then usually coupled with a periodical complete regenerationof new production plans. However, frequent occurrence of new demand information, suchas new orders or order modifications, induces the need for an on-going inclusion of respec-tive demand information into a continuously developed production plan. On the otherhand, due to cost pressure in highly competitive markets, cost considerations cannot beneglected in the development of production plans. Hence a requirement in the consideredhighly dynamic environments and competitive markets is the continuous adaptation ofproduction plans in a cost-efficient but also reliable way under constant consideration ofnew demand-related information. The way such a planning goal is pursued is, of course,specific to each individual planning application, including implemented planning meth-ods, consideration of specific costs and plan alterations as well as the desired balance ofcost-efficiency and plan reliability (cf. figure 1.3).While research work exists which considers the inclusion of new demand informa-

tion into an existing production plan (usually production scheduling problems) for someplanning applications, there is still considerable demand for research on further planning

14

1. Introduction

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 1.3.: Case-specific planning system implementation

applications and case studies intent on a more continuous plan development, in respectto plan efficiency and reliability, in challenging markets. Furthermore, while a specificplanning system implementation is very dependent on the individual planning applica-tion in focus, the formulation of a general concept summarizing and classifying commoncharacteristics of such planning applications is important in order to support a generaloverview and categorization (cf. Vieira et al. (2003) for a framework for the relatedresearch field of rescheduling problems).

1.2. Object of study

This work aims at the formulation of a general concept describing the continuous de-velopment of production plans under consideration of frequent demand variations incompetitive markets. This planning field is called “Evolutionary production planning” inthe remainder of this work. Considered evolutionary production planning problems willusually reside on the operative planning level, with short-term (or short- to mid-term)planning timeframes, though depending on each specific planning application, the defi-nition of what is considered as a short timeframe may vary considerably (e.g. a numberof shifts, days, weeks etc.).Beside the formulation of a general concept, in the core part of this work specific

production planning applications are addressed, planning methods developed and nu-merical case studies conducted. A variety of planning strategies is compared as wellas the sensitivity of planning results to environmental influences and planning param-eters. A framework supporting the design, implementation and evaluation of specificevolutionary planning systems is developed and applied in the investigated case studies.As applications of the evolutionary production planning concept, two case studies areinvestigated. While classically lot sizing and scheduling of production orders have often

15

1. Introduction

been considered in separate planning steps, lately increased attention has been givento integrated planning models in order to allow for a more efficient planning. The dis-cussed case studies are concerned with integrated lot-sizing and scheduling of beveragesand chemical commodity products, respectively. Specifically, the block planning princi-ple as a practical tool for lot-sizing and scheduling product variants in a predeterminedsequence is adopted for the modeling of the two cases. In conjunction with the seconddiscussed application, characteristics such as series dependent as well as limited productchangeovers are considered.

1.3. Way of proceeding

In chapter 2 existing concepts and planning approaches for a production planning indynamic environments, found in the literature or in practice, are discussed. The chaptercloses with a discussion of the relation as well as overlaps of these existing planningapproaches with an evolutionary production planning and indicates the demand for atailored concept focusing only on the specific aspects of evolutionary production planningapplications. Chapter 3 then presents the general concept and planning framework foran evolutionary production planning.In part II, the core of this work, two case studies, implementing the evolutionary

planning concept for a beverages production (cf. chapter 4) and a chemical commoditiesproduction system (cf. chapter 5), are presented. In numerical studies, various planningstrategies are evaluated and compared. Finally, in chapter 6 the insights gained duringthese research activities are summarized and future research possibilities are indicated.

16

2. Production planning in a dynamicenvironment

In practical applications, companies usually encounter a dynamic environment. Whenproduction activities are being planned, it is rarely the case that a once determinedproduction plan remains unchanged until the end of the last production activity, specifiedby the plan. Instead companies are faced with the necessity to adapt their productionplans to cope with new information regarding the dynamic environment, which becomesavailable as time progresses. Updated demand information, such as new, changed oreven cancelled production orders, create the necessity to replan production activities.Other changes to the planning environment may be aspects of the production site, e.g.disturbances, such as machine break-downs, variable processing times etc.In this chapter, important concepts and existing planning approaches concerned with

production planning in a dynamic environments are discussed. The chapter then closeswith an assessment of planning approaches with respect to a suitability to accomplishevolutionary planning goals.

2.1. Production planning environments

Production planning environments can be of static or dynamic nature. Static environ-ments have a finite set of demand elements and planning periods to be considered. Indynamic environments the set of demand elements and future planning time is infiniteand available information is changing as time progresses. In addition, if the environmentis static and deterministic, all relevant planning information is available and certain atthe time of planning. If some information is uncertain, such as variable processing timesfor certain production tasks, the environment is called stochastic.In a dynamic environment, demand related information is variable, albeit the kind of

variability may differ in dependence on a specific planning problem considered (e.g. orderarrival time, amount, due date etc.). Demand variability can be further distinguished bythe possibility or impossibility of alterations to already available demand information (e.g.order cancellations, due date changes, order amount changes etc.). Again, in additionto demand related information, other information may be uncertain as well. For moreinformation, the reader may confer Vieira et al. (2003) or Pfeiffer et al. (2007).The type of environments that is the focus of this work is highlighted in figure 2.1. Note

that the term “no alterations” in figure 2.1 means that while new planning informationbecomes available as time progresses, it is not subject to later alterations once it is known(e.g. incoming demand orders are not subject to later modification or cancellation).

17

2. Production planning in a dynamic environment

��

��

��

��

��

��

� ��

� ��

��

� ��

��

��

��

��

��

��

� ��

Figure 2.1.: Categorization of production planning environments

2.2. Uncertainty sources in production planning

As stated in 2.1, dynamic environments are characterized by uncertainties regardingfuture planning relevant information. These uncertainties can be demand related butmay also have other sources. As a simple categorization, these uncertainty sources aredistinguishable as being internal or external. A typical example of external sources aredemand related influences on the environment. Internal sources refer to the productionsystem itself (e.g. variable processing times, available production capacity etc.).According to Aytug et al. (2005), uncertainties can be further categorized by intro-

ducing the three dimensions cause, context and impact. Causes for uncertainties areattributed to objects, such as processes, machines, demand etc. and variability in re-spective states in which these objects may be in the future (e.g. normal production,machine break down, new demand order etc.). Furthermore, interdependencies betweenobjects may evoke consecutive reactions of other objects if an objects changes its state.Typical objects of uncertainty can be grouped into the categories of being demand-

related, material-related or production resource/process-related (cf. figure 2.2). As dis-cussed before, demand-related uncertainty causes are within the main focus of this work.Examples for these are deviations from expected due dates and demand amounts due toorder modifications by customers or realizations of predicted demands which differ fromthe predictions, order cancellations, new urgent orders or even changes in order priori-ties. Material-related uncertainty causes include variations concerning the quality (e.g.

18


��

��

��

��

��

� ��

��

��

��

��

��

��

��

��

��

��

��

��

�

�!��

"��#��

��

��

��

�

�

Figure 2.2.: Uncertainty causes

amount of rejects) and availability (e.g. material shortage, delivery delay) of requiredraw materials and other production input materials. Production resource/process-relateduncertainty causes comprise processing variances (e.g. processing time and quality),function (e.g. machine failures) and capacity (e.g. personnel shortage) of productionresources, among others (cf. Vieira et al. (2003); Neuhaus (2008); Gebhard and Kuhn(2009, p.29ff.)).Furthermore, the impact of uncertainties is not only related to a specific object and

state changes but also its context — the specific situation of the production system andenvironment at the time of a state change of an uncertainty object. Machine failureswhich occur during night shifts may be more serious then during day shifts, e.g. due toless personnel being available for repair. Processing times and quality may depend on theexpertise of assigned personnel. Short-term demand changes are more serious to adjustto than demand changes which affect orders with due dates lying further in the future.Impacts of uncertainties comprise finishing time, quality and availability of products aswell as availability and processing time of production facilities.According to Aytug et al. (2005), uncertainty should be explicitly considered during

problem modeling and execution of planning activities, including sources, impacts andinterdependencies.

19


��

��

��

��

��

��

��

��

��

��

��

��

Figure 2.3.: Rigid planning

2.3. Common production planning approaches

This section presents common planning approaches found in the literature, concernedwith various aspects of production planning in a dynamic environment.

2.3.1. Static and flexible planning

Static planning assumes a static, deterministic environment — all relevant information isknown in advance and not subject to changes. When performing a static planning, a planis regarded as fixed once it is created. It is assumed that a plan is carried out as planned,until the end of the planned time period is reached. This approach is also called predictiveplanning in the literature, especially in the area of reactive planning. Schneeweiß (1992)also distinguishes between static and rigid planning approaches — a rigid planning being astatic planning that is repeatedly performed in a dynamic environment, without attentionto its dynamic nature (and the possibility of further alterations). Instead, the infinite setof planning periods is partitioned into distinct finite subsets for which a static planningis then executed (cf. figure 2.3).While carrying out a static plan, it may of course become necessary to make ad-

justments, but these are not considered in an explicit planning process, but implicitlyassumed to being performed during plan execution. This approach has the advantage ofsimplicity and apparent reliability once a plan is created. Depending planning activitiescan rely on the apparent constancy of a released plan. On the other hand, the approachremains only realistic as long as hardly any changes to the planning information occur.In contrast to a static planning approach, flexible planning techniques try to account

for the dynamic nature of environments, incorporating changes to the available planninginformation by revising created plans or taking pro-active measures during plan creation.

20


In the following sub-sections, major planning concepts which apply — to one degree oranother — flexible planning techniques, are discussed.

2.3.2. Rolling horizon planning

A typical planning technique is the classical rolling horizon planning approach. It isfound in many planning areas, in the literature as well as in practice. It accounts for thedynamic nature of planning environments by the use of moving, overlapping planningtime windows. As time progresses, production activities are repeatedly planned. Over-lapping planning periods account for the fact that planning information for overlappedperiods may have changed since the last planning iteration and already created plans arein need of a revision. Figure 2.4 illustrates a rolling horizon planning.Sethi and Sorger (1991) list the quality of demand forecasts, often declining with the

distance in time of future planning periods, as one reason for requiring a gliding planningtechnique with overlapping planning time periods and frequent plan revisions. Rollinghorizon planning is also used in other planning fields, such as financing. Rolling horizonapproaches are most common in mid- or long-term planning application (cf. e.g. Liu et al.(2009)), but occasionally also in short-term planning applications (cf. e.g. Gomes et al.(2010)) If mid- or long term planning is performed, planned activities are typically onlyreleased and executed for the first planned period. If short term planning is performed,usually more than one planned period is released and may induce further replanning andcoordination activities, if revised at a later time. Thus, when plans with overlappingperiods are subsequently revised, these depending planning and coordination activitieswill have to be performed repeatedly.In rolling horizon planning applications, usually a discrete time frame is used, dividing

the planning time into a series of planning periods. Planning activities are then per-formed periodically, each time moving (rolling) forward the planning time window (orthe planning horizon, respectively) by a specific number of planning periods, discardingexpired periods and including an equal number of new periods at the end of the planningtime window. The planning time windows, considered in each planning iteration, over-lap by a specific number of planning periods, defining the number of repeatedly revisedperiods. Thus, planning decisions in earlier planning periods are not included in the setof overlapping periods and binding, while decisions in later periods are preliminary andgoing to be revised during subsequent planning iterations. A classical argument support-ing this approach is that it enables the periodical update and correction of productionplans by incorporation of new planning information. In consequence, plans for planningperiods which have been planned before are discarded and completely new plans are cre-ated instead. For more information on rolling horizon planning confer Stadtler (1988);Steven (1994); Sethi and Sorger (1991); Kurbel (2005); Kistner and Steven (2001); Kurbel(2011); Schneeweiß (1992).The length and number of planning periods varies depending on the planning area and

level and of course the specific planning problem under consideration. Furthermore thelength of planning periods can be either constant throughout the planning time window,

21


��

��

��

��

��

��

��

��

��

Figure 2.4.: Rolling horizon planning

or the aggregation level of planning periods may vary, allowing for a detailed planningin earlier periods and coarser planning for later composite periods.Typically, a new predictive plan is created at each planning iteration, as for a static

planning, assuming all information to be known and not subject to changes — it maybe viewed as a mix between a rigid and flexible planning. Created production plans forplanning periods which have already been planned in previous planning iterations areusually not considered during a planning iteration — instead a complete replanning isperformed.The application of rolling horizons and rolling horizon decision making has been ad-

dressed intensively in the past (cf. Sethi and Sorger (1991)). Rolling horizon planning isused in many applications in practice as well as in the literature (cf. e.g. Clark (2005b); Liand Ierapetritou (2010); Millar (1998); Clark and Clark (2000); Balakrishnan and Cheng(2009); Stauffer and Liebling (1997)). A lot of works in the literature are also concernedwith the related problem of examining the impact of and finding an efficient length forthe planning horizon parameter. For an overview, confer Chand et al. (2002). Anothertopic that has received considerable attention is concerned with the effect that planningmethods tend to react rather sensitive to even slight changes in planning data, resulting inrather dissimilar plans because of slight data alterations. Consequently, frequent replan-ning due to rolling horizon techniques (especially frequent in short-term planning) thenoften leads to a lot of changes to plans for planning periods which have been revised.This effect of plan variations is called nervousness (cf. Inderfurth and Jensen (1996);Kurbel (2011)) and has been studied extensively in the literature, especially in the areaof material requirement planning (MRP) systems, but other areas as well (cf. Pujawan

22


��

��

��

��

��

�

�

��

� ��

��

� ��

Figure 2.5.: Robust planning for a worst case scenario

(2004); Kimms (1998); Kropp et al. (1983); Sridharan et al. (1987); Carlson et al. (1979);Blackburn et al. (1986); Federgruen and Tzur (1994); Ho and Ireland (1993, 1998); Kaipiaet al. (2006)). Measures against planning nervousness include the application of penaltycosts for alterations to the original plan (cf. e.g. Kazan et al. (2000)) as well as fixationplanning periods or fixations of plan components (cf. e.g. Gomes et al. (2010)).

2.3.3. Robust planning

Robust planning approaches assume a non-deterministic (stochastic or dynamic) envi-ronment and try to anticipate disturbances by taking proactive measures to counter theimpact of planning uncertainties. A production plan is created to be robust with the goalof minimizing the effect of major disturbances (usually due to resource-related disrup-tions) and simple process variances (e.g. variable processing times) on the plan validityin respect to performance measures in terms of efficiency or predictability. Ideally, a ro-bust plan should need none or only minor adjustments during execution, if a disturbanceoccurs.A lot of literature on robust planning is focused on the area of machine scheduling and

the minimization of disruptions to machine availability. For more information on robustplanning, confer Aytug et al. (2005); Samsatli et al. (1998); Scholl (2001); Herroelen andLeus (2005); Gebhard and Kuhn (2009).Several groups of solution strategies, dealing with robust planning, can be found in the

literature. The first group of strategies considers a set of planning scenarios which differin the realization of disturbances and tries to create a valid plan under the assumption ofa worst-case scenario. Individual solutions of this worst-case scenario are rated by theirperformance over the whole set of considered scenarios (cf. e.g. Kouvelis et al. (2000)).Figure 2.5 shows a simple planning example considering 3 scenarios which differ in the

assumed processing time of order 1 and the occurrence of an urgent order 3. The finalplan includes the assumptions of the worst case — the longer processing time assumedby scenario 2 for order 1 as well as the inclusion of the urgent order 3.

23


��

��

��

��

��

��

� ��

Figure 2.6.: Robust planning for estimated plan realizations

�

��

��

��

��

��

��

� ��

�

��

��

��

Figure 2.7.: Robust planning for estimated disruptions

A second group of strategies tries to determine expected plan realizations and to min-imize the difference between predicted and realized plans in respect to a defined perfor-mance measure (cf. e.g. Wu et al. (1999)). Figure 2.6 shows a simple planning exampleconsidering 2 possible realizations for the processing time of a production order 1. Thefinal plan includes an estimate based on those 2 realizations for the processing time.The third group of strategies tries to estimate the effect of certain disruptions. The

production plan is then created in a way that, if the regarded disruptions occur, the plandoes not have to be adjusted during execution (cf. e.g. Mehta and Uzsoy (1998)). Theimpact estimation of certain disruption will usually be based on the past performance ofregarded production resources. As an example, a planning strategy could try to estimatethe impact of machine failures on the prolongation of process completion times, includethis information into the planning method creating the predictive plan and thus ensuregood estimates of realized completion times (e.g. by inclusion of buffer times). Thesestrategies try to ensure good estimates of the realized production flow by lowering theresource capacity. Figure 2.7 shows a simple example considering 2 past machine break-downs with different repair times. The final plan includes a buffer time which is estimatedfrom these past repair times.

24


Note that in approaches of the second and third group, the modeling of some planningparameters no longer treats these as deterministic but instead as random variables. Often,empirically determined statistical distribution functions are used in planning models.The characteristics of robust planning described in this sub-section lead to the conclu-

sion that such strategies are only applicable as long as actual disruptions and realizedvariances from estimated effects do not exceed a certain level. If disturbances occur,which have effects that are much stronger than estimated, or which are completely un-expected, the created production plan cannot be carried out as planned. Furthermore,there are often many different uncertainties effecting a production system, making itdifficult to create plans which are robust in respect to all, or at least to a set containingthe most important uncertainties and effected system parameters (cf. Neuhaus (2008)).

2.3.4. Reactive planning

Reactive planning assumes a production environment which is dynamic but productionplanning does not take proactive measures as in robust planning approaches. In case ofa disturbance (e.g. a machine break-down), of an amount which makes a plan adjust-ment necessary, the current production plan is adjusted, incorporating the changes tothe planning information. The main goal of reactive planning is the restoration of planfeasibility in case of occurring disturbances, albeit usually the retention of plan perfor-mance (in respect to defined planning goals) is desired as well. A replanning is initiatedon a periodical basis or tied to specific events. Sometimes a mixture of both is used (cf.2.5 for more information on planning policies).Reactive planning approaches can be divided into dynamic planning and predictive-

reactive planning approaches. In the case of a pure dynamic (also called “online” or“completely reactive”) planning, no predictive plan is created. Instead always only thenext decision is planned and executed. Further information about the environment isnot taken into account. Often, rule-based strategies are used for decision making. Thislessens the computational burden and increases solution speed of planning methods (cf.Holthaus and Rajendran (2000)).In the case of predictive-reactive planning approaches, first a predictive plan is created

and subsequently executed. Note that predictive planning is sometimes also referred toas “offline” planning (in contrast to online planning). Usually, all relevant informationis included in the planning process with the goal to create an optimal plan in respectto the efficiency goals defined. The computational burden is higher but such methodscan significantly outperform rule-based approaches by including much more informationin the planning process and realizing existing optimization potential (cf. Ovacik andUzsoy (1997)). However, if uncertainty increases, the performance-advantage of optimalmethods may decline in specific cases (e.g. high processing time variances, cf. Lawrenceand Sewell (1997)). Due to the occurrence of a disturbance, the plan is then adjusted asrequired. The applied methods for plan adjustments may again be simple rules, heuristicsor optimal methods. The plan adjustment may be partial, meaning that it is restricted toa part of the plan, or comprise the complete plan. If a complete replanning is performed,a completely new predictive plan is created. Figure 2.8 shows a simple example of a

25


�

��

��

��

��

��

��

��

��

�

�

�

�

� �

Figure 2.8.: Reactive planning for a machine break-down

reactive plan adjustment in reaction to a machine break-down. Also confer Neuhaus andGünther (2006) for an example of a reactive scheduling system for applications in theprocess industry.The majority of reactive planning papers in the literature is concerned with scheduling

problems. Most of these, according to Aytug et al. (2005), focus on resource-relateduncertainties, such as variable processing times or major disruptions, namely mean timesfor machine failures and repair operations. However some works also include or specifi-cally address the inclusion of new orders into a predetermined productions schedule (cf.e.g. Vin and Ierapetritou (2000); Artigues and Roubellat (2002); Roslöf et al. (2002);Mendez and Cerda (2003); Janak et al. (2006); Ferrer-Nadal et al. (2007); Caricato andGrieco (2008); Gomes et al. (2010)). For more information on reactive planning, conferAytug et al. (2005); Neuhaus (2008); Pfeiffer et al. (2007); Sabuncuoglu and Bayiz (2000);Herroelen and Leus (2005). Also note that robust and reactive planning approaches maybe combined, resulting in so-called robust-reactive planning methods.

2.4. Production plan evaluation

Given a decision problem in the area of production planning, a typical goal in the creationof a production plan is to not only find a valid plan under given conditions, but to alsofind the best possible plan in respect to defined planning goals. In order to be able tocompare different plans for a specific planning problem, evaluation criteria are required,in order to evaluate plan performances (cf. Neuhaus (2008), p.47 et sqq.).In many cases, in the literature as well as in practice, classical efficiency criteria are

used, usually requiring the calculation of cost- or time-related efficiency measures (e.g.inventory holding costs or production makespans). A listing of efficiency measures canbe found in Blömer (1999).As described in 2.3.3 robust planning aims at creating plans which are insensitive to

environmental influences. In order to evaluate the robustness of a plan, respective ro-bustness measures are required. As discussed before, robust planning is either focusedon preserving the feasibility of a plan (e.g. by insertion of buffer times) or on the re-duction of performance measure deterioration. Thus, robustness measures may roughly

26


be grouped into measuring robustness of feasibility or robustness against performancedeterioration, respectively (for a listing of robustness measures, confer e.g. Mignon et al.(1995)).Another criterion for the evaluation of a production plan is its flexibility. Flexibility

describes the ability of a plan to be adjustable in reaction to occurring events. A flexibleplan is easily adjustable to changing environmental influences (cf. Jensen (2001)).A third criterion, plan stability, describes the similarity between an original plan and

a resulting plan after adjustments have been made. A stable plan is very similar to itsoriginal plan. Plan variations may be due to replanning activities, resulting in differingplans or ad hoc adjustments during execution, in order to retain plan feasibility. Acontrary defined criterion is the aforementioned nervousness of a plan. An adjustedplan which is very dissimilar to its original plan has a high nervousness. To expressthe amount of plan variations, appropriate (stability or nervousness) measures may becalculated. For a listing of stability measures, confer e.g. Neuhaus (2008) (p.50 et sqq.).The following sub-section will focus on effects of plan variations, while 2.4.2 will present

a short overview on plan variation measures.

2.4.1. Plan variation impacts

As discussed before, variations from an original released plan may arise due to variancesduring execution (e.g. processing time variances) or plan adjustments in reaction tooccurring events. This sub-section will focus on the impacts of such plan variations.Typically, after a production plan has been created, a revision phase follows during whichthe plan is verified and altered if required. After this revision phase, the plan is releasedand thus made available to the production system as well as other depending planningactivities (e.g. material sourcing, personnel disposition or financing activities) withinthe company (or within the supply chain, respectively). If an already released plan isadjusted, another revision phase follows, verifying the altered plan. The type and amountof variations between the original and altered plan determine the verification efforts. Ahigher dissimilarity usually induces more verification efforts. In addition to a verification,the plan alterations have to be coordinated with other depending planning activities. Thisgenerates additional coordination efforts (as well as associated costs) between the involvedplanning authorities as well as with the executing production system. Beside coordinationefforts, a revision of depending plans may induce further costs. These occur for a widerange of reasons, e.g. higher material costs for deliveries on short notice, penalty costsfor plan alterations from external peers in the supply chain etc. Additionally, dependingplanning activities may also have to be repeated, again inducing further planning effortsfor depending planning activities. The revised plans of other planning activities of coursemay themselves lead to additional coordination and planning efforts and additional costs.Furthermore, released plans are also used for the communication of delivery dates tocustomers. Frequent changes to these will likely degrade the customer service quality oradd further penalty costs. In conclusion, in practical applications a low plan variation isusually desired to mitigate negative effects, such as additional coordination and planningefforts as well as additional costs.

27


��

��

��

� ��

��

��

� ��

��

� ��

��

��

!��"��

�#��

Figure 2.9.: Hierarchical grouping of plan variation measures

In the area of rolling horizon planning, planning nervousness induced by repeatedreplanning of complete planning periods due to the overlapping planning time windowshas been studied extensively in the literature. Research focused mostly on the effectof planning horizon length on planning nervousness and efficiency measures as well asthe ascertainment of an optimal planning horizon length. Further research examinedtechniques for a nervousness reduction by introducing penalty costs or fixation periods.In the areas of reactive and robust planning the majority of literature focuses on clas-

sical efficiency measures, ignoring additional coordination efforts induced by plan recon-figurations (cf. Aytug et al. (2005)). However, more recent literature is now addressingthis perspective and is also systematically modeling plan variations or replanning costs(cf. Neuhaus (2008)).

2.4.2. Measuring plan variations

In order to measure the amount of plan variations, a variety of stability and nervous-ness measures has been introduced in the literature. These are often case-specific butmay be grouped into several categories — Neuhaus (2008) describes three groups: thefinishing time of a production order, its assignment to a specific production facility andplanned production sequences. Further categories can be found, namely process dura-tions, production sizes, process execution (e.g. setup), production facility configurationsand simply the number of required plan alterations. Combinations of several categoriesare also possible, of course. Figure 2.9 shows a hierarchical categorization of plan varia-tion measures.Note that according to Neuhaus (2008), these measure may be further divided into

local and global measures. Local measures are based one one replanning iteration whileglobal measures refer to a whole sequence of replanning iterations over a certain period

28


��

��

��

��

��

��

��

��

��

Figure 2.10.: Plan variation measure example

of study. Some of these measures may thus only be calculated ex post. Mixed measuresmay be defined of course, referring to more than one iteration (e.g. by calculating meanvalues). Figure 2.10 shows an example of different plan variation measures. As can beseen, plan variation measures are not independent of each other but are often interrelatedin a way that if one measure changes, other measures change as well.

2.4.3. Combining multiple measures

If a single measure is calculated in order to evaluate the performance of a production planthe comparison of different plans and selection of the best solution can be simply executedwith respect to this single measure. If multiple measures are required the difficulty of thedecision process depends on the respective measures and the way how these are combinedin a planning method.If the different measures can be expressed in the same unit these may be combined to

form a single measure then used for comparison. The is, for example, usually the casewhen several monetary measures are summarized into a single one (e.g. cost or profitmeasure).As discussed in 2.4.1, plan variation may induce further costs. When e.g. both cost

and plan variation measures are considered in the evaluation of a production plan andif enough information about the resulting costs of regarded plan variations are available,the considered cost and plan variation measures can be easily summarized into a singlemeasure as well. However, due to the often complex nature of consequential efforts and

29


costs of plan variations sufficient information allowing for a sensible estimate of thesecosts is usually not available. Alternatively, a set of penalty costs on plan variationsare often applied instead (cf. e.g. Vin and Ierapetritou (2000)). The scale of penaltycosts in relation to the calculated economic costs then reflects a chosen weighting of thesegoal components which influences the solution process. Thus, ideally a chosen weightingshould reflect the desired balance of planning goals in order to create adequate productionplans. This selection of a sufficient weighting may not be an easy accomplishment,though, depending on the specific planning application. The sensitivity of the solutionprocess to small weighting alterations can further complicate this matter.Instead of summarizing different measures directly into a resulting single measure

other ways for the consideration of measures with different units have been explored.Gomes et al. (2010) e.g. presented a reactive scheduling algorithm for the inclusion ofnew orders into an existing schedule, which outputs not one final schedule solution butpresents several possible schedules (each generated by using a different set of fixatedorders in the original schedule) to the planner, each having separate cost and stabilityvalues. It is then up to the user to select the most appropriate schedule, thus using an expost calculation of stability measures. Amorim et al. (2011) developed a multi-objectivegenetic algorithm for a lot sizing and scheduling of perishable goods (yoghurt in thiscase) using a random weighting for each individual of the population in the calculationof a single objective function value.In general, Loukil et al. (2005) lists five types of approaches, dealing with multi-

objective scheduling problems, in the literature:

• A hierarchical ranking of goals which is used in the selection of favorable planningsolutions

• The calculation of a single objective function value as a weighted sum of the goalcomponents

• The inclusion of goals as constraints in planning models, favoring solutions withgood approximations of desired objective function values

• Interactive strategies, requiring the user of the respective planning software to makecertain decisions

• The calculation of the complete pareto front for a multi-objective planning problem,allowing for a selection of a planning solution according to an appropriate trade-offof goal achievement

Arguably, as every approach finally aims at the release of a single production plan to beexecuted, in the end, the combination of different objectives into a single preference fora specific solution, to be selected and eventually released as new or adjusted productionplan, is inevitable. What distinguishes different approaches, is the procedure in which thiscombination of goals is performed. For more information on multi-objective schedulingresearch, please confer Lei (2009).

30


��

��

��

Figure 2.11.: Planning policy categories

��

��

Figure 2.12.: Periodical planning policy

2.5. Planning policies

Planning policies determine the point in time when planning activities are to be per-formed, as well as the planning method to be used for a specific planning operation. Ingeneral, planning policies can be grouped into the three categories of periodical, event-based and hybrid planning policies (cf. figure 2.11). For more information on planningpolicies, confer Church and Uzsoy (1992), Vieira et al. (2003) or Pfeiffer et al. (2007).

2.5.1. Periodical planning policies

If planning is executed periodically, the time frame is divided into intervals of equallength. At the beginning (or end, respectively) of each interval, planning activities areperformed (cf. figure 2.12). The rolling horizon planning approach, described in 2.3.2,uses a periodical planning policy, for example. Confer also Kurbel (2005, 2011); Pfeifferet al. (2007). Depending on the planning problem it may be reasonable to use sev-eral periodicities, e.g. a weekly interval for major replanning activities and daily minoradjustments of plans.Periodical planning has the effect that changes to the planning information, which

occur during a specific time interval, are always only considered at the end of that timeinterval, namely at the time of the next planning process. If those changes to the planningdata were urgent it might then be too late at the next planning point in time. On theother hand, shorter intervals result in a more timely consideration of events, but also ineven more frequent planning activities and consequential coordination efforts and costs.

31


��

��

Figure 2.13.: Event-based planning policy

2.5.2. Event-based planning policies

Event-based planning does not divide time into planning points of equal distance atwhich planning activities are executed. Instead it considers predefined events as triggersof planning activities (cf. figure 2.13). Confer also Kurbel (2005, 2011); Pfeiffer et al.(2007).Events may be any changes to the environment which affect the relevant planning

data. What is considered as an event in a specific case varies and has to be determinedindividually for each planning environment. In an extreme example, each single planninginformation change could trigger planning activities to incorporate those data changesimmediately. This continuous triggering would then result in very frequent replanning,increasing the overall planning efforts drastically. A more sensible approach is the trig-gering of planning activities only if the occurring planning information changes reachor exceed a certain level, individually or accumulated, since the last planning iteration.On the other hand, the time between individual planning iterations may then becomeundesirably long if the defined triggering levels are not reached.In general, if several different types of events exist, which have to be considered, it is

reasonable to formulate different triggering rules for different event types. The kind ofplanning activities which are triggered may then also depend on the specific rule, e.g.triggering only minor adjustments or a major replanning. Note that a further difficultyarises if it is not practical or even possible to create and monitor a complete set oftriggering rules. This is not unlikely if a high variety of event types has to be treated,resulting in a rather large and complex rule set.

2.5.3. Hybrid planning policies

Hybrid planning approaches combine periodical and event-based planning techniques.They aim at the utilization of the strengths of both periodical and event-based policies,while diminishing the impact of the described weaknesses. Typically, planning activitiesare performed periodically, ideally using a periodicity which avoids unnecessary frequentplanning iterations. Additionally, specific events and corresponding triggering rules aredefined for which further aperiodic planning activities are initiated. This way, importantevents may be treated in a timely manner, while all other information of planning datachanges is collected and incorporated at the next periodically occurring planning pointin time (cf. figure 2.14). Confer also Kurbel (2005, 2011); Pfeiffer et al. (2007).

32


��

��

Figure 2.14.: Hybrid planning policy

2.6. Classification of an evolutionary production planning

This chapter provided an overview of import concepts regarding production planning ap-plications in dynamic environments. Several common production planning approaches,found in the literature as well as in practical applications, were discussed. In this lastsection, the main characteristics of these approaches are summarized in relation to simi-larities and overlappings with an evolutionary production planning.Rigid planning and rolling horizon planning are classical production planning ap-

proaches, usually dealing with the dynamic nature of an external company environment,such as demand fluctuations (often based on demand forecasts). While rigid plans for agiven time period are assumed to being not altered after plan creation, rolling horizonplanning accounts for changing planning information by periodical revision, classicallyin terms of a complete regeneration of respective plans. This general planning approachoccurs in a variety of manifestations and is originally used in mid-term to long-termplanning tasks. However some works in the literature also address short-term plan-ning problems. Plan variations, which occur naturally by overlapping of planning timewindows, are sometimes reduced by applying fixations on plan components or by anassessment and application of replanning penalty costs.Robust planning introduces proactive measures, aiming at the generation of produc-

tion plans which are preferably insensitive to environmental influences. Occurring distur-bances and resulting required plan alterations are implicitly assumed to being consideredduring the execution of respective production plans. The applicability of this type ofapproaches naturally depends on sufficient estimates for important planning parameters(such as processing times) and a preferably low level of environmental influences andassociated disturbances.Reactive planning on the other hand reacts on environmental influences as these oc-

cur, either by a simple rule-based online planning (dynamic planning) or by repairing apreviously created predictive plan (predictive-reactive planning). A multitude of reactiveplanning literature is located in the area of reactive scheduling problems.Both robust and predictive-reactive planning literature usually focus more on the inter-

nal environment and measures against associated disturbances, such as machine failuresor variable processing times. However, some literature (on scheduling problems) specifi-cally addresses the inclusion of new orders into a predetermined production schedule.Figure 2.15 (based on a figure by Neuhaus (2008), p.38, used to categorize reactive

planning approaches) presents an archetypal overview of these general production plan-

33


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 2.15.: Common production planning approaches & typical characteristics

34


ning approaches. It categorizes them in accordance to their typical appearance. Notethat of course overlappings between these approaches exist, but have been omitted forthe sake of clarity.These approaches also include work which is related to (and shares characteristics with)

an evolutionary production planning, in terms of an on-going and frequent inclusion ofnew demand information into existing production plans. However they are of coursenot tailored specifically to suit the evolutionary production planning approach and typ-ically exhibit a different focus, therefore are defined broader in some regards and tighterin others. Thus, when categorizing evolutionary production planning applications andresearch, instead of assigning it to these existing approaches in conjunction with an enu-meration of relevant characteristics, it appears sensible to define evolutionary productionplanning as a distinct planning approach in order to allow for a fitting categorization ofrespective applications and research.In the next chapter a general evolutionary production planning concept and planning

framework specifically designed to describe planning application in this planning areaare presented. Furthermore, while some work has been done already in the area ofrescheduling problems, there still is demand for research, addressing specific planningproblems and case studies, in different industries and other planning areas. In part II ofthis work, two case studies addressing integrated lot-sizing and scheduling problems asevolutionary production planning applications are presented.

35

3. Evolutionary production planningconcept

In this chapter a concept for an evolutionary production planning will be presented. Asdiscussed in the previous chapter, several research areas exist, which are concerned withproduction planning in dynamic environments. Currently missing though is a generalconcept which is specifically concerned with a continuously progressing plan developmentunder frequent inclusion of new demand-related planning information, as it is for exam-ple important in planning situations in which companies are faced with a fast changingenvironment and short planning time periods. In the following sections important char-acteristics of an evolutionary planning system are presented. Following these sections, aframework supporting the development of evolutionary production planning systems aswell as an evolutionary production planning simulation framework for implementationand study of these planning systems are presented.

3.1. Characteristics

This section discusses characteristics of evolutionary production planning systems.

3.1.1. Main characteristics

Evolutionary production planning is proposed as a general concept for a continuous de-velopment of production plans. Evolutionary production planning may be summarizedas being concerned with the following aspects.

The field of application for an evolutionary production planning is the short-term (orshort- to medium-term) production planning in fast-changing dynamic environments.Company environments in which such a planning approach is suitable usually exhibit anumber of the following characteristics:

• Competitive markets

• Cost pressure

• High product variety

• Complex and constantly changing consumer behavior

• Sophisticated and demanding consumer side

36

3. Evolutionary production planning concept

• Make-to-order prevalent

• Requirement for short and reliable lead time quotations and order acceptance

The environmental focus of an evolutionary production planning lies on demand-relateddynamics, such as new orders, order modifications or cancellations. Th goal of an evolu-tionary production planning is a continuously progressing plan development under con-stant inclusion of new demand-related information. In competitive markets, efficientplanning is required, e.g. in reaction to increasing cost pressure or the need for prefer-ably short lead time quotations. On the other hand, in practice it is desired that aproduction plan is preferably not altered after release. A requirement for reliable leadtime quotations also provides a further external reason for low planning variations. Thus,a continuous plan development requires a balance of plan reliability (low planning varia-tion) and efficiency. The definition of this balance is specific to each case of applicationand requires explicit consideration in planning methods (cf. 3.1.2).

The requirement for a balance of plan efficiency and reliability is also related to a balanceof the reduction of direct cost due to the economic plan performance and indirect costdue to additional coordination and planning efforts as a result of plan alterations (cf.3.1.2). Note that in the following the economic performance of a plan is also referredto as plan (or cost-) efficiency, while plan variation and associated costs are also simplyreferred to as plan variation.

Figure 3.1 shows the planning logic for a generic evolutionary production planningsystem. Considered environmental event types are new orders, modifications of alreadyaccepted orders as well as order cancellations. The actual event segmentation and thusnumber of different events to be considered depends on the individual planning appli-cation. The occurring events are handled by the planning policy which is defined fora specific evolutionary planning application. The planning policy decides if a planningiteration is necessary to make adjustments to the current production plan in order toincorporate the new information related to the occurred event. Depending on the spe-cific planning application it may be preferable to design a hierarchical structure to theplanning policy with each planning policy handling specific event types of the segmenta-tion and superordinated policies delegating events to an appropriate handling policy. If,according to the planning policy, no production plan adjustment is necessary, the eventis collected in the event stack. Events waiting in the event stack may be included in thedecision of planning policies on the necessity of plan adjustments.Beside these demand-related event types periodical planning intervals may be defined.

Again, the number of different periodical planning intervals which are defined is specificto each planning application. If an interval timer has expired a corresponding period-ical event is triggered. Planning policies decide if a periodical timer is to be reset. Aplanning policy handling a periodical interval will usually reset the corresponding timer,for example. Policies handling demand-related events may or may not reset periodicaltimers. If these are not reset, periodical planning events occur with fixed periodicities.If these are reset the periodical planning events will not occur in fixed intervals but only

37


��

��

��

��

��

��

��

��

��

��

�� !��!�

�� "

�� !��

��

#�� !��

$�� %&��

��

��

�� '��

��(��!��

��

��

)��"

)��'

��

)��

�� *��

+��!��

�� !��

,��

��

Figure 3.1.: Evolutionary production planning logic

38


if no timer reset occurs until the timer expires (also cf. 3.1.3). If the event handlingplanning policy decides on the necessity of a planning iteration, the actual planning isconducted by the planning method which is defined for a specific evolutionary produc-tion planning application. Depending on the specific planning application, it may againbe preferable or necessary to design several planning methods, each conducting differentplanning tasks, e.g. different planning methods for specific event types. The decision,which planning methods to apply in a planning iteration is made by the event handlingplanning policy.The planning methods include information about planning goals, such as pursued ef-

ficiency and plan variation and the desired balance between these goals. Furthermore,certain parts of the current production plan to be altered may be protected from al-terations by fixation rules. Other information adopted in the planning methods is amodeling of the production system and the current production system status. Also im-portant, in order to achieve a continuous plan development, is the inclusion of the currentproduction plan into the planning consideration. Note that used goal definitions or plan-ning information do not have to be identical for all planning methods. The number ofdefined planning policies, planning methods and planning goals defines the major strat-egy of an evolutionary production planning system for a specific planning application,though the planning system may include individual planning strategies for, e.g. differentevent types, each applying a specific combination of planning policy, method, goal defini-tion and production system information. The result of the planning operation performedby the chosen planning method is the altered production plan. Typically, this alteredplan then undergoes a verification phase, after which (if verification was successful) it isreleased to be executed. Additionally, if multiple plan alternatives were created in theplanning process, a selection is required (e.g. by a human planner).Figure 3.2 shows a general overview of important planning information affecting evolu-

tionary production planning systems. As has been presented above, the planning designof such a planning system for a specific planning application contains definitions of plan-ning goals, the intent on how to balance these goals, planning models describing theplanning application as well as planning methods and policies for the actual executionof the planning process. Individual combinations of these may be denoted as a plan-ning strategy. The planning systems react to environmental events regarding changingdemand-related planning information and as a result of each planning process the systemhas a released adjusted production plan as information output. However, other informa-tion affects the planning system as well, such as information regarding the productionsystem which is executing the production plans (e.g. availability of production resources)or the availability of materials required for the production processes. While the main fo-cus of an evolutionary production planning lies on the reaction to demand-related eventswith the goal of a continuous plan development, it can of course be extended to encom-pass other events, such as e.g. production system disruptions, as discussed by manyreactive planning studies (the case studies presented in part II of this work focus solelyon demand-related planning information, though).

39


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !��

Figure 3.2.: Evolutionary production system planning information overview

3.1.2. Balancing evolutionary production planning goals

A general overview of multi-objective production planning applications has been pre-sented in 2.4.3. In this section some of the common approaches are again discussed inrelation to evolutionary production planning requisites.

3.1.2.1. Plan efficiency & variation trade-off

In practice, a production plan, once it is created and finally released, needs to be reliable.Production planning operations are usually not isolated within a company (or a supplychain, for that matter) but have dependencies with other planning, controlling and coor-dination activities. Each adjustment which is made to an already released plan (A planis considered as released, if it is created and made available to the production system orfurther company departments and planning activities) is likely to cause a stir in the pro-duction flow and induce further planning, controlling and coordination efforts within thecompany (as well as other peers in the supply chain, such as suppliers). Consequently,ideally only necessary changes to the developed production plan should be made, whenplan adjustments are required in order to achieve a low variation in already plannedproduction activities. A complete redesign of a production plan is thus undesirable andshould be avoided.

40


��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 3.3.: High vs. low schedule variation

In addition to the requirement of reliability and the desire to introduce as little planningvariation as possible when adjusting a production plan, it is on the other hand alsoimportant to pursue typical economical planning goals. This is increasingly importantin highly competitive markets with strong cost pressure. Typically, cost (or time-based)efficiency goals are defined for a particular planning operation. In order to create acost-efficient plan it is also beneficial to include all relevant information and make use ofthe available optimization potential. A replanning operation that creates cost-efficientproduction plans often pays no attentions to plan variation. As a result, a completeredesign of the production plan is performed to maximize the cost-efficiency. Thus, twosuccessive production plans may show very little resemblance (cf. figure 3.3).For a particular planning application, it is important to find and define a sensible

trade-off between plan variation and cost-efficiency when designing the associated plan-ning operations which incorporate new demand information. This is one of the majorcharacteristics of an evolutionary production planning system and the quality of thematch of the defined trade-off (and executing planning operations) to a specific plan-ning application and associated planning goals is of paramount importance to the overallsuccess of an evolutionary production planning system.As described above, evolutionary planning strategies pursue economic performance

(cost, time etc.) as well as plan variation reduction goals. The requirement to followboth types of objectives and achieve an appropriate balance of planning goals demandsan evolutionary production planning system which is controllable and configurable by theplanning authority in order to allow for a detailed fine-tuning of the desired balance ofplanning goals. Direct control and the requirement of detailed information then inducesthe necessity to measure not only economic performance but also explicitly measure plan

41


��

��

��

��

��

��

��

��

��

��

Figure 3.4.: One dominant goal type

variations generated by a plan adjustment. A planning method for a specific planningapplication might alternatively be designed to implicitly pursue low schedule variationgoals, but is then missing direct control over the goal persecution and the possibility tofine-tune associated planning parameters.If planning methods are implemented, which include the calculation of a single objec-

tive function value, the objective weighting as well as the ratio of measuring units andrealized values between different objectives have a great influence on the production plancreation. In order to achieve direct control over the decision process, sufficient knowledgeabout this ratio is important. Several cases may occur in a specific planning application.The simplest case presents itself, if it is sufficient to consider only one goal dimension.If a low schedule variation is only pursued implicitly, for example by fixation of plancomponents preventing alterations, and only the efficiency goal dimension is considered,all objectives may be expressed in the same monetary measuring unit and easily summa-rized. A contrary example is established if on the other hand, a plan is to be repaired ina reactive planning, in which only plan variation is pursued as primary objective.However, in evolutionary production planning applications, as discussed in this work,

newly introduced demand-related planning information (e.g. for new orders) usuallyneeds to be incorporated in a cost-efficient manner as well. The combination of sched-ule variation and efficiency measures remains simple, though, if only one type of goalsis dominant for specific plan elements. If e.g. the weighting of plan variation is suffi-ciently higher than economic measures, such that previously planned plan elements arepreferably unaltered and only new plan elements are arranged according to efficiencycalculations (cf. 3.4). This of course still requires a reliable estimation of the magnitudeof realized goal element values.Otherwise monetary plan performance and plan variations measures can only be easily

combined if sufficient knowledge of consequential costs of plan variations is available,such that only monetary measures, having the same unit, are summarized. Additionally,weights may be used to control the influence of different goal elements on the plan creation(cf. 3.5). If it is not possible to express different goal types in the same unit, it is difficultto interpret a calculated objective function value, complicating a sensible control over thedecision process. Knowledge about magnitudes of objective values may still be obtainedby variation of weights and study of the impact on the objective function value (and planvariation and efficiency objectives), thus may lead to the further knowledge about the

42


��

��

��

��

��

��

��

��

��

Figure 3.5.: One quantity unit for all objectives��

��

��

� ��

��

Figure 3.6.: Example trade-off curve

trade-off between cost-efficiency and plan variation. If knowledge about this trade-offis obtained, it can be used to parameterize the objective function and control the plancreation in the desired way or allow for an ex post decision by the planner (cf. figure3.6).However, sufficient knowledge may not always be attainable, e.g. the form of a trade-

off curve determined by experimentation may vary depending on the respective planningdata sets used for studying the trade-off (cf. figure 3.7). This reduces the possibility ofdirect control via parameterization of planning methods over the plan creation somewhatand increases the importance of ex post decisions by the planner. Depending on thespecific planning application and implemented planning methods, determining the trade-off relationship anew for each plan adjustment can be a time-consuming solution.A further possibility for a goal balance definition is time-based. Typically, for planned

production activities, which lie in the near future, a very low amount of schedule varia-tion is desired by the planning authority, because time available for additional planning,controlling and coordination activities is very limited. For this reason, plan elements cor-responding to the near future are sometimes fixated. The acceptable amount of schedulevariation usually rises for production activities which occur later in time (cf. figure 3.8).

43


��

��

��

� ��

��

��

Figure 3.7.: Example trade-off curves for different data sets

��

��

��

��

��

��

Figure 3.8.: Time-based goal balance

Simple implementations of this approach might fixate elements of a plan or apply a domi-nant plan variation goal for early planning periods and a dominant economic performancegoal for later planning periods (cf. figure 3.9).

3.1.2.2. Multi-step techniques

In the following, multi-step techniques are discussed which aim at a better control of thegoal balance and definition of appropriate weights, lessening the need for an investigationof complete trade-off curves. A first technique, to be discussed, for controlling the goalbalance and plan creation process expresses one or both of the two types of planninggoals (plan efficiency maximization and plan variation minimization) as constraints inthe solution process (e.g. a constraint in a MILP model). Assuming that the bounds,used in the constraints restricting the objectives, are not discerned by other means (e.g.experience, historical data) suitable bounds may be determined in a multi-step processas described in the following.

44


��

��

��

��

��

��

��

��

Figure 3.9.: Time dependent goal dominance

Multiple planning iterations are performed, by focusing on plan efficiency (e.g. minimalproduction costs) in one iteration, then focusing on plan variation in a further iteration.In these two preliminary planning iterations the respective measures for the objectivesto be restricted are thus determined. For each objective two measuring points are deter-mined, stretching an interval from which to pick a value for a bound on this objective.These bounds are then used in a third and final planning iteration (This assumes thatby focusing on only one of both types of goals in the preliminary planning iterations aresulting plan usually shows a relatively better performance concerning that type of goalwhen compared to a planning process focusing on the other type of goal and vice versa).The definition of the constraint allows for a finely adjusted control of the goal balance

and plan creation in a way desired by the planner. Figure 3.10 shows an example ofa bound on an economic performance measure (e.g. production costs) in which, as afirst measuring point, the respective economic performance measure is determined in aplan-efficiency focused planning iteration. Then a planning iteration with plan variationfocus is conducted and a second measuring point is determined. Assuming that the firstplanning iteration yields a better economic performance result than the second, a suitablebound is then chosen from this interval. The final plan is created with the chosen boundas constraint, while focusing on the minimization of plan variations. The constrainingvalue may either be chosen by calculation according to a predefined parameter or in aninteractive way by a human planner.This 3-step planning process can be further simplified by exclusion of step two. In

this case, the first planning step focuses on the goal, which is used as a constraintand measures the corresponding goal achievement. The determined measuring point isthen used either directly as bound or relaxed in dependence on either a multiplicationwith a predefined parameter or by interaction with a human planner (planning methodsimplementing this two-step approach are examined in the numerical studies described inpart II of this work).

45


This technique lowers the need for (and importance of) a definition of weights (orpenalty costs, respectively) on different goal types. Instead the goal balance is controlledby restricting allowed realization of one or both types of goals. If e.g. a production costmeasure is used as constraint in a final planning step focusing on plan variations, a relax-ation of this cost measure corresponds to an acceptable economic plan deterioration (inorder to pursue plan variation goals). Thus, the desired balance between both goal types(economic performance and plan variation) can be defined by expressing the preferencesfor considered objectives by the setting of suitable bounds and related parameters.A further multi-step technique normalizes the objective measures to be summarized in

an objective function, aiming at an easier definition and interpretation of weights usedto express the desired goal balance. Assuming that normalization information is notdetermined by other means (e.g. empirical data), normalization values are again deter-mined in preliminary planning iterations. The determined plan variation and efficiencymeasures are then used as normalization values in a final planning. Figure 3.11 showsan example in which a first planning iteration focuses on plan efficiency (e.g. the mini-mization of production costs). Resulting plan variation measures are calculated. Then asecond planning iteration focuses on the minimization of considered plan variation mea-sures and calculates resulting efficiency measures. In the third in final planning iterationthese previously calculated measures are used to normalize the respective goal elements.The benefit of this approach can be an easier interpretation of defined weights (or penaltycosts, respectively) used to control the plan creation process (Note however that, despitethe normalization, an easier interpretation is not always guaranteed and depends on thespecific planning problem in focus as well as the sensitivity of the planning process toweighting changes).

3.1.3. Responsive evolutionary production planning

Section 2.5 presented a general overview on planning policies. In this section generalplanning policy characteristics are again discussed in relation to evolutionary planningrequisites.

An evolutionary planning system can be described as responsive if relevant changes tothe available planning information are continuously included into the production plan,ideally as early as possible with respect to plan performance as well as availability andquality of the related planning information.Periodical plan adjustment may be sensible for consideration of new planning infor-

mation which occurs due to the progression of the planning horizon as well as minorevents or changes to the planning data which do not require a plan adjustment rightaway. If required, more than one periodicity may be used for different types of planninginformation (cf. figure 3.12). In addition to periodical plan adjustments, if specific majorevents or changes to the planning data occur which require an immediate reaction, planadjustments have to be performed in between periodical plan adjustments. Otherwise,periodical planning could induce an undesired delay in the reaction to important eventswhich occur in between periodical planning operations. Alternatively, the time interval

46


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

� ��

��

��

� ��

��

��

��

��

��

Figure 3.10.: Goal as constraint example

47


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 3.11.: Normalization of goal elements

48


��

��

��

��

��

��

��

��

��

��

Figure 3.12.: Periodical planning policies

between periodical planning operations could be reduced to enable timely planning incase of urgent events but would also raise planning, controlling and coordination effortsdue to very frequent planning.On the other hand solely event-based planning might overlook planning information

that does not trigger a specified event. Lower triggering levels could be defined, of course,but would also result in more frequent planning operations and resulting additional efforts(cf. figure 3.13). Furthermore, as stated before, a complete set of triggering rules mightbe too complex, of course in dependence on the specific planning application.The best planning policy for a specific planning problem depends on the type and

frequency of events to be handled by planning processes and has to be fine-tuned toeach production system. In many cases, a hybrid planning policy may provide a sen-sible trade-off and allow for a responsive evolutionary production planning. Aside thealready discussed approach to apply a fixed periodicity for “normal” planning and addi-tional planning operations for special events, as defined in the planning policy, a furtherpossibility is, to monitor the time since the last (periodical or event-triggered) planningoperation and only initiate a periodical replanning if the time interval since the lastplanning operation has exceeded a defined periodical planning interval (cf. 3.14).

49


��

��

��

��

��

��

��

��

Figure 3.13.: Event-based planning policies

��

��

��

��

��

��

��

��

Figure 3.14.: Hybrid planning policies

Beside well matching planning policies, planning methods implemented for a specificevolutionary planning application need to provide planning solutions fast enough, inorder to allow for planning decisions to be made in a timely and sufficiently quick (withrespect to the specific case) manner.

3.1.4. Further characteristics

As this is a general concept, an explicit definition of comprising planning and modelingaspects is not suitable due to the wide range of planning problems found in produc-tion planning, in practical cases often introducing additional case-specific requirements.However, several important characteristics have been identified so far. These are the gen-eral characteristics described in 3.1.1 as well as (goal balance) controlability (cf. 3.1.2)

50


and responsiveness 3.1.3. In this sub-section, further general characteristics are discussed.

An evolutionary production planning requires flexible planning structures which al-low for frequent inclusion of new demand information. A company’s IT-infrastructureand information processes should provide relevant planning information, such as new orchanged demand information, early enough and in sufficient detail and accuracy in orderto exploit as much of the available optimization potential as possible in favor of a prefer-ably continuous plan development. An awareness of evolutionary production planningrequirements within a company and its responsible planning authority is a prerequisite,in conjunction with a willingness to reconsider and constantly evaluate and enhance ex-isting in-company planning structures and processes, which in practical situations aresometimes based more on old planning habits and the advantage of simplicity than onefficiency deliberations. In addition to an awareness and required information quality andavailability, the integration of regarded planning activities into further planning processeswithin the company has to be considered. Particularly, knowledge about dependencieswith other planning activities within the company is important. At the time when anadjusted production plan is released other plans will likely be in need of adjustment aswell, inducing further planning activities which need enough time to be performed be-fore actual production activities start and which themselves may induce further planningefforts and costs. In conclusion, flexibility of the production planning and sufficient rel-evant knowledge about dependencies is a basic prerequisite of an evolutionary planningsystem.Ideally, the developed planning methods chosen for planning processes in a specific

evolutionary production planning application should provide valid planning solutionsin a broad range of situations, regardless of the environmental context and occurringevents. Furthermore, an evolutionary production planning system should be integratedinto a holistic advanced planning system within the company (or supply chain) to provideall relevant planning data to the system in a timely and detailed way and also to achieveeasier coordination in reaction to plan adjustments which have impacts on other planningactivities. This may also included an integration with the production system in order tomonitor system events. In practical applications, usually case-specific conditions occurwhich need to be considered. Therefore, general planning approaches will generallynot encompass all relevant characteristics of a specific production system and planningenvironment. To achieve optimal evolutionary production planning solutions it is sensibleto include all relevant problem specific information in a tailored planning system and alsoconsider the aforementioned integration with other planning activities.In addition to the actual production planning, an evolutionary production planning

system should also include a simulation and analytical system which support the planningauthority with planning system analysis tools, such as sensitivity analyzes of productionand planning parameters. An example are aforementioned efficiency-variation-trade-off-analyzes and weight parameter settings. Other analyzes include environmental aspects,such as the impact of demand structure changes. Ex-post analyzes can provide target-oriented comparisons and support configuration adjustments of planning parameters orhighlight the necessity of modifications to the applied planning methods.

51


Finally, practical planning systems are always subject to limitations, e.g. unexpectedevents may not be manageable by the system in a fully automated manner. Thus, aplanning system should support human interaction, complementing automatic decisionprocesses, which also serves controlling purposes before plan adjustments are released.

3.1.5. Classification of evolutionary production planning applications

In this sub-section a categorization scheme for the classification of evolutionary produc-tion planning applications is presented. Individual evolutionary production planningapplications may be classified by description of the following characteristics.

• Industry or market (e.g. fast-moving consumer goods industry, chemical industryetc.)

• Planning area & problem (e.g. scheduling, lot-sizing etc.)

• Planning level (typically, an operative planning level)

• Timeframe (e.g. hours, days, weeks etc.)

• Demand characteristics (considered demand-related events, demand level and trends,order sizes etc.)

• Overall planning strategy and planning goals

• Efficiency planning goals (e.g. minimization of lot setup or inventory holding costsetc.)

• Plan variation reduction goals (e.g. minimization of lot starting or finishing timesetc.)

• Balancing of planning goals (estimation of real or penalty costs, fixation of plancomponents, goal hierarchy/dominant goals, pareto front determination, etc.)

• Planning methods & modeling (e.g. single / multiple method(s), optimal / heuris-tic, single / multi-step, interactive / automatic)

• Planning policies (single policy / multiple policies, one / multiple method(s) perpolicy, etc.)

• Other

As an example, table 3.1 shows a classification of the two investigated case studies, whichare presented in part II of this work. Confer chapters 4 and 5 for further information.

52


Cha

racteristics:

1.Casestud

y2.

Casestud

y

Indu

stry:

Fast-m

ovingconsum

ergo

odsindu

stry

Che

mical

indu

stry

food

/be

verage

indu

stry

commod

ityprod

ucts

Plann

ingarea:

Integrated

lot-sizing

&sche

dulin

gIntegrated

lot-sizing

&sche

dulin

gfix

edlotorde

rfix

edlotorde

r,sequ

ence-dep

ende

nt&

limited

chan

geover

Plann

inglevel:

Ope

rative,s

hort-term

Ope

rative,s

hort-term

/short-

tomid-term

Tim

eframe:

2-4weeks,o

rdersdu

eon

specificda

ys2-8weeks,o

rdersdu

eon

specificda

ysDem

andcharacteristics:

Freque

ntne

worde

rs&

orde

rmod

ification

events

Overallplan

ning

strategies

&goals:

Low

sche

dule

variations

&costs

Efficien

cygoals:

Setup&

inventoryho

ldingcosts

Produ

ctchan

geover

amou

nts/costs

&inventoryho

lding

Planvariationgoals:

(Sub

-)lotstarting

times,d

urations

/sizes,

setups

Balan

cing

ofplan

ning

goals:

Sche

dule

variationpe

naltycosts,

dominan

tgoals,

sche

dule

fixations,u

pper

cost

boun

dsPlann

ingmetho

ds:

MILP

mod

els,

blockplan

ning

principle,

sing

le-&

two-step

solution

processes,

automatic

Plann

ingpo

licies:

Simpleevent-ba

sed&

hybrid

plan

ning

policies

Tab

le3.1.:C

asestud

yclassific

ation

53


3.2. Evolutionary production planning system development

In this section a framework supporting the iterative development of evolutionary planningsystems is presented. Figure 3.15 shows the major steps involved in the system develop-ment. Origin of the development of an evolutionary production planning system is thegeneral formulation of a planning problem and associated planning goals correspondingto a specific planning application and aiming at a more continuous plan developmentand an implementation of the evolutionary production planning concept. After a generalproblem and planning goal definition a detailed system analysis of the considered pro-duction system and environment takes place in order to extract all information relevantto the planning problem. The output of this system analysis process should contain allrelevant facts of production system characteristics and environmental influences, includ-ing relevant types of events (For more information related to system analyzes the readermay consult Krallmann et al. (2002) or similar works). This information is then usedto formulate a detailed problem definition including detailed planning goals and relevantrestrictions on the production system and environmental aspects, such as the demandstructure for a specific product. With respect to an intended continuous plan develop-ment the aspects of a production plan to be developed with low variations have to beidentified and specific goals have to be defined. Once the planning problem has beendefined in detail, adequate planning strategies for a solution of the planning problem aredefined. Several different strategies may be selected for further development and com-parison at this stage if this seems appropriate for a specific planning problem. Accordingto the defined planning strategies, adequate planning policies are defined in respect tothe determined time-based characteristics of the planning problem. Planning methodsimplementing the defined planning processes of the planning strategies are subsequentlymodeled. After the initial problem definition and modeling, the planning system de-velopment continues with a selection or development of planning and simulation tools,supporting the implementation and evaluation of the designed planning strategies (Thedecision process of software selection or implementation is widely covered in the corre-sponding literature and not further explained here). For the case studies presented inpart II of this work, a simulation framework has been developed, which defines a generalstructure for components, interfaces and simulation flow and can be adapted for otherplanning applications. It is presented in the next section (3.3) of this chapter. Oncethe simulation system and planning tool as well as planning strategies, including definedpolicies and methods, are selected and implemented, a detailed study of the system be-havior and performance of the planning strategies in respect to defined planning goals isperformed. As a result of this evaluation process, the best performing combination (orcombinations, if individual environmental event types are handled differently) of plan-ning strategy, policy and method is selected for productive use. Before deployment, theplanning tool configuration, including planning method parameters (e.g. goal elementweighting), has to be fine-tuned for best planning quality. The released planning tools arethen deployed and used in production planning. Ensuring a sustainable planning quality,on-going planning tool and planning quality evaluations, including ex-post analyzes withplanned and actual production data, are performed, inducing subsequent planning sys-

54


��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

� ��

��

��

��

��

��

��

!"��

�� #��

��

Figure 3.15.: Evolutionary planning system development

tem revisions and parameter fine-tuning, if necessary. The development steps describedin this section are to be understood as an iterative approach with backcoupling to earlierdevelopment steps to allow for an iterative control and adjustment of the evolutionaryproduction planning system.

3.3. Evolutionary production planning simulation framework(EPPSF)

In this section, a general framework for the implementation and study of simulationand planning systems supporting the development of evolutionary production planningsystems is presented. The framework is based on several interacting components. Its

55


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

��

��

��

��

��

��

��

� ��

��

��

� ��

��

�� !"

��

��

Figure 3.16.: Evolutionary production planning simulation framework (EPPSF)

structure is shown in figure 3.16 (Note that in the following figures dashed arrows in-dicate information flows while continuous arrows indicate the triggering of an action).This general framework is designed with the intent to provide a general structure forsimulation and evaluation of evolutionary production planning strategies. It comprisesseveral interacting components and interactions as well as a basic simulation flow struc-ture. In order to realize a specific planning case the basic components and componentinteractions need to be adapted and extended as required. This framework is used in theimplementation of planning and simulation systems for the two case studies presented inpart II of this work.The main controlling component which steers the simulation flow is the EPPSF-

Simulator. It controls general simulation status information, such as the current sim-ulation time and orders other components to take action as required. At the beginningof each simulation iteration, the EPPSF-Simulator updates simulation status informa-tion and then communicates with the EPPSF-Planner to check for the necessity to adjust(or generate a first plan at simulation start) the current production plan. The EPPSF-

56


��

��

��

��

��

��

��

��

�

��

��

��

��

�

��

��

��

��

��

��

� ��

��

� � ��

��

��

Figure 3.17.: EPPSF-Planner example 1

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 3.18.: EPPSF-Planner example 2

57


Planner is the aggregate component which decides on the necessity and execution of plan-ning processes. It usually comprises several modules, e.g. one master module controllingthe planning process and separate modules implementing different planning policies andplanning methods, which are used to pursue the planning strategies to be evaluated (cf.figure 3.17). Figure 3.18 shows an alternative example of an EPPSF-Planner componentwhich utilizes separate planning strategy modules for decision processes associated withindividual planning strategies. The EPPSF-Production Environment constitutes the be-havior of the modeled production system and as such is executing generated productionplans. It controls status information of the production system, such as production orderswhich are currently being executed or have been finished or current inventory levels ofmaterials and finished products. The EPPSF-Event Manager controls the occurrence ofevents, such as changes to the demand data and the time when these information becomesavailable to the planning system to be considered by the planning components. The cen-tral data repository, providing all necessary simulation and planning data required duringa simulation run, is managed by the EPPSF-Data Manager component. It provides othercomponents with requested information and also allows for updates of this information.It uses EPPSF-Data connection manager components to load planning data from internaland external data sources. Configuration data for the simulation and planning systemis acquired from the EPPSF-Configuration Manager component. The EPPSF-Analysercomponent is used to determine simulation results for evaluation purposes correspond-ing to the experimentation focus, such as the calculation of various schedule variationmeasures of simulated planning strategies. The EPPSF-Log component provides loggingservices to the planning system and monitors the system status. System exceptions arehandled by the EPPSF-Exception Manager component. The EPPSF-UI component fi-nally provides an interface to the user for managing the configuration of the simulationand planning system, starting simulation runs and viewing simulation results as well aslogging information. It is not an essential component, its functionality may be providedinstead by external software components or other means, such as console input. An-other optional component is the EPPSF-Data Generator which may be used to generateplanning data for simulation runs if this planning information is not provided by otherexternal data sources or components. Figure 3.19 gives an overview over the generalsimulation logic (not included are the data handling and related components, in order toprovide a neat overview). Individual component logic has to be implemented in respectto the specific planning applications to be studied.

58


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

!��

" ��

��

�� # � �

��

��

��

�

�

��

��

��

��

��

�

�

��

��

$��%��

��

&��

��

��

&��

��

Figure 3.19.: General EPPSF simulation logic

59

Part II.

Case studies

60

4. Case 1 - Evolutionary scheduling of abeverages bottling facility

In this chapter a case study for an application of the evolutionary production planningapproach is discussed. After an introductory section and literature overview, a schedulingand a simulation model are presented which are used in a numerical study concerningthis case. This is followed by a presentation of the experimental results.

4.1. Introduction

The considered case is concerned with a company of the fast-moving consumer goodsand process industry which produces a variety of beverage products. The fast-movingconsumer goods industry provides everyday products, such as food, beverages, beautyand health products, clothing, tobacco, general household items etc. (cf. Cooper et al.(1994), Beck (2002)). It is a competitive industry, characteristic are low margins for rel-atively high volumes, a wide range of products, reduced order sizes, short delivery times,cost pressure and a high demand variability. Additionally, in the case of perishable goods(e.g. food or beverages), a minimal storage time between production and distributionis of importance. Companies often need to respond quickly to erratically changing con-sumer behavior and to account for increasingly demanding and sophisticated consumers,in terms of quality, flexibility, service and price (cf. van Dam et al. (1993), Keh and Park(1997), Meulenberg and Viaene (1998), Honkomp et al. (2000), Adebanjo and Mann(2000), van Wezel (2001), van Donk (2001), Bala and Kumar (2011)).Two major production stages exist in a beverage production plant — a beverage fluid

creation stage and a bottling stage. Typically, for such production plants, the finalproduction stage is the bottleneck of the production system (cf. Ferreira et al. (2010)).Tasks of the final production stage consist of the bottling of beverages as well as labelingand packing for distribution. Such production activities of finishing and packing of goodsare often denoted as “make-and-pack” production systems. As is typical for packagingstages in the process industry (cf. van Dam et al. (1993)) the number of end productsincreases drastically. In this case, this is due to a lot of different beverage containers,sizes and labels. The bottling and packaging of the various beverage products is usuallyorganized in a sequence of production cycles as is shown in figure 4.1. This type ofplanning is often referred to as block planning in practice.A production cycle is divided into several lots in which a specific beverage container

is used for bottling. A production lot is further subdivided into several sub-lots, eachcorresponding to a specific beverage product. Typically, production lots and sub-lotsare ordered in a predefined sequence within each production cycle in which each lot and

61

4. Case 1 - Evolutionary scheduling of a beverages bottling facility

�

��

�

��

��

�

��

�

��

�

Figure 4.1.: Example of a beverage bottling production cycle

sub-lot may be produced at most once. Note that the predefined sequences of sub-lotscorrespond to a natural order, which is obtained by proceeding from faint to strongerflavors, thus reducing necessary cleaning operations. Each lot requires a major setup ac-tivity during which bottling containers are exchanged and necessary cleaning operationsto the bottling facility are performed. As described above, the individual sub-lots areproduced in a natural order proceeding from faint to strong flavors — nevertheless, aminor setup activity is required, before the production of a specific sub-lot may start,during which product labels are being exchanged and necessary cleaning operations per-formed. Finally, at the end of each production cycle a major clean-out of the bottlingline facilities is necessary. It is not required for each lot to be produced within a produc-tion cycle. In dependence on the number of possible individual products and requiredminimal (sub-)lot sizes it may not even be possible to produce all products in a specificcycle of a given maximum length.In the case of this beverage production, a typical cycle roughly corresponds to a time-

frame of one week. Individual demand elements have due dates which are assigned to aspecific day of a week. Product amounts which are produced prior to the actual due dateare stored until the distribution date. While inventory holding costs of finished beverageproducts do not necessarily have to be considered due to a relatively low capital-intensity,it is desirable to achieve short storage times because of the perishability of these bev-erage products. Therefor, applied inventory holding costs for stored beverage productscan be interpreted as penalty costs instead of the consideration of capital commitmentcosts. Each bottling line is equipped with bottling facilities to serve a specific group of

62


beverage containers. In general a few major groups of beverage containers can be distin-guished — namely glass bottles, plastic bottles made by injection blow molding, boxesand bag-in-box containers. Production activities for lines serving different beverage con-tainer groups may be planned separately. Production scheduling for the bottling lines isusually executed with planning horizons of two to four weeks. Production schedules arefrequently regenerated as new orders arrive or demand changes to previously planned or-ders occur, such as cancellations, demand amount or due date changes. In consequence,if production scheduling is solely cost-focused, frequent rescheduling, as discussed before,can result in considerably dissimilar successive production schedules.

4.2. Literature

This planning problem can be described as a lot sizing and scheduling of products in thefast moving consumer goods (in particular in the beverage) industry, exhibiting a highproduct variety, short-term demand fluctuations and rescheduling activities. Productsare being produced on several lines, in cycles of predefined product sequences. They aregrouped into product families (corresponding to bottling container types) and requireproduct as well as product family specific setup times.Günther et al. (2006) presented a planning approach and a corresponding MILP model

using the block planning principle to address lot sizing and scheduling problems formake-and-pack production facilities in the fast moving consumer goods industry, withthe benefit of model complexity reduction while capturing sufficient detail to supportpractical applications. As described before, the block planning concept assumes thatthe production of various products on regarded production facilities follows predefinedsequences, either given by a natural order inherent in the production processes or by priordetermination. Each of these sequences is called a block and is assigned a productiontime window, which corresponds roughly to a specific production period, e.g. a week.Demand elements are assigned to the end of a production period. The time window whichis assigned to each block may begin before the corresponding production period but ablock has to be finished at the end of its production period to accomplish synchronizationbetween production output, finished product inventories and demand orders. Note thatthe predefined production sequences may vary from block to block. The purpose of theplanning model is to determine which products are to be produced within a block and todetermine production sizes and starting times of production lots, while considering setuptimes of blocks and lots, given production sequences, as well as demand amounts foreach period. A typical goal mentioned is the minimization of setup and inventory cost.While block planning applies a discrete time grid for the set of blocks to satisfy occurringdemand and synchronize inventories, it uses a continuous representation of time for thepurpose of scheduling blocks and lots. In the following Günther (2008) then presenteda block planning application for a make-and-pack production in the beverage industry,using an extended block planning model which considered a grouping of specific productvariants (corresponding to sub-lots) to product families (corresponding to lots) as well as

63


a second more detailed discrete time grid (e.g. days) to achieve a more precise modelingof production output, inventory levels and demand satisfaction.In the literature, other works are also concerned with production scheduling problems

in the consumer goods (and especially the beverage) industry. Christou et al. (2007) pre-sented a hierarchical planning approach for the beverage industry and developed a MILPmodel for solving aggregate master production scheduling problems, which plan produc-tion amounts for each of several month. Ferreira et al. (2009) considered a two-stage softdrink production system consisting of a liquid preparation and a bottling process, thenFerreira et al. (2010) compared relax and fix strategies solving the 2nd-stage planningproblem. They developed a MILP model formulation for the integrated planning prob-lem and several relaxation strategies for solving real problem instances. Clark (2005a)developed a model extension of the general lot sizing and scheduling problem (GLSP)and heuristics for a canning of liquid products with detailed scheduling for one weekand aggregated lot sizing for following weeks while additionally considering solution ap-proaches for a rolling horizon based planning. Bilgen and Günther (2010) considered anintegrated block and distribution planning for the fast moving consumer goods indus-try and executed numerical experiments for a beverage production and distribution casestudy. Ferreira et al. (2012) compared general lot sizing and scheduling as asymmet-ric travelling salesman problem formulation for the aforementioned two-stage soft drinkproduction.Further papers concerned with production scheduling in the consumer goods industry

have been presented by van Sonsbeek et al. (1997) for a slaughter by-product case on astrategic decision level, by van Dam et al. (1998) as a scheduling concept for the packagingof tobacco products, by Méndez and Cerdá (2002) for a two-stage continuous productionof candy products and Soman et al. (2004) for a planning framework supporting make-to-stock and make-to-order decisions for food production systems. Several applicationsoriginate from the dairy industry. Lütke Entrup et al. (2005) adopted the block planningapproach to consider a shelf-life-integrated planning and alternative block sequences inthe case of a yoghurt production, Amorim et al. (2011) then developed a hybrid geneticalgorithm. Marinelli et al. (2007) developed a heuristic approach to solve a yoghurtpackaging problem, Kopanos et al. (2010) a mixed continuous / discrete-time MILPmodel. Gellert et al. (2011) were concerned with sequencing and scheduling in the dairyindustry in general and presented a framework and greedy algorithm for solving suchproblems, while Kopanos et al. (2011) presented a continuous-time MILP model andMILP-based heuristic for a 3-stage ice-cream production system.Papers addressing applications in other industries include Günther (2009), who pre-

sented a similar application for a chemical production of a basic product being packedinto various product variants. Almada-Lobo et al. (2008) used a variable neighborhoodsearch for a long-term lot sizing and scheduling in a glass container industry case. Tosoet al. (2009) developed MILP-models and heuristics for an animal-feed production plant,Luche et al. (2009) for a production of electrofused grains. Hans and van de Velde (2011)present a hierarchical approach for planning of sand casting operations on a monthlybasis.

64


For a more general overview of lot sizing and scheduling research, the reader mayconfer several reviews, which have been published in the past decade. Reviews of capaci-tated lot sizing literature may be found in Karimi et al. (2003); Quadt and Kuhn (2008);Buschkühl et al. (2010) for example, whereas Robinson et al. (2009) focus on coordi-nated lot sizing research. A review of lot sizing problems from an industrial applicationperspective may be found in Jans and Degraeve (2008). Allahverdi et al. (2008) discussscheduling problems with setup times and cost that are either sequence-dependent orsequence-independent. Kallrath (2002) provides an overview of production planning andscheduling problems and techniques for the chemical process industry.

The block planning concept and corresponding models can be applied to the planningproblem of the beverages bottling production systems discussed in this chapter (cf. Gün-ther (2008)) and expanded to support the implementation and evaluation of differentscheduling strategies. Following the evolutionary planning approach, the intent is tocontinually evolve a production schedule, incorporating new or updated demand infor-mation — in contrast to a more classical planning approach, which might follow a solelycost-focused scheduling strategy, resulting in the iterative regeneration of completelynew and unrelated production schedules. In a numerical study classical and evolutionaryscheduling strategies are compared with each other while considering this case.

4.3. Model formulations

In this section a scheduling model for the planning problem described in 4.1 is presented.It is based on the block planning model developed by Günther (2008) and adapted to beused in conjunction with the EPPSF (cf. 3.3) and simulation model, described in 4.4 andused in the numerical experiments conducted for this case study, which are presented in4.5. Note that in order to provide a lucid presentation of the scheduling model, somedecision variables and constraints are presented, which are not essential to the modeland may be omitted. This is stated in the respective positions in the model definition.A compact version of the model can be found in 4.3.4.The detailed model in 4.3.2 is also presented with optional constraints (e.g. for the

fixation of schedule elements) and a generic objective function which includes objectivesfor the minimization of setup and inventory holding costs as consequence of the produc-tion schedule on one hand and schedule variations and associated efforts and costs onthe other hand. For reasons of simplicity these two types of costs are denoted as “pro-duction costs” and “schedule variation costs” in the remainder of this chapter. Followingthe presentation of the model, objectives, which are used in the numerical experimentsas elements of the objective function, are presented in 4.3.3. Specific objective functionsare determined by the scheduling strategy selected in each simulation run. The numberof studied scheduling strategies, each aiming at individual planning goals, are describedin the experimental design in 4.4. The scheduling strategies utilize different objectivefunctions in order to pursue specific planning goals.

65


��

��

��

��

��

Figure 4.2.: Time representation

4.3.1. Representation of time

The scheduling model which is described in sub-section 4.3.2 utilizes a mixed continuous-discrete time representation. A continuous time representation is used for the schedulingof production (sub-)lots and cycles while the calculation of inventory balances and theassignment of production cycles to time intervals uses a discrete time grid. In addition,the discrete time representation consists of a coarse time grid for the assignment ofproduction cycles to respective time intervals (e.g. assignment of production cycles toproduction weeks) and a second finer time grid for the calculation of product inventories(e.g. calculation of inventory balances for each day of a week). The time intervals ofthe coarser time grid are also called macro periods in the following while time intervalsof the finer time grid are also referred to as micro periods or simply planning periods.Figure 4.2 visualizes these time representations.

4.3.2. Scheduling model

In this sub-section the scheduling model used in the numerical study is presented. Themodel utilizes the following symbols. Note that the index label “cost” is used to denoteproduction cost related symbols while the index label “var” is used to denote schedulevariation cost related symbols.

66


Indices and index setspεP ProductslεL Production linestεT Consecutive number of production blocks/cycles (for all lines)t The first cycle of each production lineiεI Consecutive number of production lots of all lines

(e.g. lots 1,2,3 belong to cycle 1 of line 1, lots 4,5 to cycle 1 of line 2, ...)iεIlt Production lots to be scheduled in cycle t of line lilt First lot to be scheduled in cycle t on line lilt Last lot to be scheduled in cycle t on line liεI Set containing the first production lot of each cycle of all production linesiεIvar Set of lots used to calculate schedule variation measuresiεIfix Lots for which the starting time is fixediεIfixEnd Lots for which the end time is fixediεIfixC Fixed lots which may be changed, if necessaryl(i) line which lot i belongs tot(i) cycle which lot i belongs tojεJ Consecutive number of production sub-lots of all lines

(e.g. sub-lots 1,2,3 belong to lot 1 of cycle 1 of line 1,sub-lots 4,5 to lot 2 of cycle 1 of facility 1, ...)

jεJi Production sub-lots belonging to lot iji

First sub-lot of lot ijεJ First sub-lots of all lotsjεJp Production sub-lots producing product pjεJvar Set of sub-lots used in the calculation of schedule variation measuresjεJfix Fixed sub-lotsjεJfixC Fixed sub-lots which may be changed, if necessaryi(j) lot which sub-lot j belongs touεU Consecutive number of planning periods (u ≥ 0 ∀uεU )uεUi Time window of planning periods for the completion of lot iu(i) The first planning period of time window Uiu The first planning periodu The last planning period

67


ParametersM i Maximum size of sub-lot jM i Minimum size of sub-lot jalt Earliest start time of cycle t on line lalt Latest end time of cycle t on line lCl Clean-out time at the end of a cycle on line lSi Setup time of lot isj Setup time of sub-lot jbj Production time per quantity unit of sub-lot jdpu Cumulated demand of all orders of product p in planning period uhp Initial inventory level of product pfsubj Size of fixed sub-lot jf loti Starting time of fixed lot if lotEndi End time of fixed lot iwcost Weight of production (setup and inventory holding) cost objectivewvar Weight of schedule variation cost objectivewunsat Penalty costs for unsatisfied demandwfixS Penalty costs for size changes of fixed sub-lotswfixT Penalty costs for time changes of fixed lotscinvp Inventory holding costs per unit of product pclinel Clean-out costs on line lcloti Setup costs of lot icsubj Setup costs of sub-lot jgcost Maximum allowed total costsgcost =1, if gcost is used; 0, otherwisegvar Maximum allowed total schedule variation costsgvar =1, if gstab is used; 0, otherwisegunsat =1, if unsatisfied demand is allowed; 0, otherwise

68


Decision variables and domainsσltε{0, 1} =1, if and only if cycle t is produced on line lρiε{0, 1} =1, if and only if lot i is producedπjε{0, 1} =1, if and only if sub-lot j is producedχjεR+

0 Production size of sub-lot jαltεR+

0 Starting time of cycle t on line lδltεR+

0 Duration of cycle t on line lξiεR+

0 Starting time of lot iζjεR+

0 Starting time of sub-lot jηiεR+

0 Duration of lot iψjεR+

0 Duration of sub-lot jωiεR+

0 End time of lot iφiuε{0, 1} =1, if and only if lot i has been finished in or before planning period uµjuεR+

0 Production output of sub-lot j in planning-period uγpuεR+

0 Inventory level of product p at the end of planning-period uυDpuεR+

0 Unsatisfied demand of product p in planning-period uυfixSj εR+

0 Size change of fixed sub-lot jυfixTi εR+

0 Time change of fixed lot iβcostεR+

0 Total production (setup and inventory holding) costsβvarεR+

0 Total schedule variation costsβunsatεR+

0 Total unsatisfied demandβfixSεR+

0 Total size changes of fixed sub-lotsβfixT εR+

0 Total time changes of fixed lots

Constraints

The model contains the following constraints.

Production setup of cycles, lots and sub-lots∑iεIlt

ρi ≤ σlt · |Ilt| ∀lεL, tεT (4.1)

σlt ≤∑iεIlt

ρi ∀lεL, tεT (4.2)

∑jεJi

πj ≤ ρi · |Ji| ∀iεI (4.3)

ρi ≤∑jεJi

πj ∀iεI (4.4)

69


A production lot i may only be set up if the cycle t on line l, which it belongs to, isbeing produced. Note that (4.2) is optional and only has to be included, if a cycle ina valid schedule explicitly must not be started on a line unless at least one of its lotsiεIlt is to be produced. Likewise, a production sub-lot j may only be set up if the lot i,which it belongs, is itself set up. Again, (4.4) is optional and only has to be included, if avalid schedule explicitly must not include lots which are set up but contain no productionsub-lots.

Sub-lot production sizes

πj ·M j ≤ χj ≤ πj ·M j ∀jεJ (4.5)

If a sub-lot is not produced its size χi is enforced to 0. Otherwise, χi is bounded byits upper limit M i and lower limit M i, respectively.

Timing of cycles, lots and sub-lotsNote that it is assumed that the production runs continuously within a production

cycle.

ψj = sj · πj + χj · bj ∀jεJ (4.6)

The duration ψj of a sub-lot is determined by its setup time sj and production timeχj · bj . Note that decision variable ψj is not essential.

ηi = Si · ρi +∑jεJi

ψj ∀iεI (4.7)

The duration ηi of a lot is determined by its setup time Si and the durations of itssub-lots. Note that decision variable ηi is not essential.

δlt = σlt · Sl +∑iεIlt

ηi ∀lεL, tεT (4.8)

The duration δlt of a cycle on a line is determined by the duration of its lots and theclean-out time at the end of the cycle. Note that the decision variable δlt is not essential.

alt ≤ αlt ≤ alt − δlt ∀lεL, tεT (4.9)

αlt−1 + δlt−1 ≤ αlt ∀lεL, tεT \ {t} (4.10)

70


A cycle is not allowed to be started on a line before its earliest possible start time altand before its predecessor has been finished. A cycle has to be finished before its latestpossible end time alt.

ωi = ωi−1 + ηi ∀lεL, tεT, iεIlt, ωilt−1 = αlt (4.11)

The end time ωi of a production lot is determined by the end time of its predecessorand its own duration. If no predecessor exists, meaning it is the first lot to be scheduledwithin a cycle on a line, the end time is determined by the start time of the correspondingcycle and the lot duration.

ζj = ζj−1 + ψj−1 ∀jεJ \ J (4.12)

ζj = ξi + Si · ρi ∀jεJ (4.13)

ξi = ωi − ηi ∀iεI (4.14)

Constraints (4.12), (4.13) and (4.14) calculate the sub-lot and lot starting times. Notethat these two constraints are also not essential.

Production outputNote that it is assumed that the production output of a sub-lot is available at the

end of the planning period in which its corresponding lot is finished.

u− ωiu

≤ φiu ≤ 1 +u− ωiu

∀iεI, uεUi (4.15)

Constraint (4.15) forces the “lot finished”-status φiu to 0 for periods prior to the com-pletion and to 1 for periods after the completion of lot i. Note that φiu are so-calledheaviside variables (cf. Blömer and Günther (2000)).

∑jεJi

µju

M j

≤ (φiu − φiu−1) · |Ji| ∀iεI, uεUi, φiu(i)−1 = 0 (4.16)

∑uεU\Ui

∑jεJi

µju ≤ 0 ∀iεI (4.17)

Constraints (4.16) and (4.17) ensure that a production output decision variable µjuof a sub-lot in a planning period can only be greater than 0 if the lot has been finished

71


in that particular planning period and that the production output decision variable isforced to 0 for all other planning periods.

∑uεUi

µju =χj ∀iεI (4.18)

The production size of a sub-lot is equal to its production output. Note that thereforeχj is not essential and could be substituted by

∑uεUi

µjuj .

Inventory

γpu =γpu−1 +∑jεJp

µju − dpu + υDpu ∀pεP, uεU, γpu−1 = hp (4.19)

The product inventory level γpu at the end of a micro-period is determined by theinventory level of the previous planning period, the production output of sub-lots pro-ducing product p and the external demand dpu to be satisfied. Optionally, the decisionvariable for unsatisfied demand υDpu ensures that the model remains feasible even if thedemand cannot be completely satisfied. Note that this formulation of unsatisfied demandonly focuses on feasibility. If a more sophisticated expression of delayed demand satis-faction, considering tardiness etc. is desired, the model may be extended to encompassthese.

Fixed lots and sub-lots

χj = fsubj ∀jεJfix \ JfixC (4.20)

χj ≥ fsubj − υfixSj ∀jεJfix ∩ JfixC (4.21)

χj ≤ fsubj + υfixSj ∀jεJfix ∩ JfixC (4.22)

ξi = f loti ∀iεIfix \ IfixC (4.23)

ξi ≥ f loti − υfixTi ∀iεIfix ∩ IfixC (4.24)

ξi ≤ f loti + υfixTi ∀iεIfix ∩ IfixC (4.25)

ωi = f lotEndi ∀iεIfixEnd \ IfixC (4.26)

ωi ≥ f lotEndi − υfixTi ∀iεIfixEnd ∩ IfixC (4.27)

ωi ≤ f lotEndi + υfixTi ∀iεIfixEnd ∩ IfixC (4.28)

Constraints (4.20) to (4.28) are optional and allow for a fixation of sub-lot productionsizes and the timing of lots. These may for example be used to model lots which are

72


already running, have been finished at the time of the first planning periods or in order topreclude schedule variations for these fixed lots and sub-lots. Lot starting or end times aswell as sub-lot sizes are forced to the values f loti , f lotEndi and fsubj , respectively. Lots andsub-lots belonging to the sets IfixC and JfixC are allowed to deviate from fixed values(albeit with additional penalty costs υfixTi ·wfixT and υfixSj ·wfixS , respectively), whichmay e.g. be used to ensure the feasibility of the model without increasing unsatisfieddemand.

Goal elements

βcost =∆cost (4.29)

e.g. βcost =∑lεL

∑tεT

(cline · σlt)

+∑iεI

cloti · ρi

+∑iεJ

csubj · πj

+∑pεP

∑uεU

cinvp · γpu (4.30)

βcost · gcost ≤ gcost (4.31)

∆cost represents an expression calculating a production cost measure, which is usedas goal element βcost. Constraint (4.30) shows an example in which βcost consists of theclean-out costs of all production cycles, the setup costs of all lots and production sub-lots as well as production costs sub-lots and inventory holding cost of finished products.Constraint (4.31) is optional and allows for the definition of a maximum allowed valuegcost for the cost objective, if parameter gcostε{0, 1} is set to 1. This is constraint isapplied in the two-step strategies, evaluated in section 4.5.

βvar =∆var (4.32)

e.g.βvar =∑jεJvar

|χj − qj | · wt(i(j)) (4.33)

βvar · gvar ≤ gvar (4.34)

∆var represents an expression calculating a schedule variation cost measure, which isused as goal element βvar. (4.33) shows an example in which the variation cost measureis calculated as the sum of absolute values of differences between the sizes of produc-tion sub-lots and parameters qj representing expected sub-lot sizes, as determined from

73


the original schedule, while the wt(i(j)) parameter represents cycle-specific sub-lot sizevariation penalty costs. Note that the use of the absolute value function is for ease ofpresentation only. The expression can be linearized easily. Constraint (4.34) is optionaland allows for the definition of a maximum value gvar for the schedule variation goalelement, if parameter gvarε{0, 1} is set to 1.

βunsat =∑pεP

∑uεU

υDpu (4.35)

βunsat ≤ gunsat ·∑pεP

∑uεU

dpu (4.36)

The total unsatisfied demand βunsat is used as a goal element, if parameter gunsatε{0, 1}is set to 1.

βfixT =∑

iεIfixC

υfixTi (4.37)

βfixS =∑

jεJfixC

υfixSj (4.38)

βfixT and βfixS are calculated as the deviation of fixed lot starting and end times andsub-lot sizes for lots and sub-lots for which such deviation is allowed.Note that βcost, βvar, βunsat , βfixT and βfixS are of course not essential.

Objective function

min[wcost · βcost + wvar · βvar + wunsat · βunsat + wfixT · βfixT + wfixS · βfixS ] (4.39)

The objective function consists of the previously described goal elements βcost, βvar,βunsat , βfixT and βfixS with penalty costs wunsat, wfixT and wfixS , respectively. Ad-ditional weights wcost and wvaron the production and schedule variation cost objectiveβcost are included as well and allow for a balance definition of these objectives.

Model parameterizationDepending on the definition of the objective function (as well as chosen sets of fixed

lot and sub-lots) the described scheduling model shows different solution characteristics.This is exploited e.g. in the numerical studies for this planning application (cf. 4.4 and4.5) in order to implement different scheduling strategies. sβvar = 0 defines e.g. efficiencyfocused strategies. The additional definition of a goal element βvar or the fixation ofsets of lots and sub-lots adds schedule variation considerations, while βcost = 0 definesstrategies which consider no efficiency measures at all (though this may not be beneficial).If on the other hand schedule variation reduction is to be superior to plan-efficiency, thenwcost · βcost � wvar · βvar should be parameterized appropriately.

74


The main purpose of the unsatisfied demand goal element is the assurance of modelfeasibility even if not all demand can be satisfied. If a total demand satisfaction is strictlyrequired though, the parameter βunsat must be set to 0. If on the other hand appropri-ate resulting costs of unsatisfied demand quantities can be estimated, the correspondingpenalty cost parameter wunsat may be set to this value (and βunsat to 1). If maximumdemand satisfaction is to be realized but the model remain feasible even with disadvan-tageous model data, βunsat must be set to 1, while wcost · βcost � wunsat · βunsat andwvar · βvar � wunsat · βunsat are chosen appropriately, such that demand satisfaction isregarded as the superior goal.While the fixation of lots or sub-lots might ensure lower schedule variations, these

constraints also endanger the feasibility of the model or alternatively result in unsatisfieddemand. For this reason, fixed lot and sub-lots belonging to the sets IfixC and JfixC areallowed to deviate from these fixed values. With wfixT ·βfixT+wfixS ·βfixS correspondingpenalty costs are calculated. If IfixC or JfixC are used, it is reasonable to parameterizethe model, such that wcost·βcost � wfixT ·βfixT , wvar ·βvar � wfixT ·βfixT ,wcost·βcost �wfixS · βfixS , wvar · βvar � wfixS · βfixS wcost · βcost � wfixS · βfixS , wfixT · βfixT �wunsat · βunsat and wfixS · βfixS � wunsat · βunsat is achieved.

As a guidance, table 4.1 shows general model parameterization propositions for anumber of exemplary planning goals:

1. Production cost minimization, no unsatisfied demand

2. Production cost minimization, minimal unsatisfied demand

3. Production cost minimization, albeit with fixation of some lots and sub-lots topursue a schedule variation cost reduction

4. Production cost minimization, with fixation of lots and sub-lots as well as minimalchanges to fixed values

5. Production and schedule variation cost minimization, with a chosen balance of bothobjectives, no further fixations

6. Production and schedule variation cost minimization, with a chosen balance of bothobjectives as well as fixations with allowed changes

7. Prevalent schedule variation cost minimization, production cost minimization assecondary objective

8. Prevalent schedule variation cost minimization, with upper bound on productioncosts

4.3.3. Schedule efficiency & variation objectives

In this sub-section the production and schedule variation cost objectives used in the nu-merical experiments of this case study, as goal elements of the objective function, are

75


Goal

βcost

βvar

wcost

wvar

wunsat

wfixT

wfixS

gcost

gvar

gunsat

gcost

gvar

Ifix

IfixC

Jfix

JfixC

1*

01

00

2*

01

**0

13

*0

10

*{}

*{}

4*

01

****

0*

**

*5

**

1*

00

*{}

*{}

6*

*1

***

**0

0*

**

*7

**

1**

00

8*

*1

**1

0*

*:Se

tap

prop

riately

**:Se

tto

sufficientlyhigh

valueforthecorrespo

ndingob

jectiveto

bedo

minan

t

Tab

le4.1.:M

odel

parameterizationexam

ples

76


presented. The production costs βcost are always calculated from the incurred (sub-)lotand cycle setup costs on the production lines and inventory holding costs of finishedproducts:

βcost =∑lεL

∑tεT

(cline · σlt · wcostt )

+∑iεI

cloti · ρi · wcosti

+∑iεJ

csubj · πj · wcostj

+∑pεP

∑uεU

cinvp · γpu · wcostu (4.40)

The weights wcostt , wcosti , wcostj and wcostu are set to a value of 1 in the numerical studyexperiments, but generally may be set to other values (e.g. to put an emphasis on specificplanning periods, lots or sub-lots, respectively). The main production cost weight wcost

in the objective function is set to 1 as well. The relation between the production costobjective and schedule variation cost objective is adjusted by setting the global schedulevariation penalty cost wvar. Only if no schedule variation is to be considered in theobjective function is βvar set to 0:

βvar = 0 (4.41)

In all other cases βvar is set to the schedule variation cost objective to be used as goalelement of the objective function (while βcost is always set to the expression shown in(4.40)). The different implemented schedule variation cost objectives used in the numer-ical study are presented in the remainder of this sub-section.

βvar = ∆varSlSi =

∑jεJvar

|χj − qj | · wvarj (4.42)

The expression ∆varSlSi calculates sub-lot size variation costs from the original schedule and

may be used minimize variations in planned sub-lot sizes. The penalty cost parameterwvari is set to a value of 1 in the numerical study experiments, but generally may be setto other values (e.g. to put an emphasis on specific sub-lots).

βvar = ∆varLSt =

∑iεIvar

|ξi − qi| · wvari (4.43)

The expression ∆varLSt calculates lot starting time variation costs and may be used to min-

imize variations in planned lot starting times. Again, the penalty cost parameter wvari is

77


set to a value of 1 in the numerical study experiments, but generally may be set to othervalues (e.g. to put an emphasis on specific lots).

βvar = ∆varLSe =

∑iεIvar

|ρi − qi| · wvari (4.44)

The expression ∆varLSe calculates lot setup variation costs and may be used to minimize

variation in planned lot setups. The penalty cost parameter wvari is set to a value of 1 inthe numerical study experiments, but generally may be set to other values (e.g. to putan emphasis on specific lots)..

βvar = ∆varSlSt =

∑jεJvar

|ζj − qj | · wvarj (4.45)

The expression ∆varSlSt calculates sub-lot starting time variation costs and may be used to

minimize variations in planned sub-lot starting times. The penalty cost parameter wvarj

is again set to a value of 1 in the numerical study experiments, but generally may be setto other values (e.g. to put an emphasis on specific sub-lots).

βvar = ∆varSlStSi =

∑jεJvar

|ζj − qStj | · wvarStj +∑jεJvar

|χj − qSij | · wvarSij (4.46)

The expression ∆varSlStSi calculates sub-lot starting time as well as size variation costs and

may be used to simultaneously minimize variations in planned sub-lot starting times andsizes. The penalty cost parameters wvarStj and wvarSij may be set to scale the desiredproportion between sub-lot starting time and size and also to put an emphasis on spe-cific sub-lots. In the simulation experiments of this case study the relation of these twoschedule variation objective is set to a ratio of ca. 1:1 (as determined in preliminaryexperiments).

βvar = ∆varSlSe =

∑jεJvar

|πj − qj | · wvarj (4.47)

The expression ∆varSlSe calculates lot setup variation costs and may be used to minimize

variation in planned sub-lot setups. Again, the weight (or penalty costs, respectively)wvarj is set to a value of 1 in the numerical study experiments, but generally may be setto other values (e.g. to put an emphasis on specific sub-lots).

In section 4.4 the design of the conducted numerical experiments is described, includingthe number of scheduling strategies which are evaluated. While the scheduling modelpresented in 4.3.2 has been implemented and is solved in each scheduling iteration, eachscheduling strategy uses a specific objective function. These objective functions areconstructed as described in 4.3.2 and contain a production cost goal element βcost and aschedule variation cost goal element βvar as presented in this sub-section.

78


4.3.4. Compact scheduling model

The scheduling model described in the sub-section 4.3.2 focused on a lucid presentation,utilizing several additional decision variables and constraints. Several optional expres-sions were included as well. For reasons of thoroughness, this sub-section shows a compactversion of the previous model. It encompasses the following constraints.

Setups∑iεIlt


∑jεJi

πj ≤ ρi · |Ji| ∀iεI (4.49)

Production size

πj ·M j ≤∑uεUi(j)

µju ≤ πj ·M j ∀jεJ (4.50)

Timing

ωi = ωi−1 +∑jεJi

sj · πj +∑uεUi

µju · bj

∀lεL, tεT, iεIlt, ωilt−1 = αlt (4.51)

alt ≤ αlt ∀lεL, tεT (4.52)

ωilt + Cl · σlt ≤ alt ∀lεL, tεT (4.53)

ωilt−1+ Cl · σlt−1 ≤ αlt ∀lεL, tεT \ {t} (4.54)

Output

u− ωiu



∑jεJi

µju

M j

≤ (φiu − φiu−1) · |Ji| ∀iεI, uεUi, φiu(i)−1 = 0 (4.56)

∑uεU\Ui

∑jεJi

µju ≤ 0 ∀iεI (4.57)

79


Inventory


µju − dpu ∀pεP, uεU, γpu−1 = hp (4.58)

4.3.5. Model extension

The following extension to the scheduling model presented in 4.3.2 and used in thenumerical experiments for this case study supplements time windows for the demandsatisfaction of orders. Instead of specific due dates for orders, an interval of planningperiods may be defined for each order, in which the demand can be satisfied. In additionto explicit inclusion of time windows as defined by customer orders, this extension canalso be used for a better support of order acceptance considerations and quotations oflead times or delivery dates than when using the basic scheduling model. The modelextension employs the following additional symbols.

Additional indices and index setsoεOp Set containing orders of product p for which a due time window is definedoεOpu Set of orders of product p with a due time window containing planning period uuεUo Set containing due time window planning periods for order o

Additional parametersdo Demand amount of order o

Additional decision variables and domainsκouε{0, 1} =1, if order o is satisfied in planning period u; 0 otherwise

Constraints This extension introduces or changes the following constraints.

Inventory


µju − dpu −∑oεOpu

do · κou + υDpu ∀pεP, uεU, γpu−1 = hp (4.59)

Constraint 4.19 of the basic scheduling model is replaced by the constraint above.

Due time window∑uεUo

κou =1 ∀pεP, oεOp (4.60)

It is assumed that each order with a defined due time window is satisfied only andcompletely in one planning period.

80


4.4. Experimental design

This sub-section describes the experimental design of the numerical studies, which arepresented in the following section. In order to execute the simulation experiments, thegeneric evolutionary production planning simulation framework (cf. 3.3) and the schedul-ing model described in section 4.3.2 were implemented. In each simulation iteration, ifthe planning time changed or a demand event occurred, the EPPSF-Planner compo-nent — extended as suited to this case study (cf. figure 4.3) — decides on the startof a production scheduling iteration by executing an event-based or hybrid schedulingpolicy. If a schedule adjustment is required, the revised schedule is calculated by oneof several scheduling strategy modules. The scheduling policy and strategy used in asimulation run are defined by corresponding simulation system parameters. While thespecific objectives vary in dependence on the scheduling strategy applied, each strategyuses and parameterizes the scheduling model, developed in 4.3.2, which was implementedin “IBM Cplex Studio” in “OPL” syntax. The simulation system itself was implementedin Microsoft Visual Studio 10. The scheduling model solution process is executed andmonitored by the Solver module of the EPPSF-Planner component, which applies the“IBM Cplex 12.2” solver engine via “.NET” libraries in order to solve the schedulingmodel. The simulation experiments were executed on a computer running “MicrosoftWindows Server 2003” and featuring an “Intel Xeon E5420 2.5 GHz” cpu and 4 GB ofRAM. Note that some scheduling strategies may require more than one solution run bythe Solver module in each scheduling iteration (cf.3.1.1).The current state of the bottling production system is modeled by the EPPSF-Production

Environment module which was extended as required by this case study. The Produc-tion Environment module in this case models two production lines bottling the samecontainer type. Production is executed according to the last released schedule. At a spe-cific simulation time, the current production state of each line is defined by the sub-lotbeing produced on the line as well as the start and planned finishing time of that sub-lot.Furthermore, the inventory levels of bottled and packed beverage products are consumedby demands that are being satisfied and raised whenever a lot is finished which includeda production sub-lot of that specific product.Demand information which has to be satisfied during a simulation run is managed

by the EPPSF-Event Manager component, which was extended to suit this case study.Events studied in simulation experiments of this numerical study include new demandorders, which are either known as long as the used planning horizon or which are onlyknown for a shorter time period prior to the due date of the order. This may be defined bycorresponding simulation system parameters. Beside new demand orders which raise theproduct demand for a specific planning period, order cancellations (resulting in demandreductions) are also included. These are known for a number of planning periods, priorto the due date of the order. Note that the demand information used in the simulationexperiments is not generated anew by the Event Manager module during a simulationrun. Instead, a number of demand data sets are pre-generated to be used in the simu-lation experiments, in order to preclude result variations due to differing demand datasets, when comparing simulation experiment results. The Event Manager modules task

81


��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

� ��

��

��

Figure 4.3.: EPPSF-Planner - beverages bottling case

in this case is then to calculate the demand data which is known at a specific simulationtime and make it available to other system components, such as the EPPSF-ProductionEnvironment or EPPSF-Planner. The EPPSF-Analyser component calculates resultingproduction costs as well as schedule variation cost measures for each simulation run (cf.experiment descriptions in 4.5).

The main parameters and data, concerning the simulation experiments for this casestudy, are summarized in the following.

• Production system: The production system modeled in the simulation experimentsconsists of two bottling lines for one group of containers (e.g. plastic bottles)producing nine different beverage products with corresponding sub-lots that aregrouped into three lots (container sub-type, e.g. different plastic bottles) of threeproduction sub-lots (beverages and labeling) each. Table 4.2 shows further parame-ters of the modeled production system (note that time designations are normalizedto one planning period).

• Simulation time: The simulation runs and generated demand data sets encompasstime periods of 120 planning periods in all experiments. If assuming a planningperiod of e.g. one day, this accounts to a time period of 24 five-day weeks (sixmonth). Production cycles are allowed to start four planning periods prior to their

82


Production Lines (2):No. Production time per unit Cleaning time Cleaning cost1 0.0078125 0.1875 5002 0.0104167 0.1875 500Production lots and sub-lots:

Type Setup time Setup costLot (3) 0.05 80Sub-lot (9) 0.0125 20

Products (9):Initial inventory 0 (for all products)Inventory holding cost 0.274

Table 4.2.: Production system parameters

corresponding macro period. Macro periods have a length of five planning periods.Each simulation iteration schedules a number of plannable production cycles equalto the number of affected macro periods. Between 10 and 20 planning periods areincluded in scheduling iterations of the simulation runs. The set planning horizonparameter remains fixed during a simulation run. The standard number of planningperiods is 15.

• Demand: The demand data used in the simulation experiments was generatedsuited to the case study production system data using normal distributions for thegeneration of order amounts and uniform distributions for the determination of duedates as well as order cancellations. Required parameters include the number ofmicro and macro periods, the number of products, the average order size and theaverage demand level per macro period. Average order size and demand level varyand are listed for each numerical experiment presented in section 4.5. Informationabout demand orders or order modifications is sent to the planning system as anumber of individual events. The scheduling model presented in sub-section 4.3.2,which is used for the creation of production schedules, considered not individualorders but the accumulated demand amount for each planning period and product.Thus, new orders as well as positive order modifications increase the demandedorder amount for a specific product and planning period while order cancellationsand negative order modifications reduce the demanded order amount. For simplic-ity, in the numerical studies, which are presented in 4.5, demand increases of aspecific product are modeled by new orders while demand decreases are modeledby order cancellations. Individual demand orders are defined by a due planningperiod, a product type, a demand quantity, a demand type (new order / ordercancellation) and a date for when they become known to the planning system andare plannable, which is set as a simulation parameter to allow for a systematicstudy in respective experiments. Demand data for a simulation run consists of abase demand level of new orders known as long as the planning horizon, as well

83


as short-term changes (new orders or cancellations) known for a shorter time pe-riod before the due date (as parameterized). Demand data sets for simulation runsare pre-generated in order to allow for individual simulation runs having the samedemand data when comparing different scheduling strategies. Figures 4.4 and 4.5describe the generation procedures for demand data of a simulation run, whichconsists of the three separately generated subsets demand orders, short-term or-ders and short-term order cancellations. Also given are the parameter settings usedin the numerical studies (if these differ for individual experiments, this is denotedwith “*” or “**” and separately stated at the discussion of each experiment). Notethat the generation of new orders starts with the 6th planning period in order toallow for full demand satisfaction with initial product inventories of 0.

• Scheduling policies: Information about demand orders or order modifications issent to the planning system as a number of individual events. The decision ofthe execution of planning processes is obtained by the scheduling policy selectedfor a simulation run. Two scheduling policies have been applied in the numericalstudies, presented in 4.5, an event-based and a hybrid scheduling policy. Theimplemented event-based scheduling policy triggers a scheduling iteration wheneverthe known demand information changes, e.g. when a new order arrives. Theimplemented hybrid scheduling policy triggers scheduling iterations in a periodicalway if a set time interval (of one planning period) is reached and also if short-term(as parameterized) changes to the demand information occur (due to new orders ordemand cancellations). The set scheduling policy remains fixed during a simulationrun.

• Scheduling method and strategies: In the simulation experiments, the schedul-ing model, developed in 4.3.2, is applied and parameterized by various schedulingstrategies in order to calculate schedule adjustments. Several different schedulingstrategies are applied and evaluated, including a strategy which focuses on a mini-mization of production costs and various scheduling strategies considering schedulevariations (implicitly or explicitly). The strategy which is used in a simulation rundetermines the objective function of the scheduling model presented in 4.3.3. Thegoal element βcost is always used as described in 4.3.3 while the goal element βvar

and applied weights (or penalty costs, respectively) differ in dependence on thespecific strategy which is examined. The following types of strategies are studiedin the numerical experiments:

1. Strategies with production cost minimization focus — one strategy of this typeis studied. It applies a βvar = 0 and is denoted as “Cost” in the following.

2. Strategies with schedule variation and production cost minimization focus —strategies using six different objectives (∆var

LSt, ∆varLSe, ∆var

SlSt, ∆varSlSi, ∆var

SlStSi,∆varSlSe, cf. 4.3.3) as βvar are studied. Different weight proportions are exam-

ined. These strategies are denoted as “LStCost”, “LSeCost”, “SlStCost”, “SlSi-Cost”, “SlStSiCost” and “SlSeCost”. Where appropriate the applied weight

84


Generation of demand orders:Parameters: Set to:

M Last macro period 24N Number of micro periods per macro period 5D Average demand amount of an order *

(demand granularity)L Target demand level **

(targeted total demand amount per macro period)P Set of products which may be ordered {1..9}

Variables:m Current macro period (Starting from 1)n Order micro period (Starting from 1)d Order demand amountl Current demand level in macro period mp Ordered product

Steps:0. START1. SET m = 22. SET l = 03. Randomly determine the order micro period n,

uniformly distributed between 1 and Nand add (m-1)*N to n

4. Randomly determine the ordered product p,uniformly distributed, from P

5. Randomly determine the order demand amount d,normally distributed around D

6. Increase the current demand level l by d7. IF (l + 0.5*D < L) THEN GO TO step 38. IF (m < M) THEN increase m by 1

and GO TO step 29. END

*: defaults to 5% of the per planning period available capacity**: defaults to 40% (base demand level) and 20% (demand change level) of available capacitythese are varied in certain experiments (cf. section 4.5 for further details)

Figure 4.4.: Generation of demand orders

85


Generation of order cancellations:Parameters: Set to:

O Set of demand orders of a simulation run as generatedC Probability (0 to 1) of an order being cancelled *

Variables:o Current demand orderc Random number

Steps:0. START1. FOR EACH o IN O DO2. Determine a random number c,

uniformly distributed between 0 and 13. IF (c < C) THEN mark order o as cancelled4. END FOR EACH5. END

*: defaults to 0.1 but is varied in certain experiments(cf. section 4.5 for further details)

Figure 4.5.: Generation of order cancellations

proportion is added to the denotation according to the scheme “[strategyname][weight proportion as schedule variation measure:production cost mea-sure)]” (e.g. “SlStSiCost1:1”). In the numerical experiments weight propor-tions from 1:0,005 over 1:1 to 0,005:1 are studied.

3. Strategies with schedule variation cost minimization focus — strategies usingthe same six objectives (∆var

LSt, ∆varLSe, ∆var

SlSt, ∆varSlSi, ∆var

SlStSi, ∆varSlSe, cf. 4.3.3)

as βvar are studied. βcost is not set to 0. Instead penalty costs are appliedsuch that wcost · βcost � wvar · βvar holds, meaning that the reduction ofrespective schedule variation measures is pursued as primary objective, whilethe production cost minimization objective is only secondary. According topreliminary experiments a weight proportion of 1:0,005 is applied. Thesestrategies correspond to the strategies described in the previous point with aweight proportion of 1:0,005. In order to express the schedule variation focusand for reasons of simplicity these strategies are simply denoted as “LSt”, “LSe”,“SlSt”, “SlSi”, “SlStSi” and “SlSe” (“LSt” e.g. corresponds to “LStCost1:0,005”).

4. Strategies with production cost minimization focus and fixations of scheduleelements — two strategies are studied which fixate elements of the originalschedule for timeframes of three or five planning periods. Lots and sub-lots arefixated using the constraints (4.20) to (4.28) of the scheduling model presentedin 4.3.2. The strategies are denoted according to scheme “CostFix[number offixated planning periods]” in the following, giving “CostFix3” and “CostFix5”,respectively.

86


5. Strategies with schedule variation cost minimization focus and fixations ofschedule elements — strategies which focus on schedule variations in the ob-jective function and also fixate schedule elements are studied as well. Thesestrategies are based on the previously introduced LSt and LStSi strategieswith fixation timeframes of three or five planning periods. The denotation ofthese strategies is similar to the one of the previous point according to thescheme “[base strategy name]Fix[number of fixated planning periods]”, giving“LStFix3”, “LStFix5”, “LStSiFix3” and “LStSiFix5”, respectively.

6. Two-step strategies with production and schedule variation cost minimizationfocus and use of a production cost bound — Beside the previously discussedscheduling strategies, two-step strategies which apply a production cost boundare studied as well. These make use of the “Cost” strategy to calculate a pro-duction cost bound, as described in section 3.1.1. This production cost boundis then used in conjunction with one of the six schedule variation focusedstrategies. In the following, these multi-step strategies are denoted, includingthe name of the applied single-step strategy, according to the scheme “[basestrategy name]Cb” (e.g. “LStCb”). The cost bound itself is calculated by mul-tiplication of the resulting production cost measure, as determined by use ofthe Cost strategy, with a “cost bound factor” parameter, which is set in thesimulation system and remains fixed for a simulation run. The denotationscheme including the cost bound factor is then “[base strategy name]Cb[costbound factor]”. For example, a strategy “LStCb1.05” calculates the cost boundby multiplication of the production cost measure, as determined by use of theCost strategy, with 1.05 thus allowing for a production cost increase of max.5 % when compared to the Cost strategy. This cost bound is applied as modelconstraint to the “LSt” strategy in order to generate the adjusted schedule. Inthe numerical experiments cost bound factors of 1,00 to 1,10 are studied.

7. Other — An experiment discussed in 4.5.3.4 limits the number of planningperiods to be included in the calculation of schedule variation measures to asubset of planning periods. The SlSt strategy is used in this experiment.

Note that in the numerical study experiments penalty costs on unsatisfied demand areset to wcost · βcost � wunsat · βunsat and wvar · βvar � wunsat · βunsat. Sufficient penaltycosts were determined in preliminary experiments.

4.5. Numerical study results

A numerical study surveying the effects of the evolutionary planning approach on the con-sidered beverage bottling production system was conducted using the simulation frame-work and experimental design described in sections 3.3 and 4.5. For every individualscheduling iteration within a simulation run the scheduling model developed in 4.3.2

87


�

��

��

��

��

��

��

��

� ��

��

��

��

��

��

Figure 4.6.: Simulation run excerpt — base demand

was applied and parameterized by each of the evaluated scheduling strategies, for de-termination of necessary changes to the current production schedule. The schedulingstrategy selected for a simulation run determines the objective function of the schedulingmodel which contains production and schedule variation cost objectives. The results ofthe experiments are presented in this section. It consists of an introductory sub-section,including exemplary simulation extracts, and further sub-sections presenting the results.The main results of the numerical study are presented in 4.5.2, while further detailsand the impact of demand characteristics and simulation or planning parameters arepresented in 4.5.3.

4.5.1. Preliminary considerations and simulation excerpts

Before the main results are presented in the next sub-section, this introductory sub-section discusses preliminary considerations and shows exemplary extracts of demanddata and results. Figure 4.6 shows an example of base level demand data of 50% generated(as described in 4.4) for a particular simulation run consisting of 120 planning periods.In this figure, all individual product demand amounts induced by customer orders areaggregated for each planning period in which they have to be satisfied. The total demandper planning period is given in percent of the available production capacity per planningperiod. Note that the demand for the first planning periods is set to 0, in order to allowfor full demand satisfaction (with initial product inventories of 0). In addition to theorders of this base demand level, which is assumed to be known for a number of planningperiods equal to the chosen planning horizon parameter, in advance to the due date ofeach order, figure 4.7 shows the level of occurring short-term demand changes for eachplanning period. As discussed in the previous sub-section, these demand changes consistof new short-term orders (level 20%) and cancellations (20% probability).Figure 4.8 shows an excerpt of resulting production costs for a time period of 20

planning periods. The scheduling requirement was decided on by a hybrid schedulingpolicy, scheduling orders of the known base demand periodically each day and short-term

88


�

��

��

��

��

��

��

��

��

� ��

��

��

��

��

��

Figure 4.7.: Simulation run excerpt — demand change

demand changes immediately when these became known. The figure shows the final pro-duction costs cumulated for each day as planned according to the Cost strategy. Forcomparison, the costs generated by a schedule variation minimization strategy aimingat the minimization of lot starting time variations (LSt) are shown as well. Note thatin this detailed view, costs for a specific planning period are not directly comparablebetween these two strategies because the production system status differs, thus for suc-cessive scheduling iterations, the state of the production system at a specific time is notthe same for simulation runs using the same demand data but different strategies. Nev-ertheless, in this example figure, the LSt strategy generates slightly higher productioncost in overall than the Cost strategy because it focuses on a lot starting time variationobjective. Figure 4.9 shows the generated lot starting time variation costs, cumulatedfor each day, as generated by the two strategies. It is clear that in this example, the LStscheduling strategy generates significantly less lot starting time variation costs than theCost strategy. Figure 4.10 additionally shows generated schedule variations for the twostrategies. Lot and sub-lot setup variations are normalized by the number of availablesetups, lot and sub-lot starting time as well as lot duration variations are normalizedby the available production time and sub-lot size variations are normalized by the avail-able production capacity. It shows that schedule variations occur in significant numbersduring simulation runs, making it important to consider these.Figure 4.11 lists the average solution time of scheduling iterations in dependence on

the number of considered planning periods. Up to a number of 20 planning periods thescheduling model can be solved with acceptable speed. Finally, as the numerical ex-periments presented in the following sections simulate a dynamic environment and onlypartial information is available during each scheduling iteration, it is nevertheless inter-esting to compare resulting production costs with a theoretical deterministic planning,having full information in a single scheduling iteration covering all considered planningperiods. This is of course only feasible for a relatively small set of planning periods.Figure 4.12 compares a dynamic planning using the Cost strategy (with event-basedpolicy and planning horizon of 15 planning periods) with a deterministic planning over

89


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� �

Figure 4.8.: Simulation run excerpt — production costs

�

��

��

��

��

��

��

��

��

��

��

��

��

��

�

Figure 4.9.: Simulation run excerpt — lot starting time variation costs

90


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.10.: Simulation run excerpt — schedule variation measures

�

��

��

��

��

��

��

��

��

��

��

��

Figure 4.11.: Average solution time per scheduling iteration

91


�

��

��

��

��

��

��

��

��

��

��

��

Figure 4.12.: Cost strategy & deterministic planning comparison

30 planning periods. The demand consisted of a base demand level of 40% of availableproduction capacity (individual order sizes averaged to ca. 5% of the per planning pe-riod available production capacity) while the levels of new short-term orders and ordercancellations varied between 10% and 30% of the base demand level. The performanceof the dynamic planning in comparison to the deterministic varies widely and shows astronger dependence on the order sequence of each individual demand set than e.g. onthe level of demand changes. Figure 4.12 shows the average value as well as minimumand maximum values of the resulting production cost performance in these experiments.

The scheduling model used in the experiments of this numerical study includes theconsideration of unsatisfied demand in order to permit valid scheduling solutions evenif not all orders can be satisfied. In these simulation experiments unsatisfied demandamounts were negligibly small, either equal to or almost equal to 0.

4.5.2. Main results — strategy comparison

In this sub-section the main results, in terms of a general strategy comparison, of theconducted simulation experiments are presented, while the next sub-section examinesresult details and the impact of several simulation and planning parameters as well asfurther scheduling strategies, not included in this section. As described in 4.4 a simpleproduction cost minimization focused strategy and various scheduling strategies whichconsider schedule variation costs were examined. These evolutionary scheduling strate-gies are production cost strategies with fixations of schedule elements, strategies focusingon a minimization of schedule variation and production costs, strategies focusing onlyon schedule variation costs (with and without fixations) and two-step strategies min-imizing schedule variation costs with respect to a production cost bound. In the fol-lowing, the denotations described in 4.4 are used to identify individual strategies. Inthis sub-section, a representative selection of scheduling strategies is discussed. Using

92


Base demand Demand change Probability of Average Number of

new order level new order level cancellations order size data sets

40% 10% 0.1 5% 5

40% 20% 0.1 5% 5

40% 30% 0.1 5% 5

Table 4.3.: Demand data overview

the denotations defined in 4.4 the strategies presented in this sub-section are Cost, LSe,CostFix3, LSeCb1.00,SlSe, LStCost1:0.1, SlSeCb1.05, SlSeCost1:0.05, SlSiCb1.10, SlSi,SlSiCost1:0.1, LSt, LStCb1.10, SlStSi, LStCost1:0.05, SlSt, SlStCost1:0.1, SlStSiCb1.10,SlStSiCost1:1 and SlStCb1.05. Strategies not included in this sub-section are presentedin the next sub-section. The same is true for selected planning and simulation parame-ters. In preliminary experiments representative parameters were determined. These aredescribed in the following (also cf. 4.4 for a description of the experimental design).However, the impact of these parameters on simulation results was studied as well and ispresented in the next sub-section. The scheduling policies applied in the experiments ofthis sub-section are both the event-based and the hybrid scheduling policy, as describedin 4.4. The number of planning periods for individual simulation runs was set to 15 (cf.4.5.3.5 for experiments concerning the impact of different numbers of planning periods),the base demand level was set to 40% of available production capacity, with individualorder sizes averaging to 5% of per planning period available production capacity. Thelevel of short-term orders was set to 10% to 30% of available production capacity andorder cancellations occurred with a probability of 0.1. The parameter determining theoccurrence time of demand orders was set to 5 planning periods prior to the due date ofindividual demand changes (cf. 4.5.3.7 for experiments concerning the impact of differ-ent demand characteristics and related parameters). Table 4.3 gives an overview of thegenerated demand data sets.During the simulation experiments, various production and schedule variation cost

measures were chosen for strategy comparison purposes and calculated by the EPPSF-Analyser component for each simulation run. These measures are the production costs(in total as well as broken down to setup and inventory holding costs) on one hand andlot starting time, sub-lot starting time, lot duration, sub-lot size, lot setup and sub-lotsetup variation costs one the other hand. Figure 4.14 and 4.15 show averaged measuredschedule variation costs for the compared scheduling strategies, determined during thesimulation experiments. The measures presented in this figure are given in percent of thevalues measured for the Cost strategy. Figure 4.16 shows the production costs generatedby the compared scheduling strategies for those same simulation experiments. Besidethe total production costs, which consist of setup costs of production cycles, lots andsub-lots on one hand and inventory holding costs of finished products on the other hand,figure 4.16 also lists the measured setup and inventory holding costs separately. The costvalues are given in percent of the total production costs generated by the Cost strategy.In addition to a separate listing of production and schedule variation costs in figures

93


�

��

��

��

��

��

��

��

��

��

Figure 4.13.: Strategy comparison — total production & schedule variation costs

4.14, 4.15 and 4.16, figure 4.13 shows total schedule variation and production costs forthe compared scheduling strategies. A goal balance which considers both types of goalswith equal importance was chosen for the experiments of this case study. Appropriately,production costs and schedule variation costs (consisting of equally weighted startingtime, size and setup variation costs) were normalized (to Cost strategy results) andthen totalized with equal weighting. Figure 4.17 also shows total costs but focuseson the impact of different weightings for strategies utilizing an objective function withweighted production and schedule variation cost minimization (cf. 4.5.3.1 for a detailedexamination of the schedule variation and production cost trade-off). Total costs areagain normalized to the Cost strategy result.It can be observed from these results that, compared to the classical Cost strategy

which focuses on the minimization of production costs, all other evaluated strategiesgenerate lower total schedule variation and production costs. Of these the SlStSiCb1.10,SlStSiCost1:1 and SlStCb1.05 strategies generated the lowest cost overall (ca. 60-70% ofCost strategy results) while the SlStCost1:0.1 and SlSt strategies generate only slightlyhigher costs. In addition figure 4.17 shows that all of the examined strategies which usea weighted objective function generate the lowest total costs for an objective weightingof between 1:0.005 and 1:1.Scheduling strategies which only focus on a schedule variation cost minimization gener-

ally achieve significantly lower schedule variation costs than the Cost strategy, albeit withthe side-effect of higher production costs because of the different scheduling objective.The strongest schedule variation cost decrease appropriately results for the respectivemeasure which is related to the objective of each strategy. By far the lowest overall sched-ule variation costs are generated by the SlStSi strategy (Other strategies with compa-rably low production costs are LSeCb1.00, LStCost1:0.1, SlSeCost1:0.05, LStCost1:0.05and SlStCb1.05).

94


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.14.: Strategy comparison — lot variation costs

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.15.: Strategy comparison — sub-lot variation costs

95


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.16.: Strategy comparison — production costs

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� � ��

��

��

��

��

��

��

Figure 4.17.: Schedule variation & production cost objective weighting

96


Of the scheduling strategies which focus solely on the reduction of schedule variationcosts the SlSt generates the lowest total schedule variation and production costs whereas,as already discussed, the SlStSi strategy generates the lowest schedule variation costmeasures (albeit with lot and sub-lot starting time variation costs similar to the SlStstrategy). With regard to production costs all of these strategies generate ca. 10% (LSe)to 30% (SlStSi) higher production costs.While the aforementioned strategies lower schedule variation costs when compared to

the Cost strategy, the production costs generally increase (though the amount variesfrom one strategy to the other). These strategies mark the extreme points of schedulevariation cost minimization on one hand and production cost minimization on the otherhand. Those strategies which apply a weighted sum of schedule variation and productioncost objectives in the objective function of the scheduling model achieve results which liein between these extreme points. The strategies SlStSiCost1:1 and SlStCost1:0.1 gener-ate very low total costs which is also reflected in a good performance in both schedulevariation and production cost measures. Further weighted objective strategies as well asschedule variation and production cost trade-offs are discussed in 4.5.3.1. The strategieswhich use a weighted objective function allow for a fine-tuning of the planning processin order to achieve a desired balance of cost-efficiency and low schedule variations andassociated costs. This is also true for the examined two-step strategies which first cal-culate a production cost bound using only the production cost minimization objectiveand then apply this bound in a second scheduling iteration with a schedule variationminimization focus. The definition of the production cost bound also allows for a de-tailed control over the planning process. Additionally, these strategies do not require thedefinition of an appropriate objective function weighting. Instead acceptable productioncosts are defined and schedule variation costs are then minimized with respect to these.Of the evaluated two-step scheduling strategies the already discussed SlStSiCb1.10 andSlStCb1.05 strategies generate the lowest total costs. Of these two strategies SlStCb1.05generates lower production costs while SlStSiCb1.10 generates lower schedule variationcosts.The CostFix3 strategy generates lower schedule variations than the Cost strategy (~50-

90% of Cost strategy results), while resulting production costs increase by ca. 15%. How-ever, while creating similar production costs, other strategies which calculate schedulevariation cost measures in the objective function, generate considerably lower schedulevariation costs. Further strategies which use fixations of schedule elements in order toreduce schedule variations are discussed in 4.5.3.2.In conclusion, in respect to the production system and demand data examined in

this case study, all scheduling strategies considering schedule variations show a totalcost performance and schedule variation performance which are significantly better thanthe classical production cost minimization focused strategy. With respect to a strategyselection in practical applications, it depends of course on the main schedule variationgoal pursued and the desired balance of planning goals to determine the best matchingstrategy, as all strategies exhibit different characteristics, which in turn allows it to pickthe one which is considered to be the most appropriate. Strategies which focus on aspecific objective generally show a relatively good performance in related cost measures

97


(e.g. strategies with starting time related objectives show a good performance in measuresstarting time variation costs). However, it can be noted that for the production systemand demand data studied in these experiments, the SlStSiCb1.10, SlStSiCost1:1 andSlStCb1.05 strategies show the overall best performance of all strategies.

4.5.3. Result details & parameter impacts

While the previous sub-section focused on the overall simulation results and a comparisonof examined strategies, in this sub-section the impact of several simulation, productionsystem and environmental parameters are examined. Due to the large number of possi-ble combinations of scheduling strategies, simulation or planning parameters and demanddata sets and characteristics, only a small sub-set of these combinations is examined inthese experiments. Where not otherwise noted demand data was set similar to experi-ments described in sub-section 4.5.2 though used demand data sets were limited to thosewith a demand change level of new orders of 20% and 0.1 cancellation probability. Bothscheduling policies are used and the planning horizon parameter was set to 15 planningperiods. Where appropriate, results of specific experiments have been aggregated, if ex-amined strategies or parameter settings produced similar results (cf. e.g. figure 4.33), inorder to provide a better focus on the object of study of a specific experiment and showa clearer result presentation.

4.5.3.1. Schedule variation & production cost trade-off

This paragraph examines the sub-set of scheduling strategies which utilize a weightedobjective function. Figures 4.18, 4.19, 4.21, 4.22, 4.20 and 4.23 show production costs(blue curve) and schedule variation costs (red curve) generated by the scheduling strate-gies SlStSiCost, SlSiCost, SlStCost, LStCost, LSeCost and SlSeCost. The total schedulevariation costs consist of sub-lot starting time, size and setup variation costs which areequally weighted. Global weights on schedule variation costs and production costs werevaried between 1:0.005 and 0:1. Thus SlStSiCost1:0.005 is equal to the SlStSi strategywhile SlStSiCost0:1 is equal to the Cost strategy. Demand data was similar to experi-ments described in sub-section 4.5.2 though due to the large number of required simu-lation runs the simulation time span was limited to 50 planning periods. The schedulevariation costs shown in these figures are normalized to the respective strategies withweighting 0:1 while production costs are normalized to the respective strategies withweighting 1:0.005. Additionally an equally weighted average of production and schedulevariation costs is included in these figures (green curve).It can be observed from these figures that, starting from a weighting of 1:0.005, pro-

duction costs drop considerably until a weighting of 1:0.05 after which only minor im-provements are possible. Generally from a weighting of 1:1 to 0:1 no significant costimprovements are measured. Schedule variation costs are of course highest for an ob-jective weighting of 0:1 as this equals the Cost strategy. With an increasing weightingof the schedule variation objective respective schedule variation costs decrease down toweightings of around 1:0.1 to 1:0.05. In conclusion, considering schedule variation costs

98


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.18.: Schedule variation & production cost trade-off (SlStSiCost strategy)

and production costs simultaneously, the range of weightings from 1:0.05 to 1:1 generallygives the best scheduling results.Finally, figure 4.24 shows results of an experiment which considers the SlStSi strategy

in more detail regarding different weight proportions of sub-lot size and starting timeobjectives. It is clear from this experiment that the combination of these objectivesleads to lower overall schedule variation costs, though this comes with the side-effectof higher production costs than when only one of both schedule variation objectives isapplied. In order to reduce schedule variation costs for both variation types (sub-lotstarting time and size) less cost-efficient scheduling in terms of setups and storage is aconsequence.

4.5.3.2. Fixation of schedule elements

In this paragraph, the impact of schedule element fixations on the production and sched-ule variation cost performance is investigated. Studied strategies, for which parts ofproduction schedules were fixed, are the Cost, LSt and SlStSi strategies. Two length oftime periods for which corresponding schedule elements were fixed, are compared. Theseconsisted of 3 and 5 planning periods, respectively.Figure 4.25 shows the resulting production, sub-lot starting time and sub-lot size vari-

ation costs in comparison to the corresponding strategies without schedule fixations. Ingeneral, the resulting production costs increased, due to less available planning time foran efficient allocation of production lots and sub-lots. For the same reason sub-lot sizesincreased considerably when using the LSt strategy. However, the CostFix3 and Cost-Fix5 strategies lead to a decrease in sub-lot starting time and size variation costs by ca.20% and 40%, respectively. Altogether, except for CostFix strategies in comparison tothe Cost strategy, a use of schedule fixation does not benefit the evaluated strategies,

99


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.19.: Schedule variation & production cost trade-off (SlSiCost strategy)

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.20.: Schedule variation & production cost trade-off (SlStCost strategy)

100


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.21.: Schedule variation & production cost trade-off (LStCost strategy)

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.22.: Schedule variation & production cost trade-off (SlSeCost strategy)

101


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.23.: Schedule variation & production cost trade-off (LSeCost strategy)

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.24.: Sub-lot starting time & size variation cost trade-off (SlStSi strategy)

102


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.25.: Schedule fixation strategies

when calculating overall production and schedule variation costs (though in practical ap-plications it may often be preferred to ensure fixed schedules for the immediate future).

4.5.3.3. Two-step strategies with production cost bounds

This paragraph studies the two-step scheduling strategies as described in 4.4. The plan-ning process for each scheduling iteration is divided into two steps. First a preliminaryscheduling is performed using the Cost strategy. The measured production costs arethen multiplied by a “cost bound factor” (set as simulation parameter) to calculate aproduction cost bound constraint which is applied in a second scheduling step using ascheduling strategy focusing on the minimization of a schedule variation measure.Figures 4.26 and 4.27 show a comparison of scheduling strategies with production cost

bounds. Production cost measures and a selection of schedule variation cost measures arepresented. The cost bounds on the SlStSiCb, SlSiCb, SlStCb, LStCb, LSeCb and SlSeCbstrategies are calculated by cost bound factors of 1.00, 1.05, and 1.10 corresponding toallowed production cost increases of 0%, 5% and 10% over the production cost measurewhich is measured in the first step of each two-step scheduling iteration. The figures showthat for increasing production cost bounds the resulting production costs increase as well,while the schedule variation cost measure in focus of each respective strategy decreases.The impact on schedule variation cost measures which are not in focus of a specificstrategy differs. The LStCb1.00 and SlSeCb1.00 strategies generate the lowest productioncosts of these strategies, on par with the Cost strategy. The LStCb1.00 strategy alsoachieves significant schedule variation cost reductions in all measures, compared to theCost strategy, whereas the SlSeCb1.00 exhibits a worse performance, on par with theCost strategy, in starting time related measures. SlStCb and SlStSiCb strategies achievean even better schedule variation cost performance than the LStCb1.00 strategy, albeitat slightly higher production cost.

103


�

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.26.: Production cost bounds — schedule variation costs

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.27.: Production cost bounds — production costs

104


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.28.: Production cost bounds — SlStCb strategy

Figure 4.28 examines one of the scheduling strategies (SlStCb) for production costbound factors of 1% to 5% and also compares it with the Cost and SlSt strategies.As can be seen from this figure, a cost bound factor of even 1% leads to significantlyreduced schedule variation costs, while having almost no impact on resulting productioncosts. If further production cost increases are deemed acceptable by the planner, schedulevariation costs may be further reduced by increasing the cost bound factor further. Thisshows that even if only minor increases in production costs are deemed acceptable, thistwo-step approach can significantly reduce schedule variation costs. Most importantly, asensible trade-off of production and schedule variation costs can be defined just from aproduction cost perspective, without the necessity of detailed knowledge of the magnitudeand proportion of production and schedule variation objectives, though knowledge aboutthe magnitude of production costs may still be helpful in order to define sensible costbound factors.

4.5.3.4. Limited number of planning periods with schedule variation considerations

In this paragraph the impact of a limited number of planning periods for which schedulevariations are considered is presented. Figure 4.29 shows production and schedule vari-ation cost measures as generated by a modified SlSt strategy which considers only thefirst 5 planning period in schedule variation calculations. As comparison the productionand schedule variation cost measures generated by the Cost and standard SlSt strategiesare also included. For most schedule variation cost measures, the resulting amount ofgenerated costs lies between the Cost and SlSt strategies, albeit with a worse perfor-mance than the Cost strategy, for setup variation related measures. Total productioncosts are drastically increased though. This is due to an increase in setup costs which is

105


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

� ��

��

��

��

��

��

��

��

��

��

��

Figure 4.29.: Limited number of planning periods with schedule variation consideration

not balanced by the decrease in inventory holding costs. Thus a limitation of planningperiods for which schedule variation costs are considered is neither beneficial (at leastwhen considering the SlSt strategy) to the production cost nor to the schedule variationcost performance.

4.5.3.5. Number of planning periods

The planning horizon parameter which is set for a simulation run determines the numberof planning periods which are included in each scheduling iteration. The more planningperiods are included in a planning process, the more orders have to be included andadditional lots and sub-lots to be scheduled if need be. This paragraph focuses on theimpact of the number of planning periods on the simulation results. Scheduling strategieswhich were used in these experiments are the Cost, SlSi, LSt, SlSe and SlSt strategies.Figure 4.30 shows the production costs, as generated by these scheduling strategies,

normalized to the respective results for a planning horizons 10 planning periods (Notethat the overall performance relation between discussed strategies, as presented in 4.5.2,did not change for different numbers of planning periods). The figure shows that longerplanning horizons lead to lower production costs. Longer planning horizons allow for amore cost-efficient allocation of production resources because of the increased numberof planning periods available for planning considerations. However, for these strategiesthe production cost advantage of a planning horizon of 20 in comparison to 15 planningperiods is only minor, compared to the difference between 15 and 10 planning periods.Thus, scheduling strategies, which focus on the minimization of these production costs,such as the Cost strategy, can better exploit the increased optimization potential.

106


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.30.: Planning horizon length & production costs

A different trend is observable in respect to schedule variation costs which are calcu-lated in each simulation experiment (cf. figure 4.31). In general, schedule variation costsincrease for longer planning horizons because of a higher number of planning periods (andthus demand orders) which have to be taken into account in each scheduling iteration. Inorder to satisfy all demand orders and follow defined objectives more changes to originalschedules have to be made in individual scheduling iterations. In addition, each demandelement is included in a higher number of scheduling iterations. Due to the fact that forthe production system and demand data considered in these experiments, the examinedstrategies show only a slight production cost decrease when comparing planning horizonsof 15 and 20, a planning horizon of 15 planning period is a sensible trade-off for thestudied case (when comparing both schedule variation and production costs).

4.5.3.6. Scheduling policies

After examining the impact of the planning horizon parameter this paragraph focuseson differences of the two implemented scheduling policies (cf. 4.4) which determine theplanning process execution. The event-based scheduling policy triggers a schedulingiteration whenever a new demand order arrives or a cancellation occurs. The hybridpolicy triggers scheduling iterations periodically with an interval of 1 planning periodand also whenever demand changes (new urgent order or order cancellation) occur. Inall experiments of this numerical study these two scheduling policies were applied.The scheduling strategies utilized for these experiments are the Cost, LSt, SlSi, SlSt,

SlStSi, LSe, SlSe, LStCb1.00, SlStCb1.05 and SlStSiCb1.10 strategies. Figure 4.32 showsschedule variation and production costs as generated by the hybrid scheduling policy inpercent of the costs generated by the event-based scheduling policy. Additionally, average

107


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.31.: Planning horizon length & lot starting time variation costs

schedule variation costs per scheduling iteration are included. The figure shows that,while the impact on the resulting production costs is minor, the more frequent schedulingiterations initiated by the event-based policy in turn lead to more frequent scheduleadjustments and higher schedule variation costs overall. However, the average amountof schedule variations which are generated by each scheduling iteration is higher for thehybrid scheduling policy. The higher these changes induced by schedule adjustmentsin each iteration, the more additional planning efforts and associated costs may ariseat once in reaction to the schedule adjustments. The relative schedule variation costdifference depends on the applied strategy. The examined strategies which include asub-lot starting time objective show the lowest cost difference, hence respective averagecosts per iteration are relatively highest.

4.5.3.7. Demand characteristics

This paragraph focuses on various aspects of the product demand which occurs and hasto be satisfied during a simulation run. As described in 4.4 the demand of a simulationrun consists of a base demand level with demand quantities and due dates, which areassumed to be known at least as long as the number of considered planning periods. Thus,as the planning time window moves forward in time, meaning that new planning periodsare included in the time window, base demand order events with due dates in these newplanning periods occur subsequently and are then available for consideration in schedulingiterations. Additionally, changes to the base demand, consisting of short-term ordersor cancellations, occur during a simulation run. The demand information is handledby the EPPSF-Event Manager component and made available to other components of

108


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.32.: Scheduling policy & cost measures

the simulation system when the respective demand elements become known and areplannable.In the first experiment, presented in this paragraph, the base demand level was varied.

Figures 4.33 and 4.33 show production and schedule variation cost measures in depen-dence on the base demand level. The results for the utilized scheduling strategies (Cost,SlSi, LSt and SlSe) are normalized to the results obtained for a demand level of 60%.Demand change levels for the simulation runs of these experiments were set as follows.New orders accumulated to 10% of the corresponding base demand level and demandcancellations were also set to a probability of 0.1, keeping the overall demand level con-stant. Figure 4.33 examines the production cost impact of the base demand level whichoccurs during a simulation run. Interestingly, all evaluated strategies show more or lessthe same trend for a production cost increase with rising demand levels. Thus, the rel-ative cost increase in dependence on the base demand level is more or less independentof the chosen scheduling strategy (at least for the sub-set of strategies selected for thisexperiment). Consequently, results are aggregated in the following, in favor of a clearerpresentation, if these are similar for different examined strategies or parameter settings.Figure 4.34 shows the lot starting time variation costs generated by the scheduling strate-gies. The examined strategies also show a more or less linear increase for rising demandlevels but with differences in the gradient. The Cost strategy exhibits a relatively slowincrease, which means that it does not benefit of lower demand levels as much as theother examined strategies which consider schedule variations. The LSt strategy on theother hand exhibits the steepest gradient. In conclusion, an increase of the base demandlevel leads to a proportional increase in schedule variation and production costs.After studying the impact of the base demand level, the following figures now focus

on the impact of the time interval an occurring demand change (short-term order or

109


��

��

��

��

��

��

��

��

��

��

��

� � � � ��

��

��

��

� ��

��

��

��

Figure 4.33.: Demand level & production costs

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.34.: Demand level & lot starting time variation costs

110


��

��

��

��

��

��

� � � � � � �

��

��

��

��

��

� ��

��

��

Figure 4.35.: Demand change offset impact

cancellation) is known before its respective due date (henceforth referred to as the “de-mand change offset”) as well as the overall level of demand changes. Figure 4.35 showsschedule variation and production cost measures in dependence on the demand changeoffset as generated by the Cost and LSt strategy. Both strategies showed similar resultsin dependence on the demand change offset. Figure 4.35 shows the averaged results.The cost measures are normalized to respective measures generated for a demand changeoffset of nine planning periods. Figure shows a trend of increasing production costs forlonger demand change offset though up to a demand change offset of 4 planning periodsthe increase is minor. Schedule variation costs are lowest for a demand change offsetsof 2 to 4 planning periods but are higher for demand changes on a very short notice (1planning period). They also increase more strongly than production costs for demandchange offsets higher than 4 and up to 7. For longer demand change offsets individualorders are included in a higher number of scheduling iterations which leads to an increasein schedule variations. However when considering the percentages shown in figure 4.35(92% to 102%) the impact of the demand change offset is subtle.Far stronger is the impact of the demand level as can also be observed from figure

4.36 which focuses on the demand change level. The demand change data used in theseexperiments consists of equal amounts of order cancellation and new orders (given inpercent of a used base demand level of 40%), keeping the overall demand level moreor less constant. The Cost and LSt strategies were used as scheduling strategies. Theimpact of the demand change level was similar for both strategies. Figure 4.36 shows theaveraged results. Similar to the effect higher base demand levels had, increasing demandchange levels induce higher costs. The results show an upwards trend (albeit with the

111


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.36.: Demand change level impact

demand data sets used in the experiments for a demand change level of 40 allowing forslightly less resulting costs).The last demand characteristic which was studied in these simulation experiments is

the demand granularity, meaning the mean size of individual demand orders. In theseexperiments the Cost and the SlSt strategy were used. Three granularities are examinedwith mean demand order sizes of 5%, 10% and 20% of the available production capacityper planning period. Higher mean order sizes also correspond to a lower number ofindividual orders for a given demand level. The impact of the demand change level wassimilar for both strategies. Figure 4.36 shows the averaged results. Different order sizesshow almost no impact on the resulting production costs, as the production scheduling(among other objectives) also aims at an efficient allocation of new orders in terms ofsetup costs. A different effect can be observed in respect to schedule variation costs whichdecrease for larger order sizes because fewer individual demand orders are rescheduledin each scheduling iteration. However, considering the percentages shown in figure 4.36(94% to 101%) the impact of the demand granularity is very subtle.

4.6. Case summary

The experimental results of the investigated beverages bottling case study (using theEPPSF) show that scheduling strategies which consider schedule variations significantlydecrease the total amount of schedule variation and production costs in comparison to asimple production cost minimization approach. The reduction in schedule variation costsmay entail an increase of production cost measures because applied scheduling objectives

112


��

��

��

��

��

��

��

��

��

��

��

Figure 4.37.: Demand granularity impact

are not purely focused on a production cost minimization. A sensible balance is highlydependent on the specific planning case in focus and has to be adjusted by the planner.For the purpose of this exemplary case study both planning goals were considered asbeing of equal importance. Consequently, of the evaluated scheduling strategies thosewhich generate the lowest total schedule variation and production costs are the onesthat consider both types of objectives. These best performing strategies SlStSiCb1.10,SlStSiCost1:1, SlStCb1.05, SlStCost1:0.1 use either a weighted objective function (withnot too extreme relative weight differences) or implement the two-step approach whichcalculates and applies a production cost bound (which in turn restricts the possibility ofschedule variation reductions to those which do not raise the resulting production costsover the determined bound). As an exception the SlSt strategy also generates relativelylow total costs. Furthermore, the best performing of the examined strategies use a sub-lot starting time or sub-lot starting time and size objective as schedule variation goalelement. When only the schedule variation goal is considered the SlStSi strategy performsbest, as it generates the lowest schedule variation costs. On the other hand, resultingproduction costs are significantly higher. The lowest production costs are generated bythe Cost strategy which only focuses on the minimization of production costs.A variety of different objective weighting and cost bound factors was examined in these

simulation experiments. The results show that generated cost measures are sensitive tothe setting of these parameters. This emphasizes the importance of a detailed fine-tuning(and continuous revision) of planning parameters for practical applications in order toobtain the best possible planning results in respect to defined planning goals and thedesired production cost and schedule variation trade-off. In addition to these strategy-related observations, specific results also react more or less sensitive to changing values

113


of production system and planning parameters, as well as characteristics of the demandto be satisfied.

114

5. Case 2 - Evolutionary scheduling ofchemical commodity products

In this chapter a further case study for an application of the evolutionary productionplanning approach is discussed. After an introductory section and literature overview,a scheduling and a simulation model are shown which were used in a numerical studyconcerning this case. This is followed by a presentation of the experimental results.

5.1. Introduction

The considered case was obtained from a company of the chemical industry, which pro-duces a variety of chemical commodity products in its production facilities. Typical ex-amples for produced product types are polymer-based products (e.g. polymers used forinjection molding), surface coating materials, adhesives, films and sheets. The propertiesof the production output of each production facility depend on the setting of productionparameters and also on additional substances which are added during the productionprocesses, allowing for the production of a variety of different products with very spe-cific and well defined properties. Production is organized in a succession of productioncycles, which follow a pre-defined product sequence and in which each product may beproduced at most once. Products with similar properties are ordered close to each otherwithin a sequence and are thus produced with similar production parameters. When theproduction is switched from one product to another, for a time, no specified product isbeing produced. This so-called off-spec material output cannot be sold and has to bedisposed of. Changeover time and corresponding output of off-spec material depend onthe specific products between which a changeover occurs.Like many companies nowadays, the company considered in this case study encounters

a very dynamic environment — it is faced with competitive markets, increasing productvariety, cost pressure, higher demand variability, shorter order timeframes and more fre-quent changes. While demand, which has to be satisfied, partly consists of orders whichare known short- to medium-term, frequent new short-term orders and order cancella-tions or modifications have to be included in planning processes. Production schedulingfor different production facilities is done for timeframes of 2-8 weeks with customer ordersthat are usually due on specific days. It focuses on the reduction of off-spec materialproduction, but also product inventories. Frequent rescheduling is often necessary due todemand variability. Ideally, production schedules are desired which are cost-efficient butalso exhibit fewer schedule variations and associated costs. Following the evolutionaryplanning approach, the intent in respect to this case study again is a continuous de-velopment and adjustment of production schedules under incorporation of new demand

115

5. Case 2 - Evolutionary scheduling of chemical commodity products

information.

In the following, the planning problem considered in this case study will be described.By supplying necessary input materials and adjusting production system (e.g. chemicalprocess) parameters, such as e.g. temperature or pressure, each chemical productionfacility is able to produce a range of products of a specific product type. When theproduction system is configured for the production of a specific product, it is possible toswitch to the production of another product by changing necessary input materials andproduction system parameters. This change of input materials and production systemparameters creates a product-specific time interval in which no defined product is beingproduced. The amount of off-spec material varies in dependence on the two productsbetween which an individual production changeover occurs. The changeover time inter-val is not arbitrary but varies in accordance to the similarity of each two products. Theproduction of different products follows a natural production sequence with similar prod-ucts having similar input materials and production system parameters. Similar productsare arranged close to each other within this sequence and therefore generate less off-specmaterial production when the production is switched between them. Note that a changefrom product A to product B to product C does not necessarily equal a change fromproduct A to product C, when considering the amount of off-spec material output beingproduced. Furthermore, between certain production combinations, no direct changeoveris possible at all (e.g. due to technical reasons). Also note that in some production facil-ities production is usually running continuously (interruptions being possible but takinga lot of time and therefore being undesirable), it is instead possible to slow down theproduction speed in order to adjust the amount of production output.Considering the production system of this case study, it is possible to identify one or

more characteristic chemical process parameters for each production facility. These allowfor a determination of the current state of the production system and the product beingcurrently produced. It is possible to order the products according to an increasing (ordecreasing) characteristic chemical process parameter. Thus, it is possible to producethe whole range of products by traversing this parameter from the minimum to maxi-mum value, resulting in the aforementioned natural production order for each facility.Additionally, in some production facilities, it is possible to inverse this production cy-cle, meaning a traversion, starting at the maximum and ending at the lowest parametervalue. Figure 5.1 shows an exemplary changeover matrix with products being numberedfollowing the natural order, starting from 1. Specific product names and changeovervalues have been omitted. Instead colors indicate the amount of off-spec material out-put between each two products, green signifying a very low off-spec material output,increasing from yellow over orange to red fields, which indicate very high off-spec ma-terial amounts. Brown regions, on the other hand, indicate products between which nochangeover is possible. Note that the definition of a full matrix in this example indicatesthe possibility of inverse production cycles. Furthermore note that in general a changefrom product A to product B is not equal to a change from product B to product A.Similar products are grouped into clusters and sub-clusters, respectively. Figure 5.2

shows an excerpt of a changeover matrix for one cluster and corresponding sub-clusters.

116


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37123456789

10111213141516171819202122232425262728293031323334353637

Figure 5.1.: Exemplary changeover matrix

11 12 13 14 15 16 17 18 19 20 21 22S-Clust.3-1 11

12S-Clust.3-2 13

14S-Clust.3-3 15

Clust.3 1617

S-Clust.3-4 18S-Clust.3-5 19

20S-Clust.3-6 21

22

Figure 5.2.: Changeover matrix excerpt — product cluster with sub-clusters

117


Those products belonging to the same sub-cluster have a high similarity, resulting ina very low changeover output, when a changeover between them occurs. Products be-longing to a cluster are also likely to have a high similarity with each other, but withsome changeover combinations generating a higher changeover production or being notpossible at all. When switching the production system configuration to a new product, itis desirable to stay in this configuration, until at least a certain minimal amount of thatproduct has been produced. The same applies to clusters and sub-clusters of products.If a switch to a product of a new cluster or sub-cluster occurs, at least a certain minimalamount has to be produced before switching to products of another cluster or sub-cluster,respectively.

When developing and modifying the production schedule for the production systemdiscussed in this case study, the occurring changeover times and off-spec material out-put, as well as inventory holding costs, have to be taken into account. However, thedynamic nature of the company environment leads to frequently required adjustmentsof production schedules. Changes in lot starting times and lot production sizes to al-ready scheduled production lots induce renewed coordination and planning efforts andassociated costs. Therefor, when modifying the production schedule, minimal changes toalready planned production activities are desired as well.

5.2. Literature

The planning problem of this case study, as described in section 5.1, can be character-ized as an integrated lot sizing and scheduling of products having a natural order, withsequence dependent and limited product changeovers, as well as further characteristicsdescribed in 5.1. Despite originating from a different industry, the planning problem ofthis case exhibits many similarities to the case study discussed in chapter 4, albeit withseveral specific characteristics. The literature overview presented in 4.2 is also relevantto the case study discussed in this chapter. Specifically, Allahverdi et al. (2008) includean overview of scheduling problems with sequence-dependent setups while Lütke Entrupet al. (2005) consider alternative block sequences in their block planning application.Günther (2009) presents a block planning application for the chemical industry andKallrath (2002) presents an overview of production planning and scheduling research forthe chemical process industry. Additionally, a review paper, specifically concerned withlot sizing and scheduling with sequence dependent setups, has been presented by Zhuand Wilhelm (2006). This case study can be modeled by adopting the block planningapproach. Due to the similarity of the planning problem of this case study to the casestudy discussed in chapter 5.1 the scheduling model and simulation model presented in4.3.2 and 4.4 can be adapted and expanded to encompass the planning problem studiedin this chapter.

118


5.3. Model formulations

In this section a scheduling model for the planning problem described in 5.1 is presented.The mixed-integer linear programming (MILP) model is based on the scheduling modelpresented in 4.3.2. Alterations to that model include the consideration of productionlots as contributing to the production output of specific products instead of productionsub-lots. In addition, sequence-dependent changeover times and corresponding costs areintroduced, as well as the characteristic that certain product changeover combinationsare not viable. Production lots with similar characteristics are grouped into sub-clustersand clusters, respectively. Accordingly, minimal production output amounts are definedper cluster and sub-cluster.First, the main scheduling model, used in the numerical experiments of this case study,

is presented in 5.3.1. Then, in 5.3.4, two extensions are developed. The scheduling modelis used for each scheduling iteration of a simulation run in the numerical study. Thesimulation model is similar to the model discussed in 4.4 and is presented in section 5.4.Scheduling as well as the simulation model can again be parameterized to implementdifferent scheduling strategies. Note that, in order to provide a lucid presentation ofthe scheduling model, some decision variables and constraints are presented which arenot essential and may be omitted. This is stated in the respective positions in themodel definition. A compact version of the model can be found in 5.3.3. The detailedmodel in 5.3.1 is also presented with optional constraints (e.g. for the fixation of scheduleelements) and a generic objective function which includes objectives for the minimizationof changeover and inventory holding costs as consequence of the production schedule onone hand and schedule variations and associated efforts and costs on the other hand. Forreasons of simplicity these two types of costs are again denoted as “production costs”and “schedule variation costs” in the remainder of this chapter. It follows a presentationof the model objectives, which are used in the numerical experiments as elements of theobjective function, in 5.3.2. Specific objective functions are determined by the schedulingstrategy selected in each simulation run. The number of studied scheduling strategies,each aiming at individual planning goals, are described in the experimental design in 5.4.The scheduling strategies utilize different objective functions in order to pursue specificplanning goals.

5.3.1. Scheduling model

In this sub-section, the scheduling model used in the numerical study is presented. Inthis model it is assumed that lots are produced without interruption within a produc-tion cycle, while production cycles themselves do not need to run directly one after eachother without interruptions. It is furthermore assumed that the production system isrunning with a constant production speed and that production cycles do not use theinverses of the predefined cycle sequences. Extensions to this basic model are developedin sub-section 5.3.4. The model utilizes a mixed continuous-discrete time representationas discussed in sub-section 4.3.1 and contains the following symbols. Furthermore notethat the index label “cost” is used to denote production cost related symbols while the

119


index label “var” is used to denote schedule variation cost related symbols.

Indices and index setspεP ProductslεL Chemical production facilitiestεT Consecutive number of production cycles (of all facilities)t The first cycle of each production facilityiεI Consecutive number of production lots of all facilities

(e.g. lots 1,2,3 belong to cycle 1 of facility 1, lots 4,5 to cycle 1 of facility 2, ...)iεIlt Production lots to be scheduled in cycle t of facility lilt First lot to be scheduled in cycle t of facility lilt Last lot to be scheduled in cycle t of facility liεIp Production lots producing product piεI Set containing the first production lot of each cycle of all production facilitiesiεIvar Set containing lots for which schedule variation is measurediεIfixLs Lots with fixed sizeiεIfixSt Lots with fixed starting timeiεIfixLe Lots with fixed end timeiεIfixC Fixed lots which may be changed nevertheless, if necessaryl(i) Facility l which lot i belongs tot(i) Cycle t in which lot i is scheduledrεRcll Product clusters in facility lsεRscl Product sub-clusters in facility lsεRsclr Product sub-cluster of cluster r in facility liεIltr Production lots grouped into cluster r in facility l in cycle tiεIlts Production lots grouped into sub-cluster s in facility l in cycle tuεU Consecutive number of planning periods (u ≥ 0 ∀uεU)uεUi Time window of planning periods for the completion of lot iu(i) The first planning period of time window Uiu The first planning periodu The last planning period

120


ParametersM i Maximum size of lot iM i Minimum size of lot iN cllr Minimum production size in cluster r in facility l

N scls Minimum production size in sub-cluster s in facility l

alt Earliest start time of cycle t on facility lalt Latest end time of cycle t on facility lSl Startup off-spec material amount of a cycle in facility lCij Off-spec material amount for a changeover from lot j to iCmax Maximum off-spec material amountbl Production time per quantity unit in facility ldpu Cumulated demand of all orders of product p in planning period uhp Initial inventory level of product pf lsi Size of fixed lot ifsti Starting time of fixed lot if lei End time of fixed lot iwcost Weight of production (changeover & inventory holding) cost objectivewvar Weight of schedule variation cost objectivewunsat Penalty costs for unsatisfied demandwfixS Penalty costs for size changes of fixed lotswfixT Penalty costs for time changes of fixed lotscCO Changeover quantity unit costscInvp Inventory holding costs of product pgcost Maximum allowed total costsgcost =1, if gcost is used; 0, otherwisegvar Maximum allowed total schedule variation costsgvar =1, if gvar is set; 0, otherwisegunsat =1, if unsatisfied demand is allowed; 0, otherwise

121


Decision variables and domainsσltε{0, 1} =1, if and only if cycle t is produced in facility lρiε{0, 1} =1, if and only if lot i is producedκclltrε{0, 1} =1, if and only if product cluster r is produced in cycle t in facility lκscltsε{0, 1} =1, if and only if product sub-cluster s is produced in cycle t in facility lχiεR+

0 Production size of lot iαltεR+

0 Starting time of cycle t in facility lδltεR+

0 Duration of cycle t in facility lξiεR+

0 Starting time of lot iηiεR+

0 Duration of lot iτiεR+

0 Changeover time of lot iωiεR+

0 End time of lot iφiuε{0, 1} =1, if and only if lot i has been finished up to planning period uµiuεR+

0 Production output of lot i in planning period uγpuεR+

0 Inventory level of product p at the end of planning period uυDpuεR+

0 Unsatisfied demand of product p in planning period uυfixSi εR+

0 Size change of fixed lot iυfixTi εR+

0 Time change of fixed lot iβcostεR+

0 Total production (changeover and inventory holding) costsβvarεR+

0 Total schedule variation costsβunsatεR+

0 Total unsatisfied demandβfixSεR+

0 Total size changes of fixed lotsβfixT εR+

0 Total time changes of fixed lots

ConstraintsThe model contains the following constraints.

Production of cycles and lots∑iεIlt


σlt ≤∑iεIlt

ρi ∀lεL, tεT (5.2)

A production lot i may only be produced if the cycle t in facility l, which it belongs to,is being produced. Constraint (5.2) is optional and only has to be included if a schedulesolution is only to be regarded as valid if a cycle strictly should not be started in a facilityunless at least one of its lots iεIlt is to be produced.

Production lot sizes

ρi ·M i ≤ χi ≤ ρi ·M i ∀iεI (5.3)

122


If a lot is not produced its size χi is enforced to 0. Otherwise, χi is bounded by itsupper limit M i and lower limit M i, respectively.

Product changeover

Cij · bl(i) ·

ρj −∑kεI:

j<k<i

ρk − 1 + ρi

≤ τi ∀iεI \ I, jεIl(i)t(i) : j < i (5.4)

τi ≤ Cij · bl(i) ·

ρj +∑kεI:

j<k<i

ρk + 1− ρi

∀iεI \ I, jεIl(i)t(i) : j < i (5.5)

τi ≤ ρi · Cmax · bl(i) ∀iεI \ I, τi = 0∀iεI (5.6)

The changeover time τi of a lot is determined by the off-spec material amount in-duced by the product changeover from the previously produced lot within the corre-sponding cycle as well as the production time per quantity unit of the correspondingfacility. Constraints (5.4) and (5.5) determine the previously produced lot and resultingchangeover time. Constraint (5.5) is optional and only has to be included if strictly nolarger changeover sizes than Cij are permitted in valid schedule solutions. Constraint(5.6) ensures that the changeover time is enforced to 0 if the corresponding lot is notproduced.

ρi + ρj ≤ 1 +∑kεI:

j<k<i

ρk ∀iεI \ I, jεIl(i)t(i) : j < i (5.7)

Lots between which no changeover is possible are only allowed to be produced withinthe same cycle, if there is at least one other lot produced in between. Alternatively,constraint (5.7) could be excluded, if instead large enough values for Cij are chosen in(5.4), prohibiting this constraint from being satisfied if both lots were produced withnone in between.

123


Product clusters & sub-clusters∑sεRsclr

κsclts ≤ κclltr · |Rsclr | ∀lεL, tεT, rεRcll (5.8)

A product cluster r is considered as produced (κltr = 1) if at least one of its sub-clusterss is produced (κlts = 1) in the respective facility and production cycle.

∑iεIltr

χi ≥ κclltr ·N cllr ∀lεL, tεT, rεRcll (5.9)

If a product cluster is produced, meaning at least one of the products grouped intothe cluster is produced, then at least a certain minimal production amount has to beproduced in that product cluster in total.

∑iεIlts

ρi ≤ κsclts · |Ilts| ∀lεL, tεT, sεRscl (5.10)

A product sub-cluster s is considered as produced (κs = 1), if at least one of itsproducts is produced in the respective facility and production cycle.

∑iεIlts

χi ≥ κsclts ·N scls ∀lεL, tεT, sεRscl (5.11)

If a product sub-cluster is produced, meaning at least one of the products groupedinto the sub-cluster is produced, then at least a certain minimal production amount hasto be produced in that sub-cluster in total.

Timing of cycles and lotsThe production is assumed to run continuously within a production cycle.

ηi = τi + χi · bl(i) ∀iεI (5.12)

The duration ηi of a lot is determined by its changeover time τi and its productiontime χi · bi. Note that decision variable ηi is not essential.

δlt = σlt · Sl +∑iεIlt

ηi ∀lεL, tεT (5.13)

The duration δlt of a cycle is determined by its startup changeover time and theduration of its lots. Note that decision variable δlt is not essential.

124


alt ≤ αlt ≤ alt − δlt ∀lεL, tεT (5.14)

αlt−1 + δlt−1 ≤ αlt ∀lεL, tεT \ {t} (5.15)

A cycle is not allowed to be started in a facility before its earliest possible start timealt and before its predecessor has been finished. A cycle has to be finished before itslatest possible end time alt.

ωi = ωi−1 + ηi ∀lεL, tεT, iεIlt, ωilt−1 = αlt (5.16)

The end time ωi of a production lot is determined by the end time of its predecessor andits own duration. If no predecessor exists, meaning it is the first lot to be scheduled withina cycle on a facility, the end time is determined by the start time of the correspondingcycle and the lot duration.

ξi = ωi − ηi ∀iεI (5.17)

Constraint (5.17) calculates the starting times of production lots. It is not essential.

Production outputu− ωiu



Constraint (5.18) forces the “lot finished”-status φiu to 0 for periods prior to the com-pletion and to 1 for periods during or after the completion time of the lot. Note that φiuare so-called heaviside variables (cf. Blömer and Günther (2000)).

µiu ≤ (φiu − φiu−1) ·M i ∀iεI, uεUi, φiu(i)−1 = 0 (5.19)

∑uεU\Ui

µiu ≤ 0 ∀iεI (5.20)

Constraints (5.19) and (5.20) ensure that a production output µiu of a lot in a periodcan only be greater than 0 if the lot has been finished in that particular period. Theproduction output is forced to 0 for all other periods.

∑uεUi

µiu =χi ∀iεI (5.21)

The size of a production lot is equal to its production output. Thus, χi is not essentialand may be substituted by

∑uεUi

µiu.

125


Inventory

γpu =γpu−1 +∑iεIp

µiu − dpu + υDpu ∀pεP, uεU, γpu = hp (5.22)

The product inventory level γpu at the end of a micro-period is determined by theinventory level of the previous micro-period, the production output of lots producing theproduct p and the external demand dpu to be satisfied. Optionally, the decision variablefor unsatisfied demand υpu ensures the feasibility of the model, even if the demandcannot be completely satisfied. Note again that this formulation of unsatisfied demandonly focuses on feasibility. If a more sophisticated expression of delayed or incompletedemand satisfaction is desired, the model may be extended to encompass this.

Fixed lots

χi = f lsi ∀iεIfixLs \ IfixC (5.23)

χi ≥ f lsi − υfixSi ∀iεIfixLs ∩ IfixC (5.24)

χi ≤ f lsi + υfixSi ∀iεIfixLs ∩ IfixC (5.25)

ξi = fsti ∀iεIfixSt \ IfixC (5.26)

ξi ≥ fsti − υfixTi ∀iεIfixSt ∩ IfixC (5.27)

ξi ≤ fsti + υfixTi ∀iεIfixSt ∩ IfixC (5.28)

ωi = f lei ∀iεIfixLe \ IfixC (5.29)

ωi ≥ f lei − υfixTi ∀iεIfixLe ∩ IfixC (5.30)

ωi ≤ f lei + υfixTi ∀iεIfixLe ∩ IfixC (5.31)

Constraints (5.23) to (5.31) allow for a fixation of lot production sizes and times, e.g. tomodel lots which are already running, have been finished at the time of the first planningperiods or in order to preclude schedule variations for specific sets of lots. Lot times aswell as lot sizes are forced to the values fsti , f lei and f lsi , respectively. Lots belongingto the set IfixC are allowed to deviate from fixed values (albeit with additional penaltycosts υfixTi ·wfixT and υfixSj ·wfixS , respectively), which may e.g. be used to ensure thefeasibility of the model without increase of unsatisfied demand.

Goal elements

βcost =∆cost (5.32)

e.g. βcost =∑lεL

∑tεT

(cCO · Sl · σlt) +∑iεI

cCO · τibl(i)

+∑pεP

∑uεU

cInvp · γpu

126


βcost · gcost ≤ gcost (5.33)

∆cost represents an expression calculating an efficiency measure which is used as goalelement βcost. (5.32) shows an example in which the efficiency measure consists of thetotal changeover costs of all lots as well as startup off-spec material costs of cycles andinventory holding costs of products. Constraint (5.33) is optional and allows for thedefinition of a maximum value gcost for this cost goal element if parameter gcostε{0, 1} isset to 1. This is constraint is applied in the two-step strategies, evaluated in 5.5.

βvar =∆var (5.34)

e.g. βvar =∑iεIvar

|χi − qi| · wvari (5.35)

βvar · gvar ≤ gvar (5.36)

∆var represents an expression calculating a schedule variation cost measure which isused as goal element βvar. (5.35) shows an example in which the variation cost measureis calculated as the sum of absolute values of differences between the sizes of productionlots iεIvar and parameters qi representing expected lot sizes (and penalty costs of 1), asdetermined from the original schedule. wvari is a penalty cost parameter. Note that useof the absolute value function is for ease of presentation only and that the expressioncan be linearized easily. Constraint (5.36) is optional and allows for the definition of amaximum value gvar for the schedule variation goal element if parameter gvarε{0, 1} isset to 1.

βunsat =∑pεP

∑uεU

υpu (5.37)

βunsat ≤ gunsat ·∑pεP

∑uεU

dpu (5.38)

The total unsatisfied demand βunsat is used as a goal element if parameter gunsatε{0, 1}is set to 1.

βfixT =∑

iεIfixC

υfixTi (5.39)

βfixS =∑

iεIfixC

υfixSi (5.40)

βfixT and βfixS are calculated as the deviation of fixed lot starting and end times andsub-lot sizes for lots and sub-lots for which such a deviation is allowed.Note again that βcost, βvar, βunsat , βfixT and βfixS are not essential.

127


Objective function

min[wcost · βcost + wvar · βvar + wunsat · βunsat + wfixT · βfixT + wfixS · βfixS ] (5.41)

The objective function consists of the previously described goal elements βcost, βvar,βunsat , βfixT and βfixS with penalty costs wunsat, wfixT and wfixS respectively. Addi-tional weights wcost and wvar on the production and schedule variation cost objectivesβcost and βvar are included as well and allow for a balance definition of these objectives.

Model parameterizationDepending on the definition of the objective function (as well as chosen sets of fixed

lots) the described scheduling model shows different solution characteristics. This isexploited e.g. in the numerical studies for this case study (cf. 5.4 and 5.5) in orderto implement different scheduling strategies. βvar = 0 defines e.g. efficiency-focusedstrategies. The additional definition of a goal element βvar or the fixation of sets of lotsadds schedule variation considerations, while βcost = 0 defines strategies which considerno efficiency measures at all (though this may not be beneficial). If schedule variationreduction is to be superior to plan-efficiency then wcost · βcost � wvar · βvar should beparameterized appropriately.The main purpose of the unsatisfied demand goal element is the assurance of model

feasibility even if not all demand can be satisfied. If a total demand satisfaction is strictlyrequired though, the parameter βunsat must be set to 0. If, on the other hand, appropri-ate resulting costs of unsatisfied demand quantities can be estimated, the correspondingpenalty cost parameter wunsat may be set to this value (and βunsat to 1). If maximumdemand satisfaction is to be realized but the model to remain feasible, even with disad-vantageous demand data, βunsat must be set to 1, while wcost · βcost � wunsat · βunsatand wvar · βvar � wunsat · βunsat are set appropriately, such that demand satisfaction isregarded as the superior goal.While the fixation of lots might ensure lower schedule variations, these constraints also

endanger the feasibility of the model (or result in unsatisfied demand, respectively). Forthis reason fixed lots belonging to the set IfixC are allowed to deviate from these fixedvalues. With wfixT · βfixT + wfixS · βfixS corresponding penalty costs are calculated.If IfixC is used, it is reasonable to parameterize the model, such that wcost · βcost �wfixT · βfixT , wvar · βvar � wfixT · βfixT , wcost · βcost � wfixS · βfixS , wvar · βvar �wfixS ·βfixS wcost ·βcost � wfixS ·βfixS , wfixT ·βfixT � wunsat ·βunsat and wfixS ·βfixS �wunsat · βunsat is achieved.As a guidance, table 5.1 again shows general model parameterization examples for a

number of general planning goals:

1. Production cost minimization, minimal unsatisfied demand, partial fixation of lotsizes

2. Production cost minimization, with fixation of early lots as well as minimal changesto fixed values

128


3. Production and schedule variation cost minimization, with a chosen balance of bothobjectives

4. Production and schedule variation cost minimization, with a chosen balance of bothobjectives as well as lot start fixations with allowed changes

5. Prevalent schedule variation cost minimization, production cost minimization assecondary objective

6. Prevalent schedule variation cost minimization, with upper bound on productioncosts

5.3.2. Schedule efficiency & variation objectives

In this sub-section the production and schedule variation cost objectives used in thenumerical experiments of this case study, as goal elements of the objective function, arepresented. The production costs βcost are always calculated from the incurred changeoverand inventory holding costs of finished products:

βcost =∑lεL

∑tεT

(cCO · Sl · σlt · wcostt ) +∑iεI

cCO · τibl(i)· wcosti +

∑pεP

∑uεU

cInvp · γpu · wcosti

(5.42)

The weights wcostt , wcosti and wcosti are set to a value of 1 in the numerical study exper-iments, but generally may be set to other values (e.g. to put an emphasis on specificplanning periods and lots). The main production cost weight wcost is set to 1 as well.In the numerical experiments the relation between the production cost objective andschedule variation cost objective is adjusted by setting the schedule variation cost weightwvar. Only if no schedule variation is to be considered in the objective function is βvar

set to 0:

βvar = 0 (5.43)

In all other cases βvar is set to the schedule variation objective to be used as goal elementof the objective function (while βcost is always set to the expression shown in (5.42)).The different implemented schedule variation objectives used in the numerical study arepresented in the remainder of this sub-section.

βvar = ∆varLSi =

∑iεIvar

|χi − qi| · wvari (5.44)

The expression ∆varLSi calculates lot size variations from the original schedule and may be

129


Goal

βcost

βvar

wcost

wvar

wunsat

wfixT

wfixS

gcost

gvar

gunsat

gcost

gvar

IfixLs

IfixSt

IfixLe

IfixC

1*

01

**0

1*

{}{}

{}2

*0

1**

**0

**

**

3*

*1

*0

04

**

1*

**0

0*

{}{}

*5

**

1**

00

6*

*1

**1

0*

*:Se

tap

prop

riately

**:Se

tto

sufficientlyhigh

valueforthecorrespo

ndingob

jectiveto

bedo

minan

t

Tab

le5.1.:M

odel

parameterizationexam

ples

130


used to minimize variations in planned lot sizes. The penalty cost parameter wvari is setto a value of 1 in the numerical study experiments, but generally may be set (e.g. toother values to put an emphasis on specific lots).

βvar = ∆varLSt =

∑iεIvar

|ξi − qi| · wvari (5.45)

The expression ∆varLSt calculates lot starting time variations from the original schedule

and may be used to minimize variations in planned lot starting times. The penalty costparameter wvari is set to a value of 1 in the numerical study experiments, but generallymay be set to other values (e.g. to put an emphasis on specific lots).

βvar = ∆varLSe =

∑iεIvar

|ρi − qi| · wvari (5.46)

The expression ∆varLSe calculates lot setup variations from the original schedule and may

be used to minimize variations in planned lot setups. Again, the penalty cost parameterwvari is set to a value of 1 in the numerical study experiments, but generally may be setto other values (e.g. to put an emphasis on specific lots).

βvar = ∆varLStSi =

∑iεIvar

|ξi − qSti | · wvarSti +∑iεIvar

|χi − qSii | · wvarSii (5.47)

The expression ∆varLStSi calculates lot starting time as well as size variations and may

be used to simultaneously minimize variations in planned lot starting times and sizes.Again, the penalty cost parameters wvarSti and wvarSii may be set to values other than1 to scale the desired proportion between lot starting time and size and also to put anemphasis on specific lots. In the simulation experiments of this case study the relationof these two schedule variation objective is set to a ratio of ca. 1:1 (as determined inpreliminary experiments).

In section 5.4 the design of the conducted numerical experiments is described, includingthe number of scheduling strategies which are evaluated. While the scheduling modelpresented in 5.3.1 has been implemented and is solved in each scheduling iteration, eachscheduling strategy uses a specific objective function. These objective functions areconstructed as described in 5.3.1 and contain the production cost goal element βcost anda schedule variation cost goal element βvar as presented in this sub-section.

5.3.3. Compact scheduling model

The scheduling model described in sub-section 5.3.1 focused on a lucid presentation, uti-lizing several additional decision variables and constraints. Several optional expressionswere included as well. For reasons of thoroughness, this sub-section shows a compactversion of this model. It encompasses the following constraints.

131


Production of cycles and lots∑iεIlt



ρi ·M i ≤∑uεUi

µiu ≤ ρi ·M i ∀iεI (5.49)

Product changeover

Cij · bl(i) ·

ρj −∑kεI:

j<k<i

ρk − 1 + ρi

≤ τi ∀iεI \ I, jεIl(i)t(i) : j < i (5.50)

Product clusters & sub-clusters∑sεRsclr

κsclts ≤ κclltr · |Rsclr | ∀lεL, tεT, rεRcll (5.51)

∑iεIltr

∑uεUi

µiu ≥ κclltr ·N cllr ∀lεL, tεT, rεRcll (5.52)

∑iεIlts

ρi ≤ κsclts · |Ilts| ∀lεL, tεT, sεRscl (5.53)

∑iεIlts

∑uεUi

µiu ≥ κsclts ·N scls ∀lεL, tεT, sεRscl (5.54)

Timing of cycles and lots

ωi = ωi−1 + τi +∑uεUi

µiu · bl ∀lεL, tεT, iεIlt, ωilt−1 = αlt (5.55)

alt ≤ αlt ∀lεL, tεT (5.56)

ωilt ≤ alt ∀lεL, tεT (5.57)

ωilt−1≤ αlt ∀lεL, tεT \ {t} (5.58)

132


Production output

u− ωiu



µiu ≤ (φiu − φiu−1) ·M i ∀iεI, uεUi, φiu(i)−1 = 0 (5.60)

∑uεU\Ui

µiu ≤ 0 ∀iεI (5.61)

Inventory

γpu =γpu−1 +∑iεIp

µiu − dpu ∀pεP, uεU, γpu−1 = hp (5.62)

5.3.4. Model extensions

In 5.3.1 a scheduling model for the described planning problem of this case study waspresented. In this section two extensions are developed which address the planningproblem in a slightly more detailed way but also increase model complexity by introducingfurther decision variables and constraints, thereby inducing larger problem sizes.

5.3.4.1. Inverse production sequences

The basic model allows only one predefined natural sequence of lots within a produc-tion cycle. The following constraints model the fact that in some facilities lots may bescheduled not only in ascending but also in descending order, giving two possible naturalsequences. This model extension is examined in an experiment presented in 5.3.1. Theextension introduces the following additional symbols.

Additional indices and index setsiεI Set containing the last production lot of each cycle of all production facilitieslεL Set containing the production facilities,

in which production may alternatively run in descending orderAdditional parametersSAl Startup off-spec material amount of a cycle in facility l in ascending lot orderSDl Difference to SAl in startup off-spec material of a cycle in facility l

in descending lot orderAdditional decision variables and domainsλltε{0, 1} =1, if lots of cycle t in facility l are to be scheduled in

ascending order; =0, if in descending order

133


ConstraintsThis extension introduces or changes the following constraints which reflect that two

lot orders are possible.

Product changeover

Cij · bl(i) ·

ρj −∑kεI:

j<k<i

ρk − 1 + ρi

≤ τi ∀iεI \ I : l(i)/∈L, jεIl(i)t(i) : j < i (5.63)

τi ≤ Cij · bl(i) ·

ρj +∑kεI:

j<k<i

ρk + 1− ρi

∀iεI \ I : l(i)/∈L, jεIl(i)t(i) : j < i

(5.64)

τi ≤ ρi · Cmax · bl(i) ∀iεI \ I : l(i)/∈L, τi = 0∀iεI : l(i)/∈L (5.65)

−

i−1∑k=j+1

ρk + 2− ρi − λl(i)t(i)

≤ τiCij · bl(i)

− ρj ≤

i−1∑k = j + 1

ρk + 2− ρi − λl(i)t(i)

∀iεI \ I : l(i)εL, jεIl(i)t(i) : j < i (5.66)

−

j−1∑k = i+ 1

ρk + 1− ρi + λl(i)t(i)

≤ τiCij · bl(i)

− ρj ≤

j−1∑k = i+ 1

ρk + 1− ρi + λl(i)t(i)

∀iεI \ I : l(i)εL, jεIl(i)t(i) : i < j (5.67)

τi ≤ (1− λl(i)t(i)) · Cmax · bl(i) ∀iεI : l(i)εL (5.68)

134


τi ≤ λl(i)t(i) · Cmax · bl(i) ∀iεI : l(i)εL (5.69)

The constraints (5.4) to (5.6) of the basic model are replaced by the above constraints.For production facilities, which can run production in descending order, constraints (5.66)and (5.67) determine the previously produced lot and resulting changeover time, bothin dependence on the chosen scheduling order λl(i)t(i) of lots. Note again that (5.68) to(5.69) as well as the right hand side of (5.66) and (5.67) only have to be included ifstrictly no larger changeover sizes than Cij are permitted in valid schedule solutions.

ρi + ρj ≤ 1 +∑kεI :

j < k < i

ρk ∀iεI \ I : l(i)/∈L, jεIl(i)t(i) : j < i (5.70)

ρi + ρj ≤ 2 +∑kεI :

j < k < i

ρk − λl(i)t(i) ∀iεI \ I : l(i)εL, jεIl(i)t(i) : j < i (5.71)

ρi + ρj ≤ 1 +∑kεI :

i < k < j

ρk + λl(i)t(i) ∀iεI \ I : l(i)εL, jεIl(i)t(i) : i < j (5.72)

The constraint (5.7) of the basic model is replaced by the above constraints. Lotsbetween which no changeover is possible are only allowed to be produced in the samecycle if there is at least one other lot produced in between.

Timing of cycles and lots

ωi = ωi−1 + ηi ∀lεL \ L, tεT, iεIlt, ωilt−1 = αlt (5.73)

ωi−1 + ηi − (1− λlt) · u ≤ ωi ≤ ωi−1 + ηi + (1− λlt) · u ∀lεL, tεT, iεIlt, ωilt = αlt(5.74)

ωi+1 + ηi − λlt · u ≤ ωi ≤ ωi+1 + ηi + λlt · u ∀lεL, tεT, iεIlt, ωilt = αlt (5.75)

The constraint (5.16) of the basic model is replaced by the above constraints, whichcalculate the end time of production lots.

135


Goal elements

σlt ≥ 1− λlt ∀lεL (5.76)

βcost =cCO ·

∑lεL

∑tεT

SAl · σlt +∑iεIlt

τibl

+∑lεL

∑tεT

SDl · (1− λlt)

+∑pεP

∑uεU

cInvp · γpu

(5.77)

The exemplary expression ∆cost for goal element βcost now consists of the total changeoverquantity costs of all lots as well as setup quantity costs of cycles and inventory holdingcosts of products. The startup off-spec material output of production cycles depends onthe lot order. SDl is the difference in produced off-spec material if the cycle is producedin descending order.

5.3.4.2. Variable production speed

A second extension to the basic model reflects that in some of the production facilities,production usually runs continuously. It should not be stopped after finishing one pro-duction cycle and started again at a later time for the next cycle. Instead of suspendingthe production it is possible to lower the production speed. The basic model implicitlyassumed that the production speed could be slowed down arbitrarily by modeling thesuspension of the production system between production cycles. If instead the actualproduction speed may not be lowered beneath a certain minimum, this fact can be mod-eled by the following extensions to the basic model. In contrast to the basic model, inthis extension the startup off-spec material output of production cycles is not assumedas being constant, but depends on the last produced lot of the previously produced cycle.Note that the first extension is included as well.

Additional indices and index setsi0l Last lot produced in facility l before current first lot iltAdditional parametersbl Minimum fraction by which the production speed in facility l

can be slowed downAdditional decision variables and domainsζltiε{0, 1} =1, if and only if lot i is the last lot produced in cycle t in facility l

Constraints

Production output∑uεUi

µiu ≤ χi ∀iεI (5.78)

136


χi · bl ≤∑uεUi

µiu ∀iεI (5.79)

Constraint (5.21) of the basic model is replaced by the above constraints. The size ofa lot is allowed to be larger than the production output, meaning that the productionspeed is slowed down for this lot. The minimum production speed is defined by bl.


ρi ·M i ≤∑uεUi

µiu ≤ ρi ·M i ∀iεI (5.80)

Instead of restricting the lot size, as in constraint (5.3) of the basic model, which isreplaced by the above constraint,M i andM i now restrict the production output, similarto the compact version of the basic model.

Last lot produced in a cycle∑iεIlt

ζlti = σlt ∀lεL, tεT (5.81)

ρi −ilt∑

j=i+1

ρj ≤ ζlti ∀lεL \ L, tεT, iεIlt (5.82)

ρi −ilt∑

j=i+1

ρj − 1 + λlt ≤ ζlti ∀lεL, tεT, iεIlt (5.83)

ρi −i−1∑j=ilt

ρj − λlt ≤ ζlti ∀lεL, tεT, iεIlt (5.84)

If a cycle is produced, there exists one lot which is the last to be produced in thiscycle. A lot is the last one to be produced, meaning ζlti is forced to 1, if no successor lot(defined in dependence on the lot order λlt) is set up.

Product changeover

Cij · bl(i) ·

∑jεIls

ζl(i)sj −t−1∑

r = s+ 1

σlr −i−1∑j=ilt

ρj − 1 + ρi

≤ τi∀lεL \ L, tεT, iεIlt, sεT : s < t (5.85)

137


τi ≤Cij · bl(i) ·

∑jεIls

ζl(i)sj +

t−1∑r = s+ 1

σlr +

i−1∑j=ilt

ρj + 1− ρi

∀lεL \ L, tεT, iεIlt, sεT : s < t (5.86)

−

t−1∑r = s+ 1

σlr +i−1∑j=ilt

ρj + 2− ρi − λlt

≤ τiCij · bl

−∑jεIls

ζlsj ≤

t−1∑r = s+ 1

σlr +i−1∑j=ilt

ρj + 2− ρi − λlt

∀lεL, tεT, iεIlt, sεT : s < t (5.87)

−

t−1∑r = s+ 1

σlr +

ilt∑j=i+1

ρj + 1− ρi + λlt

≤ τiCij · bl

−∑jεIls

ζlsj ≤

t−1∑r = s+ 1

σlr +

ilt∑j=i+1

ρj + 1− ρi + λlt

∀lεL, tεT, iεIlt, sεT : s < t

(5.88)

Constraints (5.4) and (5.5) of the basic scheduling model and (5.63) to (5.69) of thefirst model extension, respectively, are complemented by the above constraints. If a lot isthe first one being produced in a cycle within a facility, its changeover time is calculatedby the above constraints from the last produced lot of the last set up predecessor cycle.Note again that (5.86) as well as the right hand sides of (5.87) and (5.88) only have tobe included if strictly no larger changeover sizes than Cij are permitted in valid schedulesolutions.

While the second extension models the planning problem of the case study in a slightlymore realistic way for some production facilities, the complexity of the model is alsosignificantly increased by the introduction of these additional decision variables and con-straints. It is described here in order to provide a thorough presentation but is not usedin the numerical experiments discussed in 5.5.

5.4. Experimental design

This sub-section describes the experimental design of the numerical studies which arepresented in the following section. In order to execute the simulation experiments, the

138


��

� ��

� ��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

��

! ��

��

Figure 5.3.: EPPSF-Planner - chemical commodity case study

generic evolutionary production planning simulation framework (cf. 3.16 and 4.4) andthe scheduling model described in section 5.3.3 were implemented. In each simulationrun, if the planning time or demand information has changed, the EPPSF-Planner com-ponent — extended as suited to this case study (cf. figure 5.3) — decides on the startof a production scheduling iteration by executing an event-based or hybrid schedulingpolicy. If a schedule adjustment is required the revised schedule is calculated by one ofseveral scheduling strategy modules. The scheduling policy and strategy, to be used in asimulation run, are defined by corresponding simulation system parameters. While thespecific objectives vary in dependence on the scheduling strategy applied, each strategyuses and parameterizes the scheduling model, developed in 5.3.3 (implemented in IBMCplex Studio in OPL syntax). Also confer 4.4 for further descriptions of the simulationsystem and used computing equipment.The specific simulation parameters and data, concerning the simulation experiments

for this case study, are summarized in the following.

• Production system: The structure and data of the production system being mod-eled in the simulation experiments, and used to parameterize the scheduling model,were obtained and abstracted from actual data of the company from which this caseoriginated (the presented data is also normalized). The production system, mod-eled in the simulation experiments, consists of one production facility producinga set of 12 chemical commodity products grouped into 3 product clusters and 6sub-clusters (2 products per sub-cluster and 2 sub-clusters per cluster). Table 5.2shows further parameters of the modeled production system (time designations arenormalized to one planning period). Table 5.3 shows the resulting off-spec material

139


Production Facility (1):Production time per quantity unit 0.0028Cycle startup time 0.096Product changeover amount 0 to 180(cf. table 5.3) (or “-” if changeover not allowed)Changeover cost per quantity unit 1Cluster min. production size 30Sub-cluster min. production size 20

Products (11):Initial inventory: 0 (for all products)Inventory holding cost 0.1

Table 5.2.: Production system parameters

amounts for product changeovers. These were generated based on actual data andby application of uniform distributions.

• Simulation time: The simulations runs and generated demand data sets encompasstime periods of 180 planning periods. If assuming a planning period of e.g. one daythis accounts to a time period of 36 five-day weeks or ca. nine month. Productioncycles are allowed to start eight planning periods prior to their corresponding macroperiod. Macro periods have a length of five planning periods. Each simulationiteration schedules a number of plannable production cycles equal to the numberof affected macro periods. Between 15 and 40 planning periods are considered insimulation experiments. The set planning horizon remains fixed during a simulationrun. The standard number of planning periods is 30.

• Demand: The demand data used in the simulation experiments was again generatedsuited to the case study production system data using normal distributions for thegeneration of order amounts and uniform distributions for the determination of duedates as well as order cancellations. This is similar to the demand generation forthe first case study (cf. 4.4). Required parameters include the number of microand macro periods, the number of products, the average order size and the averagedemand level per macro period. Average order size and demand level vary and arelisted for each numerical experiment presented in section 5.5. Information aboutdemand orders or order modifications is sent to the planning system as a numberof individual events. The scheduling model presented in sub-section 5.3.3, whichis used for the creation of production schedules, considered not individual ordersbut the accumulated demand amount for each planning period and product. Thus,new orders as well as positive order modifications increase the demanded orderamount for a specific product and planning period while order cancellations andnegative order modifications reduce the demanded order amount. For simplicity,

140


From To Amount From To Amount From To Amount From To Amount

1 2 0 4 8 70 2 1 0 9 3 60

1 3 10 4 9 80 3 2 0 9 2 60

1 4 30 4 10 80 3 1 20 9 1 80

1 5 30 4 11 120 4 3 10 10 9 50

1 6 40 4 12 130 4 2 20 10 8 60

1 7 50 5 6 0 4 1 20 10 7 -

1 8 70 5 7 0 5 4 30 10 6 80

1 9 80 5 8 10 5 3 30 10 5 110

1 10 100 5 9 20 5 2 - 10 4 120

1 11 150 5 10 90 5 1 0 10 3 160

1 12 180 5 11 90 6 5 10 10 2 180

2 3 0 5 12 100 6 4 30 10 1 -

2 4 10 6 7 10 6 3 30 11 10 0

2 5 30 6 8 20 6 2 40 11 9 40

2 6 30 6 9 30 6 1 40 11 8 50

2 7 - 6 10 50 7 6 0 11 7 80

2 8 70 6 11 70 7 5 0 11 6 90

2 9 80 6 12 80 7 4 40 11 5 90

2 10 100 7 8 10 7 3 60 11 4 -

2 11 150 7 9 30 7 2 80 11 3 150

2 12 170 7 10 50 7 1 100 11 2 160

3 4 0 7 11 - 8 7 - 11 1 180

3 5 20 7 12 120 8 6 10 12 11 30

3 6 30 8 9 0 8 5 10 12 10 40

3 7 50 8 10 10 8 4 50 12 9 60

3 8 70 8 11 30 8 3 60 12 8 90

3 9 90 8 12 30 8 2 80 12 7 90

3 10 110 9 10 0 8 1 110 12 6 100

3 11 - 9 11 20 9 8 10 12 5 -

3 12 180 9 12 30 9 7 30 12 4 110

4 5 10 10 11 10 9 6 30 12 3 130

4 6 20 10 12 0 9 5 40 12 2 170

4 7 40 11 12 40 9 4 50 12 1 180

Table 5.3.: Production system parameters — Product changeover

141


Generation of demand orders:Parameters: Set to:

M Last macro period 36N Number of micro periods per macro period 5D Average demand amount of an order *

(demand granularity)L Target demand level **

(targeted total demand amount per macro period)P Set of products which may be ordered {1..12}

*: defaults to 20% of the per planning period available capacity**: defaults to 45% (base demand level) and 20% (demand change level) of available capacitythese are varied in certain experiments (cf. section 5.5 for further details)

Figure 5.4.: Generation of demand orders

in the numerical studies, which are presented in 5.5, demand increases of a specificproduct are modeled by new orders while demand decreases are modeled by ordercancellations. Individual demand information is defined by a due planning period,a product type, a demand quantity, a demand type (new order / order cancellation)and a date for when it becomes known to the planning system and is plannable(which is set as a simulation parameter to allow for a systematic study in respectiveexperiments). Demand data of a simulation run consists of a base demand level ofnew orders known as long as the set planning horizon as well as short-term changes(new orders or cancellations) known for a shorter time period before the due date(as parameterized). Demand data sets of simulation runs are pre-generated inorder to allow for individual simulation runs having the same demand data whencomparing different scheduling strategies. The demand data generation procedureswhich are described in figures 4.4 and 4.5 in conjunction with the first case studyalso apply for this second case study. Figures 5.4 and 5.5 list the parameter settingsused in the numerical studies of this second case study (if these differ for individualexperiments, this is again denoted with “*” or “**” and separately stated at thediscussion of the experiments). Note that the generation of new orders starts withthe 6th planning period in order to allow for full demand satisfaction with initialproduct inventories of 0.

• Scheduling policies: Information about demand orders or cancellations is sent tothe planning system as a number of individual events. The decision of the executionof planning processes is obtained by the scheduling policy selected for a simulationrun. Two scheduling policies have been applied in the numerical studies, presentedin 5.5, an event-based and a hybrid scheduling policy. The implemented event-based scheduling policy triggers a scheduling iteration whenever the known demandinformation changes, e.g. when a new order arrives. The implemented hybridscheduling policy triggers scheduling iterations in a periodical way if a set time

142


Generation of order cancellations:Parameters: Set to:

O Set of demand orders of a simulation run as generatedC Probability (0 to 1) of an order being cancelled *

*: defaults to 0.2 but is varied in certain experiments(cf. section 5.5 for further details)

Figure 5.5.: Generation of order cancellations

interval (of one planning period) is reached and also if short-term changes to thedemand information occur (due to new orders or demand cancellations). The setscheduling policy remains fixed during a simulation run.

• Scheduling method and strategies: In the simulation experiments, the schedul-ing model, developed in 5.3.1, is applied and parameterized by various schedulingstrategies in order to calculate schedule adjustments. Furthermore, the first modelextension is implemented as well and applied in 5.5.3.5 to study its impact on thesimulation results in comparison to the basic model. Several different schedulingstrategies are applied and evaluated, including a strategy which focuses on a mini-mization of production costs and various scheduling strategies considering schedulevariations (implicitly or explicitly). The strategy which is used in a simulation rundetermines the objective function of the scheduling model presented in 5.3.2. Thegoal element βcost is always used as described in 5.3.2 while the goal element βvar

and applied weights (or penalty costs, respectively) differ in dependence on thespecific strategy which is examined. The following types of strategies are studiedin the numerical experiments:

1. Strategies with production cost minimization focus — one strategy of this typeis studied. It applies a βvar = 0 and is denoted as “Cost” in the following.

2. Strategies with schedule variation and production cost minimization focus —strategies using four different objectives (∆var

LSt, ∆varLSi, ∆var

LStSi, ∆varLSe, cf. 5.3.2)

as βvar are studied. Different weight proportions are examined. These strate-gies are denoted as “LStCost”, “LSiCost”, “LStSiCost” and “LSeCost”. Whereappropriate the applied weight proportion is added to the denotation accord-ing to the scheme “[strategy name][weight proportion as schedule variationmeasure:production cost measure)]” (e.g. “LStSiCost1:1”). In the numericalexperiments weight proportions from 1:0,005 over 1:1 to 0,005:1 are studied.

3. Strategies with schedule variation cost minimization focus — strategies usingthe same four objectives (∆var

LSt, ∆varLSi, ∆var

LStSi, ∆varLSe, cf. 5.3.2) as βvar are

studied. βcost is not set to 0. Instead penalty costs are applied such thatwcost · βcost � wvar · βvar holds, meaning that the reduction of respectiveschedule variation measures is pursued as primary objective, while the pro-duction cost minimization objective is only secondary. According to prelimi-nary experiments a weight proportion of 1:0,005 is applied. These strategies

143


correspond to the strategies described in the previous point with a weightproportion of 1:0,005. In order to express the schedule variation focus and forreasons of simplicity these strategies are denoted as “LSt”, “LSi”, “LStSi” and“LSe” (“LSt” e.g. corresponds to “LStCost1:0,005”).

4. Strategies with production cost minimization focus and fixations of scheduleelements — one strategy is studied which fixates elements of the originalschedule for a timeframe of five planning periods. Lots are fixated using theconstraints (5.23) to (5.31) of the scheduling model presented in 5.3.1. Thestrategy is denoted according to scheme “CostFix[number of fixated planningperiods]” in the following, giving “CostFix5”.

5. Strategies with schedule variation cost minimization focus and fixations ofschedule elements — strategies which focus on schedule variations in the ob-jective function and also fixate schedule elements are studied as well. Thesestrategies are based on the previously introduced LSt, LSi and LStSi strate-gies with fixation timeframes of five planning periods. The denotation ofthese strategies is similar to the one of the previous point according to thescheme “[base strategy name]Fix[number of fixated planning periods]”, giving“LStFix5”, “LSiFix5” and“LStSiFix5”, respectively.

6. Two-step strategies with production and schedule variation cost minimiza-tion focus and use of a production cost bound — beside the previously dis-cussed scheduling strategies, two-step strategies which apply a production costbound, are studied as well. These make use of the “Cost” strategy to calcu-late a production cost bound, as described in section 3.1.1. This productioncost bound is then used in conjunction with one of the four schedule variationfocused strategies. In the following, these two-step strategies are denoted,including the name of the applied single-step strategy with schedule variationfocus, according to the scheme “[base strategy name]Cb” (e.g. “LStCb”). Thecost bound itself is calculated by multiplication of the resulting productioncost measure, as determined by use of the Cost strategy, with a “cost boundfactor” parameter, which is set in the simulation system and remains fixedfor a simulation run. The denotation scheme including the cost bound factoris then “[base strategy name]Cb[cost bound factor]”. For example, a strategy“LStCb1.05” calculates the cost bound by multiplication of the productioncost measure, as determined by use of the Cost strategy, with 1.05 and thusallows for a production cost increase of max. 5 % when compared to the Coststrategy. This cost bound is applied as model constraint to the “LSt” strategyin order to generate the adjusted schedule. In the numerical experiments costbound factors of 1,00 to 1,10 are studied.

7. Other — An experiment discussed in 5.5.3.4 limits the number of planningperiods to be included in the calculation of schedule variation measures to asubset of planning periods.

144


Again, in the numerical study experiments penalty costs on unsatisfied demand are setto wcost ·βcost � wunsat ·βunsat and wvar ·βvar � wunsat ·βunsat. Sufficient penalty costswere determined in preliminary experiments.

5.5. Numerical study results

A numerical study surveying the effects of the evolutionary production planning approachon the considered chemical commodity production system was conducted using the sim-ulation framework and experimental design described in section 3.3 and 5.4. For everyindividual scheduling iteration within a simulation run the scheduling model developedin 5.3.1 was applied and parameterized by each of the evaluated scheduling strategies fora determination of necessary changes to the current production schedule. The schedulingstrategy selected for a simulation run determines the objective function of the schedulingmodel which contains production and schedule variation cost objectives. Simulation runswith varying numbers of individual scheduling iterations, depending on the demand dataand scheduling policies, were conducted. The results are presented in this section. Themain results of the numerical study are presented in 5.5.2, while further details as wellas simulation and planning parameters, including demand characteristics, are discussedin 5.5.3.

5.5.1. Preliminary considerations

Exemplary simulation excerpts were presented for the first case study (cf. 4.5.1). Asthese excerpts have an appearance similar to excerpts for this second case study suchexcerpts are not reiterated here. Figure 5.6 shows generated schedule variations for anexemplary simulation run (base demand level of 45% of available production capacity,demand change level of 20%, cancellation probability of 0.2, hybrid policy, 30 planningperiods) using the Cost strategy, though, similar to figure 4.10 of the first case study.It shows that also for this second case study the consideration of schedule variations isimportant, as these occur in significant numbers. Figure 5.7 lists the average solutiontime of scheduling iterations in dependence on the number of considered planning periods.Up to the maximum examined number of 40 planning periods the scheduling model canbe solved with acceptable speed.Again, as the numerical experiments presented in the following sections simulate a

dynamic environment and only partial information is available during each schedulingiteration, it is nevertheless interesting to compare resulting costs with a theoretical de-terministic planning (cf. 4.5.1 for a similar experiment in conjunction with the first casestudy), having full information in a single scheduling iteration covering all consideredplanning periods. This is of course only feasible for a relatively small set of planningperiods. Figure 4.12 compares a dynamic planning using the Cost strategy (with event-based policy and planning horizon of 20 planning periods) with a deterministic planningover 40 planning periods. The demand consists of a base demand level of ca. 45% ofavailable production capacity (individual order sizes averaged to ca. 20% of the per plan-ning period available production capacity), while the levels of new short-term orders and

145


�

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.6.: Simulation run excerpt - schedule variation measures

�

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.7.: Average solution time per scheduling iteration

146


�

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.8.: Cost strategy & deterministic planning comparison

order cancellations varied between 10% and 30% of the base demand level. The perfor-mance of the dynamic planning in comparison to the deterministic varies again widelyand shows a stronger dependence on the order sequence of each individual demand setthan e.g. on the level of demand changes. Figure 4.12 shows the range and and averagevalue of the resulting cost performance in these experiments.

The scheduling model used in the experiments of this numerical study includes theconsideration of unsatisfied demand in order to permit valid scheduling solutions evenif not all orders can be satisfied. In these simulation experiments unsatisfied demandamounts were again negligibly small, either 0% or at most 0,00001% of available pro-duction capacity (in these cases all examined strategies generated similar amounts ofunsatisfied demand).

5.5.2. Main results — strategy comparison

Similar to the procedure for the first case study, this sub-section presents the main resultsof the conducted simulation experiments, in terms of a general strategy comparison. Thenext sub-section examines result details and the impact of several simulation and plan-ning parameters as well as further scheduling strategies, not included in this sub-section.As described in 5.4 a simple production cost minimization focused strategy and vari-ous scheduling strategies which consider schedule variation costs were examined. Theseare production cost strategies with fixations of schedule elements, strategies focusing ona minimization of schedule variation and production costs, strategies focusing only onschedule variation costs (with and without fixations) and two-step strategies minimizingschedule variation costs with respect to a production cost bound. In this sub-section, arepresentative selection of scheduling strategies is discussed. Using the denotations de-fined in 5.4 the strategies presented are Cost, LSe, CostFix5, LStSi, LStSiFix5, LSt, LSi,

147


Base demand Demand change Probability of Average Number of

new order level new order level cancellations order size data sets

45% 10% 0.1 20% 5

45% 20% 0.2 20% 5

45% 30% 0.3 20% 5

Table 5.4.: Demand data overview

LStCb1.10, LSiCost1:1, LSiCb1.05, LStSiCost1:1 and LStSiCb1.00. Further strategiesnot included in this sub-section are included in the next sub-section. In preliminary ex-periments representative parameters and demand data (based on actual company data)for this main strategy comparison were determined. The scheduling policies applied inthe experiments of this sub-section are both the event-based and the hybrid schedulingpolicy, as described in 5.4. The number of planning periods for individual simulation runswas set to 30 (cf. 5.5.3.6 for experiments concerning the impact of different numbers ofplanning periods). The base demand level was set to 45% of available production capac-ity, with individual order sizes of 20% of the per planning period available productioncapacity. The level of short-term orders was set to 10% to 30% of available productioncapacity and order cancellations occurred with a probability of 0.1 to 0.3. The occurrencetime parameter of these demand changes was set to 10 planning periods prior to the duedate of individual demand changes. These demand parameters were chosen accordingto preliminary experiments (and also based on actual company demand data) and pre-sented results are representative of the overall performance relationship of the schedulingstrategies compared in this sub-section (cf. 5.5.3.8 for experiments concerning the gen-eral impact of different demand characteristics and related parameters). Table 5.4 givesan overview of the generated demand data sets.During the simulation experiments, production and schedule variation cost measures

were again calculated by the EPPSF-Analyser component for each simulation run. Thesemeasures are the production costs (in total as well as broken down to changeover andinventory holding costs) on one hand and lot starting time, lot size and lot setup varia-tion costs one the other hand. Results are normalized to the result of the Cost strategy.Figure 5.10 shows averaged measured schedule variation costs determined during the sim-ulation experiments, as generated by the compared scheduling strategies. The measurespresented in this figure are given in percent of the values measured for the Cost strategy.Figure 5.11 shows the production costs generated by the compared scheduling strategiesfor those same simulation experiments. Beside the total production costs, which consistof changeover costs for the start of production cycles and lots on one hand and inventoryholding costs of finished products on the other hand, the figure also lists the measuredchangeover and inventory holding costs separately. The cost values are given in percent ofthe total production costs generated by the Cost strategy. In addition to a separate list-ing of production and schedule variation costs in figures 5.10, and 5.11, figure 5.9 showstotal schedule variation and production costs for the compared scheduling strategies. Agoal balance which considers both types of goals with equal importance was again chosen

148


�

��

��

��

��

��

��

��

��

��

��

Figure 5.9.: Strategy comparison — total production & schedule variation costs

for these calculations. Appropriately, production costs and schedule variation costs (con-sisting of equally weighted starting time, size and setup variation costs) were normalized(to Cost strategy results) and then totalized with equal weighting. Figure 5.12 also showstotal costs but focuses on the impact of different weightings for strategies utilizing anobjective function with weighted production and schedule variation cost minimization(cf. 5.5.3.1 for a detailed examination of the schedule variation and production costtrade-off). The total costs are again normalized to the Cost strategy result.These results again show the benefit of the inclusion of schedule variation consideration

in comparison with strategies which only focus on a production cost minimization. Themajority of the evaluated strategies generate lower total schedule variation and produc-tion costs than the Cost strategy. The exceptions are the CostFix5 and LSe strategieswhich have a negative effect on the resulting costs. Of the evaluated strategies, by farthe lowest costs overall are generated by the LStSiCb1.00 strategy (ca. 50% of Coststrategy result), followed by the LStSiCost1:1 and LSiCb1.05 strategies (ca. 60%-70% ofCost strategy result) as well as the LSiCost1:1 and LStCb1.10 strategies (ca. 70%-80%of Cost strategy result). In addition figure 5.12 shows strategies which use a weightedobjective function. The LStSiCost and LSiCost strategies generate lowest total costs foran objective weighting of 1:1. The LSeCost strategy shows decreasing costs for higherproduction cost weightings but always performs worse than the Cost strategy. The LSt-Cost strategy finally shows slightly increasing costs for higher production cost weightings.In general, strategies which focus solely on the minimization of schedule variation costsachieve a significantly worse total cost performance (90%-110% of Cost strategy result)in comparison with the strategies which try to define a sensible balance by application

149


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.10.: Strategy comparison — schedule variation costs

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.11.: Strategy comparison — production costs

150


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� � ��

��

� ��

��

��

Figure 5.12.: Schedule variation & production cost objective weighting

of either a weighted objective function or production cost bound. The same is truefor the examined strategies which consider schedule variations by fixing elements of theproduction schedules.Scheduling strategies, which consider schedule variation costs, predominantly (the ex-

ception being the again LSe and CostFix5 strategy) generate significantly lower schedulevariation costs than the Cost strategy. The largest difference in variation cost measures isrelated to the schedule variation objective used by the respective strategy. The LSt strat-egy e.g. generates relatively low lot starting time variation costs while the LSi strategygenerates low lot size variation costs. By far the lowest overall schedule variation costsare generated by the LStSi and LStSiFix5 strategies (ca. 5%-10% of Cost strategy result)followed by the overall best LStSiCb1.00 strategy (ca. 10%-20% of Cost strategy result)because these focus on a reduction of lot starting times as well as sizes. Application of alot setup objective is not beneficial, on the other hand.Strategies which generate low production costs, on par with the Cost strategy, are

LStSiCb1.00, LStSiCost1:1, LSiCb1.05 and LSiCost1:1. For demand data sets used inthese experiments, costs were even slightly lower than the Cost strategy result. Thisshows that the stabilizing effect of reduced schedule variations does not necessarily implyincreasing production costs but may even lead to lower production cost measures thanthose generated by the Cost strategy (at least for the demand data sets used in thesesimulation experiments). Strategies which focus solely on a minimization of schedulevariation costs generate significantly higher production cost measures than the Coststrategy on the other hand. Of these the LSi strategy, which focuses on a reduction ofproduction size variations and associated costs, is the best performing — in contrast to

151


the results of the first case study which showed a strategy focusing on a reduction ofstarting times (SlSt) as best performing.Further strategies which use fixations of schedule elements in order to reduce sched-

ule variations are discussed in 5.5.3.2. Further weighted objective strategies as well asschedule variation and production cost trade-offs are discussed in 5.5.3.1. The strategieswhich use weighted objective functions allow for a fine-tuning of the planning processin order to achieve a desired balance of cost-efficiency and low schedule variations andassociated costs. This also true for the examined two-step strategies which first calculatea production cost bound using only the production cost minimization objective and thenapply this bound in a second scheduling iteration with a schedule variation minimizationfocus. The definition of the production cost bound also allows for a detailed controlover the planning process. Additionally, these strategies do not require the definitionof an appropriate objective function weighting. Instead acceptable production costs aredefined and schedule variation costs are then minimized with respect to these.In conclusion, in respect to the production system and demand data examined in this

case study, scheduling strategies considering schedule variations, predominantly show atotal cost performance and schedule variation performance which are significantly betterthan the classical production cost minimization focused Cost strategy. With respect toa strategy selection in a practical application, it depends of course on the main schedulevariation goal pursued and the desired balance of planning goals to determine the bestmatching strategy, as all examined strategies exhibit different characteristics, which inturn allows it to pick the one which is considered to be the most appropriate. Strate-gies which focus on a specific objective generally show a relatively good performance inrelated cost measures (e.g. strategies with starting time related objectives show a goodperformance in measures starting time variation costs). However, it can be noted that forthe production system and demand data studied in these experiments, the LStSiCb1.00strategy shows the overall best performance of all strategies evaluated in conjunctionwith this case study.

5.5.3. Detailed results & parameter impacts

While the previous sub-section focused on the overall simulation results and a comparisonof examined strategies, in this sub-section the impact of several simulation, productionsystem and environmental parameters is examined. Due to the large number of pos-sible combinations of scheduling strategies, simulation or planning parameters as wellas demand data sets and characteristics, only a small sub-set of these combinations isexamined in these experiments. Where not otherwise noted demand data is set similarto experiments described in sub-section 5.5.2 though used demand data sets are limitedto those with a demand change level of new orders of 20% and a cancellation probabilityof 0.2. Both scheduling policies are used and the planning horizon parameter is set to 30planning periods. Where appropriate, results of specific experiments have been aggre-gated, if examined strategies or parameter settings produced similar results (cf. figure4.33 of the first case study), in order to provide a better focus on the object of study ofa specific experiment and show a clearer result presentation.

152


5.5.3.1. Schedule variation & production cost trade-off

As discussed in 4.5.3.1 for the first case study, this paragraph examines the sub-set ofscheduling strategies which utilize a weighted objective function in conjunction withthe second case study. Figures 5.13, 5.14, 5.16 and 5.15 show production costs (bluecurve) and schedule variation costs (red curve) generated by the scheduling strategiesLStSiCost, LSiCost, LStCost and LSeCost. The total schedule variation costs consist ofsub-lot starting time, size and setup variation costs which are equally weighted. Globalweights on schedule variation costs and production costs were varied between 1:0.005and 0:1. Thus LStSiCost1:0.005 is equal to the LStSi strategy while LStSiCost0:1 isequal to the Cost strategy. Demand data was similar to experiments described in sub-section 5.5.2, though due to the large number of required simulation runs the simulationtime span was limited to 50 planning period. The schedule variation costs shown inthese figures are normalized to the respective strategies with weighting 0:1 (equaling theCost strategy) while production costs are normalized to the respective strategies withweighting 1:0.005. Additionally an equally weighted average of production and schedulevariation costs is included in these figures (green curve).It can be observed from these figures that, starting from a weighting of 1:0.005 to

1:0.05, production costs drop considerably until a weighting of ca. 1:1 after which nofurther improvements are observable. Interestingly the LStSiCost and LSiCost strategiesdo not benefit (production cost-wise) from a slightly higher production cost weighting incomparison to the 1:0.005 weighting, at least in respect to the considered demand datasets. Schedule variation costs are highest for an objective weighting of 0:1 as this equalsthe Cost strategy. With the exception being the LSe strategy, an increasing weighting ofthe schedule variation objective leads to a decrease of respective schedule variation costs.The LStSiCost and LSiCost strategies show a relatively strong decrease for weightingsof ca. 1:1 to 1:0.1. For the LStCost strategy it is strongest between ca. 1:0.5 and 1:0.01while the LSeCost is always performing worse than Cost strategy. Considering schedulevariation costs and production costs simultaneously, a weighting of 1:1 generally producesthe best schedule performance in conjunction with the LStSiCost and LSiCost strategies.The LStCost strategy leads to the best results for weightings of 1:0.005 (correspondingto the LSt strategy) to 1:0.01 while the application of the LSe strategy is not beneficialat all, as has also been indicated in the previous sub-section.

5.5.3.2. Fixation of schedule elements

In this paragraph, the impact of schedule fixations on the production and schedule vari-ation cost performance is investigated. Studied strategies, for which parts of productionschedules were fixed, are the Cost, LSi, LSt and LStSi strategies. The length of the timeperiod for which corresponding schedule elements are fixed was set to 5 planning periods.Apart from total costs, figure 5.17 shows the resulting production, lot starting time, lot

size and lot setup variation costs, in comparison to the corresponding strategies withoutschedule fixations. The examined strategies do not benefit from a fixation of parts ofthe schedule. Total costs are higher or at best on par in comparison with respective

153


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.13.: Schedule variation & production cost trade-off (LStSiCost strategy)

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.14.: Schedule variation & production cost trade-off (LSiCost strategy)

154


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.15.: Schedule variation & production cost trade-off (LStCost strategy)

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.16.: Schedule variation & production cost trade-off (LSeCost strategy)

155


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.17.: Schedule fixation strategies

strategies without fixations. The CostFix5 strategy results are very similar to the Coststrategy results and even resulted in a slight relative increase of production as well asschedule variation cost measures in comparison to the Cost strategy. Similarly, obtainedresults for the LStSiFix5 strategy almost match the results of the LStSi strategy. Aslight relative decrease of production and lot starting time variation costs is faced bya slight relative increase in lot size and setup variation costs. In respect to the LStand LSi strategies the impact on production and setup variation costs is again small.The fixations of schedule elements decrease the lot starting time variation costs for theLSi strategy and lot size variation costs for the LSt strategy. On the other hand, thesefixations, which decrease the optimization potential, lead to relatively higher lot startingtime variation costs for the LStFix5 strategy in comparison to the LSt strategy andhigher lot size variation costs for the LSiFix5 strategy in comparison to the LSi strategy.Even though the impact of fixations are not clearly beneficial, in practical applicationsit may generally be preferred to ensure very stable schedules for the immediate future byfixing parts production schedules.

5.5.3.3. Two-step strategies with production cost bounds

This paragraph studies two-step scheduling strategies as described in 5.4. The plan-ning process of each scheduling iteration is divided into two steps. First a preliminaryscheduling is performed using the Cost strategy. The measured production costs arethen multiplied by a “cost bound factor” (set as simulation parameter) to calculate a costbound constraint which is applied in a second and final scheduling step using a schedulingstrategy focusing on the minimization of a schedule variation measure.

156


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.18.: Production cost bounds — schedule variation costs

Figures 5.18 and 5.19 show a comparison of scheduling strategies with production costbounds. Production cost measures and a selection of schedule variation cost measuresare presented. The cost bounds on the LStSiCb, LSiCb, LStCb and LSeCb strategiesare calculated by cost bound factors of 1.00, 1.05, and 1.10 corresponding to allowedproduction cost increases of 0%, 5% and 10% over the production cost measure which ismeasured in the first step of each two-step scheduling iteration. The figures show that forincreasing production cost bounds the resulting production costs slightly increase as well,while the schedule variation cost measures slightly decrease. The overall performancerelationship of strategies is similar to the results presented in 5.5.2. The LStSi, LSi andLSt strategies generate significantly lower schedule variation costs than the Cost strategyfor all examined production cost bounds. As discussed in 5.5.2, for the applied demanddata sets, the LStSiCb and LSiCb strategies even achieve slightly lower production coststhan the Cost strategy. As presented in 5.5.2 LStSiCb1.00 strategy generates the lowesttotal production and schedule variation costs. Even slightly lower schedule variationcosts result from an application of the LStSiCb1.10 strategy.

5.5.3.4. Limited number of planning periods with schedule variation considerations

In this paragraph the impact of a limited number of planning periods for which schedulevariations are considered is presented. Figure 5.20 shows production and schedule varia-tion cost measures as generated by modified LSt and LSi strategies which consider onlya limited number of planning periods (5, 10 and 15) in schedule variation calculations.The results are averaged for both strategies as these were similar. The more planning

157


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.19.: Production cost bounds — production costs

periods in which schedule variations are considered the higher is the increase in resultingproduction costs as these two strategies focus on a reduction of schedule variation costs.A strong decrease in schedule variation costs is only obtained for simulation runs in whicha number of 15 planning periods, for which schedule variations are considered, were used,albeit this is accompanied by a relatively strong increase in production costs. A numberof 5 and 10 planning periods does even generate higher lot starting time variation coststhan the Cost strategy — the reduction of schedule variations in those 5 and 10 planningperiods leads to even stronger alterations in the remaining planning periods for which noschedule variations are considered.

5.5.3.5. Inverse production sequences

This paragraph focuses on the impact of different product sequences on the resultingproduction and schedule variation cost measures. The simulation experiments were con-ducted with variants of the standard product sequence which corresponds to the naturalproduction sequence. As described in the problem description of this case study theproduction system in some production facilities may also be planned in a reversed pro-duction order within a cycle. The first examined product sequence variant correspondsto the inverse of the standard sequence for all production cycles. The second variantalternates between standard and inverse product order in successive production cycles.As a third variant the first extension to the basic scheduling model was examined. Thisextension expresses the choice between standard and inverse production sequence as adecision of the scheduling model.

158


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�

��

��

Figure 5.20.: Limited number of planning periods with schedule variation consideration

Figure 5.21 shows the relative difference of schedule variation and production cost mea-sures for three examined sequence variants, normalized to the standard sequence results.In these experiments the Cost, LSt and LSi strategies were applied. The overall strategyperformance relation, as presented in 5.5.2, did not change for different sequences. Fur-thermore these strategies showed similar results in respect to relative differences due tothese sequence variants. Figure 5.21 shows the average results for the three strategies. Itis observable that cost measures vary for different sequences, though the impact on mostmeasures is small. However, the standard product sequence is the best match for theutilized demand data sets. In theory, the model extension should allow for a more cost-efficient scheduling due to the increased optimization potential of the included sequencechoice (standard or inverse order). As a side-effect, this might result in higher schedulevariation costs. Higher schedule variation costs can indeed be observed from figure 5.21.The anticipated decrease in production costs could not be realized when considering awhole simulation run, though (or at least not for the demand data sets used in theseexperiments).

5.5.3.6. Number of planning periods

The planning horizon parameter which is set for a simulation run determines the numberof planning periods which are included in each scheduling iteration. The more planningperiods are included in a planning process, the more orders have to be included and addi-tional lots and sub-lots to be scheduled if need be. This paragraph focuses on the impactof the number of planning periods on the simulation results. Scheduling strategies whichwere used in these experiments are the Cost, LSi, LSt, LStSi, LSiCost1:1, LStCost1:1and LStSiCost1:1 strategies. Figure 5.22 shows the schedule variation and productioncosts resulting from different numbers of included planning period. Generated cost mea-

159


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

��

!��"��

Figure 5.21.: Product sequence impact

sures of all examined strategies exhibited a similar progression for an increasing numberof planning periods while the general performance relation of strategies, as presented in5.5.2, did not change. Figure 5.22 presents aggregated results and focuses on the generalimpact of the planning horizon length.In contrast to the observations presented in 4.5.3.5 for the first case study the in-

creased optimization potential provided by longer planning horizons does not lead tolower production costs. While product changeover costs resulting from planned sched-ules indeed decrease for a higher number of planning periods, this is offset by increasedinventory holding and results in slightly increasing total production costs. Schedule vari-ation costs again increase for longer planning horizons because of a higher number ofplanning periods (and thus demand orders) which have to be taken into account in eachscheduling iteration. In order to satisfy all demand orders and follow defined objectivesmore changes to original schedules have to be made in individual scheduling iterations.In addition, each demand element is included in a higher number of scheduling iterations.The increase in schedule variation costs is stronger for 25 planning periods and higherwhile production costs increase only very slightly because of reductions in changeovercosts.

5.5.3.7. Scheduling policies

After examining the impact of the planning horizon parameter this paragraph focuseson differences of the two implemented scheduling policies (cf. 5.4) which determine theplanning process execution. The event-based scheduling policy triggers a schedulingiteration whenever a new demand order arrives or a cancellation occurs. The hybridpolicy triggers scheduling iterations periodically with an interval of 1 planning period

160


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.22.: Planning horizon length & production costs

and also whenever demand changes (new urgent order or order cancellation) occur. Inall experiments of this numerical study these two scheduling policies were applied.The scheduling strategies utilized for these experiments are the Cost, LSt, LSi and

LSe strategies. Figure 5.23 shows schedule variation and production costs as generatedby the hybrid scheduling policy in percent of the costs generated by the event-basedscheduling policy. Additionally, average schedule variation costs per scheduling iterationare included. Similar to the observations in 4.5.3.6 the figure shows that, while theimpact on the resulting production costs is minor, the more frequent scheduling iterationsinitiated by the event-based policy lead to more frequent schedule adjustments and higherschedule variation costs overall. However, the average amount of schedule variationswhich are generated by each scheduling iteration is higher for the hybrid schedulingpolicy. The higher these changes induced by schedule adjustments in each iteration, themore additional planning efforts and associated costs may arise at once in reaction tothe schedule adjustments. The relative schedule variation cost difference depends on theapplied strategy. The Cost strategy exhibits the largest difference of these four strategiesbecause it does not consider schedule variations — thus, additional scheduling iterationslead to relatively higher additional variations. The LStSi strategy on the other hand,which generates very low schedule variation costs in general, show the lowest schedulevariation cost difference between both scheduling policies (hence respective average costsper iteration are relatively highest).

5.5.3.8. Demand characteristics

Similar to 4.5.3.7 this paragraph focuses on various aspects of the product demand whichoccurs and has to be satisfied during a simulation run. As described in 5.4 the demand

161


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.23.: Scheduling policy & cost measures

of a simulation run consists of a base demand level, with demand quantities and duedates which are assumed to be known as long as the number of considered planningperiods, and demand changes consisting of new short-term orders as well as cancella-tions (modeling demand reductions). As planning time progresses, new demand-relatedevents occur subsequently and are then available for consideration in scheduling itera-tions. The demand information is handled by the EPPSF-Event Manager componentand made available to other components of the simulation system when the respectivedemand elements become known and are plannable. Scheduling strategies used for theseexperiments are the Cost, LStSi and LStSiCost1:1 strategies.Figure 5.24 examines the impact of the total demand level which occurs during a

simulation run. Three different demand levels were studied, corresponding to 45% (thestandard demand level), 30% and 15% of available production capacity as base demandlevel. The demand change level was set to new order amounts of 30% of the base demandlevel as well 30% cancellations, keeping the overall demand level similar to the base de-mand. Note that the general performance relation between the three examined schedulingstrategies, as presented in 5.5.2, did not change for these three demand levels. However,the relative progression of costs in dependence on the varying demand level is differentfor individual strategies. Production costs, schedule variation costs as well as total costsare presented for each strategy, normalized to a demand level of 45%. For decreasing de-mand levels figure 5.24 shows decreasing cost measures. A linear total cost decrease canbe observed for the Cost strategy while the LStSi and and LStSiCost1:1 strategies showan even stronger decrease. This is due to significant reductions in schedule variations —in respect to lower demand levels it is easier to keep elements of a production scheduleunchanged. Production costs of all strategies decrease more or less linearly for lower

162


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

!�

��

Figure 5.24.: Demand level impact

demand levels with LStSi strategy showing the least relative benefit. The LStSiCost1:1not only generates the lowest total costs of these three strategies (cf. 5.5.2) but alsoexhibits the best relative cost decrease in dependence on decreasing demand levels whenconsidering both schedule variation and production costs.Figure 5.25 shows the impact of the demand granularity. Three demand granularities

were studied, corresponding to average order sizes of 20% (the standard granularity),40% and 80% of available production capacity per planning period. A larger averageorder quantity size means that less individual orders with higher order quantities haveto be scheduled for a given demand level. The figure shows the production and schedulevariation costs for the three examined granularities, aggregated as the results of the threeapplied scheduling strategies were similar. The impact of the demand granularity on lotstarting time and size variation costs is minor — these very slightly decreasing for largeraverage order sizes. The impact on lot setup variations is a bit stronger with larger ordersizes and thus fewer individual orders resulting in less setup variations. Production costsare decreasing as well for larger order sizes, mainly due to lower product changeoveramounts.After studying aspects of the demand level and granularity, figure 5.26 now focuses

on the impact of the time interval an occurring demand change is known before itsrespective due date (the demand change offset). In order to allow for a systematic studyof the demand offset in this experiment, the demand offset was set to the same valuefor all demand changes within a simulation run. As the examined strategies producedsimilar results the production and schedule variation costs (individual schedule variationmeasures also showed similar results) presented in figure 5.26 are again aggregated. Theimpact of different demand change offsets on resulting production costs are negligible.The impact on schedule variation costs is also minor, with a very slight increase for anoffset of 15 and decrease for an offset of 20, at least in respect to the demand data setsexamined in these experiments.

163


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.25.: Demand granularity impact

�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

Figure 5.26.: Impact of demand change occurrence

164


�

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 5.27.: Impact of demand change level

As the last examined aspect of the simulated demand, figure 5.27 shows the impactof the level of demand changes on the schedule variation and production costs, varyingfrom 10% to 50% of the standard base demand level of 45% of available productioncapacity. In these experiments a demand change level of e.g. 10% means a level of neworders of 10% of the base demand level and cancellations with a probability of 10%.Thus, the total demand level remains unaffected. This allows for a study of the impactthese variations have without significant changes to the total demand level. Results fordifferent scheduling strategies (normalized to a demand change level of 50% for eachstrategy) and also schedule variation costs have been aggregated again due to the factthat these were similar. It can be observed from figure 5.27 that production costs areunaffected. This is not unexpected as the total demand level did not change. Schedulevariation costs are slightly increasing with for higher demand change levels

5.6. Case summary

The experimental results of this chemical commodity production case study (using theEPPSF) again show that scheduling strategies which consider schedule variations signifi-cantly decrease the total amount of schedule variation and production costs in comparisonto a simple production cost minimization approach. Of the evaluated scheduling strate-gies, those which generate the lowest total schedule variation and production costs arethe ones that consider both types of objectives. These best performing strategies — LSt-SiCb1.00, LStSiCost1:1, LSiCb1.05, LSiCost1:1 and LStCb1.10 — use either a weightedobjective function (with a weighting of 1:1) or implement the two-step approach whichcalculates and applies a production cost bound (and in turn restricts the possibility ofschedule variation reductions to those which do not raise the resulting production costsover the determined bound). Furthermore, the best performing strategies utilize a com-bined lot starting time and size objective as schedule variation goal element. When only

165


the schedule variation goal is considered the LStSi and LStSiFix5 strategies performbest, as these generate the lowest schedule variation costs. On the other hand, resultingproduction costs are significantly higher which is also true for all strategies which pre-dominantly focus on schedule variations. The lowest production costs are generated bythe Cost, LStSiCb1.00, LStSiCost1:1, LSiCb1.05 and LSiCost1:1 strategies which, apartfrom the Cost strategy, aim at a sensible balance of both cost goal types.A variety of different objective weightings and cost bound factors was examined in these

simulation experiments. The results show that generated cost measures are sensitive tothe setting of these parameters. This emphasizes the importance of a detailed fine-tuning(and continuous revision) of planning parameters for practical applications in order toobtain the best possible planning results in respect to defined planning goals and thedesired production and schedule variation cost trade-off. In addition to these strategy-related observations, specific results also react more or less sensitive to changing valuesof production system and planning parameters, as well as characteristics of the demandto be satisfied.

166

6. Concluding remarks and outlook

Companies, today’s, often conduct business in increasingly competitive markets. Theyare exposed to environments exhibiting very dynamic characteristics, are faced with theneed to constantly react to environmental influences (especially demand-related events)and adjust and continuously develop production plans. An important aspect of an evolu-tionary production planning is a balancing of the desire for preferably unaltered alreadyplanned production activities (and thus a reduction of otherwise arising associated co-ordination or planning efforts and costs) on one hand and the necessity of conductingcost-efficient planning (and remaining competitive) on the other hand.

In chapter 2 important concepts and common approaches for an execution of produc-tion planning activities in dynamic environments have been discussed. The importanceof an evolutionary plan development in today’s markets, with frequent demand-relatedevents, is not reflected by a high number of corresponding publications in the researchliterature. Despite some publications which consider the problem of the inclusion of neworders or order modifications into an existing plan for specific scheduling applications,there is still a lot of demand for research on this kind of planning problems. Further-more, while the research literature commonly classifies these planning problems as beingwithin the general area of reactive planning, the kind of planning problems researchedin this work exhibits very special characteristics, making it reasonable to define theseas a distinct type of production planning problems (or sub-type of reactive planning,respectively). This planning area was then called evolutionary production planning inthis work. Chapter 3 presented a general concept describing common characteristics ofevolutionary production planning applications. A simulation framework supporting theimplementation and study of such applications was presented as well. This simulationframework was then applied in the core of this research, in part II of this work, in theinvestigation of two case study evolutionary production planning applications.

The first case study in chapter 4 investigated the final bottling stage of a beveragesproduction facility, while the second case study in chapter 5 was occupied with theproduction of chemical commodity products. Scheduling iterations for both case studyplanning problems were modeled and solved as mixed-integer linear programming (MILP)problems. The parameterization of generic scheduling models, in conjunction with anumber of different objective functions, allowed for the implementation and evaluationof a variety of scheduling strategies. The characteristics of both case studies inducedthe application of the block planning principle in the scheduling models, which allowsfor relatively efficient MILP-representations of such integrated lot-sizing and schedulingproblems.

167


In the numerical studies several types of scheduling strategies were evaluated, solelycost focused strategies, cost objective strategies with fixations of schedule components,single-step as well as two-step strategies with cost and schedule variation reduction ob-jectives and single-step strategies with fixations of schedule components and cost as wellas schedule variation objectives. Planning strategies with multiple objectives require theestimation of realistic costs, resulting from schedule variations or the definition of appro-priate schedule variation penalty costs (either providing a good estimation of resultingcosts or chosen to steer the planning solution process in a desired way). For the two casestudies no information about realistic costs of schedule variations was available, thereforethe multi-objective planning strategies required the estimation of penalty costs. As inpractice it is often difficult to choose appropriate penalty costs and as solution processestend to react sensitive to variations in these chosen values, the trade-off of these plan-ning goals was investigated. Two-step strategies, implemented in the numerical studies,tried to elude the estimation of appropriate penalty costs by focusing on the definitionof a maximum production cost increase defined acceptable for the sake of the reductionof schedule variations. The acceptable production cost increase was calculated in eachplanning iteration by first applying a cost minimization strategy in a first planning step,then multiplying determined production costs with a “cost bound factor” (parameterizedfor the allowed percentage of cost increases) to calculate a cost bound for use in a sec-ond planning step, in which one of the strategies with a dominant schedule reductionobjective was applied in order to generate the adjusted schedule.The main result of both case studies is that these two-step planning strategies as well

as single-step strategies, focusing equally on schedule variation and production costs,showed the best performance overall. Among these, the strategies focusing on the si-multaneous reduction of starting times and sizes of production (sub-)lots achieved thebest results. Not only did these strategies generate production costs comparable to solecost minimizations (or even slightly lower), but the schedule variation costs generated bysuccessive scheduling iterations were also very low.These results show the applicability of the evolutionary planning approach to both

planning problems. In addition, with respect to the implemented two-step strategiesthe results show that it is possible to pursue both schedule variation and cost-efficiencyobjectives simultaneously with good performance, while eluding or reducing penalty costestimation difficulties, by instead defining acceptable planning cost increases for the sakeof schedule variation reductions.

Future possibilities for research on evolutionary production planning and schedulingare still plenty. For instance, numerous applications in other planning areas and indus-tries need to be addressed — for example the short-term scheduling of car body partsproduction systems in the automotive industry requires the inclusion of a significantnumber of short-term orders and frequent demand modifications. In respect to the plan-ning applications of the two investigated case studies, other planning strategies may bedefined and evaluated, e.g. the use of schedule fixations might require further attention.A more detailed investigation of scheduling policies, including context-sensitive policies,might be desirable. Additionally, only a small number of possible combinations of plan-

168


ning and simulation parameters have been studied as well as a relatively small number ofdemand data sets generated and used in simulation experiments. Further investigationsmay confirm and further strengthen or also relativize the observations gained from theconducted numerical studies. Furthermore, while the block planning principle allows forrelatively efficient MILP-formulations, larger problem instances will require the develop-ment of sufficient heuristic approaches in order to achieve quick solution times. The twoextensions of the second case studies also provide opportunities for further investigations.

169

Bibliography

A

D. Adebanjo and R. Mann. Identifying problems in forecasting consumer demand inthe fast moving consumer goods sector. Benchmarking: An International Journal, 7(3):223–230, 2000.

A. Allahverdi, C. T. Ng, T. C. E. Cheng, and M. Y. Kovalyov. A survey of schedulingproblems with setup times or costs. European Journal of Operational Research, 187(3):985 – 1032, 2008. ISSN 0377-2217. doi: 10.1016/j.ejor.2006.06.060.

B. Almada-Lobo, J. F. Oliveira, and M. A. Carravilla. Production planning andscheduling in the glass container industry: A vns approach. International Journal ofProduction Economics, 114(1):363 – 375, 2008. ISSN 0925-5273. doi:10.1016/j.ijpe.2007.02.052. Special Section on Competitive Advantage throughGlobal Supply Chains.

O. Amorim, C. H. Antunes, and B. Almada-Lobo. Multi-objective lot-sizing andscheduling dealing with perishability issues. Industrial & Engineering ChemistryResearch, 50(6):3371–3381, 2011. doi: 10.1021/ie101645h.

C. Artigues and O. Roubellat. An efficient algorithm for operation insertion in amulti-resource job-shop schedule with sequence-dependent setup times. ProductionPlanning and Control, 13(2):175–186, 2002.

H. Aytug, M. A. Lawley, K. McKay, S. Mohan, and R. Uzsoy. Executing productionschedules in the face of uncertainties: A review and some future directions. EuropeanJournal of Operational Research, 161(1):86 – 110, 2005. ISSN 0377-2217. doi:10.1016/j.ejor.2003.08.027. IEPM: Focus on Scheduling.

B

M. Bala and D. Kumar. Supply chain performance attributes for the fast movingconsumer goods industry. Journal of Transport and Supply Chain Management, 5(1):23–38, 2011.

J. Balakrishnan and C. H. Cheng. The dynamic plant layout problem: Incorporatingrolling horizons and forecast uncertainty. Omega, 37(1):165 – 177, 2009. ISSN0305-0483. doi: 10.1016/j.omega.2006.11.005.

170

Bibliography

A. Beck. Automatic product identification & shrinkage: Scoping the potential.Whitepaper, ECR Europe, 2002.

B. Bilgen and H.-O. Günther. Integrated production and distribution planning in thefast moving consumer goods industry: a block planning application. OR Spectrum,32:927–955, 2010. ISSN 0171-6468. 10.1007/s00291-009-0177-4.

J. D. Blackburn, D. H. Kropp, and R. A. Millen. A comparison of strategies to dampennervousness in mrp systems. Management Science, 32(4):pp. 413–429, 1986. ISSN00251909.

F. Blömer. Produktionsplanung und -steuerung in der chemischen Industrie:Ressourceneinsatzplanung von Batchprozessen auf Mehrzweckanlagen. Gabler, 1999.

F. Blömer and H.-O. Günther. Lp-based heuristics for scheduling chemical batchprocesses. International Journal of Production Research, 38:1029–1051(23), 2000.

L. Buschkühl, F. Sahling, S. Helber, and H. Tempelmeier. Dynamic capacitatedlot-sizing problems: a classification and review of solution approaches. OR Spectrum,32:231–261, 2010. ISSN 0171-6468. 10.1007/s00291-008-0150-7.

C

P. Caricato and A. Grieco. An online approach to dynamic rescheduling for productionplanning applications. International Journal of Production Research, 46(16):4597–4617, 2008. doi: 10.1080/00207540601136225.

R. C. Carlson, J. V. Jucker, and D. H. Kropp. Less nervous mrp systems: A dynamiceconomic lot-sizing approach. Management Science, 25(8):pp. 754–761, 1979. ISSN00251909.

S. Chand, V. Hsu, and S. Sethi. Forecast, solution, and rolling horizons in operationsmanagement problems: A classified bibliography. Manufacturing & ServiceOperations Management, Vol. 4, No. 1, pp. 25-43, Winter 2002, 2002.

I. T. Christou, A. G. Lagodimos, and D. Lycopoulou. Hierarchical production planningfor multi-product lines in the beverage industry. Production Planning & Control, 18(5):367–376, 2007. doi: 10.1080/09537280701340631.

L. K. Church and R. Uzsoy. Analysis of periodic and event-driven rescheduling policiesin dynamic shops. International Journal of Computer Integrated Manufacturing, 5(3):153–163, 1992. doi: 10.1080/09511929208944524.

A. R. Clark. Rolling horizon heuristics for production planning and set-up schedulingwith backlogs and error-prone demand forecasts. Production Planning & Control, 16(1):81–97, 2005a. doi: 10.1080/09537280412331286565.

171

Bibliography

A. R. Clark. Rolling horizon heuristics for production planning and set-up schedulingwith backlogs and error-prone demand forecasts. Production Planning & Control, 16(1):81–97, 2005b. doi: 10.1080/09537280412331286565.

A. R. Clark and S. J. Clark. Rolling-horizon lot-sizing when set-up times aresequence-dependent. International Journal of Production Research, 38(10):2287–2307, 2000. doi: 10.1080/00207540050028106.

J. Cooper, M. Browne, and M. Peters. European Logistics: Markets, Management andStrategy. Wiley-Blackwell, Oxford and Camebridge, 2nd edition edition, 1994.

F

A. Federgruen and M. Tzur. Minimal forecast horizons and a new planning procedurefor the general dynamic lot sizing model: Nervousness revisited. Operations Research,42(3):pp. 456–468, 1994. ISSN 0030364X.

D. Ferreira, R. Morabito, and S. Rangel. Solution approaches for the soft drinkintegrated production lot sizing and scheduling problem. European Journal ofOperational Research, 196(2):697 – 706, 2009. ISSN 0377-2217. doi:10.1016/j.ejor.2008.03.035.

D. Ferreira, R. Morabito, and S. Rangel. Relax and fix heuristics to solve one-stageone-machine lot-scheduling models for small-scale soft drink plants. Computers &Operations Research, 37(4):684 – 691, 2010. ISSN 0305-0548. doi:10.1016/j.cor.2009.06.007.

D. Ferreira, A. R. Clark, B. Almada-Lobo, and R. Morabito. Single-stage formulationsfor synchronised two-stage lot sizing and scheduling in soft drink production.International Journal of Production Economics, 136(2):255 – 265, 2012. ISSN0925-5273. doi: 10.1016/j.ijpe.2011.11.028.

S. Ferrer-Nadal, C. A. Mendez, M. Graells, and L. Puigjaner. Optimal reactivescheduling of manufacturing plants with flexible batch recipes. Industrial &Engineering Chemistry Research, 46(19):6273–6283, 2007. doi: 10.1021/ie061255.

G

M. Gebhard and P. D. H. Kuhn. Hierarchische Produktionsplanung Bei Unsicherheit.Produktion Und Logistik. Gabler, 2009. ISBN 9783834916778.

T. Gellert, W. Höhn, and R. Möhring. Sequencing and scheduling for filling lines indairy production. Optimization Letters, 5:491–504, 2011. ISSN 1862-4472.10.1007/s11590-011-0336-9.

172

Bibliography

H.-O. Günther. The block planning approach: A case study application from thebeverage industry. In Industrial Engineering and Engineering Management, 2008.IEEM 2008. IEEE International Conference on, pages 359 –363, dec. 2008. doi:10.1109/IEEM.2008.4737891.

H.-O. Günther. An application of milp-based block planning in the chemical industry.In The Eighth International Symposium on Operations Research and Its Applications(ISORA09), pages 103–110, Zhangjiajie, China, September 20-22 2009.

H.-O. Günther, M. Grunow, and U. Neuhaus. Realizing block planning concepts inmake-and-pack production using MILP modelling and SAP APO. InternationalJournal of Production Research, 44(18-19):3711–3726, October 2006. ISSN0020-7543. doi: 10.1080/00207540600589127.

M. C. Gomes, A. P. Barbosa-Pavoa, and A. Q. Novais. A discrete time reactivescheduling model for new order insertion in job shop, make-to-order industries.International Journal of Production Research, 48(24):7395–7422, 2010. doi:10.1080/00207540903433858.

H

E. Hans and S. van de Velde. The lot sizing and scheduling of sand casting operations.International Journal of Production Research, 49(9):2481–2499, 2011. doi:10.1080/00207543.2010.532913.

W. Herroelen and R. Leus. Project scheduling under uncertainty: Survey and researchpotentials. European Journal of Operational Research, 165(2):289 – 306, 2005. ISSN0377-2217. doi: 10.1016/j.ejor.2004.04.002. Project Management and Scheduling.

C.-J. Ho and T. C. Ireland. A diagnostic analysis of the impact of forecast errors onproduction planning via mrp system nervousness. Production Planning & Control, 4(4):311–322, 1993. doi: 10.1080/09537289308919453.

C.-J. Ho and T. C. Ireland. Correlating mrp system nervousness with forecast errors.International Journal of Production Research, 36(8):2285–2299, 1998. doi:10.1080/002075498192904.

O. Holthaus and C. Rajendran. Efficient jobshop dispatching rules: Furtherdevelopments. Production Planning & Control, 11(2):171–178, 2000. doi:10.1080/095372800232379.

S. J. Honkomp, S. Lombardo, O. Rosen, and J. F. Pekny. The curse of reality - whyprocess scheduling optimization problems are difficult in practice. Computers &Chemical Engineering, 24(27):323 – 328, 2000. ISSN 0098-1354. doi:10.1016/S0098-1354(00)00468-3.

173

Bibliography

I

K. Inderfurth and T. Jensen. Planungsnervosität im Rahmen der Produktionsplanungund-steuerung. Preprint // Otto-von-Guericke-Universitaet Magdeburg, Fakultät fuerWirtschaftswissenschaft. Otto-von-Guericke-Univ., Fak. für Wirtschaftswissenschaft,1996.

J

S. L. Janak, C. A. Floudas, J. Kallrath, and N. Vormbrock. Production scheduling of alarge-scale industrial batch plant. i. short-term and medium-term scheduling.Industrial & Engineering Chemistry Research, 45(25):8234–8252, 2006. doi:10.1021/ie0600588.

R. Jans and Z. Degraeve. Modeling industrial lot sizing problems: a review.International Journal of Production Research, 46(6):1619–1643, 2008. doi:10.1080/00207540600902262.

M. T. Jensen. Improving robustness and flexibility of tardiness and total flow-time jobshops using robustness measures. Applied Soft Computing, 1(1):35 – 52, 2001. ISSN1568-4946. doi: 10.1016/S1568-4946(01)00005-9.

K

R. Kaipia, H. Korhonen, and H. Hartiala. Planning nervousness in a demand supplynetwork: an empirical study. The International Journal of Logistics Management, 17(1):95–113, 2006. doi: doi:10.1108/09574090610663455.

J. Kallrath. Planning and scheduling in the process industry. OR Spectrum, 24:219–250, 2002. ISSN 0171-6468. 10.1007/s00291-002-0101-7.

P. Kaminsky and O. Kaya. Combined make-to-order/make-to-stock supply chains. IIETransactions, 41(2):103–119, 2009. doi: doi:10.1080/07408170801975065.

B. Karimi, S. M. T. F. Ghomi, and J. M. Wilson. The capacitated lot sizing problem: areview of models and algorithms. Omega, 31(5):365 – 378, 2003. ISSN 0305-0483.doi: 10.1016/S0305-0483(03)00059-8.

O. Kazan, R. Nagi, and C. M. Rump. New lot-sizing formulations for less nervousproduction schedules. Comput. Oper. Res., 27(13):1325–1345, November 2000. ISSN0305-0548. doi: 10.1016/S0305-0548(99)00076-3.

H. T. Keh and S. Y. Park. To market, to market: the changing face of groceryretailing. Long Range Planning, 30(6):836 – 846, 1997. ISSN 0024-6301. doi:10.1016/S0024-6301(97)00069-1.

174

Bibliography

A. Kimms. Stability measures for rolling schedules with applications to capacityexpansion planning, master production scheduling, and lot sizing. Omega, 26(3):355– 366, 1998. ISSN 0305-0483. doi: 10.1016/S0305-0483(97)00056-X.

K. P. Kistner and M. Steven. Produktionsplanung. Physica-Lehrbuch. Physica-Verlag,2001. ISBN 9783790814262.

G. M. Kopanos, L. Puigjaner, and M. C. Georgiadis. Optimal production schedulingand lot-sizing in dairy plants: The yogurt production line. 49(2):18, 2010. Anglais.

G. M. Kopanos, L. Puigjaner, and M. C. Georgiadis. Efficient mathematicalframeworks for detailed production scheduling in food processing industries.Computers & Chemical Engineering, (0):–, 2011. ISSN 0098-1354. doi:10.1016/j.compchemeng.2011.12.015.

P. Kouvelis, R. L. Daniels, and G. Vairaktarakis. Robust scheduling of a two-machineflow shop with uncertain processing times. IIE Transactions, 32:421–432, 2000. ISSN0740-817X. 10.1023/A:1007640726040.

H. Krallmann, H. Frank, and N. Gronau. Systemanalyse im Unternehmen. Oldenbourg,2002. ISBN 9783486272031.

D. H. Kropp, R. C. Carlson, and J. V. Jucker. Heuristic lot-sizing approaches fordealing with mrp system nervousness. Decision Sciences, 14(2):156–169, 1983. ISSN1540-5915. doi: 10.1111/j.1540-5915.1983.tb00177.x.

K. Kurbel. Produktionsplanung und -steuerung im Enterprise Resource Planning undSupply Chain Management. Anwendungen in Naturwissenschaften, Technik undMedizin. Oldenbourg, 2005. ISBN 9783486575781.

K. Kurbel. Enterprise Resource Planning und Supply Chain Management in derIndustrie. Oldenbourg, 2011. ISBN 9783486704624.

L

S. R. Lawrence and E. C. Sewell. Heuristic, optimal, static, and dynamic scheduleswhen processing times are uncertain. Journal of Operations Management, 15(1):71 –82, 1997. ISSN 0272-6963. doi: 10.1016/S0272-6963(96)00090-3.

D. Lei. Multi-objective production scheduling: a survey. The International Journal ofAdvanced Manufacturing Technology, 43:926–938, 2009. ISSN 0268-3768. doi:10.1007/s00170-008-1770-4.

Z. Li and M. G. Ierapetritou. Rolling horizon based planning and schedulingintegration with production capacity consideration. Chemical Engineering Science,65(22):5887 – 5900, 2010. ISSN 0009-2509. doi: 10.1016/j.ces.2010.08.010.

175

Bibliography

S. Liu, J. M. Pinto, and L. G. Papageorgiou. Medium-term planning of multistagemultiproduct continuous plants using mixed integer optimisation. In JacekJeÅŒowski and Jan Thullie, editors, 19th European Symposium on Computer AidedProcess Engineering, volume 26 of Computer Aided Chemical Engineering, pages 393– 398. Elsevier, 2009. doi: 10.1016/S1570-7946(09)70066-5.

T. Loukil, J. Teghem, and D. Tuyttens. Solving multi-objective production schedulingproblems using metaheuristics. European Journal of Operational Research, 161(1):42– 61, 2005. ISSN 0377-2217. doi: 10.1016/j.ejor.2003.08.029. IEPM: Focus onScheduling.

M. Lütke Entrup, H.-O. Günther, P. Van Beek, M. Grunow, and T. Seiler.Mixed-integer linear programming approaches to shelf-life-integrated planning andscheduling in yoghurt production. International Journal of Production Research, 43(23):5071–5100, 2005.

J. R. D. Luche, R. Morabito, and V. Pureza. Combining process selection and lot sizingmodels for the production scheduling of electrofused grains. Asia-Pacific Journal ofOperational Research (APJOR), 26(03):421–443, 2009.

M

F. Marinelli, M. Nenni, and A. Sforza. Capacitated lot sizing and scheduling withparallel machines and shared buffers: A case study in a packaging company. Annalsof Operations Research, 150(1):177–192, 2007. doi: doi:10.1007/s10479-006-0157-x.

S. V. Mehta and R. M. Uzsoy. Predictable scheduling of a job shop subject tobreakdowns. Robotics and Automation, IEEE Transactions on, 14(3):365 –378, jun1998. ISSN 1042-296X. doi: 10.1109/70.678447.

C. A. Mendez and J. Cerda. Dynamic scheduling in multiproduct batch plants.Computers and Chemical Engineering, 27(8):1247–1259, 2003. doi:doi:10.1016/S0098-1354(03)00050-4.

M. T. G. Meulenberg and J. Viaene. Changing food marketing systems in westerncountries. 1998.

D. J. Mignon, S. J. Honkomp, and G. V. Reklaitis. A framework for investigatingschedule robustness under uncertainty. Computers & Chemical Engineering, 19,Supplement 1(0):615 – 620, 1995. ISSN 0098-1354. doi:10.1016/0098-1354(95)87103-9. European Symposium on Computer Aided ProcessEngineering 3-5.

H. Millar. The impact of rolling horizon planning on the cost of industrial fishingactivity. Computers & Operations Research, 25(10):825 – 837, 1998. ISSN 0305-0548.doi: 10.1016/S0305-0548(98)00023-9.

176

Bibliography

C. A. Méndez and J. Cerdá. An milp-based approach to the short-term scheduling ofmake-and-pack continuous production plants. OR Spectrum, 24:403–429, 2002. ISSN0171-6468. 10.1007/s00291-002-0103-5.

N

U. Neuhaus. Reaktive Planung in der chemischen Industrie: Verfahren zur operativenPlananpassung für Mehrzweckanlagen. Produktion Und Logistik. Gabler, 2008. ISBN9783834910684.

U. Neuhaus and H.-O. Günther. Development of a reactive scheduling system forapplication in the process industry. In V. Botta-Genoulaz, editor, ILS2006,Proceedings of the First International Conference on Information Systems, Logisticsand Supply Chain, Lyon, France, May 14-17 2006.

O

I. M. Ovacik and R. Uzsoy. Decomposition Methods for Complex Factory SchedulingProblems. Kluwer Academic Publishers, 1997.

P

A. Pfeiffer, B. Kádár, and L. Monostori. Stability-oriented evaluation of reschedulingstrategies, by using simulation. Computers in Industry, 58(7):630 – 643, 2007. ISSN0166-3615. doi: 10.1016/j.compind.2007.05.009. Performance Measurement SpecialIssue.

I. N. Pujawan. Schedule nervousness in a manufacturing system: a case study.Production Planning & Control, 15(5):515–524, 2004. doi:10.1080/09537280410001726320.

Q

D. Quadt and H. Kuhn. Capacitated lot-sizing with extensions: a review. 4OR: AQuarterly Journal of Operations Research, 6:61–83, 2008. ISSN 1619-4500.10.1007/s10288-007-0057-1.

177

Bibliography

RP. Robinson, A Narayanan, and F. Sahin. Coordinated deterministic dynamic demandlot-sizing problem: A review of models and algorithms. Omega, 37(1):3 – 15, 2009.ISSN 0305-0483. doi: 10.1016/j.omega.2006.11.004.

J. Roslöf, I. Harjunkoski, T. Westerlund, and J. Isaksson. Solving a large-scaleindustrial scheduling problem using milp combined with a heuristic procedure.European Journal of Operational Research, 138(1):29 – 42, 2002. ISSN 0377-2217.doi: 10.1016/S0377-2217(01)00140-0.

SI. Sabuncuoglu and M. Bayiz. Analysis of reactive scheduling problems in a job shopenvironment. European Journal of Operational Research, 126(3):567 – 586, 2000.ISSN 0377-2217. doi: 10.1016/S0377-2217(99)00311-2.

N. J. Samsatli, L. G. Papageorgiou, and N. Shah. Robustness metrics for dynamicoptimization models under parameter uncertainty. AIChE Journal, 44(9):1993–2006,1998. ISSN 1547-5905. doi: 10.1002/aic.690440907.

C. Schneeweiß. Planung: Band 2: Konzepte Der Prozeb- Und Modellgestaltung.Springer-Lehrbuch. Springer, 1992. ISBN 9783540551751.

A. Scholl. Robuste Planung und Optimierung. Physica-Verlag Heidelberg, 2001.

S. Sethi and G. Sorger. A theory of rolling horizon decision making. Annals ofOperations Research, 29:387–415, 1991. ISSN 0254-5330. 10.1007/BF02283607.

C. A. Soman, D. P. van Donk, and G. Gaalman. Combined make-to-order andmake-to-stock in a food production system. International Journal of ProductionEconomics, 90(2):223 – 235, 2004. ISSN 0925-5273. doi:10.1016/S0925-5273(02)00376-6. <ce:title>Production Planning andControl</ce:title>.

V. Sridharan, W. L. Berry, and V. Udayabhanu. Freezing the master productionschedule under rolling planning horizons. Management Science, 33(9):pp. 1137–1149,1987. ISSN 00251909.

H. Stadtler. Hierarchische Produktionsplanung Bei Losweiser Fertigung.Physica-Schriften Zur Betriebswirtschaft. Physica-Verlag, 1988. ISBN 9783790804010.

L. Stauffer and T. M. Liebling. Rolling horizon scheduling in a rolling-mill. Annals ofOperations Research, 69(0):323–349, 1997.

M. Steven. Hierarchische Produktionsplanung. Physica-Lehrbuch. Physica-Verlag, 1994.ISBN 9783790807561.

178

Bibliography

TE. A . V. Toso, R. Morabito, and A. R. Clark. Lot sizing and sequencing optimisationat an animal-feed plant. Computers & Industrial Engineering, 57(3):813 – 821, 2009.ISSN 0360-8352. doi: 10.1016/j.cie.2009.02.011.

VP. van Dam, G. J. C. Gaalman, and G. Sierksma. Scheduling of packaging lines in theprocess industry: An empirical investigation. International Journal of ProductionEconomics, 30-31(0):579 – 589, 1993. ISSN 0925-5273. doi:10.1016/0925-5273(93)90123-3. Special Issue Proceeding of the Seventh InternationalWorking Seminar on Production Economics.

P. van Dam, G. J. C. Gaalman, and G. Sierksma. Designing scheduling systems forpackaging in process industries: A tobacco company case. International Journal ofProduction Economics, 56-57(0):649 – 659, 1998. ISSN 0925-5273. doi:10.1016/S0925-5273(98)00048-6. <ce:title>Production Economics: The LinkBetween Technology And Management</ce:title>.

D. P. van Donk. Make to stock or make to order: The decoupling point in the foodprocessing industries. International Journal of Production Economics, 69(3):297 –306, 2001. ISSN 0925-5273. doi: 10.1016/S0925-5273(00)00035-9.

J. T. M. van Sonsbeek, P. van Beek, H. A. P. Urlings, P. G. H. Bijker, and J. F. L.Hagelaar. Mixed integer programming for strategic decision support in the slaughterby-product chain. OR Spectrum, 19:159–168, 1997. ISSN 0171-6468.10.1007/BF01545519.

W. M. C. van Wezel. Tasks, hierarchies, and flexibility : planning in food processingindustries. 2001.

G. E. Vieira, J. W. Herrmann, and E. Lin. Rescheduling manufacturing systems: Aframework of strategies, policies, and methods. Journal of Scheduling, 6:39–62, 2003.ISSN 1094-6136. 10.1023/A:1022235519958.

J. P. Vin and M. G. Ierapetritou. A new approach for efficient rescheduling ofmultiproduct batch plants. Industrial & Engineering Chemistry Research, 39(11):4228–4238, 2000. doi: 10.1021/ie000233z.

WS. D. Wu, E.-S. Byeon, and R. H. Storer. A graph-theoretic decomposition of the jobshop scheduling problem to achieve scheduling robustness. Operations Research, 47(1):pp. 113–124, 1999. ISSN 0030364X.

179

Bibliography

Z

X. Zhu and W. E. Wilhelm. Scheduling and lot sizing with sequence-dependent setup:A literature review. IIE Transactions, 38(11):987–1007, 2006. doi:10.1080/07408170600559706.

180

Documents

Evolutionary production planning and scheduling - TU · PDF fileEvolutionary production planning and scheduling vorgelegt von Dipl.-Ing. Andreas Schöpperl aus Berlin von der Fakultät