Faim 2010 - Caricato Scribd

8/9/2019 Faim 2010 - Caricato Scribd

1/52

An improved patterngeneration procedure for thecutting stock problemAn application in a metal rolling rm

P. Caricato - A. GriecoUniversit del Salento - Lecce (Italy)

July 12-14, 2010

California State University, East Bay


2/52

Decision problemProduction coupling


3/52

Consider a set of orders for aluminum strip in coils,

characterized by

width (to be within a speci

ed tolerance range)

thickness (tolerance range)

required aluminum alloy

lubricant type (if any)

coil length

due date


4/52

Strip coils are manufactured from aluminum blocks

,which provide the input to the rolling process

Each order to be ful

lled is divided into positions

,further composed by schedule lines (di

erent duedates)

The length of a required strip is expressed as an integernumber called equivalent coils

Glossary


5/52

UnitA speci

c schedule line within a single position of a givenorder, with a quantity equal to the required equivalentcoils

Below are three units fromone order: 20090001two positions: 1 and 2 of the same orderthree schedule lines: two from the former position andone from the latter


6/52

Several orders, characterized by di

erent lengths, can becombined to better use the available aluminum blocks tobe rolled

This decision problem is referred to as coupling

As a result of the coupling process, groups of units areselected to be produced rolling a single block

Coupling allows an e

cient use of similarities existingamong di

erent units, in order to optimize theproduction process

Coupling


7/52

Main assumptions - Blocks

Aluminum blocks can be freely selected from a set of

standard widthsPractically unlimited blocks are available from eachstandard width (thanks to the internal foundry)

Blocks inventory problems are not treated (no inventory,make-to-order)


8/52

Main assumptions - Batches

The coupling problem is solved for homogeneousbatches of units

A homogeneous batch is formed by units requiring

the same aluminum alloy

the same lubricant typeUnits from di erent batches cannot be coupled


9/52


10/52

Thickness

The required thicknesses of the units to be coupled mustbe compatible

i.e. the intersection range must be larger than a giventechnology-related limit

Unit 1 [0,15 mm 0,25 mm]

Unit 2 [0,18 mm 0,28 mm]

Unit 3 [0,20 mm 0,25 mm]

Unit 4 [0,10 mm 0,17 mm]

Unit 5 [0,11 mm 0,18 mm]


11/52

Tech-rel limit 0,03 mm

Unit 1 [0,15 mm 0,25 mm]

Unit 2 [0,18 mm 0,28 mm]

Unit 3 [0,20 mm 0,25 mm]

Unit 4 [0,10 mm 0,17 mm]

Unit 5 [0,11 mm 0,18 mm]

Thickness



4+5 OK


12/52


Unit 1 [0,15 mm 0,25 mm]

Unit 2 [0,18 mm 0,28 mm]

Unit 3 [0,20 mm 0,25 mm]

Unit 4 [0,10 mm 0,17 mm]

Unit 5 [0,11 mm 0,18 mm]

Thickness



1+5 OK 1+4 NO


13/52


Unit 1 [0,15 mm 0,25 mm]

Unit 2 [0,18 mm 0,28 mm]

Unit 3 [0,20 mm 0,25 mm]

Unit 4 [0,10 mm 0,17 mm]

Unit 5 [0,11 mm 0,18 mm]

Thickness



1+2+3 OK


14/52

Due dates and widths

The time gap between the units with the earliest and thelatest due dates must be less or equal than a user-de ned threshold

The sum of the widths of the coupled units must not

exceed the maximum block standard width


15/52

Objectives

Minimize the number of blocks used to exactly producethe given units

Minimize the unused material


16/52

Proposed approach


17/52

CSP

The cutting stock problem (CSP) is a recurring problem inmany industries (sheet metal, textile, paper, wood)

These activities share the common need to cut more orless homogeneous raw material optimizing its usage

The coupling problem can be addresses as a one-dimensional CSP

the strip coils lengths do not add a second dimension,since they are translated into equivalent coils


18/52

Earliest works on CSPK. Eisemann. The trim problem. Management Science,3(3):279284, 1957P. C. Gilmore and R. E. Gomory. A linear programmingapproach to the cutting-stock problem. OperationsResearch, 9(6):849859, 1961

Most common approachespattern generation + integer linear programmingheuristics

CSP Literature


19/52

Our reference

S. M. A. Suliman. A sequential heuristic procedure forthe two-dimensional cutting-stock problem.International Journal of Production Economics, 99(1-2):177185, 2009

S. M. A. Suliman. Pattern generating procedure for thecutting stock problem. International Journal of Production Economics, 74(1-3):293301, 2001

CSP Literature


20/52

Proposed approach

Each batch is independently addressed as a 1D-CSP

Two steps solution algorithm

pattern generation

optimization of patterns usage

A pattern is the allocation of coils of one or more units toa same standard width block


21/52

Pattern generation


22/52

Pattern generation

Each generated pattern must satisfy all the couplability

constraintsA pattern represents a possible real aluminum block usage

Its width includes

the widths of the units in the pattern

the unused width (if any)


23/52

Example

Unit 1 (1) Unit 1 (2)

