Capacitated Lot-Sizing and Scheduling with Scarce Setup Resources E-Book

Karina Copil

• Herausgeber: Books on Demand
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 323

Veröffentlichungsjahr: 2016

Beschreibung

Lot-sizing and scheduling problems can be found in all companies producing multiple products with sequence-dependent setups. Thereby, company and industry specific aspects often exist which restrict the production periods and quantities. The generation of cost-minimal and feasible productions plans with respect to the available capacity and the given restrictions can create possible savings and therefore has a great influence on the profitability of a company. This thesis focuses on simultaneous lot-sizing and scheduling problems with scarce setup resources. These are shared by multiple production machines and thus restrict the possible starting and ending times of the corresponding operations. Further practical aspects are incorporated including inter alia alternative production machines and setup resources, batch-production or shelf-life restrictions. The thesis provides mathematical formulations for these problems and presents MIP-based heuristics as well as a metaheuristic to solve problems of practical size. This book addresses practitioners from the industry, developers and consultants in the field of supply chain management and production or operations research as well as students and lecturers in business studies, information systems or industrial engineering with a focus on supply chain management.

Leseprobe

PREFACE

This book was accepted as a PhD thesis in January 2016 and it was written during my employment at the department of Supply Chain Management and Production at the University of Cologne. I would like to thank all my supporters who made this thesis possible and who contributed so much to this thesis with their professional and personal advices, emotional support during all circumstances and their friendship.

First of all, I would like to thank my advisor Prof. Dr. Horst Tempelmeier who gave me an understanding about lot-sizing already during my academic studies. The freedom for my scientific work, his ongoing support and guidance, constructive discussions and his high standards combined with his profound knowledge and humor made my time at the department and writing this thesis an interesting, challenging and enriching experience. I would also like to thank Prof. Dr. Ulrich W. Thonemann for being the co-referee of my thesis and Prof. Dr. Ludwig Kuntz for being the chairman of my disputation. Furthermore, I would like to thank Prof. Dr. Herbert Meyr and Martin Wörbelauer for the fruitful and outstanding joint research.

This thesis would not be the same without all my colleagues during the employment at the department. I thank my former and current colleagues Dr. Johannes Antweiler, Dr. Oliver Bantel, Sascha Düerkop, Dr. Sascha Herpers, Dr. Timo Hilger, Michael Kirste, Prof. Dr. Svenja Lagershausen, Prof. Dr. Michael Manitz, Julia Mindlina and Manuela Pioch for their support, their advices and most of all for the wonderful and enriching atmosphere at the department. I am particularly grateful for the help of my colleagues and friends Sascha Düerkop, Dr. Timo Hilger, Julia Mindlina and Michael Kirste who proofread my thesis, discussed the results and shared with me a lot of gorgeous memories outside the time at the department. I also thank Dr. Johannes Antweiler for always having an open ear and also supporting and understanding me in all situations of life. With his tireless commitment for the department, he always covered the backs of all members and allowed an atmosphere of productivity, comfort and friendship. I have had the pleasure to work in an amazing team which brought me joy, happiness and very good friends. Furthermore, I would like to thank Dr. Gabriele Reith-Ahlemeier, Philipp Heene, Dirk van Bergen and Guido Volkmann for their support and advices during all phases but particularly at the beginning of my dissertation.

Special thanks go to Deborah Schächtele who has supported me with her friendship in all possible ways already for half of my life. We have been together in so many good and bad times and can share a lot of wonderful and unforgettable memories. On my very first day at the university, I met Fabian Stein and he has shown to be a true and loyal friend since then. I thank him for his friendship, for being such a good listener and for continuously reminding me to take a break once in a while. Further, I also thank my friends Kathrin Beringer, Heide Haas, Dr. Victor Mauri, Melanie Meyer, Dr. Raik Öczen, Katrin Posch, Jutta Rosenstein, Birgit Schorn, Inge Vogt and Dr. Vera Weingärtner for their support, open ears and many amazing moments.

Christoph Czerwinski especially strengthened my back and showed me to take only one step at a time during the final and exhausting months of finishing my PhD thesis. He always makes me smile with his Cologne lifestyle, his great dancing skills and most of all with his enduring love and patience. I thank him so much for the strong emotional backing and great understanding he gave me during this hard time.

