Capacitated Lot-Sizing and Scheduling with Scarce Setup Resources

By Karina Copil

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.

• Language: English
• Publisher: Books on Demand
• Release date: Mar 22, 2016
• ISBN: 9783741255175

Karina Copil

Karina Copil is employed at the Department of Supply Chain Management and Production at the University of Cologne, Germany.

Book preview

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.5 Numerical results of CPLEX for batch-production with bsk = 20, tck = 3

6.6 Numerical results of CPLEX for time windows with zk = 4, ck = 0

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

LIST OF SYMBOLS

Indices

Sets:

Parameters/Data:

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