Sequencing and Sorting in Just-In-Time Production

BTU Cottbus
Institut für Mathematik

Sequencing and Sorting in Just-In-Time Production

Diplomarbeit

eingereicht von

Robert Nickel

2004

Contents

1. Introduction
1.1 Problem Formulation and Simplification
1.1.1 Simplification
1.1.2 History of the Subproblems
1.2 Structure of this Work
1.3 Notations

2. Assembly Line Balancing
2.1 Objectives on Leveled Words
2.2 A Simplified Problem: Maximum Deviation Just-In-Time Scheduling
2.3 A Model and an Integer Program
2.4 Complexity Results
2.4.1 NP-complete Cases
2.4.2 Polynomial Cases
2.5 Solution Approaches
2.5.1 Exact Approaches
2.5.2 Heuristic Approaches

3. Reduction of Color Changes
3.1 Previous Work
3.2 Weak Balance of a Sequence
3.3 A Model and an Integer Program
3.4 Solution Approaches
3.4.1 Exact Approaches
3.4.2 Heuristic Approaches

4. Combining the Subproblems with the Buffer
4.1 Theoretical Background
4.2 Re-sorting the Paint Shop Sequence to an Assembly Line Sequence
4.3 Re-sorting an Assembly Line Sequence to a Paint Shop Sequence

5. Computational Results
5.1 Distance Constraint Balancing
5.2 Weakly Balanced Color Reduction
5.3 PS2AL versus AL2PS

6. Returning to Practice
6.1 Basic Concepts
6.1.1 Plant Layout
6.1.2 Routing Pattern
6.1.3 Rules
6.2 Sequence Construction
6.2.1 Clustering into Slots
6.3 Suggestions for Real World Production Plants

7. Conclusions

Bibliography

Introduction

Since Karl Benz built the first motor driven vehicle in 1886 a new industry was born which is still one of the most important and influential sectors of economy. His 0.9 horse-power engine only reached 15 kilometers per hour but gave the starting shot for more and more inventions and a rapidly growing automobile industry. First cars where used for racing only but during the first period of the twentieth century it established its position as a new and individual means of transport. In 1936 the first Volkswagen called Beetle, a vehicle for the masses, was developed by Ferdinand Porsche and has been produced for 67 years. The last Beetle was built in the summer of 2003 in Mexico.

Worldwide 100.000 new cars are being produced every day and in 2010 there will be over 1 billion private cars all over the world. This development requires perfectly organized and well optimized production processes and still calls for new inventions and improvements.

The production process in automobile manufacturing splits into three major stages. The moulding and welding of the car body in the body shop, the painting of the welded car bodies in the paint shop and the customization of the painted car bodies in the assembly shop.

The work presented here deals with the last two stages. The production plant contains a system of production lines which sometimes split into parallel lines and reunite to a non-parallel line. Each of these lines can require some set of restrictions on the cars sequenced on that line.

In the paint shop the cars are being painted on a line by a robot which through jets sprays the color onto the surface of the car body. Whenever the next car on the line has the same color the jets can be re-used. Otherwise they have to be cleaned which requires time and causes pollution. Therefore, minimizing the color changes that occur in the paint shop can save non negligible costs.

In the assembly shop separate teams install different options into the cars such as sun-roof, air-conditioning, central locking system etc. Therefore the order of the cars on the line has to fulfill some restrictions considering that each option requires a fixed time for installation and resources which have to be available at the time of installation.

Between the stages of manufacturing we can make use of some kind of storage system to re-sort cars that leave the paint shop such that the resulting ordering fulfills the requirements of the assembly shop. Furthermore during the production process we have to cope with sudden perturbations caused by manufacturing errors. The storage systems can be used to recover the sequence after an error.

One example of such a storage system is the main subject of this thesis: a buffer between paint shop and assembly shop that can hold a fixed number of cars and allows to move any contained car from the buffer to the assembly line. We analyze the problem of how such a buffer can be used to save costs at the paint shop, i.e. to reduce the color changes on each paint shop line. On the other hand we still want to keep the quality requirements for the assembly shop. The buffer will act as a re-sorter of cars leaving the paint shop. We will follow three major steps:

1. Formulate the requirements of the assembly shop and present solution strategies
2. Formulate the requirements of the paint shop by keeping in mind teat the ordering of cars should not alter too much from a potential ordering for the assembly shop and present solution strategies
3. Analyze the capabilities of the buffer, define the term re-sortability′′ and combine the solution strategies from 1. and 2.

[...]