Finally, I thank my beloved family for supporting and encouraging me during my whole life. My parents made studying in this great city Cologne possible in the first place and they have always supported me in every possible way. They have tried to quench my thirst for knowledge, picked me up in hard times and shared my joy in good times. I thank my brother for hilarious childhood memories and my grandmothers for pampering me and providing me with great food.

Cologne, March 2016.

CONTENTS

List of Figures

List of Tables

List of Abbreviations

List of Symbols

1 Introduction

2 Lot-Sizing in Operational Production Planning

2.1 Successive Production Planning

2.2 Hierarchical Capacitated Production Planning

3 Literature Review of Lot-Sizing and Scheduling Models

3.1 Characteristics of Lot-Sizing and Scheduling Models

3.2 Small-Bucket Models

3.2.1 Discrete Lot-Sizing and Scheduling Problem

3.2.2 Continuous Setup and Lot-Sizing Problem

3.2.3 Proportional Lot-Sizing and Scheduling Problem

3.3 Big-Bucket Models

3.3.1 Capacitated Lot-Sizing Problem with Linked Lot-Sizes and Sequence-Dependent Setups

3.3.2 General Lot-Sizing and Scheduling Problem

3.4 Other Models

3.5 Summary and Analysis

4 Lot-Sizing and Scheduling with Common Setup Resources

4.1 PLSP with a Common Setup Resource

4.2 CLSD with Common Setup Operators

4.2.1 CLSD with a Common Setup Operator

4.2.2 CLSD with a Common Setup Operator and Multiple Lots

4.2.2.1 Virtual Products

4.2.2.2 Multiple Sub-Periods per Macro-Period

4.2.3 CLSD with a Common Setup Operator and Parallel Machines

4.2.4 CLSD with a Common Setup Operator and Batch-Production

4.2.5 CLSD with a Common Setup Operator and Shelf-Life Constraints

4.2.6 CLSD with Parallel Common Setup Operators

4.2.7 CLSD with Common Setup Operators and Multiple Production Steps

4.2.7.1 One Common Setup Operator

4.2.7.2 Parallel Common Setup Operators

5 Solution Approaches for the CLSD

CSR

and its Extensions

5.1 MIP-Based Heuristics

5.1.1 Fix-and-Optimize Heuristic

5.1.2 Fix-and-Relax Heuristic

5.2 Variable Neighborhood Search

5.2.1 General Structure of the Algorithm

5.2.2 Problem-Specific Program Structure

5.2.3 Calculation of Starting and Ending Times for Setups

5.2.3.1 Production Process with One Production Step

5.2.3.2 Production Process with Multiple Production Steps

5.2.4 Initial Solution

5.2.5 Improving the Solution with Moves

5.2.5.1 Moving a Lot to an Earlier Period

5.2.5.2 Moving a Lot to a Later Period

5.2.5.3 Moving a Random Part of a Lot to the Next Period

5.2.5.4 Swapping the Sequence of Two Lots to Improve the Setup Costs

5.2.5.5 Swapping the Positions of Two Lots to Improve the Setup Sequence of the Setup Operator

5.2.5.6 Moving a Lot to Another Machine within the Same Period

5.2.5.7 Changing the Setup Operator

6 Computational Study

6.1 Structure of the Experimental Data

6.2 Numerical Analysis of the Models with CPLEX

6.2.1 Comparison of the Models CLSD

CSR

and PLSP

CSR

6.2.2 Analysis of the Model CLSDCSR

6.2.3 Numerical Results for the Extensions

6.2.3.1 Parallel Machines

6.2.3.2 Batch-Production

6.2.3.3 Time Windows

6.2.3.4 Parallel Common Setup Resources

6.2.3.5 Multiple Production Steps

6.2.3.6 Multiple Lots

6.3 Numerical Analysis of the Heuristic Solution Approaches

6.3.1 Configurations of the Heuristics

6.3.1.1 Configuration of the MIP-based Heuristics

6.3.1.2 Configuration of the VNS

6.3.2 Computing Time

6.3.3 Feasibility

6.3.4 Solution Quality

6.3.5 Recommendation for the Use of the Heuristics

6.4 Impact of Integrated Planning

7 Conclusions