Unit 2

Unit 3

Block SW2

Block SW1

Block SW2

Block SW2Unit 2

Block SW1Unit 1 (1)

Block SW1

Block SW1

Block SW1

Block

Block

Unit 2

Unit 3

Unit 1 (1) Unit 1 (2)

Unit 1 (1)

Unit 1 (1) Unit 3

Unit 2 Unit 3

Unit 1 (1) Unit 1 (2) Unit 3


24/52

Enhancements vs literature[Suliman2009] algorithm

generates all possible patterns for each standard widthblock (a generation tree for each width)

allows over-production in order to avoid thegeneration of highly ine cient patterns

The proposed algorithm

uni es the pattern generation using a single tree

guarantees the possibility to produce the exactrequired quantities


25/52

How?

E ectively consider minimum and maximum standard

widths when generating each patternUse required production quantities to cuto patterns theILP model would not use

Use couplability constraints to cuto patterns thatcannot be produced


26/52

Production optimization


27/52

Production optimization

An ILP (Integer Linear Programming) model is used tooptimize the patterns usage in order to produce therequired units

Each pattern can either be used (one or more times) ornot

The amount of produced coils for each unit must exactly

match the required quantity The objective is to minimize the unused material withinthe produced patterns


28/52

Model glossary

p is a generic pattern

i is a generic unit

x p is the decision variable related to pattern p , indicatinghow many replicas of such pattern will be produced

q ip is the quantity of units i contained in pattern p

Qi is the overall quantity of units i that must be producedt p is the trim loss for pattern p, i.e. the unused part of thebar in the pattern


29/52

ILP Model

Most of the complexity of

the problem is handled bythe pattern generationprocedure

The ILP model isstraightforward

s.t.

min

p

t p

x p

p

qip x p = Q i i

x p N p


30/52

Test caseKPIs


31/52

Performance evaluation

KPIs (Key Performance Indicator) calculated for eachbatch

number of blocks used

trim

Lower and upper bounds on the number of blocks Trim characterization


32/52

Lower Bound (LB) on blocks

W_tot is the total width required by the batch

its obtained as the sum of the width of each unit

multiplied by the number of equivalent coils itrequires

W_max is the largest standard width available

N_min = RoundUp (W_tot / W_max)


33/52

Not less than 3 blocks

LB calculation example

4 equivalent coils to be produced

Maximum standard width

Trim


34/52

Notice

The LB on the number of blocks does not necessarilyprovide a LB on the trim

The LB over the actual W_max (1.370 cm) wouldproduce a 520 cm trim


35/52

Upper Bound (UB) on blocks

In the worst case, no coupling happenseach equivalent coil uses a di erent block

This provides both

an UB on the blocks to be useda rst feasible solution


36/52

4 blocks UB

UB calculation example4 equivalent coils to be produced

Smallest standard width


37/52

Trim characterization

Each produced pattern can generate trim

We classi ed the percentage trim per block 0% 5% trim

5% 10% trim

10% 100% trimFor each batch we calculate the number of patternsproduced in each class


38/52

Time limits per batch

Time limit for pattern generation

120 seconds

Time limit for ILP solution

120 seconds


39/52

Couplability constraints

Technology related thickness limit

5

Maximum time gap between the units with the earliestand the latest due dates on a same pattern

30 days


40/52

Test caseResults


41/52

Data

The proposed approach was implemented in a DSS(Decision Support System)

The DSS was tested and evaluated on a set of real data2006 units

5650 equivalent coils to be produced

215 batches

due dates between 13/01/2009 and 23/06/2009


42/52

Processing times

All tests on Intel Core2Duo 2,33GHz, RAM 2GB

Total time used to process all batches

15 minutes

circa 4 seconds per batch

Timeout batches

1 during pattern generation


43/52

Output example for a batch

Trim/

Pattern width


44/52

Performance


45/52

Overall results

Blocksaverage LB: 9

average used blocks: 11,3average theoretical gap: 12,4%

Trimaverage trim: 6,1%0%5% average blocks: 9,65%10% average blocks: 0,610%100% average blocks: 1,1


46/52

Theoretical % gap


47/52

% Trim


48/52

Equivalent coils


49/52

Most common case

8 equivalent coilsLB: 3 blocks

Solution: 3 blocks Average trim: 1,5% Trim per class: 3 | 0 | 0


50/52

Conclusions


51/52

Real decision problem in an aluminum rolling rm

Modeled the problem as a CSP

Up to date reference papers in the literature

Developed an original algorithmstarted from a reference approachimproved general pattern generation algorithmextended it to consider speci c production issues

Integrated the proposed approach into a DSS

Proved its e ectiveness on real production data


52/52

An improved pattern generation

procedure for the CS PAn application in a metal rolling rm

Find this presentation here:

Contact the authors:

July 12-14, 2010California State University East Bay

by P. Caricato and A. Grieco
mailto:[email protected]:[email protected]:[email protected]:[email protected]:[email protected]://www.scribd.com/http://www.scribd.com/

Faim 2010 - Caricato Scribd

Documents

Transcript of Faim 2010 - Caricato Scribd