Bibliography

LIST OF FIGURES

2.1 Successive production planning system

2.2 Hierarchical capacitated production planning system

3.1 Problem structure of lot-sizing models

3.2 Product structures

4.1 Production plan without a CSR

4.2 Production plan with a CSR

4.3 Production plan with multiple lots of the same product

4.4 Redefinition of the data to allow multiple lots

4.5 Redefinition of the data for parallel machines

4.6 Production plan with a CSR and batch-production

4.7 Production plan with one CSR

4.8 Production plan with two CSR

4.9 Production plan with a CSR and three production steps

4.10 Production plan with two CSR and three production steps

5.1 Initial solution for the Fix-and-Optimize heuristic

5.2 Fixing and optimizing decision variables

5.3 Fix-and-Optimize heuristic

5.4 Fixing and relaxing decision variables

5.5 Local and global optima

5.6 Calculation of setup dates with max{lastactionm[m], lastactiono[o]}

5.7 Calculation of setup dates using idle times

5.8 Scenarios for overlapping setups

5.9 Standard initial solution

5.10 Initial solution with changing machines

5.11 Moving a complete lot to an earlier period - product is already produced

5.12 Moving a complete lot to an earlier period - machine is in the right setup state

5.13 Moving a complete lot to an earlier period - setup carry-over for last product

5.14 Moving a complete lot to an earlier period - product does not exist

5.15 Moving a part to an earlier period - product is already produced

5.16 Moving a part to an earlier period - machine is in the right setup state

5.17 Moving a part to an earlier period - setup carry-over for last product

5.18 Moving a part to an earlier period - product does not exist

5.19 Changing positions to improve the setup sequence

6.1 Average gap for different numbers of machines and TBOs

6.2 Costs derived by CPLEX for the model CLSDCSR

6.3 Number of cleaning operations (TBO=10)

6.4 Costs derived by CPLEX for the model CLSDPCSR (TBO=10)

6.5 Costs derived by CPLEX for multiple lots and virtual products (TBO=10)

6.6 Number of feasible solutions in CTHeuristic

6.7 Number of feasible solutions derived by CPLEX and the VNS in CTHeuristik depending on the utilization

6.8 Average deviation in CTHeuristic

LIST OF TABLES

3.1 Attributes, characteristics and acronyms

3.2 Acronyms for industrial settings

3.3 Symbols used in model DLSP

3.4 Literature overview of model DLSP

3.5 Symbols used in model CSLP

3.6 Literature overview of model CSLP

3.7 Symbols used in model PLSP

3.8 Literature overview of model PLSP

3.9 Symbols used in model CLSD

3.10 Literature overview of model CLSD

3.11 Symbols used in model GLSP

3.12 Literature overview of model GLSP

3.13 Literature overview of other models

4.1 Symbols used in model PLSPCSR

4.2 Symbols used in model CLSDCSR

4.3 Symbols used in model CLSD-MLSPCSR

4.4 Symbols used in model CLSD-BCCSR

4.5 Symbols used in model CLSDPCSR

4.6 Symbols used in model CLSD-MPSCSR

4.7 Modified symbols used in model CLSD-MPSPCSR

6.1 Parameters of the data set

6.2 Comparison between the model PLSPCSR and CLSDCSR

6.3 Comparison between TBO=2 and TBO=10

6.4 Numerical results of CPLEX for parallel machines

6.7 Numerical results of CPLEX for parallel common setup operators

6.8 Numerical results of CPLEX for multiple lots with sub-periods

6.9 Numerical results of CPLEX for multiple lots with virtual products

6.10 Time limits L for the MIP-based heuristics

6.11 Configuration of the VNS

6.12 Average computing time in seconds

6.13 Best solution approaches depending on the problem size

LIST OF ABBREVIATIONS

AFI

Animal Food Industry

AI

Automobile Industry

APS

Advanced Planning System

ATSP

Asymmetric Traveling Salesman Problem

BA

Backward-oriented heuristic

BACKADD

Backward-oriented, regret-based, biased random sampling method

BC

Batch-production with variable cleaning times

B&B

Branch&Bound

B&C

Branch&Cut

BI

Beverage Industry

BOM

Bill-of-materials

BVNS

Basic Variable Neighborhood Search

CG

Column Generation

CGI

Consumer Goods Industry

CHES

DuPont, BASF, James River, Champion International (practical problems which are not dedicated to a specific industry, see Baker and Muckstadt Jr. (1989))

CLSD

Capacitated Lot-Sizing Problem with Linked Lot-Sizes and Sequence-Dependent Setups

CLSD

CSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups and a common setup resource

CLSD

PCSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups and parallel common setup resources

CLSD

sub

CSR

Subproblem generated by decomposition of the Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups and a common setup resource

CLSD-BC

CSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups, a common setup resource and batch-production associated with variable cleaning times

CLSD-ML

SP

CSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups and a common setup resource allowing multiple lots modeled with sub-periods

CLSD-MPS

CSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups, multiple production steps per machine and a common setup resource

CLSD-MPS

PCSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups, multiple production steps per machine and parallel common setup resources

CLSP

Capacitated Lot-Sizing Problem

CLSP-L

Capacitated Lot-Sizing Problem with Linked Lot-Sizes

CLSP-L-SD

Capacitated Lot-Sizing Problem with Linked Lot-Sizes and Sequence-Dependent Setups

CLSP-L-SD-CSR

Capacitated Lot-Sizing Problem with Linked Lot-Sizes, Sequence-Dependent Setups and a common setup resource

CPUTime

Function which provides the passed computing time of the VNS

CSLP

Continuous Setup and Lot-Sizing Problem

CSR

Common setup resource

CI

Chemical Industry

CT

CPLEX

Computing time for an instance with CPLEX

CT

Heuristic

Computing time for an instance with a Heuristic

DLSP

Discrete Lot-Sizing and Scheduling Problem

DP

Dynamic Programming

DS

Demand Shuffle

EI

Electronics Industry

Eq.

Equations

ERP

Enterprise Resource Planning System

FI

Food Industry

F&O

Fix-and-Optimize

F&R

Fix-and-Relax

GA

Genetic Algorithm

GLSP

General Lot-Sizing and Scheduling Problem

GLSPCS

General Lot-Sizing and Scheduling Problem with conservation of setup state

GLSPLS

General Lot-Sizing and Scheduling Problem with loss of setup state

GLSPMS

General Lot-Sizing and Scheduling Problem with multiple production stages

GLSPPL

General Lot-Sizing and Scheduling Problem with parallel lines

GLSPST

General Lot-Sizing and Scheduling Problem with setup times

GRASP

Greedy Randomized Adaptive Search Procedure

GVNS

General Variable Neighborhood Search

HLSA

Hybrid Lagrangean-Simulated Annealing-based heuristic

HOPS

Hamming-Oriented Partition Search

INS

Iterative Variable Neighborhood Search

INSRF

Iterative Variable Neighborhood Search with a Relax-and-Fix construction heuristic

LD

Lagrangean Decomposition

LP

Linear Programming

LR

Lagrangean Relaxation

LS

Local Search

MA

Memetic Algorithm

ML

Multiple lots

MPS

Multiple production steps per maschine

MIP

Mixed Integer Programming

MRP

Material Requirements Planning

MRP II

Material Resource Planning

NP

Nondeterministic polynomial time

nPM

Number of parallel (alternative) machines to produce a product

nSP

Number of sub-periods per macro-period

nVP

Number of virtual products per (end-)product

PCSR

Parallel common setup resources

PhI

Pharmaceutical Industry

PI

Process Industry

PLSP

Proportional Lot-Sizing and Scheduling Problem

PLSP

CSR

Proportional Lot-Sizing and Scheduling Problem with a common setup resource

POST1

PLSP with period overlapping setup times 1

POST2

PLSP with period overlapping setup times 2

PSO

Particle Swarm Optimization

P1SMM

Single-stage multi-machine lot-scheduling model

P2SMM

Two-stage multi-machine lot-scheduling model

RH

Rolling Horizon

RM

Randomized Measures

RR

Randomized Regrets

S

Seconds

SA

Simulated Annealing

SI

Semiconductor Industry

SP

Sub-period

SPL

Simple Plant Location

SPP

Set Partitioning Problem

SITLSP

Synchronized and Integrated Two-Level Lot-Sizing and Scheduling Problem

STN

State-Task-Network

TA

Threshold Accepting

TBO

Time Between Orders

TS

Tabu Search

TSP

Traveling Salesman Problem

TSPTW

Traveling Salesman Problem with Time Windows

UB

Upper bound

VND

Variable Neighborhood Descent method

VNDS

Variable Neighborhood Decomposition Search

VNS

Variable Neighborhood Search

LIST OF SYMBOLS

Indices

Sets:

Parameters/Data:

b

s

Capacity of the production machine in micro-period

s

(time)

b

m

s

Capacity of the production machine

m

in micro-period

s

(time)

b

O

s

Capacity of the setup operator in micro-period

s

(time)

b

t

Capacity of the production machine in macro-period

t

(time)

bs

k

Batch-size of product

k

(units)

c

k

Minimum shelf life\quarantine time of product

k

(periods)

d

Average demand

d

ks

Demand of product

k

in micro-period

s

(units)

d

kt

Demand of product

k

in macro-period

t

(units)

hc

Average inventory holding costs

hc

k

Inventory holding costs for product

k

(per unit and period)

H

Large number

I

shake-max

η

Maximum number of repetitions for executing the

Shake-

function

lc

k

Penalty costs for lost sales for product

k

(per unit and period)

L

Time limit for the solution of a sub-problem

nm

max

η

Maximum number of repetitions for a move

η

in a row

nl

m

Number of production steps on machine

m

pc

k

Standby costs for preserving the setup state of product

k

(per unit and period)

p

f

t

First sub-period in macro-period

t

(

p

f

t

∈

P

t

)

q

min

Minimum lot-size (units)

s

sub

Sub-problem ∈

Sub

sc

Average setup costs

sc

k

Setup costs for a changeover to product

k

sc

ik

Setup costs for a changeover from product

i

to product

k

sc

oik

Setup costs for a changeover from product

i

to product

k

performed by setup operator

o

t

max

Time limit for the Variable Neighborhood Search heuristic

tc

k

Cleaning time per batch of product

k

tp

k

Production time of product

k

(per unit)

tp

ℓk

Production time of product

k

for production step

ℓ

(per unit)

t

opt

Optimal length of the production cycle

ts

ik

Setup time for a changeover from product

i

to product

k

ts

ℓik

Setup time for a changeover from product

i

to product

k

for production step

ℓ

ts

oik

Setup time for a changeover from product

i

to product

k

performed by setup operator

o

ts

oℓik

Setup time for a changeover from product

i

to product

k

for production step

ℓ

performed by setup operator

o

U

Utilization

z

k

Maximum shelf-life of product

k

(periods)

α

Time units to shift setups

λ

Length of a time window (periods)

ξ

Number of periods for shifting the time window forward

φ

Dummy product for the initial solution of the Fix-and-Optimize heuristic

σ

Standard deviation of a normal distribution

µ

Mean value of a normal distribution

ikt

Predefined value of the setup variable

ikt

for a setup from product

i

to

k

in macro-period

t

kt

Predefined value of the setup state variable

kt

for product

k

at the beginning of macro-period

t

Variables:

CHAPTER

ONE

INTRODUCTION

Technological progress and an increasing competition on the market demand for improved methods to solve lot-sizing and scheduling problems. To gain an advantage by generating feasible and cost-optimal production plans, particularly practical aspects have to be incorporated into the solution approaches. An overview of literature for simultaneous lot-sizing and scheduling problems shows that an increasing number of publications exists handling practical problems with additional constraints. In this context, additional scarce resources or bottleneck procedures exist which need a synchronization of production or setup operations.

In some companies, setups on different production machines are carried out by specialized machines or a limited number of workers. As these machines or workers can carry out only one setup at a time, waiting times occur on other machines sharing the same setup resource. In practice, production plans are usually generated neglecting the common setup resource. However, this approach may cause unnecessary waiting times or even delays which again can lead to costs for adjustments, lost sales, customer dissatisfaction or penalty costs. This means that the lot-sizing and scheduling problem must be simultaneously solved with a synchronization of the setups in order to generate feasible production plans in terms of the available capacity and to avoid overlapping of setups with respect to the setup resource.

Lot-sizing problems often occur in manufacturing companies if multiple products are produced on the same machine. The machine must be prepared for a new product by for instance cleaning the machine or changing tools. This setup operation is usually linked to setup times and setup costs. In literature and practice, the latter often represent concrete costs for material or labor as well as opportunity costs as the machine cannot continue the production during a setup. To decrease the number of setups, demands for different periods can be combined to one production order, which is called a lot. However, this involves the production of a later demand quantity that must be stored until its due date which again is linked to inventory holding costs. Hence, the lot-sizing problem handles the optimization problem of deciding ”how many parts to make at once”1 by searching for the best trade-off between decreasing the number of setups and simultaneously saving inventory holding costs. In addition, the available capacity of a production machine usually is limited for example by the length of a shift or period in general. Therefore, a feasible production plan defines the production quantities in a way that the demand is fulfilled on time, the capacity is not exceeded and setup as well as inventory holding costs are minimized.

In some cases, setup times and costs depend on the preceding product, i.e. they are sequence-dependent. Examples can be found in the food industry or in companies producing paints. For instance a cleaning of the machine for the color white after producing the color black is usually more expensive and time consuming than cleaning for black after the lighter color white. In the food industry, this problem can be of importance if products which are dangerous to health are involved. For example peanuts can evoke allergic reactions. A thorough cleaning is necessary which may be linked to long setups and high costs. This means that the sequence of products has a high influence on the total costs and therefore, the lot-sizing and scheduling problems have to be simultaneously solved in order to generate feasible production plans and to minimize the total costs.

Despite its high relevance and although this problem can be found in several companies, hardly any publication exists which considers scarce setup resources. Since the consideration of common setup operators is crucial for the generation of feasible and improved production plans, this dissertation focuses on scarce setup resources for lot-sizing and scheduling problems. A German company from the food industry is the basis for the applications described in this thesis. In the underlying production facility, setups are performed by a limited number of specialized and expensive cleaning machines. Several additional characteristics resulting from the production machines or the food processing have to be considered and are integrated into the proposed approaches. In this thesis, a big bucket model for the Capacitated Lot-sizing Problem with linked lot-sizes, multiple machines and sequence-dependent setups (CLSD) is formulated which considers scarce setup resources.2 This model is extended by additional selected characteristics from the food company to formulate and solve the underlying problems more precisely. These include the following characteristics. Multiple lots of the same product are usually forbidden as they are linked to unnecessary additional costs. However, the common setup operator is an additional scarce resource and allowing multiple setups per product may lead to feasible plans considering the limited capacity of the scarce setup resource. Therefore, modeling approaches are presented allowing multiple lots for each product per period. In addition, parallel machines and batch-production can be found and time windows for the production have to be considered due to shelf-life restrictions or quality controls. Furthermore, one or multiple setup operators are available for different groups of production machines. Finally, the production machines have to perform different production steps each linked to a setup.

All models are implemented with OPL and solved with ILOG CPLEX 12.6. As the solution for larger instances of practical relevance is linked with long computing times, different heuristic solution approaches are presented. First, two MIP-based heuristics are developed based on the Fix-and-Optimize heuristic by Helber and Sahling (2010) and a Fix-and-Relax heuristic which amongst others is presented by Dillenberger et al. (1994). Since the resulting sub-problems are still very complex especially with respect to the additional problem aspects, an alternative meta-heuristic is developed to solve instances of practical size. The underlying Variable Neighborhood Search procedure picks up ideas from Mladenović and Hansen (1997).

At the beginning of this thesis, production planing concepts are introduced and the lot-sizing problem is placed into these systems in chapter two. Afterwards, basic models for the simultaneous lot-sizing and scheduling problem are presented and a detailed review and classification of the corresponding model formulations found in the literature is given in chapter three. Model formulations for the PLSP and CLSD considering common setup operators are presented in chapter four. Based on the practical case from the underlying German company, several additional extensions are developed and formulated in this chapter. For the solution of larger instances, heuristic solution approaches are described in chapter five. Hereby, it is differentiated between MIP-based and metaheuristics. Chapter 6 provides a detailed numerical analysis of the results derived by CPLEX and the presented heuristic solution approaches for all problem aspects. A data set of 108 different instances is generated for the analysis of computing times, feasibility and solution quality. Based on the results of the heuristics, the suitability of the heuristics is derived afterwards. Finally, the impact of the integrated planning approach presented in this thesis is demonstrated by solving the instances with an iterative approach.

1Harris (1913).

2See also Tempelmeier and Copil (2015).

CHAPTER

TWO

LOT-SIZING IN OPERATIONAL PRODUCTION PLANNING

Content

2.1 Successive Production Planning2.2 Hierarchical Capacitated Production Planning

In order to consider lot-sizing in the context of production planning, two different concepts for the production planning are presented in this chapter. In general, it can be distinguished between different planning levels.3 In the long-term or strategic planning, basic conditions for an enterprise are generated comprising for example the structure of an enterprise, the locations of factories, the selection of products and suppliers or the introduction of new complex production techniques. The mid-term (tactical) planning aims at meeting the resulting targets by for instance defining a general production programme or defining the layout of a factory. In the short term planning, also called operational planning, production processes are planned and controlled using the available capacities resulting from the preceding levels.

Lot-sizing is a part of the operational planning. The operational production planning can be supported by computer-aided production planning systems which are usually part of a so called Enterprise Resource Planning System (ERP).4 Most systems used in practice correspond to a successive production planning concept which is also known as Material Resource Planning (MRP II).5 This concept is an advancement of the earlier Material Requirements Planning (MRP) as some new functions are added. The MRP II concept will shortly be described in chapter 2.1. Since it may involve imprecise planning results, an alternative capacitated production planning concept following a hierarchical structure, will be presented in chapter 2.2.

2.1 Successive Production Planning

The successive production planning concept (MRP II) comprises the following four levels which are illustrated in Figure 2.1.6

Master Production Scheduling: In the first level, the primary demand for important end-products or spare parts is determined for a planning horizon of three to twelve months by synchronizing the demand with the production quantities.

Material Requirements Planning: The material requirement of a product is composed of a primary and a secondary demand which arises due to the demand of a successive product in case of a multi-level structure. The secondary demand is determined for each isolated subassembly by successively considering the complete demand of each succeeding product, respectively. Net requirements are determined by subtracting the available stock of inventory. Uncapacitated single-item heuristics are used to determine lot-sizes for each product based on the calculated net requirements.

Figure 2.1: Successive production planning system7

Scheduling: In the next level, the earliest and latest starting and ending times for each operation of the production process are determined within the lead time scheduling. The material requirements planning provides due dates for the scheduling. Afterwards, the capacity requirements resulting from the preceding decisions are calculated. As capacities have been neglected in the previous planning steps, the capacity requirements may exceed the available capacity. Therefore, capacity requirements have to be adjusted by using overtime or shifting production quantities in order to avoid an exceeding of the available capacity.

Production Control: Finally, production orders are released and assigned to resources in the last level. Also, the detailed sequence is determined.

For the coordination of materials and information along the complete supply chain, so called Advanced Planning Systems (APS) are used.8 They include several additional functions which support or integrate, inter alia, the network design, transportation and distribution planning, forecasting methods or functions such as replenishment and vendor-managed inventory for purchase and procurement. The APS communicates with the internal ERP-system and gathers information from the material requirements planning. It also communicates with the APS and ERP-systems of other partners within the supply chain.

However, the Material Resource Planning concept used in practice has some flaws which are criticized for example by Drexl et al. (1994) or Günther and Tempelmeier (2014). In general, the MRP II rather enables an automation of manually performed processes but does not provide real planning tools. It does not differentiate between production segment specific problems but simplifies the problems and solution procedures to approach to as many problems as possible.

An aggregate planning is missing and the master production scheduling synchronizes the production quantities with the demand instead of balancing out capacities. In general, limited capacities are neglected on all planning levels which may lead to infeasible plans. Therefore, balancing capacity requirements after the lead time scheduling is necessary to generate feasible production plans. Though, this step is often manually performed and may be very complex or error-prone.

In addition, even if a product consists of a multi-level structure, lot-sizes are isolatedly determined for each subassembly without a consideration of cost or capacity interdependencies. This can raise very high total capacity requirements or costs. Thus, all products within a Bill-of-materials (BOM) structure should be simultaneously considered and the material requirement should result from the lot-sizes (instead of the other way round) to save costs and to generate a feasible production plan.