Geï ntegreerde versnijding en productieplanning problemen

Geï ntegreerde versnijding en productieplanning problemen. Wouter Desplenter

Promotor: prof. dr. El-Houssaine Aghezzaf Begeleiders: Frank Van den Broecke (Agfa-Gevaert en UGent), Carles Sitompul Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek

Vakgroep Technische bedrijfsvoering Voorzitter: prof. dr. ir. Hendrik Van Landeghem Faculteit Ingenieurswetenschappen Academiejaar 2009-2010

De auteur en promotor geven de toelating deze scriptie voor consultatie beschikbaar te stellen en delen ervan te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting uitdrukkelijk de bron te vermelden bij het aanhalen van resultaten uit deze scriptie. The author and promoter give the permission to use this thesis for consultation and to copy parts of it for personal use. Every other use is subject to the copyright laws, more specifically the source must be extensively specified when using from this thesis. Gent, 30 mei 2010 De promotor

Prof. dr. E-H. Aghezzaf

De begeleider

Prof. dr. ir. F. Van den broecke

De auteur

W. Desplenter

Woord vooraf Deze masterproef had nooit tot stand kunnen komen zonder de hulp en steun van velen. Iedereen die mij tijdens dit laatste jaar, zij het van dichtbij of veraf, heeft gesteund in het creëren van deze thesis wil ik dan ook van harte bedanken. Vooreerst wens ik mijn begeleider Prof. dr. ir. Frank Van den broecke te bedanken voor de ge¨ınvesteerde tijd en energie, het beantwoorden van al mijn vragen en om mij de kans te bieden dit onderzoek te verrichten. Verder wens ik ook mijn promotor Prof. dr. El-Houssaine Aghezzaf te bedanken voor de deskundige begeleiding en waardevolle suggesties. Een bijzonder woord van dank gaat uit naar mijn ouders. Zij hebben mij de kans gegeven verder te studeren en hebben mij altijd ten volle gesteund in mijn studies. Ook mijn vriendin, Leen, mag zeker en vast niet ontbreken in dit dankwoord. Zij slaagt er telkens weer in mij te motiveren en staat altijd voor me klaar. Tenslotte nog een woord van dank aan alle mensen uit mijn omgeving die me gedurende mijn studies gesteund hebben.

Wouter Desplenter Gent, 30 mei 2010

Ge¨ıntegreerde versnijding en productieplanning problemen door Wouter Desplenter Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek Academiejaar 2009–2010 Promotor: Prof. Dr. El-Houssaine Aghezzaf Begeleiders: Prof. Dr. Ir. . Frank Van Den broecke, Carles Sitompul Faculteit Ingenieurswetenschappen Universiteit Gent Vakgroep Technische Bedrijfsvoering Voorzitter: Prof. Dr. Ir. Hendrik Van Landeghem

Samenvatting In dit werk worden er twee modellen ontwikkeld ter optimalisatie van het versnijdingsproces binnen de confectieafdeling voor printed circuit board film van Agfa-Gevaert. Een eerste model is gebaseerd op de techniek van column generation, er worden enkele uitbreidingen toegevoegd aan een basismodel om te voldoen aan de concrete voorwaarden van dit versnijdingsprobleem. Een tweede model zal een snijplan gaan genereren vanuit een bibliotheek met alle historisch gebruikte combinaties. Deze beide modellen worden onderling met elkaar vergeleken en worden beiden toegepast op een concrete testcase. De combinatieverliezen van de uit de testcase gegenereerde snijplannen worden vergeleken met historische data.

Trefwoorden cutting stock , column generation, versnijdingsoptimalisatie, PCB film, combinatieverlies

Integrated cutting stock and production planning problems Wouter Desplenter Supervisor(s): prof. dr. El-Houssaine Aghezzaf, prof. dr. ir. Frank Van den Broecke Abstract— This article investigates two different models to optimize the cutting process in the confection department for Printed Circuit Board (PCB) film within Agfa-Gevaert NV. The first model is based on the column generation technique proposed by Gilmore & Gomory [1], [2]. A few extensions are added to this model to deal with all the specific requirements of the practical problem. The second model will search a in library containing all the historical cutting patterns for the most optimal combination of these patterns. During this article the models will be compared with each other and a testcase is solved using both models. The resulting combination losses will be compared with the historical value of this parameter. Keywords— Cutting stock problem, column generation, trim loss problem, PCB film, combination loss

I. I NTRODUCTION HE well known goal of cutting optimization consists of minimizing the trim loss while maintaining a low stock level. The confection process within Agfa Gevaert consists of three phases. In the first phase a cutting machine cuts the masterrolls in the length into different reels. The second phase consists of repetitive cutting these reels, in the width, on a certain cutting length into sheets or small reels. The third phase is the packaging of the final products on an packaging machine. There are two different models developed. The first one, the column generation model, will generate new patterns without taking the historical cutting patterns into account. The second model, the library model will unlike the first model generate a cutting plan while combining only historical patterns. A possible advantage of this model is that only a limited number of cutting widths will be used. Recently a part of the second and third phase of the confectionprocess is moved to Wuxi, China, since the main market of this product is situated in the Far East. Due to the standardization in the dimensions of the PCB products it is possible to cover 80% of the demand while using only 4 reelwidths. Afga-Gevaert decided to limit the reelwidths processed in Wuxi to this four widths. An issue discussed in this paper is the ideal approach to combine the Wuxi demand with the other PCB articles.

T

optimal results the the use of heuristic of meta-heuristic methods is recommended. The heuristic methods don’t guarantee an optimal solution, but usually generate faster an acceptable solution. An acceptable solution is a solution that is close enough to the optimal solution. A drawback of the heuristic methods is the need for adaptation of the method for every specific problem. The heuristic methods may appear little of use on apparently similar problems [4]. Another drawback of the heuristic methods is the change of being trapped in local optima. Metaheuristic methods have the ability of not being trapped in local optima unlike heuristic methods. The solution process of metaheuristic methods is often guided by some lower level heuristic. The solution method for solving a Linear Programming (LP) relaxation of the CSP, is actually a combination of an algorithmic and a heuristic method. Indeed Hinxman classifies this problem as an algorithmic solution method, although it does not guarantee the optimal solution for the integer CSP [4]. III. C OLUMN GENERATION MODEL The column generation model is based on the model opposed by Gilmore & Gomory [1], [2]. After modifying this model for the specific situation this base model is given as: min

(1)

cp xp

p∈P

subject to: si +

X

p∈P

api xp − di ≤ tdi

xp ≥ 0 and integer

min v −

II. L ITERATURE REVIEW The first formulation of a Cutting Stock Problem (CSP) was produced by Kantorovich in 1939, although it was only published in English in 1960 [3]. Since this publication the interest in CSP grew continuously. There were a lot of possible solutions method developed. It is possible to distinct three main types of solution methods. Algorithmic methods guarantee the optimal solution to be found. The drawback of these methods exist in the complexity of the computation, this mostly results in large calculation times, definitely when dealing with large problems. When the calculation time is considered to be more important then obtaining the

X

subject to: n X i=1

W−

n X i=1

i = 1, ..., n ∀p ∈ P

πi bL/li cyi

i=1

wi yi ≤ v

yi ≥ 0 and integer v≥0

(3)

(4)

(5)

wi yi ≤ W

n X

(2)

i = 1..n

(6) (7) (8)

The main problem, with objective function (1) and restrictions (2) and (3), will minimize the combination loss. The variable xp denotes the number of masterrolls cut while using pattern p. cp is a parameter representing the width loss of the pattern p. The parameters si , di , li , wi represent respectively the stock value, the demand, the length and the width of item i. t is a tolerance level for the items produced in surplus on the demand. A pattern is described by the vector Ap = (ap1 , ..., api , ..., apn ), the element api represent the quantity of items i cut in pattern p. The knapsack problem will search the pattern with the minimal reduced cost. The value πi represents the shadowprice of item i concerning restriction (2). The total width and length of the masterroll are represented by W and L. yi denotes the number of item i produced in the proposed pattern. When the resulting pattern has a negeative reduced cost, the pattern is added to the main problem and The calculation restarts until there are no more pattern with a negative reduced cost. This model is further adapted to the specific requirements of the cutting environment in three extensions. A first extension will implement the possibility to combine the two masterrolls with a different coating surface. To work with two different masterrolls instead of one, the set P of all patterns p is divided into two subsets each representing the cutting patterns for a certain masterrol. Furthermore a knapsack problem need to be solved for each width of the two masterrolls separately. In a second extension the possibility to rotate the items is implemented. To allow a 90 degrees rotation of the items the variable yi is split into yil and yib . The variables yil , yib represents the number of items in pattern p positioned in their respectively lengthwise, widthwise direction. The third extensions increases the scope of the model in consequence of adding the possibility to cut multiple items out of one reed. To do so a change in the cutting lengths is necessary during the cutting of a reed. To implement this possibility an extra subproblem is added to the model. In this subproblem not only the item that defined the cutting width of the reed but all the items that are either in length or in width equal to the reed width are considered. IV. L IBRARY OF HISTORICAL COMBINATIONS There is a lot of pre-processing needed to filter the historical combinations out of the historical data and represent this data as inputdata for this model. Once the pre-processing is completed, a rather simple model of linear combination of these patterns deals with the optimization problem. This problem is represented by objective function (9) and restrictions (10) and (11) X min cp xp (9) p∈P

subject to: si +

X

p∈P

2

am pi xp − di ≤ tdi


i = 1, ..., n

∀p ∈ P

(10)

(11)

V. E XPERIMENTS To analyze both models a testcase is created. This testcase consists of the monthly forecast of the demand for the period from March 2010 until October 2010. There are three different testsets for each month. The first considers only the Wuxi items, the second considers the Wuxi items in combination with the PCB items who have an length or width similar to one of the Wuxi reed widths. The third consideres all the PCB items at a time. VI. C ONCLUSIONS After intensive analyses of the results of the different testcases there are some conclusions that can be made. The conclusions are briefly discussed during this chapter. While comparing the two models it is clear that the library model experiences some difficulties when a demand arises for a (new) item that was never used in some historical combination. To be able to make cutting plans for this item with te library model, expanding the library with some combinations containing this item is necessary. The column generation model experiences no difficulties to deal with new items. The rounding of the results after solving the LP relaxation of the models leads to a strong reduction of the number of different patterns needed. This lower number of different cutting patterns will reduce the amount of changeovers of the cutting machine. Although the rounding of the results can result in a violation of some restrictions. Some ad hoc rounding or a heuristic approach could limit these violations. The column generation model minimize the combination loss the best if the Wuxi items are considered together with all the other PCB items. There can be no clear rule described for the library model. Since the solution highly depend on the combinations in the library. The difference between the three testsets will depend on the combinations in the library as well. Comparing the results of both the models with the historical percentage of combination loss shows a major reduction of this loss percentage. The historical combination loss is 3.50% while the column generation model generates in these testcases cutting plans with a mean combination loss of 0.42% and for the library model this value is 0.80%. While comparing these results it is necessary to keep in mind that these models suppose a startstock that is in balance. Furthermore the historical value has to be approached with a certain caution because of some extra combination losses due to mistakes in the emulsion surface. So an exact percentage of improvement is hard to calculate, neverthless these results demonstrate a big opportunity for improvement. R EFERENCES [1] P.C. Gilmore, R. E. Gomory, A linear programming approach to the cuttingstock problem, Operations Research, 1961, vol. 9, pp. 849-859. [2] P.C. Gilmore, R. E. Gomory, A linear programming approach to the cuttingstock problem - Part II, Operations Research, 1961, vol. 13, pp. 94-120. [3] L. V. Kantorovich, Mathematical methods of organizing and planning production, Management Science, 1966, vol. 5, pp. 336-442. [4] A.I. Hinxman, The trim-loss and assortment problems: A survey, European Journal of Operations Research, 1979, vol. 5, pp. 8-18.

Inhoudsopgave Woord vooraf

ii

Overzicht

iii

Extended abstract

iv

Inhoudsopgave

vii

Gebruikte afkortingen

viii

1 Inleiding 1.1 Thesisopbouw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1

2 Agfa-Gevaert NV 2.1 Situering Agfa-Gevaert NV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Situering PCB film . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Situering versnijdingsproblematiek . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 5

3 Literatuurstudie 3.1 Het Cutting Stock Probleem . . . . . . . . . . . . . . . . . . 3.1.1 Algemene situering en typologie . . . . . . . . . . . 3.1.2 Oplossingsmethoden voor het cutting stock probleem 3.2 Heuristische oplossingsmethoden . . . . . . . . . . . . . . . 3.2.1 Lineair programmeringsmodel . . . . . . . . . . . . . 3.2.2 Gilmore & Gomory column generation model . . . . 3.2.3 Sequentieel heuristische methode . . . . . . . . . . . 3.3 Meta-heuristische methoden . . . . . . . . . . . . . . . . . . 3.3.1 Tabu search . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Algoritmische methoden . . . . . . . . . . . . . . . . . . . . 3.5 Vergelijking van de verschillende oplossingsmethoden . . . . 4 Probleemdefinitie en onderzoeksvragen 4.1 Het productieproces . . . . . . . . . . . 4.1.1 Productiefase . . . . . . . . . . . 4.1.2 Confectiefase . . . . . . . . . . . 4.1.3 Confectieafdeling in Wuxi . . . . 4.1.4 Historische data . . . . . . . . . vi

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . . .

6 6 6 9 10 10 14 17 20 20 21 22 22

. . . . .

23 23 23 25 25 26

vii

Inhoudsopgave 4.2

Versnijdingsprobleem . . . . . 4.2.1 Huidige problematiek 4.2.2 Onderzoeksvragen . . 4.2.3 Design of Experiments 4.2.4 Historische bibliotheek 4.2.5 Software . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . vs column . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . generation . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

28 28 29 30 33 33

. . . . . . . . . . . . .

35 35 35 40 44 46 52 53 55 57 59 60 63 64

6 Conclusies en suggesties voor verder onderzoek 6.1 Conclusies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Suggesties voor verder onderzoek . . . . . . . . . . . . . . . . . . . . . . . . .

66 66 68

A Model opgelost met de Excel solver

70

B AMPL code column generation model B.1 Het .RUN bestand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Het .MOD bestand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 72 78

C AMPL code bibliotheek model C.1 Het .RUN bestand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Het .MOD bestand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81 81 83

D Resultaten column generation model

84

E Resultaten historische bibliotheek model

88

F Conventionele afronding van het bibliotheek model

92

Bibliografie

94

5 Ontwerp en validatie versnijdingsmodel 5.1 Gegenereerde combinaties via column generation . . . . . . . . . . 5.1.1 Basismodel gebaseerd op model van Gilmore & Gomory . . 5.1.2 Eerste uitbreiding: verschillende breedtes van masterrollen . 5.1.3 Tweede uitbreiding: lengte/breedte problematiek . . . . . . 5.1.4 Derde uitbreiding: verschillende producten per band . . . . 5.2 Bibliotheek van historische combinaties . . . . . . . . . . . . . . . 5.3 Experimenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Resultaten historische bibliotheek model . . . . . . . . . . . 5.3.2 Resultaten column generation model . . . . . . . . . . . . . 5.3.3 Aanpassingsvermogen modellen . . . . . . . . . . . . . . . . 5.3.4 Invloed van afronden . . . . . . . . . . . . . . . . . . . . . . 5.3.5 Invloed van tolerantie op combinatieverlies . . . . . . . . . 5.3.6 Vergelijking van beide modellen . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . . .

Gebruikte afkortingen CSP

Cutting Stock Problem

DRP

Distribution Requirements Planning

fbs

fabricagesoort

GRASP

Greedy Randomized Adaptive Search Procedure

I

Integer

LP

Lineaire Programmering

MPS

Master Production Scheduling

MRP

Material Requirements Planning

NI

Non-Integer

PCB

Printed Circuit Board

S&OP

Sales & Operations Planning

TL

Tabu List

TS

Tabu Search

Hoofdstuk 1

Inleiding Deze thesis behandelt de versnijdingsoptimalisatie van de Printed Circuit Board (PCB) film binnen de confectieafdeling van Agfa-Gevaert NV. In deze confectieafdeling wordt een masterrol, begoten met fotografische emulsie, in een eerste stap versneden in verschillende banden. Vervolgens worden deze banden op de juiste lengte gekapt tot vellen of bobijnen waarna ze verpakt worden tot eindproduct. Nu zal men vanuit een voorspelling van de vraag de versnijding van de masterrollen gaan inplannen. Dit gebeurt op basis van de ervaring en intu¨ıtie van de werknemers verantwoordelijk voor het opstellen van de snijplanning. Het doel van deze thesis is het ontwikkelen van een theoretisch model dat, aan de hand van de gemaakte voorspellingen, een snijplan ontwikkelt. Dit snijplan dient te voldoen aan een aantal voorwaarden en heeft als doel het minimaliseren van het combinatieverlies. Dit model wordt dan getoetst aan en vergeleken met de gemaakte combinatieverliezen uit het verleden. Aangezien een beperkte, vaste set combinaties een voordeel kan opleveren bij het instellen van de snijmachines zal ook een model ontwikkeld worden waarin enkel uit een beperkte bibliotheek aan combinaties kan gekozen worden.

1.1

Thesisopbouw

Eerst en vooral zal de thesis in Hoofdstuk 2 starten met een algemene beschrijving van het bedrijf Agfa-Gevaert NV. Vervolgens zal meer in detail het effectieve eindproduct en de confectieafdelingen die de focus van deze thesis vormen besproken worden. Ook het specifieke versnijdingsprobleem wordt kort toegelicht. Hoofdstuk 3 zal de literatuurstudie aangaande de versnijdingsproblematiek behandelen. Het is noodzakelijk, alvorens te starten met de ontwikkeling van een model, de literatuur betreffende dit onderwerp grondig te bestuderen. Er wordt gestart met een algemene beschrijving van cutting stock problemen. Vervolgens worden verschillende technieken besproken om dit soort problemen op te lossen. Hoofdstuk 4 zal het versnijdingsprobleem duidelijk in kaart brengen en de concrete thesisdoelstellingen en onderzoeksvragen formuleren. Nu de theoretische achtergrond verduidelijkt is en de concrete doelstellingen beschreven zijn kan het ontwerp van het model beginnen. Hoofdstuk 5 1

2

Hoofdstuk 1. Inleiding

bespreekt in een eerste fase de verschillende stappen in de ontwikkeling van beide modellen. In een tweede fase worden de resultaten weergegeven, toegelicht, vergeleken, ge¨ınterpreteerd en getoetst aan de historische data. Tot slot zullen in Hoofdstuk 6 de conclusies van deze thesis samengevat worden. Bijkomend worden suggesties gedaan voor verder onderzoek. In figuur 1.1 wordt de thesisopbouw schematisch weergegeven.

Figuur 1.1: Thesisopbouw

Hoofdstuk 2

Agfa-Gevaert NV 2.1

Situering Agfa-Gevaert NV

Agfa Gevaert is een bedrijf actief in de beeldvormingsindustrie. Het produceert toepassingen voor de analoge en digitale filmindustrie. Met productieafdelingen in 10 landen, waaronder China, de Verenigde staten, Duitsland en België, en ondersteunende verkoopafdelingen in meer dan 40 landen is Agfa Gevaert één van de grote wereldspelers op vlak van fotografische film. De activiteiten van Agfa Gevaert zijn opgesplitst in drie kerngroepen; Healthcare, Graphics en Materials. Agfa Healthcare produceert en distribueert film en toepassingen voor medische doeleinden, zoals X-ray film, contrastvloeistoffen en systemen voor medische beeldvorming. Agfa Graphics, produceert grafische film en drukplaten voor allerhande toepassingen binnen de beeld-, publicatie- en drukindustrie. Agfa Materials ten slotte heeft enerzijds een eigen verkoopsorganisatie voor een aantal niche producten en produceert anderzijds film voor derde partijen en de twee andere kerngroepen van Agfa Gevaert. De productie-afdeling van Agfa Materials bevindt zich hoofdzakelijk in Mortsel en het is binnen deze productie-omgeving dat de thesis zich situeert. Het filmproductieproces kan men als semi-proces beschrijven. In een eerste proces-georiënteerde productiestap wordt een fotografische emulsie gegoten op een PET onderlaag. Agfa’s gietzalen produceren hier het halffabrikaat, namelijk fotografische masterrollen. Deze rollen zijn meestal 1.728 meter breed en hebben een lengte van enkele duizenden meter. Binnen de gietzalen wordt gegoten voor zes verschillende toepassingen, meer bepaald Healthcare film, Graphical film, Non Destructive Testing film, Cine film, Microfilm en PCB (Printed Circuit Board ) film. Deze masterrollen zijn dan weer input voor Agfa’s confecties of worden als halffabrikaat verkocht aan externe verwerkers (MR customer ). De confecties (of verpakkingsafdelingen) versnijden de masterrol tot een groot aantal verschillende eindproducten, verschillend naargelang hun formaat en verpakkingsvorm. Via een twee-echelon distributiesysteem worden de eindproducten verdeeld naar eind-klanten, ofwel rechtstreeks (Direct Customer ) ofwel via de eigen verkoopsorganisatie (Sales Organisation customer ). De forecasting (op eindproduct niveau) en Sales & Operations Planning (S&OP, op ge3

Hoofdstuk 2. Agfa-Gevaert NV

4

aggregeerd niveau) sturen de productie aan. De MPS (Master Production Scheduling) systemen van gietzalen en confectie bepalen in detail de productiehoeveelheden. Via de MRP (Material Requirements Planning) logica worden de grondstoffen aangekocht. De distributie en de herbevoorrading van de dochtermagazijnen wordt aangestuurd vanuit het DRP systeem (Distribution Requirements Planning).

Figuur 2.1: Globale voorstelling van het productiesysteem binnen Agfa-Gevaert

2.2

Situering PCB film

Deze thesis situeert zich in de PCB confectie waar fotografische film wordt versneden ten behoeve van de Printed Circuit Board industrie. Bij het aanmaken van een Printed Circuit Board worden de benodigde geleidingsbanen meestal fotografisch geëtst. In dit geval bevindt zich bovenop de drager een lichtgevoelige laag. Door belichting met UV-licht wordt het ontwerp-patroon in deze laag gebrand. Daar waar de printplaat belicht is, kan door ontwikkelen met natronloog de lichtgevoelige laag verwijderd worden. Agfa levert film die in dit Phototooling proces kan gebruikt worden. Via deze hoge precisie film maakt men een beeld van de benodigde banen, en dit beeld wordt dan gebruikt om het gewenste patroon via UV belichting over te brengen naar de printed circuit board . De verbruiksmarkt van PCB film bevindt zich in het verre oosten. Denk maar aan bijvoorbeeld de Chinese, Japanse en Koreaanse speelgoed en hifi-industrie. Om die reden heeft Agfa recent beslist haar confectie in Wuxi (China) uit te breiden met een versnijdings-en verpakkingslijn voor PCB film, dicht bij de locale markt. De Chinese fabriek werd uitgerust met een extra kap-machine (kappen van versneden banden tot vellen) en verpakkingslijn. Het snijden van de masterrollen tot banden zal voorlopig nog in Mortsel gebeuren. Deze banden worden dan verpakt en vanuit Mortsel verstuurd naar de Wuxi fabriek.

Hoofdstuk 2. Agfa-Gevaert NV

5

De belangrijkste gietsoort binnen PCB is de soort RL56G. Deze soort wordt om de zes weken gegoten (cyclische productie van masterrollen). Het gieten gebeurt op twee verschillende gietbreedtes. In beide gevallen is de onderlaagdrager 1.728 meter breed. In de brede gietsoort RL56G is de begoten breedte = 1.682 meter. Bij de smalle gietsoort RL56GS4 begiet men slechts 1.350 meter en laat men daardoor een belangrijk gedeelte van de onderlaag onbenut.

2.3

Situering versnijdingsproblematiek

Binnen de PCB film markt zijn de formaten grotendeels gestandardiseerd. Het confectie of versnijdingsproces bestaat uit 3 fazen. Een snijmachine versnijdt de masterrollen tot banden. Het combinatieverlies is het verschil van de nuttige breedte van de masterrol (= begoten breedte) t.o.v. de som van snijplan bandbreedtes. Een kapmachine kapt de gesneden banden vervolgens tot vellen. Een verpakkingslijn zorgt tenslotte voor de eindverpakking. Meestal wordt er per band maar één artikel gecombineerd. Toch komt het occasioneel voor dat binnen een band een tweede artikel, verschillend in kaplengte wordt gecombineerd. Wegens de standaardisatie van formaten kan men met vier verschillende formaatbreedtes 80% van het gevraagde volume afdekken. Dit verklaart waarom Agfa besliste de voor Wuxi te snijden banden te beperken tot vier verschillende breedtes. Andere artikelen, met één van de snijmaten verschillend van de Wuxi-bandbreedtes, blijft men dan vanuit Mortsel leveren. Voor de gietsoort die in deze wordt thesis bestudeerd (RL56G) werden volgende bandbreedtes en daarmee corresponderende verzend-artikelen (verzenden van gesneden banden) gecreëerd.

Figuur 2.2: Verschillende Wuxi bandbreedtes en corresponderende artikelen

Het combineren van de Wuxi band-behoeftes uit de beschikbare hoeveelheid masterrollen is een typisch CSP (Cutting Stock Problem) en bevat het focuspunt van deze masterthesis. De verlegging van een deel van het PCB productievolume naar Wuxi zorgde binnen Agfa voor een vernieuwde aandacht aangaande het ’versnijdings’ of ’combinatieprobleem’ (Cutting Stock Problem). Deze masterthesis bestudeert het CSP probleem, toegespitst op de versnijding van PCB film en gebruikt de ’Wuxi case’ om een antwoord te bieden met welke aanpak men optimaal de Wuxi artikelen (al of niet samen gecombineerd met andere PCB artikelen) versnijdt uit de beschikbare masterrollen.

Hoofdstuk 3

Literatuurstudie Alvorens de ontwikkeling van een model te starten is het noodzakelijk de nodige literaire achtergrond en reeds uitgevoerd onderzoek naar soortgelijke problemen te schetsen. Aan de hand van de tijdens dit hoofdstuk verworven inzichten moet het vervolgens mogelijk worden om het versnijdingsprobleem binnen Agfa-Gevaert NV te analyseren en op een doordachte, correcte manier over te gaan tot het ontwikkelen van een model. Eerst zal het cutting stock probleem (CSP) algemeen besproken worden: hierbij worden ook de verschillende types, categorieën en klassen toegelicht. Hierdoor wordt een algemeen beeld van de verschillende cutting stock problemen verworven en zal het nadien gemakkelijker worden om een bepaald type CSP in de juiste context te situeren. Vervolgens worden enkele modellen voor het oplossen van een CSP toegelicht. We onderscheiden hier drie hoofdtypes, namelijk heuristische, meta-heuristische en algoritmische methoden. Binnen de heuristische methoden worden zowel het lineaire programmeringsmodel als sequentieel heuristische methoden besproken. Bij het lineaire programmeringsmodel dient de opmerking gemaakt te worden dat dit eigenlijk een combinatie is van een heuristische en een algoritmische methode. We bespreken ook een techniek om het aantal kolommen binnen het lineaire programmeringsmodel te beperken, de column generation techniek. Binnen de meta-heuristische methoden worden de tabu search en GRASP methodes toegelicht. Vervolgens worden de algoritmische methoden kort besproken. Tot slot zal een vergelijking tussen de verschillende types van methoden gemaakt worden.

3.1

Het Cutting Stock Probleem

3.1.1

Algemene situering en typologie

Het cutting stock probleem (CSP) was één van de problemen die Kantorovich ge¨ıdentificeerd heeft in zijn artikel, genaamd Mathematical methods of organizing and planning production, die voor het eerst verscheen in 1939 in Rusland en pas veel later in het engels gepubliceerd werd in Management Science (1960). Het probleem bestaat erin de best mogelijke manier te 6

Hoofdstuk 3. Literatuurstudie

7

vinden om een set van grote objecten te versnijden in kleinere objecten. De optimalisatie van dit soort problemen brengt grote potentiële besparingen met zich mee. Cutting stock problemen komen voor in een zeer brede waaier van toepassingen binnen verschillende takken van de industrie. Voorbeelden van toepassingen van CSP bevinden zich onder meer in de staal-, glas-, papier-, kleding- en houtindustrieën. Het één dimensionale CSP wordt beschreven in Gilmore & Gomory (1961) als ’the problem of filling an order at minimum cost for specified numbers of lengths of materials to be cut from given stock lengths of given cost’. Sinds het onderzoek naar cutting stock problemen een vijftigtal jaar geleden op volle toeren begon te draaien werden er een sterk groeiend aantal formuleringen en verschillende oplossingsmethodes over dit onderwerp gepubliceerd. Om een totaal beeld te schetsen worden in wat volgt een aantal karakteristieken besproken van het CSP. In 1990 werd door Dyckhoff een schema ontwikkeld om verschillende CSP efficiënt te classificeren. Aangezien het sterke verband tussen snijden en stapelen werd het schema veralgemeend naar beide categorieën. Dit sterke verband kan ge¨ıllustreerd worden met het feit dat in zekere zin snijden kan gezien worden als het stapelen van kleine objecten in een groter object. Aan de andere kant kan stapelen gezien worden als het snijden van een groot object in lege volumes. Sommige van deze lege volumes worden gevuld met kleinere objecten, anderen kunnen gezien worden als snijverlies. In figuur 3.1 wordt het door Dyckhoff ontworpen schema tot categoriseren van Cutting & Packing problemen weergegeven. De auteur introduceeerde 4 criteria volgens dewelke de categorisering plaatsvindt. Het eerste en meest belangrijke criterium is dimensionality . Dit duidt op het minimum aantal dimensies die betekenisvol zijn bij het determineren van een oplossing. Dyckhoff onderscheidt de verschillende dimensies als one- , two-, three- en multidimensional problems. Er bestaat een zeker aantal CSP met complexiteit tussen een en twee dimensies. Deze kunnen gekarakteriseerd worden als 1,5 dimensionale problemen. (Hinxman, 1979; Haessler & Sweeney, 1991) In het meest eenvoudigste geval is slechts één dimensie van de voorraad relevant voor de oplossing. Een typisch voorbeeld van een 1-dimensionaal CSP is het snijden van stalen staven waarbij de lengte van de te versnijden staven vast ligt. Bij een 1,5 dimensionaal probleem heeft de stock 1 vaste en 1 variabele dimensie. Dit is bijvoorbeeld het geval bij het versnijden van banden waarvan de voorraad een vaste breedte heeft maar een variabele bandlengte. Bij twee-dimensionale problemen kunnen de bestelde objecten in 2 vrije dimensie uit het voorraadmateriaal gesneden worden. Twee-dimensionale CSP kunnen onderverdeeld worden naargelang de snijprocedure die ze ondergaan. Zo kan een snijproces bestaan uit verschillende stappen waarbij het oorspronkelijk materiaal versneden is in subvellen waarbij de snijrichtingen een rechte hoek maken met de snijrichtingen in de vorige stap. Dit snijproces wordt staged two- dimensional cutting


8

Figuur 3.1: Schema van Dyckhoff ter categorisering van Cutting & Packing problemen: categorieën en hoofdtypes (Dyckhoff, 1990, p. 154)

genoemd. Als de voorgaande snijbewegingen evenwijdig moeten zijn met de zijden van het oorspronkelijke vel zal het probleem orthogonal two-dimensional genoemd worden. Indien bovendien de sneden over de volledige breedte van het oorspronkelijk vel gaan of over de volledige breedte van een vel verkregen in een voorgaande stap zal naar het probleem verwezen worden als een guillotine cut. In figuur 3.2 wordt het verschil tussen een guillotine cut patroon en een non guillotine cut patroon weergegeven. Het is hier duidelijk te zien dat figuur 3.2-b niet opgebouwd is uit sneden die over een volledige breedte van het oorpronkelijk vel of van een vel verkregen in een vorige stap uitgevoerd werden. Naast dimensionality wordt nog een andere belangrijke karakteristiek beschreven in figuur 3.1 namelijk kind of assignment . Er wordt in deze categrorie een onderscheid gemaakt tussen de volgende twee categorieën, B en V. In de eerste zal de volledige voorraad opgebruikt worden maar niet alle vraag kan/moet voldaan zijn. In de tweede categorie moet aan de volledige vraag voldaan worden, hiervoor zal slechts een gedeelte van de voorraad aangesproken worden. De derde karakteristiek uit figuur 3.1, assortments of large objects wordt onderverdeeld in 3 klassen. deze klassen onderscheiden zich van elkaar in de te snijden (grote) objecten. Zo kan


9

Figuur 3.2: (a): voorbeeld van een guillotine cut patroon, (b): voorbeeld van een non guillotine cut patroon (Hifi et al., 2009, p. 305)

er vertrokken worden van 1 groot object of meerdere objecten met gelijkaardige afmetingen of van meerdere objecten met verschillende afmetingen. Een gelijkaardig onderscheid wordt gemaakt met betrekking tot de te snijden objecten, de gevraagde objecten. Deze karakteristiek wordt in figuur 3.1 als assortments of small objects beschreven. Op analoge manier met de voorgaande karakteristiek worden hier vier klassen onderscheiden met betrekking tot de gevraagde (kleine) objecten: weinig objecten met verschillende afmetingen, veel objecten met verschillende afmetingen, veel objecten met meerendeel gelijke afmetingen en tot slot veel objecten met allemaal gelijke afmetingen.

3.1.2

Oplossingsmethoden voor het cutting stock probleem

Er zijn algemeen gezien drie grote klassen waarin we oplossingsmethoden voor het CSP kunnen onderverdelen. Algoritmische methoden garanderen de optimale oplossing als resultaat; een nadeel van deze methodes schuilt hem in de complexiteit van de berekening wat resulteert in lange rekentijden, zeker bij grote problemen. Omwille van dit nadeel worden deze methodes in de praktijk slechts heel beperkt gebruikt. Daartegenover staan de heuristische methoden; deze garanderen niet altijd een optimale oplossing maar genereren meestal veel vlugger een acceptabele oplossing. Een oplossing wordt beschouwd als acceptabel als deze oplossing zich dicht genoeg bevindt bij de optimale oplossing. Heuristische methoden zijn erg domein afhankelijk, zo zal voor verschillende problemen meestal andere heuristische methoden dienen ontwikkeld worden. Eenzelfde heuristische methode kan slechts beperkt gebruikt worden voor problemen die van een gelijke aard lijken (Hinxman, 1979). Meta-heuristische methoden hebben de eigenschap dat ze zich niet laten vangen in locale optima, wat wel kan gebeuren bij heuristische methoden. In meta-heuristische methoden is het oplossingsproces

10

Hoofdstuk 3. Literatuurstudie meestal ondersteund door een onderliggende heuristiek.

3.2

Heuristische oplossingsmethoden

3.2.1

Lineair programmeringsmodel

Het oplossen van het CSP door relaxatie van het Lineair Programmeringsmodel(LP) kan eigenlijk gezien worden als een combinatie van algoritmische en heuristische methoden. Hinxman classificeerde deze methode als algoritmisch hoewel ze geen optimale oplossing vindt voor het integer CSP (Hinxman, 1979). Deze methode levert in feite enkel een optimale oplossing voor het gerelaxeerde probleem. Indien men uit dit resultaat een haalbare oplossing voor het integer CSP wil halen zal men enkele ad hoc methoden moeten toepassen. Een vaak gebruikte methode is het afronden. Een integer oplossing is praktisch bruikbaar, daar waar een non-integer oplossing, in het geval van versnijden van staven zonder afronding praktisch niet bruikbaar is. Het is namelijk in de praktijk niet mogelijk een op één enkele staaf meerdere versnijdingspatronen toe te passen. Kantorovich integer lineair programmeringsmodel Zoals ex ante besproken werd, introduceerde Kantorovich een mathematisch programmeringsmodel voor het CSP. Dit met de bedoeling van het minimaliseren van het aantal rollen gebruikt om alle items te snijden. Variabelen: xk0 xki

1 als rol k gebruikt wordt, 0 anders aantal items i in rol k

Parameters: di wi W K n

vraag naar item i breedte van item i breedte van een masterrol bovengrens aantal rollen totaal aantal items

Model: min

K X k=1

xk0

(3.1)

11

Hoofdstuk 3. Literatuurstudie onder voorwaarden: K X k=1

n X i=1

xki ≥ di ,

wi xki ≤ W xk0 ,

i = 1, ..., n k = 1, ..., K

(3.2) (3.3)

xk0 = 0 or 1,

(3.4)

k = 1, ..., K,

(3.5)

i = 1, ..., n,

(3.6)

xki ≥ 0 and integer,

(3.7)

Waarbij K een gekende bovengrens is op het aantal rollen die nodig zijn om aan alle vraag te voldoen. xk0 is een binaire variabele waarvoor geldt dat xk0 = 1 als rol k gebruikt wordt en xk0 = 0 wanneer deze rol niet gebruikt wordt. xki is het aantal keren dat item i wordt gesneden in rol k. Beperkingen 3.2 zullen ervoor zorgen dat voldaan wordt aan de vraag naar alle items. Beperkingen 3.3 voorkomen dat het aantal items in een rol niet groter zal zijn dan de capaciteit van deze rol. Deze groep van beperkingen worden de knapsack problemen genoemd. Men kan eenvoudig zien dat wanneer xk0 = 1 de beperkingen 3.3 kunnen geschreven worden als in vergelijking 3.8 en in het geval dat xk0 = 0 kunnen deze beperkingen geschreven worden zoals weergegeven in vergelijking 3.9. In een volgende paragraaf wordt dieper ingegaan op het knapsack probleem. Tijdens deze paragraaf zal het duidelijk worden dat vergelijkingen 3.8 en 3.9 de beperkingen zijn van een knapsack probleem met capaciteit respectievelijk W en 0. n X

wi xki ≤ W

k = 1, ..., K

(3.8)

wi xki ≤ 0

k = 1, ..., K

(3.9)

i=1 n X i=1

Een ondergrens voor het probleem kan bekomen worden uit de lineaire relaxatie van het probleem. Deze relaxatie kan bekomen worden door beperkingen 3.4 en 3.7 te vervangen door de vergelijkingen 3.10 en 3.11. Deze ondergrens kan heel zwak zijn. De ondergrens kan gezien worden als de minimum oppervlakte die nodig is om alle items te kunnen plaatsen, zoals weergegeven in vergelijking 3.12. Deze ondergrens zal erg zwak zijn voor problemen met grote hoeveelheden verlies. In geval van problemen met kleinere verlies percentages zal de lineaire relaxatie ons dit een bruikbare ondergrens opleveren.

12


0 ≤ xk0 ≤ 1, xki ≥ 0 n X di wi i=1

W

(3.10) (3.11) (3.12)

Knapsack probleem Een knapsack probleem kan letterlijk vertaald worden als een rugzak probleem. Om meer inzicht te krijgen in dit soort problemen zal een eerste voorbeeld van een bergbeklimmer besproken worden (Martello & Toth, 1990). Hier wordt ook meteen duidelijk waar dit soort problemen hun naam vandaan halen. Veronderstel een bergbeklimmer die op expeditie vertrekt en hiervoor zijn rugzak dient te vullen. Hij kan hiervoor kiezen tussen verschillende mogelijke items. De bergbeklimmer zijn rugzak heeft een beperkte capaciteit en hij wil dus zijn rugzak op die manier vullen dat de capaciteit van zijn rugzak niet overschreden wordt maar toch een zo waardevol mogelijk inhoud heeft. In figuur 3.3 wordt dit knapsack probleem visueel voorgesteld.

Figuur 3.3: Een visuele voorstelling van het knapsack probleem (Wikipedia, the free encyclopedia)

Dit knapsack probleem kan mathematisch geformuleerd worden door alle items te nummeren van 1 tot n en vervolgens een binaire variabele xj te introduceren. Deze variabele zal 1 worden als item j geselecteerd is en 0 anders. Stel dat pj een maat is voor de waarde van item j, wj stelt het gewicht van item j voor en W de capaciteit van de rugzak. Het probleem bestaat erin om van uit alle mogelijke combinaties die voldoen aan beperking 3.14 degene te kiezen die doelfunctie 3.13 maximaliseert. Hieronder wordt het probleem mathematisch uitschreven:

13

Hoofdstuk 3. Literatuurstudie Variabelen: xj

1 als object i geselecteerd wordt, 0 anders

Parameters: pi wi W n

waarde van item i gewicht van item i capaciteit van de rugzak totaal aantal items

Model: max

n X

p j xj

(3.13)

i = 1, ..., n

(3.14)

j=1

onder voorwaarden: n X j=1

wj xj ≤ W,

xj = 0 or 1,

(3.15)

i = 1, ..., n,

(3.16)

Het is voor de hand liggend dat deze problemen niet enkel in de sector van bergbeklimmers hun toepassing vinden. Veronderstel bijvoorbeeld dat je een kapitaal van W euro ter beschikking hebt en je overweegt n mogelijke investeringen. Laat nu pj het verwachte rendement van investering j zijn, en wj de hoeveelheid kapitaal (in euro) die investering j kost. Het is duidelijk dat de optimale oplossing van het hierboven besproken model ons de de best mogelijke keuze van investering zal aanduiden. Een op het eerste zicht voor de hand liggende mogelijke oplossing voor dit probleem bestaat erin met een computer alle mogelijke vectoren x te analyseren en daarna uit alle vectoren die aan de beperkingen voldoen degene die de doelfunctie maximaliseert te kiezen. We moeten hierbij echter rekening houden met het aantal binaire vectoren x dat berekend wordt door 2n . Een hypothetische computer, in staat om één biljoen vectoren per seconde te analyseren, zou een rekentijd nodig hebben van meer dan 30 jaar voor n = 60, meer dan 60 jaar voor n = 61,... De rekentijd voor grote problemen wordt dus immens. Hoewel we hier dienen op te merken dat gespecialiseerde algoritmes in staat zijn een probleem met n = 100000 in enkele seconden op te lossen (Martello & Toth, 1990). De interesse in knapsack problemen kwam er hoofdzakelijk door hun simpele structuur, dit liet toe om combinatieproblemen nader te bestuderen. Anderzijds biedt deze simpele structuur mogelijkheden om complexere problemen op te lossen door een sequentie van knapsack problemen op te lossen. De toepassing op het CSP van deze techniek voor het oplossen van complexere problemen door middel van een aantal knapsack problemen wordt besproken in Hoofdstuk 3.2.2.

14


3.2.2

Gilmore & Gomory column generation model

Gilmore & Gomory stelden een nieuw model voor om eendimensionale CSP problemen van Dyckhoff’s types 1/V/I/R en 1/V/D/R op te lossen. Het is een model waarin de snijpatronen beschreven worden door de vector Ap = (ap1 , ..., api , ..., apn ) waarin api het aantal items i, met breedte wi , worden gesneden in snijpatroon p. Een snijpatroon p moet voldoen aan de voorwaarden 3.17 en 3.18. Parameters: api wi W P

aantal stuks van item i in patroon p breedte van item i breedte van masterrol verzameling van alle patronen

Voorwaarden voor een patroon: n X i=1

api wi ≤ W,

api ≥ 0 and integer,

i = 1, ..., n, ∀p ∈ P

(3.17) (3.18)

We definiëren P als de verzameling met alle patronen en xp als de beslissingsvariabele die het aantal rollen gesneden volgens patroon p representeert. Wordt vervolgens de kost, in praktijk meestal het verlies, van ieder patroon p, gerepresenteerd door cp , dan kan het CSP zoals weergegeven in 3.19,3.20 en 3.21 gemodelleerd worden. (Gilmore & Gomory, 1961) Variabelen: xp

aantal keren dat patroon p gebruikt wordt

Parameters: api di W n

aantal stuks van item i in patroon p vraag naar item i breedte van masterrol totaal aantal items

Model: min

X

xp

(3.19)

i = 1, ..., n

(3.20)

p∈P

onder voorwaarden: X p∈P

api xp ≥ di ,


∀p ∈ P

(3.21)

15


Het aantal kolommen in vergelijkingen 3.19 tot 3.21 kan erg groot worden, zelfs voor problemen van gemiddelde grootte. Gilmore & Gomory stelde een techniek voor om de LP relaxatie op te lossen genaamd column generation (Gilmore & Gomory, 1961). De oplossingsprocedure start met een initiële set patronen. Dit kan bijvoorbeeld door voor elk item een patroon te ontwikkelen met het hoogst mogelijk aantal van dat specifiek item die uit de masterrol kunnen gemaakt worden. Dit aantal stuks kan berekend worden volgens formulering 3.22. Merk hierbij op dat bxc gelijk is aan het grootste integer getal niet groter dan x. bW/wi c

∀i

(3.22)

Vervolgens wordt de LP relaxatie van het probleem opgelost. Bijgevolg is men in staat om voor elke beperking 3.20 de schaduwprijs πi te berekenen. Deze schaduwprijzen zullen gebruikt worden om het meest aantrekkelijk patroon te zoeken. Dit patroon zal bekomen worden door oplossing van het deelprobleem met doelfunctie 3.23 en met beperkingen 3.24 en 3.25. Dit deelprobleem is een integer knapsack probleem. Variabelen: yi

aantal keren dat item i gebruikt wordt

Parameters: πi wi P m n

schaduw prijs van item i met betrekking tot beperking 3.20 breedte van item i verzameling van alle patronen totaal aantal patronen totaal aantal items

Model: min 1 −

n X

πi yi

(3.23)

i=1

onder voorwaarden: n X i=1

yi wi ≤ W,

yi ≥ 0 and integer

i = 1, ..., n

(3.24) (3.25)

Dit model levert het patroon, meer bepaald de kolom A met een minimale gereduceerde kost 1 − πA. Als deze gereduceerde kost positief is de huidige oplossing optimaal. Dit is logisch aangezien geen enkele kolom een negatieve gereduceerde kost heeft en bijgevolg het toevoegen van eender welke kolom geen verbetering van de doelfunctie 3.19 tot gevolg heeft. Indien echter de minimale gereduceerde kost kleiner is dan nul, zal het patroon dat gepaard


16

gaat met de kolom die deze gereduceerde kost minimaliseert, toegevoegd worden aan de verzameling van patronen. Het knapsack probleem kan opgelost worden door bijvoorbeeld een branch and bound algoritme. Branch and bound zal de verzameling F met mogelijke oplossingen onderverdelen in een eindige verzameling van deelverzameling F1 , ..., Fk . Deze deelverzamelingen worden nogmaals gesplitst in deelproblemen. Op deze manier bekomt men een boomstructuur die een ondergrens voor het probleem geeft. Het knapsack probleem kan ook opgelost worden door een algoritme gebaseerd op dynamic programming zoals beschreven in Gilmore & Gomory (1964, 1966). We kunnen tot slot de verschillende stappen in de oplossingsmethode voor eendimensionale CSP samenvatten als een proces van opeenvolgende stappen. In wat volgt worden deze stappen beschreven en figuur 5.1 vat deze stappen schematisch samen.

Figuur 3.4: Een visuele voorstelling van het oplossingsproces via column generation voor het eendimensionaal CSP


17

Procedure: 1. Maak een verzameling van initiële patronen (evenveel als er items/vragen/beperkingen zijn) 2. Los de LP relaxatie van het hoofdprobleem op met deze patronen 3. Bereken de schaduwprijzen 4. Deelprobleem oplossen met de in stap 3 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC  RC < 0 Er bestaat nog een betere oplossing, ga naar stap 5 Gereduceerde kost: RC ≥ 0 Optimale oplossing gevonden en ga naar stap 6 5. Voeg patroon toe aan verzameling van patronen en ga terug naar stap 2 6. Los hoofdprobleem op met huidige verzameling van patronen

3.2.3

Sequentieel heuristische methode

Sequentieel heuristische methoden behoren tot de klasse van lokaal zoekende heuristieken. Om deze methode te beschrijven zal de notatie gevolgd worden zoals beschreven door Maniezzo & Carbonara (Maniezzo & Carbonara, 1999). In dit hoofdstuk zal de werkwijze voor toepassing van sequentieel heuristische methoden op CSP besproken worden. In wat volgt zal eerst de algemene werkwijze besproken worden en vervolgens zal verduidelijkt worden hoe deze techniek toegepast kan worden op het CSP. Neem nu een combinatorisch optimalisatie probleem over een verzameling C = {c1 , c2 , ..., cn }. Noem S een oplossing van het probleem, F is de verzameling van alle haalbare oplossingen en F ⊆ P(C). P(C) is de machtsverzameling van C. Een kost functie z wordt gedefinieerd als z : P(C) → R. Het doel van dit algoritme is het vinden van een haalbare oplossing S ∗ die een minimum kost oplevert. We dienen dus S ∗ te vinden zodanig dat z(S ∗ ) ≤ z(S), ∀S ∈ F . Bovenop deze definities is ook nog de definitie van omgeving een noodzakelijk gegeven om deze procedure volledig te doorgronden. De omgeving van een oplossing S, voorgesteld door N (S), is een deelverzameling van P(C) gedefinieerd door een specifieke omgevingsdefinitie functie N : P(C) → P(P(C)). In het geval dat enkel haalbare oplossingen worden bekeken neemt deze definitie de vorm aan: N : F → P(F ). Gebruik makend van de hierboven beschreven notaties kunnen we lokaal zoekende heuristieken beschrijven met volgende stappen procedure.


18

Procedure: 1. Genereer een initieel haalbare oplossing S ˆ : ∀Sˆ ∈ N (S)} 2. Zoek S 0 zodanig dat S 0 ∈ N (S) en z(s0 ) = min{z(S) 3. if z(s0 ) < z(S) then S = S0 ga naar stap 2 end if 4. S ∗ = S De methode voor het oplossen van CSP gebruik makend van een sequentieel heuristische methode bestaat erin snijpatronen één voor één te genereren totdat aan alle voorwaarden met betrekking tot vraag voldaan wordt. De geselecteerde snijpatronen moeten een laag snijverlies hebben om de objectieve functie te doen dalen. Verder dient men ook rekening te houden dat een verzameling met gevraagde breedtes dient over te blijven om te voorkomen dat louter te wijde of te smalle breedtes overblijven in een stap van de oplossingsprocedure. Dit zou nefaste gevolgen op het snijverlies tot gevolg kunnen hebben. De procedure die Haessler & Sweeney beschreef in een aantal publicaties wordt hier beknopt weergegeven. (Haessler, 1971, 1975, 1988; Haessler & Sweeney, 1991) Deze methode heeft enkele voordelen, zo is er geen afronding nodig. Verder is het mogelijk om exact aan de vraag te voldoen. Parameters: wi di d0i xp api W n

breedte van item i vraag naar item i deel van de vraag naar item i waaraan nog niet voldaan is aantal keren dat patroon p gebruikt wordt aantal stuks van item i in patroon p breedte van masterrol totaal aantal items

Procedure: 1. Er wordt gestart met een analyse van de vraag; hiertoe worden er 2 parameters berekend. Een eerste parameter 3.26 schat het aantal masterrollen nodig om aan de vraag te voldoen. Een tweede parameter 3.27 schat het gemiddelde aantal rollen die moeten uit een masterrol gehaald worden. Pn 0 i=1 di wi (3.26) PnW 0 di Pn i=1 (3.27) 0 ( i=1 di wi )/W

19


2. Bepaal met behulp van de berekende parameters minimumvereisten waaraan een snijpatroon moet voldoen om meegenomen te worden in de oplossing. De te bepalen karakteristieken zijn: ∆max : maximum toelaatbaar snijverlies amin en amax : het minimum en maximum aantal items toegelaten per snijpatroon xmin : het minimum aantal masterrollen die moeten versneden worden volgens een bepaald snijpatroon

Volgens Haessler & Sweeney liggen typische waarden voor ∆max ergens tussen 0.006W en 0.03W . De waarde van xmin varieert over het algemeen tussen 0.5 en 0.9 keer de eerste parameter berekend in 3.26. amax wordt meestal ingesteld op het maximum aantal stuks waarin de machine van de masterrol kan snijden. amin wordt meestal gezet op 1 minder dan het gemiddelde berekend voor de tweede parameter in vergelijking 3.27. 3. Nu zoeken we een patroon dat aan de minimumvoorwaarden voldoet. Een haalbaar patroon beschreven door vector Ap = (ap1 , ..., api , ..., apn ) voldoet aan deze minimum voorwaarden als deze voldoet aan de beperkingen 3.28, 3.29 en 3.30

W−

n X i=1

amin ≤

api wi ≤ ∆max

n X

(3.28)

api ≤ amin

(3.29)

d0i ≤ 1 ∀api > 0 api xmin

(3.30)

i=1

4. Als er een patroon gevonden is; voeg het patroon toe aan de oplossing aan maximum mogelijk waarde van xp , zodat de vraag naar alle items niet overschreden wordt in de oplossing. Verminder nu de vraag naar de desbetreffende items en ga terug naar stap 1. 5. Als er geen patroon gevonden is; verzwak dan een minimum vereiste. Meest gebruikelijk zal men xmin verlagen, waardoor men meer snijpatronen in overweging neemt. Het beëindigen van dit proces volgt na het selecteren van het patroon met het minimale snijverlies wanneer xmin een waarde van 1 heeft. Indien het proces nog niet kan beëindigd worden, ga terug naar stap 3. De voordelen van de sequentieel heuristische methode ten opzichte van de lineaire programmeringsmethode zitten hem onder andere in het feit dan men via de sequentieel heuristische methode de mogelijkheid heeft andere factoren, naast snijverlies, die buiten het bereik van lineaire programmeringsmodellen liggen, aan de doelfunctie toe te voegen . Zo kan men bijvoorbeeld het aantal veranderingen van patronen in rekening brengen, door te zoeken naar


20

patronen met een hoog gebruik. Hier staat wel tegenover dat wanneer men een CSP gaat oplossen via de sequentieel heuristische methode men een groter snijverlies tot gevolg kan hebben (Haessler, 1988).

3.3

Meta-heuristische methoden

Een probleem bij lokaal zoekende heuristieken zit hem in het feit dat ze kunnen vastlopen in lokale optima. Alternatieve benaderingen voor deze traditionele heuristieken begonnen op te komen midden de jaren ’70. Een gemeenschappelijke factor van deze meta-heuristische methoden is hun mogelijkheid om een lokaal zoekende heuristiek te gidsen zodat de val van lokale optima kan vermeden worden (Glover, 1986). Er bestaat een groot aantal verschillende meta-heuristische methoden. Een groot deel van deze methoden zijn toegepast geweest op CSP. In wat volgt worden twee methodes besproken, namelijk tabu search (TS) en greedy randomized adaptive search procedure (GRASP). In deze beschrijving ligt de nadruk veeleer op de werking, het idee achter deze methodes, dan het aanbieden van volledig uitgewerkte modellen voor het oplossen van CSP.

3.3.1

Tabu search

In TS zal tijdens een iteratie altijd de beste oplossing uit de omgeving meegenomen worden, ook al is ze slechter dan de vorige oplossing. Hierdoor voorkomt men dat de methode vastloopt in locale optima. Dit is in tegenstelling met de sequentieel heuristische methode waar enkel naar de beste oplossing uit de omgeving gegaan wordt als deze beter is dan de huidig beste oplossing. Alle reeds onderzochte oplossingen worden opgeslagen in een lijst, namelijk de tabu list (TL). Het is gedurende de oplossingsprocedure strikt verboden terug te keren naar een oplossing uit de lijst. Er wordt een stopcriterium toegevoegd, het algoritme zal dus blijven lopen ofwel tot een op voorhand vastgelegd aantal iteraties bereikt wordt, ofwel tot een bepaalde tijdslimiet bereikt is. Hieronder wordt de procedure van het TS oplossingsalgoritme weergegeven (Maniezzo & Carbonara, 1999). De typologie is dezelfde als deze voorheen gebruikt bij de algemene beschrijving van de sequentieel heuristische methode in hoofdstuk 3.2.3. Procedure: 1. Genereer een initieel haalbare oplossing S, stel S ∗ = S en stel T L = ∅ ˆ : ∀Sˆ ∈ N (S), Sˆ ∈ 2. Zoek S 0 zodanig dat S 0 ∈ N (S) en z(s0 ) = min{z(S) / T L} 3. S = S 0 , T L = T L ∪ S, if z(S 0 ) < z(S) then S ∗ = S end if 4. if not stopcriterium then ga naar stap 2 end if


21

Een voorbeeld waarin deze techniek toegepast wordt voor het oplossen van een CSP kan gevonden worden in het artikel van Alvares-Valdés et al. (2002). Hierin wordt een tweedimensionaal guillotine CSP besproken van Dyckhoff’s type 2/V/I/M. In essentie komt het oplossen van dit probleem neer op het oplossen van een tweedimensionaal knapsack probleem (Gilmore & Gomory, 1966). In het hierboven vermelde artikel (Alvares-Valdés et al., 2002) worden 4 verschillende versies, zoals geclassifieerd door Fayard et al. van dit probleem besproken en toegelicht (Fayard et al., 1998). Voor een gedetailleerde beschrijving van deze toepassing wordt doorverwezen naar de vermelde literatuur.

3.3.2

GRASP

De GRASP (greedy randomized adaptive search procedure) methode werd ontwikkeld door Feo & Resende voor het oplossen van problemen met betrekking op verzamelingen (Feo & Resende, 1995). Om aan locale optima te ontsnappen zal de GRASP methode, telkens een optima bereikt wordt, herstarten in een andere veel belovende plaats. Elke iteratie zal dusdanig bestaan uit fases waarin lokaal gezocht wordt en uit een procedure voor verandering van regio waarin gezocht wordt. De selectie van het volgende element gebeurt op basis van een greedy, letterlijk vertaald gulzige functie. Verder is deze methode ook adaptive aangezien de greedy functie ook rekening houdt met de voorheen gekozen elementen (Alvares-Valdés et al., 2002). Hieronder wordt de procedure van het GRASP oplossingsalgoritme weergegeven. De typologie is terug dezelfde als deze voorheen gebruikt bij de algemene beschrijving van de sequentieel heuristische methode in hoofdstuk 3.2.3 en de beschrijving van het TS algoritme in 3.3.1. Procedure: 1. Genereer een oplossing S door gebruik te maken van een greedy randomized procedure. In de eerste iteratie, stel S = S ∗ 2. Maak gebruik van een lokaal zoekende procedure om startende vanaf S, tot een waarde voor S 0 te komen 3. if z(S 0 ) < z(S) then S ∗ = S 0 end if 4. if not stopcriterium then ga naar stap 1 end if Alvares-Valdés et al. hebben de toepassing van GRASP bestudeerd op tweedimensionale guillotine CSP van Dyckhoff’s type 2/V/I/M. In stap 1 van de procedure wordt er gebruik gemaakt van een constructief algoritme dat rechthoeken snijdt uit een grotere rechthoek. Om de oplossing te verbeteren worden de delen waar snijverlies optreedt samen genomen met andere aanliggende stukken tot grotere rechthoeken. Deze grotere rechthoeken worden dan opnieuw versneden via het algoritme met als doel een kleiner snijverlies. Een typisch stopcriterium voor deze procedure is een aantal iteraties zonder verbetering aan de huidige


22

oplossing. (Alvares-Valdés, Parajón & Tamarit, 2002) Voor een volledige beschrijving en uitwerking van deze toepassing wordt naar de literatuur verwezen.

3.4

Algoritmische methoden

Naast heuristische en meta-heuristische methoden bestaat er nog een derde groep, de algoritmische methoden. Deze methoden garanderen de globale optimale oplossing in tegenstelling tot heuristische en meta-heuristische methoden die deze globale optimale oplossing niet kunnen garanderen maar wel een aanvaardbare oplossing binnen een beperkte tijd geven. Om deze globale optimale oplossing te garanderen gaan algoritmische methoden gepaard met een (zeer) trage convergentie. Algoritmische methoden zijn gebaseerd op het transformeren van een origineel niet-convex mixed integer nonlinear problem (MINLP) naar een oplosbaar probleem. Wegens de complexiteit van en diversiteit aan algoritmische methoden drijft dit onderwerp ons te ver af van de focus van deze literatuurstudie. Er wordt hier dan ook niet verder op ingegaan. Voor meer informatie hierover wordt naar de literatuur verwezen.

3.5

Vergelijking van de verschillende oplossingsmethoden

Algoritmische methoden geven de optimale oplossing voor een probleem. Hiertegenover staat dat deze nauwkeurigheid zich laat voelen in tragere convergentie tijden. Wanneer de rekentijd belangrijker geacht wordt dan de preciesheid van de oplossing, ligt de keuze voor heuristische of meta-heuristische methoden voor de hand. Als echter rekentijden niet belangrijk zijn, maar men wel zekerheid wil over het optimaal zijn van de bekomen oplossing, kiest men best voor een algoritmische oplossing. Heuristische methoden hebben wel het nadeel dat ze aanpassingen vergen naargelang het probleem waarvoor ze toegepast worden. Ook kunnen heuristische methoden vastlopen in lokale optima. Meta-heuristische methoden weten dit probleem te voorkomen door kandidaat oplossingen, die zich buiten de lokale regio bevinden waarbinnen de heuristische methoden zoeken, te gaan kiezen. In meta-heuristieken is het zoekproces meestal ondersteund door een onderliggende heuristische methode.

Hoofdstuk 4

Probleemdefinitie en onderzoeksvragen Na het doornemen van de nodige literatuur tijdens Hoofdstuk 3 zijn we nu in staat ons een beeld te vormen van het specifieke versnijdingsprobleem binnen Agfa-Gevaert. Alvorens van start te gaan met het ontwerpen van een model wordt in dit hoofdstuk eerst stil gestaan bij het versnijdingsprobleem zelf. Eerst worden de verschillende fasen van het productieproces beschreven, vervolgens wordt beschreven welke historische data beschikbaar zijn. Nu is er een voldoende solide basis om na het beschrijven van de huidige optimalisatiemethode een aantal doelstellingen en onderzoeksvragen voor deze thesis te formuleren. Tot slot wordt ook de keuze van software, om het model in te programmeren, kort toegelicht.

4.1

Het productieproces

Zoals reeds kort besproken in hoofdstuk 2.3 verloopt het productieproces van PCB film in twee fazen. verschillende productiefasen: Fase 1: de productiefase: gieten van masterrollen Fase 2: de confectiefase: versnijden van de masterrol tot eindproduct

4.1.1

Productiefase

In een eerste fase wordt de fotografische emulsie op een PET onderlaag gegoten. Er wordt een halffabricaat geproduceerd, namelijk de masterrollen. De PET onderlaag heeft een breedte van 1.728 meter. Deze breedte is de fysieke breedte van een masterrol. Vervolgens wordt op deze onderlaag een fotografische emulsie aangebracht. Deze kan niet over de volledige breedte van de masterrol gegoten worden, want aan beide kanten van de masterrol dient een karteling te worden voorzien. Deze karteling is noodzakelijk aangezien tijdens het op- en afrollen de 23

Hoofdstuk 4. Probleemdefinitie en onderzoeksvragen

24

masterrol dient te kunnen vast genomen en begeleid te worden zonder de dure fotografische emulsie te beschadigen. Door deze karteling is de maximaal te begieten breedte gelijk aan 1.682 meter. Er bestaan twee fabricage soorten van deze masterrollen voor PCB film. Deze fabricage soorten verschillen niet in fysieke breedte van de PET onderlaag, maar verschillen wel in gietbreedte. Deze fabricage soorten zijn fbs280528 en fbs280668. Fabricage soorten: Fbs 280528: er wordt fotografische emulsie gegoten op de volle breedte van 1.682 meter Fbs 280668: er wordt fotografische emulsie gegoten op een smallere breedte van 1.350 meter

In wat volgt zal naar de fabricage soort fbs 280528 verwezen worden als brede masterrol en naar de fabricage soort fbs 280668 als smalle masterrol . Hierbij dient de opmerking gemaakt te worden dat hoewel de benaming anders doet vermoeden deze twee masterrollen eenzelfde fysieke breedte hebben, beide bestaan uit een PET onderlaag van 1.728 meter. Deze benaming heeft echter zijn oorsprong in het verschil in de gietbreedte van de fotografische emulsie. Bij de brede masterrol wordt deze gegoten over de volledige breedte van de masterrol, met uitzondering van de karteling, terwijl bij de smalle masterrol slechts een beperkt deel van de PET onderlaag begoten wordt. Dit verschil wordt verduidelijkt in figuur 4.1.

Figuur 4.1: Visuele voorstellingen van de verschillende fabricagesoorten, alle afmetingen in meter


4.1.2

25

Confectiefase

In de tweede fase van het productieproces, de confectiefase, zal de masterrol versneden worden tot eindproduct. Deze eindproducten zijn vellen van rechthoekig formaat. Deze worden verpakt in pakken van x stuks. Uitzonderlijk worden eindproducten verpakt in bobijnvorm. Het proces om gedurende de confectiefase van masterrol tot eindproduct te gaan, bestaat uit verschillende stappen. Verschillende stappen in de confectiefase: Stap 1: versnijden van masterrol in verschillende bandbreedtes (in praktijk meestal 2 of 3) Stap 2: de verschillende bandbreedtes worden gekapt op een bepaalde lengte Stap 3: inpakken van de vellen of bobijnen

In figuur 4.2 worden de verschillende fasen en stappen in het productieproces van PCB film, die hierboven besproken werden, schematisch weergegeven.

Figuur 4.2: Een visuele voorstelling productieproces voor PCB film binnen Agfa-Gevaert

4.1.3

Confectieafdeling in Wuxi

Voor de confectieafdeling in Wuxi wordt de tweede fase, de confectiefase, van het productieproces opgesplitst. Enkel de laatste twee stappen zullen in Wuxi ter plaatse uitgevoerd worden. De voorbereiding zal in Mortsel gebeuren. Fase 1 van het productieproces en de


26

eerste stap van de tweede fase worden in Mortsel uitgevoerd. Het productieproces wordt weergegeven in figuur 4.3.

Figuur 4.3: Een visuele voorstelling productieproces van PCB film voor artikelen gedeeltelijk geproduceerd in Wuxi

4.1.4

Historische data

Om een representatief model te ontwikkelen en een vergelijkingsbasis voor te stellen dienen we de data uit het verleden nader te bekijken. Uit de historische snijplannen binnen AgfaGevaert kunnen een aantal belangrijke parameters gehaald worden, deze gegevens bevatten data met betrekking tot de periode van september 2008 tot augustus 2009. Historische parameters: een uniek ge¨ıdentificeerd artikelcode (mabc-code) de lengte en breedte van ieder artikel verpakhoeveelheid van een bepaald product de vraag naar een artikel historische combinaties snijbreedtes per combinatie


27

Het zal dus noodzakelijk worden om uit de overvloed aan informatie uit het verleden de nodige informatie te filteren en in een correcte vorm weer te geven. Er zal dus voor dat het model uitgevoerd wordt een pre-processing van de data dienen te gebeuren. Nadat een model zijn oplossing voorstelt zal een post-processing dienen te gebeuren zodat de resultaten op een bruikbare manier worden voorgesteld. Hoe dit concreet in zijn werk zal gaan, en welke vereenvoudigingen gemaakt worden komt uitgebreid aan bod bij het beschrijven van de verschillende modellen in hoofdstuk5. Naast gegevens over de verschillende artikels en de historisch gebruikte snijplannen, dienen er ook gegevens met betrekking tot het combinatieverlies in de huidige planningsmethode verzameld te worden. Deze waarden zijn noodzakelijk om nieuwe optimaliseringsmodellen te toetsen aan de huidige methode. Om de representativiteit van deze gegevens te waarborgen worden de gegevens met betrekking tot de combinaties van een volledig jaar opgevraagd. Hierdoor wordt er vermeden dat de resultaten van een ontworpen model vergeleken zouden worden met een waarde die slechts een momentopname is. De gegevens met betrekking tot de combinatieverliezen in de periode van 1 mei 2009 tot en met 30 april 2010 worden weergegeven in figuur 4.4.

Figuur 4.4: Gegevens met betrekking tot het historische combinatieverlies binnen Agfa-Gevaert van 01/05/2009 tem 30/04/2010

Om alle misverstanden en interpretatieverschillen uit de weg te ruimen wordt nu elk van de in figuur 4.4 aangehaalde parameters toegelicht en gedefinieerd. De typologie van deze parameters is dezelfde als deze gebruikt binnen Agfa-Gevaert. Parameters met betrekking tot het combinatieverlies: Bruto oppervlakte (m2 ): met de bruto oppervlakte wordt de volledige oppervlakte van de gebruikte masterrollen weergegeven. Concreet komt dit neer op de fysieke breedte, meer bepaald de breedte van de PET onderlaag van de masterrol te vermenigvuldigen met de voor het versnijden gebruikte lopende meters van de masterrollen. Nuttige oppervlakte (m2 ): de nuttige oppervlakte houdt in tegenstelling tot de bruto oppervlakte geen rekening met de PET onderlaag maar kijkt enkel naar de met


28

fotografische emulsie begoten oppervlakte. Dit komt dus eigenlijk neer op de totale oppervlakte die kon gebruikt geweest zijn om vellen uit te snijden. Gecombineerde oppervlakte (m2 ): de gecombineerde oppervlakte is de oppervlakte die effectief versneden is tot banden. Deze oppervlakte is dus de nuttige oppervlakte verminderd met het breedteverlies. Boordverlies (m2 ): het boordverlies wordt gedefinieerd als het verschil tussen de bruto oppervlakte en de nuttige oppervlakte. Dus het boordverlies geeft eigenlijk de hoeveelheid vierkante meter van de PET onderlaag aan die niet begoten is met fotografische emulsie. Boordverlies (%): dit is het boordverlies in vierkante meter gedeeld door de bruto oppervlakte. Dit percentage geeft dus het onbegoten percentage van de onderlaag weer. ´ e´ endimensioneel combinatieverlies (m2 ): het ééndimensioneel combinatieverlies geeft het verschil weer tussen de nuttige oppervlakte en de gecombineerde oppervlakte. Dit verschil is in feite het breedteverlies van een patroon vermenigvuldigd met de gebruikte lopende meters van dat patroon. ´ e´ endimensioneel combinatieverlies (%): dit is het percentage breedteverlies ten opzichte van de nuttige oppervlakte.

4.2 4.2.1

Versnijdingsprobleem Huidige problematiek

De huidige versnijdingsoptimalisatie gebeurt op basis van ervaring en intu¨ıtie van de werknemer die momenteel verantwoordelijk is voor het opmaken van de snijplannen. Hoewel we de kennis, ervaring en expertise van deze werknemers zeker niet in twijfel willen trekken, dient opgemerkt te worden dat er geen enkele garantie is dat het gekozen snijplan optimaal is. Een mogelijke verbetering schuilt hem in de huidige aanpak waar men een combinatie die weinig verlies oplevert toch gaat gebruiken ook al zijn maar 2 van de 3 gecombineerde artikelen gevraagd. Er wordt dus een stock van dit derde artikel opgebouwd om een veel gebruikte, goede combinaties aan te wenden. Eenmaal dit derde artikel te veel stock heeft mag het niet meer geproduceerd worden en zal er nu gecombineerd worden met andere combinaties met een groter breedteverlies. Door in eerste instantie een andere combinatie te kiezen kon dit groter verlies misschien vermeden worden.


4.2.2

29

Onderzoeksvragen

Deze thesis heeft als doel het ontwikkelen van een model ter optimalisatie van de versnijdingsproblematiek omtrent PCB film binnen de confectieafdeling van Agfa-Gevaert in Mortsel. Hierbij wenst deze thesis een vergelijking te maken tussen twee modellen. Een eerste model zal zich baseren op de techniek van column generation, het tweede model zal vanuit een bibliotheek met historisch gebruikte combinaties een snijplan genereren. De thesis wenst na te gaan wat nu net de voor- en nadelen zijn van deze twee technieken. Niet enkel het combinatieverlies wordt hierin beschouwd, ook gebruiksgemak en aanpassingsvermogen van beide modellen zijn belangrijke eigenschappen. Er dient ook nagegaan te worden welke de invloed van een aantal parameters is met betrekking tot zowel het percentage combinatieverlies, het aantal gebruikte patronen als de hoeveelheden producten teveel geproduceerd. Zo wil men tijdens dit onderzoek de invloed van onder andere de tolerantie op de hoeveelheden teveel geproduceerd nagaan. Verder dient er ook onderzocht te worden wat de invloed is van het niet integer zijn van het aantal rollen geproduceerd met een bepaald patroon. Aangezien het bij het versnijden van de masterrol tot banden niet gebruikelijk en niet eenvoudig is om halverwege de masterrol van snijbreedtes te veranderen, dient hier ofwel gestreefd te worden naar een integer aantal rollen per patroon, ofwel dient de mogelijkheid om het veranderen van snijbreedtes te implementeren in het snijproces onderzocht te worden. In verband met deze problematiek dient ook de mogelijkheid om deze hoeveelheden af te ronden onderzocht te worden. Verder wil dit onderzoek ook een antwoord bieden op de vraag hoe men best de Wuxi artikelen gaat combineren. Er zijn hier 3 verschillende mogelijkheden te onderscheiden. In een eerste mogelijke aanpak wordt de vraag naar Wuxi artikelen op zich, los van de Mortsel artikelen gecombineerd. Een tweede mogelijkheid bestaat uit het betrekken van alle artikelen die hun breedte of lengte delen met één van de Wuxi bandbreedtes in de versnijdingsoptimalisatie van de Wuxi artikelen. Een derde manier zal alle artikelen, zowel de Mortsel als Wuxi artikelen onafhankelijk van hun afmetingen meenemen in de versnijdingsoptimalisatie. Een vergelijking van deze verschillende mogelijkheden is gewenst. Daarnaast is een vergelijking van de met beide modellen behaalde resultaten ten opzichte van het historische percentage combinatieverlies wenselijk. De onderzoeksvragen van deze thesis kunnen als volgt samengevat worden: Onderzoeksvragen: Wat zijn de voor- en nadelen van het column generation model en het historische bibliotheek model? Wat is de invloed van bepaalde parameters op de resultaten van modellen?


30

Hoe groot is de noodzaak van een integer oplossing, en op welke manieren kan deze bekomen worden? Hoe zal men de Wuxi behoeftes optimaal (al of niet gecombineerd samen met andere PCB artikelen) versnijden uit de beschikbare masterrollen? Hoe verhouden de resultaten van modellen zich ten opzichte van de historisch behaalde resultaten?

4.2.3

Design of Experiments

In het voorgaand hoofdstuk 4.2.2 werden een aantal onderzoeksvragen en doelstellingen van deze thesis beschreven. Om nu op een systhematische en stapsgewijze werkwijze te werk te gaan wordt er een design of experiments opgesteld. Dit design of experiments geeft de gekozen methodologie weer van de thesis. Door deze methode te volgen zullen we in staat zijn een leerproces te creëren en zodoende stapsgewijs naar een algemeen geldend model te kunnen toewerken. Het design of experiments is schematisch weergegeven in figuur 4.5.

Figuur 4.5: Een visuele voorstelling van het design of experiments met aanduiding van de verschillende fasen en stappen

In wat volgt zal dit design of experiments stap voor stap besproken worden. Er zal voor elke stap een duidelijke beschrijving gegeven worden van de precieze inhoud van deze stap alsook waarom deze stap noodzakelijk is. Enerzijds voor het voltooien van het groeiproces naar een


31

algemeen bruikbaar model, anderzijds om een antwoord te kunnen formuleren op bepaalde onderzoeksvragen. Het design of experiments is zoals te zien in figuur 4.5 ook nog opgedeeld in twee fasen. In een eerste fase wordt gestart met een eenvoudig model om stapsgewijs naar een algemeen bruikbaar model toe te groeien. In de tweede fase is dit model afgewerkt en algemeen toepasbaar en gaan we nu de modellen zowel onderling als met de historische waarden gaan vergelijken. Fase 1: Stap 1: In een eerste stap zal enkel de vraag vanuit Wuxi geanalyseerd en gecombineerd worden. Zoals eerder besproken worden er slechts vier bandbreedtes geleverd aan Wuxi. Deze vier bandbreedtes zijn 0.5075 m, 0.5583 m, 0.6091 m en 0.6559. De vraag vanuit Wuxi wordt doorgegeven in lopende meter. Er wordt speciaal voor deze Wuxi-artikelen vier nieuwe unieke artikelcodes gecreëerd en deze codes komen overeen met een vel met als breedte de specifieke bandbreedte van de artikelen die gevraagd worden door Wuxi en als lengte één meter. Zo kan de vraag naar lopende meter eenvoudig vertaald worden naar een aantal vellen. Tijdens deze stap zal het model zoals beschreven in hoofdstuk 3.2.2 uitgebreid worden om binnen dit model de mogelijkheid om te werken met 2 masterrollen, van verschillende breedte te implementeren. De tolerantiegrens op de in surplus productiehoeveelheden per artikel wordt hier vrij smal verondersteld. Stap 2: In deze tweede stap zal van exact dezelfde situatie als in stap 1 vertrokken worden, maar de tolerantie op de productiehoeveelheden per artikel zal breder genomen worden. Deze bredere tolerantiegrens heeft zijn oorsprong in de veronderstelling dat het surplus aan geproduceerde hoeveelheden kan weggewerkt worden door ofwel een groter volume naar Wuxi te sturen of de banden in surplus in de Mortsel confectie te verwerken. Door vergelijking met de oplossing in geval 1 zal worden nagegaan welke de invloed van de tolerantie op het combinatieverlies is. Stap 3: De derde stap van de eerste fase bestaat erin tijdens de snijoptimalisatie naast de Wuxi-artikelen ook de artikelen, waarvan ofwel hun lengte ofwel hun breedte gelijk is aan één van de Wuxi bandbreedtes mee te combineeren. Nu is het zo dat in het huidige column generation model een keuze of het artikel langs of dwars gecombineerd wordt noodzakelijk is. Om deze keuze niet te hoeven vast te leggen en een vrije keuze van de langs- of dwarsligging mogelijk te maken, zal een tweede uitbreiding van het model noodzakelijk zijn. In het model, gebruik makende van de historische bibliotheek, stelt de langs/dwars problematiek zich niet aangezien voor beide gevallen een apart snijpatroon kan toegevoegd worden aan de bibliotheek.

Fase 2: Stap 4: In deze stap worden alle artikelen samen gecombineerd. Ook artikelen die zowel in lengte als breedte verschillen van de Wuxi bandbreedtes worden meegenomen in de versnijdingsoptimalisatie. Indien haalbaar, wordt er geopteerd om in deze fase een derde


32

uitbreiding aan het model toe te voegen. Deze uitbreiding heeft als doel de mogelijkheid te implementeren om binnen een bepaalde band van artikel te veranderen. Zonder deze uitbreiding wordt een keuze gemaakt welke artikelen de bandbreedtes bepalen. Eenmaal deze banden gesneden, wordt enkel dat artikel dat de breedte heeft bepaald uit deze band gesneden. Na het opzoeken van dergelijke gevallen in de historische combinaties zien we dat deze gevallen effectief in het verleden voorgekomen zijn, het gaat meestal om hetzelfde artikel (dezelfde afmetingen) maar een andere verpakhoeveelheid. Artikelen die in minstens 1 afmeting van elkaar verschillen komen zelden voor in eenzelfde band, hoewel vermoed wordt dat deze uitbreiding een merkbare invloed kan hebben op het combinatieverlies bij smalle tolleraties. Stap 5: Er kan pas een oordeel over de methodes geveld worden als de bekomen resultaten vergeleken worden met historische data. Het is dan ook het doel van deze stappen dat we de modellen gaan toetsen ten op zichte van de historische waarden.

Tijdens de beknopte beschrijving van alle stappen van het design of experiments werd duidelijk dat het model van Gilmore & Gomory in drie stappen zal worden uitgebreid tot een model dat in staat is een representatief snijplan te produceren. De verschillende stappen vragen ook om verschillende input gegevens. Uitbreidingen model: 1. Uitbreiding 1: Verschillende breedtes van masterrol 2. Uitbreiding 2: langs- vs. dwars positionering (90° rotatie) 3. Uitbreiding 3: Verschillende artikelen in een band Inputgegevens: 1. Stap 1 en stap 2: enkel de 4 Wuxi artikelen 2. Stap 3: 4 Wuxi artikelen samen met artikel die lengte of breedte delen met een Wuxi bandbreedte 3. Stap 4 en stap 5: alle artikelen Door het volgen van de specifieke stappen in dit design of experiments wordt een leerproces gecreëerd waardoor we stap voor stap het probleem gaan doorgronden. Er wordt gestart met een vrij eenvoudig model en dit wordt dan verder uitgebreid tot de volledige snijproblematiek binnen Agfa-Gevaert in het model aan bod komt. In figuur 4.6 wordt het leerproces schematisch weergegeven.


33

Figuur 4.6: Weergave van het leerproces tijdens het design of experiments

4.2.4

Historische bibliotheek vs column generation

In het design of experiments worden naast de verschillende stappen ook 2 kolommen weergegeven. Er wordt voor gekozen om twee verschillende modellen te ontwikkelen en deze onderling te vergelijken. Het eerste model genereert combinaties via de techniek van column generation, het tweede model zal uit een bibliotheek combinaties kiezen. Gegenereerde combinaties via column generation Dit model bouwt verder op de in de literatuurstudie besproken column generation techniek (zie 3.2.2). Er wordt in dit model vertrokken vanuit een vraag naar bepaalde artikelen. Er wordt een initiële set patronen gemaakt. In een aantal iteraties zal men telkens nagaan of een patroon bestaat dat de doelfunctie nog kan verbeteren. Bestaat er zo een patroon dan wordt dit patroon toegevoegd. De complexiteit zit hem, in tegenstelling tot het bibliotheek model, veeleer in het model dan in de pre-processing van de data. Bibliotheek van historische combinaties Uit de historische data is het mogelijk de gebruikte snijplannen te filteren. Door al deze gegevens te verzamelen kan een bibliotheek van historisch gebruikte combinaties opgesteld worden. In dit model zal er dus heel wat pre-processing nodig zijn om de bibliotheek aan te maken. Het model op zich is echter een eenvoudig integer lineair programmeringsmodel, waar het de bedoeling is om net deze combinaties te kiezen uit de bibliotheek die een minimaal verlies geven.

4.2.5

Software

Een eenvoudig lineair programmeringsprobleem kan geprogrammeerd worden gebruik makend van Microsoft Excel . Zo kan met de Excel omgeving een model gebouwd worden ter oplossing


34

van de eerste twee stappen van ons design of experiments besproken in hoofdstuk 4.2.3. Een screenshot van het desbetreffende model is gegeven in bijlage A. Het wordt duidelijk dat deze solver enkel kan toegepast worden op het model dat, aan de hand van een bibliotheek van de historische combinaties, een oplossing voor het CSP zoekt. Ook dient opgemerkt te worden dat bij uitbreiding van het aantal parameters in de volgende stappen van het design of experiments het model in de Excel solver niet krachtig genoeg en te omslachtig zal worden. Wegens de beperktheden van het model via de Excel solver zullen de modellen worden ontworpen met behulp van de programmeertaal AMPL (A Mathematical Programming Language). AMPL is een krachtige algebra¨ısche modelleringstaal voor lineaire en niet-lineaire optimaliseringsproblemen. De typische notatie vergt enige ervaring maar eens de notatie en denkwijze doorgrond zijn, vallen de vele mogelijkheden en de scheiding tussen data en model meteen op. Een typisch model in AMPL bestaat uit 3 bestanden: AMPL bestanden: .RUN bestand: het .RUN bestand is het hoofdbestand dat wordt opgeroepen door de solver. In dit bestand worden verwijzingen gemaakt naar de .MOD en .DAT bestanden. Hierin wordt de algemene oplossingsprocedure geprogrammeerd. .MOD bestand: het .MOD bestand start met het definiëren van de verschillende parameters en variabelen. In dit bestand worden voorts nog de verschillende optimaliseringsfuncties en hun beperking geprogrammeerd .DAT bestand: dit bestand bevat alle gegevens die gebruikt worden tijdens het oplossen van het model. Het bestand met de data staat dus los van de bestanden met het eigenlijk optimaliseringsmodel. Het is dus eenvoudig om het model op andere data uit te voeren. Enkel dient er naar een ander .DAT bestand verwezen worden vanuit het .RUN bestand.

Het model opgelost via de Excel solver zal enkel gebruikt worden om, in kleinschalige cases, de correctheid van de modellen ontworpen met behulp van de AMPL-software te valideren.

Hoofdstuk 5

Ontwerp en validatie versnijdingsmodel In dit hoofdstuk zullen de modellen ontwikkeld worden. Zowel het column generation model als het model waarbij gebruik wordt gemaakt van de historische combinaties zullen aan bod komen. Zoals besproken in Hoofdstuk 4 wordt er vanuit Agfa-Gevaert geopteerd om zowel de mogelijkheden als de beperkingen van deze twee modellen te analyseren. Het column generation model zal op zoek gaan naar een nieuwe combinatie die de doelfunctie kan verbeteren. Het model met de historische bibliotheek zoekt uit vele combinaties de best mogelijke. Er zal in beide modellen vertrokken worden van een vraag naar verschillende artikelen. De vraag naar artikelen met eenzelfde afmetingen, maar met een verschil in verpakkingshoeveelheden, wordt samengenomen. Aangezien het voor de versnijding geen verschil uitmaakt per hoeveel stuks een bepaald artikel verpakt wordt, is dit een veronderstelling die geen invloed zal hebben op het bekomen resultaat.

5.1

Gegenereerde combinaties via column generation

5.1.1

Basismodel gebaseerd op model van Gilmore & Gomory

Er zal vertrokken worden vanuit het model om een ééndimensioneel CSP probleem op te lossen van Dyckhoff’s types 1/V/I/R en 1/V/D/R, zoals besproken tijdens de literatuurstudie in hoofdstuk 3.2.2. Eerst en vooral dient het model aangepast te worden aan de specifieke situatie waarvoor dit model een oplossing wenst te bieden. Vervolgens zullen er een drietal uitbreidingen aan het model worden toegevoegd om te voldoen aan alle eisen die aan het model gesteld worden. Om het model aan te passen aan de specifieke situatie worden enkele parameters toegevoegd. In dit specifiek geval worden geen staven in verschillende stukken gesneden. Hoewel het snijden van de masterrol in verschillende bandbreedtes veel gelijkenissen vertoont met deze 35

Hoofdstuk 5. Ontwerp en validatie versnijdingsmodel

36

situatie is ze niet volledig identiek. Een gesneden band is namelijk geen eindproduct, wat wel zo is voor de staaflengten die gesneden worden uit grote staven. Er zal bijgevolg ook rekening moeten gehouden worden met het aantal vellen van een bepaald artikel dat men uit een band kan halen. In de praktijk blijkt de lengte van een masterrol licht te variëren. Er wordt besloten om in alle modellen te rekenen met een constante rollengte van 3730 meter. Dit is een gemiddelde waarde voor de lengte van de masterrol. Deze veronderstelling van een constante rollengte zal geen invloed hebben op onze resultaten aangezien het breedteverlies en niet het verlies op het einde van een rol bepalend is bij het berekenen en vergelijken van de verschillende modellen onderling en het toetsen van deze modellen aan de historische waarden. In het basismodel worden enkele veronderstellingen gedaan met betrekking tot de werkelijke situatie. Deze veronderstellingen houden enkele vereenvoudigingen van het model in. Hierdoor zal de analogie met het model van Gilmore & Gomory duidelijk worden. Deze veronderstellingen worden dan in enkele uitbreidingen weggewerkt zodat het uiteindelijke model toepasbaar zal zijn op de werkelijke situatie. Veronderstellingen van het basismodel: 1. Er kan slechts op één breedte van masterrol gecombineerd worden. De uitbreiding naar twee breedtes van masterrollen gebeurt in een eerste uitbreiding op dit basismodel. 2. Alle artikelen liggen in de langsrichting, er wordt geen rotatie van de artikelen toegestaan. In een tweede uitbreiding van het basismodel zal deze mogelijkheid van 90° roteren aan het model toegevoegd worden. 3. Er komt binnen een band slechts één artikel voor, de kaplengte blijft dus constant over de volledige rollengte. De mogelijkheid te veranderen van artikel binnen een band zal in een derde uitbreiding toegevoegd worden aan het model. Met bovenstaande veronderstelling wordt er nu een model ontwikkeld voor het versnijdingsprobleem: Variabelen: xp yi v

aantal rollen die versneden worden gebruik makende van patroon p aantal banden waarbij artikel i de bandbreedte bepaalt variabele die breedteverlies van het te ontwerpen patroon weergeeft

37

Hoofdstuk 5. Ontwerp en validatie versnijdingsmodel Parameters: πi wi li si t api cp di W L P m n

schaduwprijs van artikel i met betrekking tot eerste beperking van hoofdprobleem breedte van item i lengte van item i hoeveelheid in stock van artikel i tolerantie op hoeveelheid te veel geproduceerd aantal stuks van artikel i in patroon p breedteverlies van patroon p vraag naar artikel i gietbreedte van masterrol rollengte van masterrol verzameling van alle patronen totaal aantal patronen totaal aantal artikelen

Hoofdprobleem: min

X

cp xp

(5.1)

p∈P

onder voorwaarden: si +

X

p∈P

api xp − di ≤ tdi


i = 1, ..., n ∀p ∈ P

(5.2) (5.3)

Knapsack probleem: min v −

n X i=1

πi bL/li cyi

(5.4)


W−

wi yi ≤ W

n X i=1

(5.5)

wi y i ≤ v


i = 1..n

(5.6) (5.7) (5.8)

Ook in dit basismodel wordt er gebruik gemaakt van twee optimaliseringsfuncties beiden met een aantal beperkingen. Het hoofdprobleem wordt weergegeven door de optimaliseringsfunctie 5.1 en beperkingen 5.2 en 5.3. Het knapsack probleem wordt weergegeven door de


38

doelfunctie 5.4 en de voorwaarden 5.5, 5.6, 5.7 en 5.8. In wat volgt worden de aanpassingen ten opzichte van het model beschreven in de literatuur. Na vergelijking van het hoofdprobleem in beide modellen ziet men dat er bij de doelfunctie P niet enkel geoptimaliseerd wordt naar het totaal aantal gebruikte patronen p∈P xp maar P dat er in het hoofdprobleem van dit basismodel geoptimaliseerd wordt naar p∈P cp xp . De waarde van cp is het breedteverlies van een bepaald patroon. De reden van deze verandering is dat in het geval van het snijden van staven kan aangetoond worden dat het minimaliseren van P p∈P xp exact hetzelfde resultaat zal opleveren als het optimaliseren van het totale verlies. Door de uit te voeren uitbreidingen zal deze gelijkheid niet meer opgaan en wordt dus een verliesfactor toegevoegd. Ook in de beperking 5.2 ziet men een wijziging ten opzichte van deze in de literatuurstudie. De snijpatronen moeten zodanig gekozen worden dat naast het voldoen aan de vraag naar alle artikelen, deze snijpatronen ook moeten voldoen aan een tolerantiegrens op de hoeveelheden die teveel geproduceerd worden. Deze tolerantiegrens wordt bepaald door een percentage t van de totale vraag di . Het is duidelijk dat voorwaarde 5.2 er voor zorgt dat de productiehoeveelheden voldoen aan deze extra beperking. Door de wijzigingen in de doelfunctie van het hoofdprobleem is een wijziging van de optimaliseringsfunctie van het knapsack probleem noodzakelijk. Aangezien deze doelfunctie in feite de gereduceerde kost van het hoofdprobleem weerspiegelt zal de 1 moeten vervangen worden door de coëfficiënt van xp in de doelfunctie 5.1 van het hoofdprobleem, meer bepaald het breedteverlies cp van patroon p. Nu wordt in het knapsack probleem gezocht naar een nieuw patroon, bijgevolg is het breedteverlies hiervan onbekend. Er wordt een nieuwe variabele v ge¨ıntroduceerd. Het is duidelijk dat tijdens het oplossen van het knapsack probleem de waarde van deze variable effectief de waarde van het breedteverlies van het gevonden patroon Ap = {ap 1 , ap 2 , ..., ap n } zal hebben. Dit is zo aangezien de doelfunctie de waarde van de variabele v zal minimaliseren, terwijl beperking 5.6 een ondergrens voor deze variabele weergeeft, namelijk het breedteverlies van het patroon. Indien men via het knapsack probleem tot een nieuw patroon komt, kan men eenvoudig uit dit knapsack probleem de waarde van de parameters api (aantal stuks van artikel i in patroon p) en cp (breedteverlies van patroon p) afleiden. Een ander verschil in het knapsack probleem is dat de variabele yi nog vermenigvuldigd wordt met de term bL/li c. Deze vermenigvuldiging gebeurt omdat er, in tegenstelling tot bij het snijden van staven op bepaalde staaflengtes, bij het snijden van de masterin banden niet één maar meerdere artikelen uit die band kunnen gehaald worden. De hoeveelheid artikelen per band wordt bepaald door de lengte van het artikel aangezien aangenomen wordt dat ieder artikel in de langsrichting ligt. Deze hoeveelheid wordt berekend door de rollengte te delen door de lengte van het artikel en af te ronden naar de hoogst mogelijk integer kleiner dan of gelijk aan dit quotiënt.


39

De oplossingsprocedure van dit basismodel is analoog met deze besproken in de literatuur. In wat volgt worden de verschillende stappen van de oplossingsprocedure weergegeven. Figuur 5.1 toont een flowchart van deze procedure. Oplossingsprocedure voor het basismodel: 1. Maak een verzameling van initiële patronen (evenveel als er items/vragen/beperkingen zijn) 2. Los de LP relaxatie van het hoofdprobleem op met deze patronen 3. Bereken de schaduwprijzen 4. Deelprobleem oplossen met de in stap 3 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC  RC < 0 Er bestaat nog een betere oplossing, ga naar stap 5 Gereduceerde kost: RC ≥ 0 Optimale oplossing gevonden en ga naar stap 6 5. Voeg patroon toe aan verzameling van patronen en ga terug naar stap 2 6. Los hoofdprobleem op met huidige verzameling van patronen

Figuur 5.1: Een visuele voorstelling van het oplossingsproces via column generation voor het eendimensionaal CSP


5.1.2

40

Eerste uitbreiding: verschillende breedtes van masterrollen

Een eerste uitbreiding bestaat erin om niet enkel vanuit de brede masterrol te gaan combineren maar ook combinaties op de smalle masterrol mogelijk te maken. Het model moet dus in staat zijn om voor zowel de brede als de smalle masterrol patronen te genereren en te combineren. Hiertoe wordt er gebruik gemaakt van twee knapsack problemen. Beide deelproblemen zijn analoog met deze van het basismodel, in het eerste zal er een nieuw patroon gezocht worden binnen een brede masterrol, het tweede doet hetzelfde voor een smalle masterrol. De verzameling van patronen P wordt opgesplitst in twee deelverzamelingen. P 1 is de deelverzameling met alle patronen voor een brede masterrol, P 2 de deelverzameling met alle patronen voor een smalle masterrol. Het model waarin deze eerste uitbreiding ge¨ımplementeerd is ziet er als volgt uit: Variabelen: xbp xsp yi v

aantal brede rollen die versneden worden gebruik makende van patroon p aantal smalle rollen die versneden worden gebruik makende van patroon p aantal banden waarbij artikel i de bandbreedte bepaalt variabele die breedteverlies van het te ontwerpen patroon weergeeft

Parameters: πi wi li si t abpi aspi cbp csp di Wb Ws L P Pb Ps m mb ms n

schaduwprijs van artikel i met betrekking tot eerste beperking van hoofdprobleem breedte van item i lengte van item i hoeveelheid in stock van artikel i tolerantie op hoeveelheid te veel geproduceerd aantal stuks van artikel i in patroon p, brede masterrol aantal stuks van artikel i in patroon p, smalle masterrol breedteverlies van patroon p, brede masterrol breedteverlies van patroon p, smalle masterrol vraag naar artikel i gietbreedte van brede masterrol gietbreedte van smalle masterrol rollengte van masterrol verzameling van alle patronen verzameling van alle patronen voor een brede masterrol verzameling van alle patronen voor een smalle masterrol totaal aantal patronen totaal aantal patronen voor een brede masterrol totaal aantal patronen voor een smalle masterrol totaal aantal artikelen

41

Hoofdstuk 5. Ontwerp en validatie versnijdingsmodel Hoofdprobleem: min

X

X

cbp xbp +

X

aspi xsp − di ≤ tdi

csp xsp

(5.9)

p∈P s

p∈P b

onder voorwaarden: si +

X

abpi xbp +

p∈P s

p∈P b

xbp ≥ 0 and integer

xsp

≥ 0 and integer

i = 1, ..., n

(5.10)

∀p ∈ P b

(5.11)

∀p ∈ P

(5.12)

s

Eerste knapsack probleem (brede masterrol): min v −

n X i=1

πi bL/li cyi

(5.13)

onder voorwaarden: n X

wi y i ≤ W b

i=1

n X

Wb −

i=1

wi y i ≤ v

yi ≥ 0 and integer

i = 1..n

v≥0

(5.14) (5.15) (5.16) (5.17)

Tweede knapsack probleem (smalle masterrol): min v −

n X i=1

πi bL/li cyi

(5.18)


wi yi ≤ W s

Ws −

n X i=1

wi y i ≤ v


i = 1..n

(5.19) (5.20) (5.21) (5.22)

Zoals blijkt uit bovenstaande beschrijving van het model voor deze eerste uitbreiding verschillen beide knapsack problemen enkel in beperkingen 5.14 vs. 5.19 en 5.15 vs. 5.20. Het verschil is hier het gebruik van de respectievelijke breedte van de masterrol die gebruikt


42

wordt, meer bepaald W b , de breedte van de brede masterrol in het eerste knapsack probleem en W s , de breedte van de smalle masterrol in het tweede knapsack probleem. Naast de opsplitsing in twee knapsack problemen dient ook in het hoofdprobleem de opsplitsing van de verzameling P in de twee deelverzamelingen P b en P s te gebeuren. Hiertoe wordt P in doelfunctie 5.9 en in beperking 5.10 de sommeringen over de verzameling P ( p∈P ...) opP P gesplitst in een sommering over beide deelverzamelingen afzonderlijk ( p∈P b ... + p∈P s ...). Ook de beperking 5.3 werd vervangen door twee analoge beperkingen 5.11 en 5.12. Door deze uitbreiding zal ook de procedure voor het oplossen van dit model in enige zin anders verlopen. Elke iteratie zal een patroon met een zo laag mogelijke gereduceerde kost zeoeken, dit zowel voor de brede als de smalle masterrol, en dit onafhankelijk van elkaar. Als en slechts als de bekomen minimale gereduceerde kost negatief is voor een gegenereerd patroon wordt dat patroon toegevoegd, onafhankelijk van het resultaat van het andere knapsack probleem. Pas indien beide knapsack problemen een positieve gereduceerde kost opleveren zal gestopt worden met het genereren van patronen en wordt vervolgens het hoofdprobleem opgelost met alle gegenereeerde patronen. Dit proces wordt in wat volgt stap voor stap besproken, een flowchart wordt weergegeven in figuur 5.2. Oplossingsprocedure voor eerste uitbreiding van het basismodel: 1. Maak een verzameling van initiële patronen voor de brede masterrol(evenveel als er items/vragen/beperkingen zijn) 2. Maak een verzameling van initiële patronen voor de smalle masterrol(evenveel als er items/vragen/beperkingen zijn) 3. Los de LP relaxatie van het hoofdprobleem op met alle patronen Stel stopcriterium = 0 4. Bereken de schaduwprijzen 5. Eerste knapsack probleem oplossen met de in stap 4 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC b  RC b < 0 Er bestaat nog een betere oplossing, ga naar stap 6 Gereduceerde kost: RC b ≥ 0 ga naar stap 7

6. Voeg patroon toe aan verzameling van patronen en ga naar stap 8 7. Verhoog stopcriterium met 1 en ga naar stap 8

8. Tweede knapsack probleem oplossen met de in stap 4 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC s  RC s < 0 Er bestaat nog een betere oplossing, ga naar stap 9 Gereduceerde kost: RC s ≥ 0 ga naar stap 10


43

9. Voeg patroon toe aan verzameling van patronen en ga naar stap 11 10. Verhoog stopcriterium met 1 en ga naar stap 11 11. Als stopcriterium < 2 dan, ga terug naar stap 3 12. Los hoofdprobleem op met huidige verzameling van patronen

Figuur 5.2: Een visuele voorstelling van het oplossingsproces via column generation voor de eerste uitbreiding van het basismodel


5.1.3

44

Tweede uitbreiding: lengte/breedte problematiek

Nu is het model reeds in staat vanuit twee verschillende breedtes van masterrollen snijpatronen te zoeken en te combineren maar het is nog niet mogelijk om een artikel ofwel in de langsrichting ofwel in de dwarsrichting te leggen. Deze tweede uitbreiding zal het model zodanig aanpassen dat ook dit mogelijk wordt. Om deze uitbreiding in het model te implementeren is het noodzakelijk de variabele yi te gaan opsplitsen zodat het model de mogelijkheid krijgt het artikel 90° te roteren. Het model waarin deze tweede uitbreiding ge¨ımplementeerd is ziet er als volgt uit: Variabelen: xbp xsp yil yid v

aantal brede rollen die versneden worden gebruik makende van patroon p aantal smalle rollen die versneden worden gebruik makende van patroon p aantal banden waarbij artikel i in de langsrichting geörienteerd wordt aantal banden waarbij artikel i in de dwarsrichting geörienteerd wordt variabele die breedteverlies van het te ontwerpen patroon weergeeft

Parameters: πi wi li si t abpi aspi cbp csp di Wb Ws L P Pb Ps m mb ms n

schaduwprijs van artikel i met betrekking tot eerst beperking van hoofdprobleem breedte van item i lengte van item i hoeveelheid in stock van artikel i tolerantie op hoeveelheid te veel geproduceerd aantal stuks van artikel i in patroon p, brede masterrol aantal stuks van artikel i in patroon p, smalle masterrol breedteverlies van patroon p, brede masterrol breedteverlies van patroon p, smalle masterrol vraag naar artikel i gietbreedte van brede masterrol gietbreedte van smalle masterrol rollengte van masterrol verzameling van alle patronen verzameling van alle patronen voor een brede masterrol verzameling van alle patronen voor een smalle masterrol totaal aantal patronen totaal aantal patronen voor een brede masterrol totaal aantal patronen voor een smalle masterrol totaal aantal artikelen

45


X

cbp xbp +

X

csp xsp

(5.23)

p∈P s

p∈P b

onder voorwaarden: X X abpi xbp + aspi xsp − di ≤ tdi si +

i = 1, ..., n

(5.24)

p∈P s

p∈P b


xsp

≥ 0 and integer

∀p ∈ P b

(5.25)

∀p ∈ P

(5.26)

s


n X i=1

πi (bL/li cyil + bL/wi cyid )

(5.27)


wi yil +

i=1

n X i=1

Wb −

n X

wi yid ≤ W b n X

wi yid ≤ v

(5.29)

yil ≥ 0 and integer

i = 1..n

(5.30)

≥ 0 and integer

i = 1..n

(5.31)

yid

i=1

wi yil −

(5.28)

i=1

v≥0

(5.32)


n X i=1


(5.33)


wi yil

i=1

s

W −

+

n X i=1

n X i=1

wi yil

−

li yid ≤ W s n X i=1


yid ≥ 0 and integer v≥0

(5.34)

wi yid ≤ v

(5.35)

i = 1..n

(5.36)

i = 1..n

(5.37) (5.38)

Om deze uitbreiding te implementeren verandert er niets aan het hoofdprobleem. Bij toevoegen van een patroon Ap = {ap 1 , ap 2 , ..., ap n } wordt ieder element api van de vector Ap gelijk


46

gesteld aan de som van yil en yid . Het aantal stuks van artikel i wordt dus gelijkgesteld aan som van het aantal stuks van artikel i in langs- en dwarsrichting. In de doelfunctie van beide knapsack problemen wordt een opsplitsing gemaakt tussen de artikelen die in langsrichting liggen en deze in dwarsrichting. In het geval dat het artikel in langsrichting gepositioneerd wordt zullen dus de lengte van het artikel en de lengte van de masterrol eenzelfde oriëntatie hebben. In dit geval zal het aantal artikelen per band bepaald worden door bL/li c. Indien het artikel in dwarsligging gepositioneerd wordt zal echter het aantal stuks per band gelijk zijn aan bL/wi c. Dit verschil in aantal stuks per band volgens de positionering verklaart de noodzaak van de opsplitsing. Ook in vergelijking 5.28, 5.29, 5.34en 5.35 is een opsplitsing noodzakelijk. Er wordt eenzelfde redenering gevolgd als bij de doelfunctie van de knapsack problemen. Deze vier beperkingen hebben allen betrekking tot de breedte van de masterrol. Hier zal dus bij positionering in langsrichting de breedte van het artikel gebruikt worden als snijbreedte voor de desbetreffende band en bij positionering in dwarsrichting zal dit de lengte van het artikel zijn. Door het toevoegen van de mogelijkheid om artikelen 90° te roteren zal er echter niets veranderen aan de oplossingsprocedure die besproken werd na de implementatie van de eerste uitbreiding. Voor een bespreking van de verschillende stappen in het oplossingsproces van dit model wordt dan ook verwezen naar het stappenplan en de flowchart besproken in hoofdstuk 5.1.2.

5.1.4

Derde uitbreiding: verschillende producten per band

Door een laatste uitbreiding van het model zal de mogelijkheid ge¨ımplementeerd worden om verschillende artikelen binnen een bepaalde band te snijden. Deze artikelen dienen wel minstens één maat gemeenschappelijk te hebben aangezien eens een band gesneden deze niet meer zal bijgesneden worden. Er bestaat enkel een mogelijkheid om verschillende kaplengtes toe te passen binnen een band. Om deze uitbreiding te implementeren zal na het vinden van een patroon met gereduceerde kost kleiner dan 0, per bandbreedte een extra deelprobleem opgelost worden om een zo optimaal mogelijk gebruik van artikelen binnen de band te verkrijgen. Het model na implementering van de derde uitbreiding is:

47

Hoofdstuk 5. Ontwerp en validatie versnijdingsmodel Variabelen: xbp xsp yil yid zil zid v

aantal brede rollen die versneden worden gebruik makende van patroon p aantal smalle rollen die versneden worden gebruik makende van patroon p aantal banden waarbij artikel i in de langsrichting geörienteerd wordt aantal banden waarbij artikel i in de dwarsrichting geörienteerd wordt aantal stuks per band waarbij artikel i in de langsrichting geörienteerd wordt aantal stuks per band waarbij artikel i in de dwarsrichting geörienteerd wordt variabele die breedteverlies van het te ontwerpen patroon weergeeft

Parameters: πi wi li si t abpi aspi cbp csp di Wb Ws L P Pb Ps m mb ms n A wband

schaduwprijs van artikel i met betrekking tot eerste beperking van hoofdprobleem breedte van item i lengte van item i hoeveelheid in stock van artikel i tolerantie op hoeveelheid te veel geproduceerd aantal stuks van artikel i in patroon p, brede masterrol aantal stuks van artikel i in patroon p, smalle masterrol breedteverlies van patroon p, brede masterrol breedteverlies van patroon p, smalle masterrol vraag naar artikel i gietbreedte van brede masterrol gietbreedte van smalle masterrol rollengte van masterrol verzameling van alle patronen verzameling van alle patronen voor een brede masterrol verzameling van alle patronen voor een smalle masterrol totaal aantal patronen totaal aantal patronen voor een brede masterrol totaal aantal patronen voor een smalle masterrol totaal aantal artikelen verzameling van alle artikelen bandbreedte van de desbetreffende band

Hoofdprobleem: min

X

p∈P b

cbp xbp +

X

csp xsp

onder voorwaarden: X X si + abpi xbp + aspi xsp − di ≤ tdi p∈P b

(5.39)

p∈P s

i = 1, ..., n

(5.40)

p∈P s


xsp ≥ 0 and integer

∀p ∈ P b

∀p ∈ P s

(5.41) (5.42)


48


n X i=1


(5.43)


n X

wi yil +

i=1

i=1

Wb −

n X i=1

wi yid ≤ W b

wi yil −

n X i=1


yid ≥ 0 and integer

(5.44)

wi yid ≤ v

(5.45)

i = 1..n

(5.46)

i = 1..n

(5.47)

v≥0

(5.48)


n X i=1


(5.49)


wi yil

+

i=1

s

W −

n X i=1

n X

wi yil

i=1

−

li yid ≤ W s n X i=1


yid ≥ 0 and integer

(5.50)

wi yid ≤ v

(5.51)

i = 1..n

(5.52)

i = 1..n

(5.53)

v≥0

(5.54)

Deelprobleem verschillende artikelen per band : min 1 −

n X i=1

πi (zil + zid )

(5.55)


49

onder voorwaarden:

L−

n X

n X

L−

i=1 n X

wi zid +

i=1 n X

wi zid +

i=1

(5.57)

li zil ≤ lj

∀j ∈ A : lj 6= wband

(5.58)

i=1 n X

= 0 ∀i ∈ A : wi 6= wband

zid = 0 ∀i ∈ A : li 6= wband

zil

(5.56)

∀j ∈ A : wj 6= wband

i=1

zil

li zil ≤ L

li zil ≤ wj

wi zid +

i=1

n X

≥ 0 and integer

zid ≥ 0 and integer

(5.59) (5.60)

i = 1..n

(5.61)

i = 1..n

(5.62)

Het deelprobleem met doelfunctie 5.55 en beperkingen 5.56, 5.57, 5.58, 5.59, 5.60, 5.61 en 5.62 zal opgelost worden voor elke band bepaald in het desbetreffende knapsack probleem. De parameter wband geeft de bandbreedte van deze band weer. Daarnaast worden er twee nieuwe variabelen zil en zid gedeclareerd. Deze variabelen geven het aantal stuks van artikel i die in de desbetreffende band versneden worden in langs- respectievelijk dwarspositionering. P De doelfunctie van het deelprobleem zal 1− ni=1 πi (zil +zid ) minimaliseren, de analogie met het P knapsack probleem is treffend. Door dit te minimaliseren zal de uitdrukking ni=1 πi (zil + zib ) gemaximaliseerd worden. Door dit voor iedere band te doen zal de gereduceerde kost van het hoofdprobleem geminimaliseerd worden. Met andere woorden wordt er hier dus gezocht naar een patroon dat een zo groot mogelijke verbetering van het hoofdprobleem tot gevolg heeft. Hier worden echter, in tegenstelling tot bij het eerste en tweede knapsack probleem, de snijbreedtes als constant verondersteld en binnen deze breedte wordt er gezocht naar een zo goed mogelijke combinatie van kaplengten. Binnen Agfa-Gevaert wordt bij vergelijking naar combinatieverlies rekening gehouden met het ééndimensioneel combinatieverlies en niet met het tweedimensionale verlies. Mede hierdoor maar ook wegens de kleine variatie op de rollengte is het weinig relevant het verlies op het einde van een rol effectief te gaan minimaliseren. Daarentegen wordt er door beperkingen 5.57 en 5.58 voor gezorgd dat dit verlies niet groter is dan het kleinste artikel dat binnen deze band kan versneden worden. Beperking 5.56 zorgt er dan weer voor dat de lengte van de masterrol niet overschreden wordt. Verder wordt er door voorwaarden 5.59 en 5.60 voor gezorgd dat als een artikel in zijn lengte verschilt van de bandbreedte de variabele zil gelijk moet zijn aan nul. Eenzelfde redenering gaat op voor de breedte van een artikel en de variabele zid . Hierdoor zullen enkel artikelen kunnen gekozen worden die, ofwel in hun lengte ofwel in hun breedte exact dezelfde afmeting hebben als de bandbreedte (wi = wband of li = wband ).


50

De oplossingsprocedure zal door het toevoegen van deze derde uitbreiding enkele wijzigingen ondergaan. Zo zal er na het oplossen van zowel het eerste als het tweede knapsack probleem, indien er een patroon gevonden wordt, na het toevoegen van dit patroon nagegaan worden of er binnen deze bandbreedtes niet een beter patroon kan gevonden worden door variatie van artikelen toe te laten binnen een band. Dit proces wordt in wat volgt stap voor stap besproken, een flowchart wordt weergegeven in figuur 5.3. Oplossingsprocedure voor derde uitbreiding van het basismodel: 1. Maak een verzameling van initiële patronen voor de brede masterrol(evenveel als er items/vragen/beperkingen zijn) 2. Maak een verzameling van initiële patronen voor de smalle masterrol(evenveel als er items/vragen/beperkingen zijn) 3. Los de LP relaxatie van het hoofdprobleem op met alle patronen Stel stopcriterium = 0 4. Bereken de schaduwprijzen 5. Eerste knapsack probleem oplossen met de in stap 4 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC b  RC b < 0 er bestaat nog een betere oplossing, ga naar stap 6 Gereduceerde kost: RC b ≥ 0 verhoog stopcriterium met 1 en ga naar stap 8 6. Voeg patroon toe aan verzameling van patronen

7. Los voor iedere band het deelprobleem op, berekenen de nieuwe gereduceerde kost RC2  RC < 0 voeg patroon toe aan verzameling en ga naar stap 8 2 Gereduceerde kost: RC ≥ 0 ga naar stap 8 2

8. Tweede knapsack probleem oplossen met de in stap 4 berekende schaduwprijzen en noem resulterende minimale gereduceerde kost RC s  RC s < 0 er bestaat nog een betere oplossing, ga naar stap 9 Gereduceerde kost: RC s ≥ 0 verhoog stopcriterium met 1 en ga naar stap 11 9. Voeg patroon toe aan verzameling van patronen

10. Los voor iedere band het deelprobleem op, berekenen de nieuwe gereduceerde kost RC3  RC < 0 voeg patroon toe aan verzameling en ga naar stap 11 3 Gereduceerde kost: RC ≥ 0 ga naar stap 11 3


51

11. Als stopcriterium ≤ 2 dan, ga terug naar stap 3 12. Los hoofdprobleem op met huidige verzameling van patronen

Figuur 5.3: Een visuele voorstelling van het oplossingsproces via column generation voor de derde uitbreiding van het basismodel


52

Bij dit model dient de niet onbelangrijke opmerking gemaakt te worden dat de oplossing geproduceerd door deze methode geen optimale oplossing garandeert. De bandbreedtes worden nog steeds bepaald zonder rekening te houden met een variatiemogelijkheid van artikelen in de lengte. Daarna wordt gezocht binnen de band of er mits variatie niet nog een beter patroon kan gevonden worden. Deze methode zal geen optimale oplossing garanderen maar zal er wel in slagen een aanvaardbare oplossing te produceren. Voor het vertalen van dit wiskundig model naar de AMPL wordt wordt verwezen naar bijlage B waar de .MOD en .RUN bestanden voor dit probleem weergegeven worden. Indien men echter voor het bepalen van de bandbreedtes toch rekening wenst te houden met de mogelijkheid tot variatie binnen een band, zal men het probleem veeleer moeten benaderen als een tweedimensioneel CSP met de nodige beperkingen dan om vertrekkende vanuit een eendimensionaal probleem via enkele uitbreidingen tot een werkend oplossingsmodel voor dit probleem te komen.

5.2

Bibliotheek van historische combinaties

In dit model worden geen patronen gegenereerd. In een pre-processing fase worden uit de historische data alle ooit gebruikte snijpatronen met betrekking tot de gevraagde artikelen gefilterd en in de juiste vorm gepresenteerd. De patronen worden weergegeven door de vector 2 m2 m2 m2 Ap = {am 1p , a1p , ..., anp } waarin de vectorelementen aip in tegenstelling tot bij het column generation model niet het aantal stuks weergeeft maar het aantal vierkante meter van artikel i dat gesneden wordt als een volledige masterrol versneden wordt volgens patroon p. Nu kan een eenvoudig lineair model het aantal masterrollen bepalen die volgens een bepaald patroon zullen versneden worden. Variabelen: xp

aantal masterrollen die versneden worden gebruik makende van patroon p

Parameters: si t 2 am pi cp di L P m n

hoeveelheid in stock van artikel i tolerantie op hoeveelheid te veel geproduceerd aantal m2 van artikel i in patroon p, per masterrol breedteverlies van patroon p vraag naar artikel i rollengte van masterrol verzameling van alle patronen totaal aantal patronen totaal aantal artikelen

53


X

cp xp

(5.63)

p∈P

onder voorwaarden: X 2 si + am pi xp − di ≤ tdi

i = 1, ..., n

(5.64)

p∈P


∀p ∈ P

(5.65)

Het is onmiddellijk duidelijk dat dit model op zich veel eenvoudiger is dan het model dat gebruik maakt van de column generation techniek. Er werd ook vanuit Agfa-Gevaert gevraagd om dit bibliotheek model zo eenvoudig mogelijk te houden. Dit eenvoudig model staat wel ten koste van de complexiteit van de pre-processing. Daar waar bij het model via de column generation techniek enkel de eigenschappen van en de vraag naar de verschillende artikelen dient aangeleverd te worden omvat de data die voor het bibliotheek model moet als input gegeven worden ook nog eens alle informatie met betrekking tot in het verleden gebruikte snijpatronen. Als men zich beperkt tot de 4 Wuxi artikelen (bandbreedtes) en hun historische snijpatronen valt het aantal historische combinaties nogal mee. Zodra men echter uitbreidt en ook de Mortsel artikelen toevoegt aan het model, loopt het aantal historische combinaties echter op tot meerdere duizenden. Voor het vertalen van dit wiskundig model naar de AMPL wordt wordt verwezen naar bijlage C waar de .MOD en .RUN bestanden voor dit probleem weergegeven worden.

5.3

Experimenten

Tijdens dit hoofdstuk zullen beide modellen gebruikt worden om in een testcase snijpatronen op te stellen vanuit een voorspelling van de vraag per maand. De testset bestaat uit de voorspelling van de maandelijkse vraag naar de respectievelijke artikelen voor de periode van maart 2010 tot en met oktober 2010, er zijn dus voor elke testset gegevens voor acht maanden beschikbaar. Zoals besproken in hoofdstuk 4.2.3 zal er gewerkt worden met drie soorten inputgegevens. Hieronder wordt het onderscheid tussen de typologie van de verschillende input databestanden opgesomd. Verschillende databestanden: Databestanden waarin enkel de Wuxi artikelen beschouwd worden. De data bestanden voor het bibliotheek model worden aangeboden met als typologie BXC JJMM , voor het column generation model wordt de typologie WXC JJMM gebruikt. Waarbij JJ de laatste 2 cijfers van het jaartal weergeeft en MM de respectievelijke maand representeert. Databestanden waarin naast de Wuxi artikelen ook alle artikelen die lengte of breedte delen met een Wuxi bandbreedte beschouwd worden. De data bestanden voor het


54

bibliotheek model worden aangeboden met als typologie BXB JJMM, voor het column generation model wordt de typologie WXB JJMM gebruikt. Databestanden waarin alle artikelen met betrekking tot de beschouwde filmsoort beschouwd worden. De data bestanden voor het bibliotheek model worden aangeboden met als typologie BXA JJMM, voor het column generation model wordt de typologie WXA JJMM gebruikt.

Voor ieder databestand zal nu een snijpatroon opgesteld worden via enerzijds het bibliotheek model en anderzijds via het column generation model. De resultaten worden weggeschreven naar een Excel bestand. In dit Excel bestand worden verschillende tabbladen aangemaakt om alle informatie met betrekking tot de oplossing, berekend door het model te kunnen gebruiken en controleren. Zo worden alle patronen weergegeven inclusief het aantal rollen waarvoor deze patronen gebruikt worden en hun breedteverlies. Verder worden ook de beginvoorraad, de geproduceerde hoeveelheid, de vraag en de eindvoorraad met elkaar vergeleken. In een laatste tabblad worden de parameters die gebruikt zullen worden bij het vergelijken van de modellen weggeschreven. Deze parameters worden als volgt gedefinieerd. Parameters gebruikt ter vergelijking van de modellen: ´ e´ endimensionaall combinatieverlies (%): dit is de verhouding van het totale breedteverlies ten opzichte van de nuttige oppervlakte. De nuttige oppervlakte is de met fotografische emulsie begoten oppervlakte. In de resultaten wordt deze parameter weergegeven als ’% CombVerlies’. aantal gebruikte rollen: Deze parameter geeft het aantal rollen weer die gebruikt worden om het volledige snijplan uit te voeren. In de resultaten zal deze parameter worden aangeduid als ’aantalrollen’. aantal gebruikte patronen: Deze parameter geeft het totaal aantal verschillende patronen weer die gebruikt worden om het volledige snijplan uit te voeren. In de resultaten zal deze parameter worden aangeduid als ’aantalpatronen’. percentage teveel geproduceerd (%): Dit percentage wordt weergegeven door de verhouding van de hoeveelheid teveel geproduceerd ten opzichte van de gevraagde hoeveelheid. In de resultaten zal deze parameter worden aangeduid als ’% Overschot’.

Het model zal naast een LP gerelaxeerde oplossing ook een integer oplossing zoeken voor het probleem hoewel, gezien de grote rollengte en de kleine tolerantie op de hoeveelheden teveel geproduceerd in de meeste gevallen een integer oplossing binnen de tolerantiegrenzen onmogelijk blijkt te zijn. Indien deze integer oplossing niet mogelijk is, kan gezocht worden naar een methode om de resultaten ad hoc af te ronden. In deze thesis wordt de invloed onderzocht van afronden, volgens de conventionele regels, op de verschillende parameters.


5.3.1

55

Resultaten historische bibliotheek model

In figuren 5.4, 5.5, 5.6 worden de resultaten van de verschillende testcases opgelost met het historische bibliotheek model weergegeven. De tolerantie op artikelen teveel geproduceerd is in alle drie de gevallen gelijk aan 1 %. Figuur 5.4 geeft de resultaten weer indien enkel de Wuxi artikelen gecombineerd worden. Figuur 5.5 toont de resultaten van alle artikelen met een lengte of breedte gelijk aan een Wuxi bandbreedte en figuur 5.6 geeft de parameters weer bij oplossing van het combinatieprobleem waar alle artikelen voor deze gietsoort mee gecombineerd werden. In onderstaande figuren wordt enkel het resultaat voor de LP relaxatie van het probleem weergegeven. Voor de volledige resultaten wordt doorverwezen naar bijlage E.

Figuur 5.4: Resultaten bekomen met bibliotheek model, enkel Wuxi artikelen gecombineerd, tolerantie = 1%

Figuur 5.5: Resultaten bekomen met bibliotheek model, enkel artikelen die lengte of breedte delen met een Wuxi bandbreedte gecombineerd, tolerantie = 1%


56

Figuur 5.6: Resultaten bekomen met bibliotheek model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 1%

In figuur 5.4 dient opgemerkt te worden dat de resultaten die hier worden weergegeven niet voldoen aan de vooropgestelde 1% tolerantie. Het percentage teveel geproduceerd neemt bijgevolg zeer hoge waarden aan. De reden dat de tolerantiegrens van 1% niet kan gehaald worden zit hem in de beperkte bibliotheek aan historische combinaties. Deze bibliotheek wordt weergegeven in figuur 5.7. De beperktheid van deze bibliotheek methode zit hem niet enkel in het aantal combinaties. Ook het feit dat artikel A001 slechts in 1 combinatie niet voorkomt en artikel A004 maar in 1 combinatie voorkomt leidt ertoe dat de tolerantiegrens niet kan gehaald worden. De oplossingen in figuur 5.4 werden bekomen door het gaandeweg optrekken van de tolerantiegrens.

Figuur 5.7: Bibliotheek met historische combinaties voor de Wuxi artikelen

Figuur 5.8 vergelijkt de percentages combintatieverlies van enerzijds het combineren van alle artikelen met een afmeting gelijk aan een Wuxi breedte en anderzijds alle artikelen van deze gietsoort. De resultaten van het geval waarin men enkel de Wuxi artikelen combineert worden hier buiten beschouwing gelaten wegens het niet voldoen aan de gestelde tolerantie grenzen, zoals ex ante besproken.


57

Figuur 5.8: Grafische voorstelling van het percentage combinatieverlies met betrekking tot de oplossing van het historische bibliotheek model

Deze grafiek geeft een misschien niet direct verwacht verband aan tussen beide data sets input data. Men zou de verwachting kunnen hebben dat indien men meer artikelen kan combineren men ook het verliespercentage kan drukken. Dit blijkt echter tegenovergesteld te zijn volgens figuur 5.8. De verklaring hiervoor schuilt zich in een analoge redenering als waarom de tolerantiegrenzen te nauw waren voor combinaties met enkel de Wuxi breedtes. Hier is het echter ook zo dat sommige artikelen historisch slechts in een beperkt aantal combinaties voorkomen. Dit beperkt ons in onze combinatiemogelijkheden en zal leiden tot een verhoogd percentage combinatieverlies. Voor september 2010 waren er geen inputgegevens beschikbaar voor het oplossen van het model met de artikelen die een afmeting delen met een Wuxi bandbreedte. De waarde voor deze maand kon dus niet worden berekend. Er werd dan ook gekozen om deze maand in figuur 5.8 buiten beschouwing te laten.

5.3.2

Resultaten column generation model

In figuren 5.9, 5.10, 5.11 worden de resultaten van de verschillende testcases opgelost met het column generation model weergegeven. De tolerantie op artikelen te veel geproduceerd is in alle drie de gevallen gelijk aan 1 %. Figuur 5.9 geeft de resultaten weer indien enkel de Wuxi artikelen gecombineerd worden, figuur 5.10 toont de resultaten van alle artikelen met een lengte of breedte gelijk aan een Wuxi bandbreedte en figuur 5.11 geeft de parameters weer bij oplossing van het combinatieprobleem waar alle artikelen voor deze gietsoort mee gecombineerd werden. In deze figuren wordt naar analogie met hoofdstuk 5.3.1 enkel het


58

resultaat voor de LP relaxatie van het probleem weergeven. Voor de volledige resultaten wordt doorverwezen naar bijlage D.

Figuur 5.9: Resultaten bekomen met column generation model, enkel Wuxi artikelen gecombineerd, tolerantie = 1%

Figuur 5.10: Resultaten bekomen met column generation, enkel artikelen die lengte of breedte delen met een Wuxi bandbreedte gecombineerd, tolerantie = 1%

Figuur 5.11: Resultaten bekomen met column generation, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 1%


59

Figuur 5.12 toont het percentage combinatieverlies van de verschillende data sets. Hier wordt in tegenstelling met het historische bibliotheek model weergegeven wat verwacht kan worden. Het combinatieverlies daalt indien het aantal betrokken artikelen stijgt. Meer artikelen zorgen voor nieuwe opportuniteiten om een eventueel beter snijpatronen te vinden. Aangezien in het column generation model voor iedere iteratie naar nieuwe interessante patronen op zoek gegaan wordt, zal een stijging in aantal artikelen normaliter een mogelijkheid tot daling van het combinatieverlies meebrengen.

Figuur 5.12: Grafische voorstelling van het percentage combinatieverlies met betrekking tot de oplossing van het column generation model

5.3.3

Aanpassingsvermogen modellen

Een moeilijkheid bij het oplossen via het historische bibliotheek model doet zich voor indien er vraag is naar een (nieuw) artikel dat in geen enkele historische combinatie voorkomt. Er zal dus op geen enkele manier kunnen voldaan worden aan de vraag naar dit artikel. Dit geeft tot gevolg dat er om tot een oplossing te komen nieuwe patronen, waarin het nieuwe artikel wel voorkomt, zullen moeten toegevoegd worden aan de historische bibliotheek of de vraag naar dit artikel dient op nul gezet te worden. Deze moeilijkheid stelt zich ook tijdens het oplossen van de testcases. Er wordt besloten om in deze analyse de vraag voor deze artikelen te negeren, op nul te zetten. Deze keuze zorgt ervoor dat men nog steeds de vergelijking kan maken tussen het historisch combinatieverlies en het kleinst mogelijk verlies gebruik makende van dezelfde historische combinaties. Indien men patronen zou toevoegen aan de bibliotheek gaat deze vergelijking niet meer op. De desbetreffende artikelen worden in onderstaande lijst weergegeven per databestand.


60

BXA 1005: A011 BXA 1006: A011 & A055 BXA 1007: A017 & A061 BXA 1008: A013 & A057 BXA 1009: A013 & A058 BXA 1010: A060

Het is duidelijk dat het column generation model veel meer aanpassingsvermogen bezit dan het historische bibliotheek model. Het heeft bij dit model geen enkel belang of een artikel al dan niet in het verleden reeds gecombineerd werd. Er wordt in dit model vanuit de vraag vertrokken om zelf patronen te genereren. Het grote aanpassingsvermogen van het column generation model blijkt een belangrijk voordeel te zijn ten opzichte van het historische bibliotheek model dat veeleer situatieafhankelijk blijkt te zijn.

5.3.4

Invloed van afronden

De resultaten verkregen via de LP relaxatie zijn niet uitgedrukt in volledige rollen. In de praktijk zal men echter niet midden een rol de snijbreedtes en bijgevolg ook de bandbreedtes gaan wijzigen. Bijgevolg zullen de waarden verkregen na LP relaxatie tijdens een post-processing fase moeten afgerond worden naar volledige rollen. Een andere mogelijkheid bestaat erin een heuristiek te ontwikkelen voor het zoeken van een integer oplossing. In dit hoofdstuk zullen we de invloed van conventioneel afronden op de verschillende parameters onderzoeken. De invloed van het afronden wordt onderzocht voor de data set van waarin alle artikelen gecombineerd worden (column generation output). Figuren 5.13, 5.14 en 5.15 tonen de parameters, respectievelijk percentage combinatieverlies, aantal gebruikte patronen en het percentage overschot zowel voor als na afronding van de LP relaxatie voor oplossing via het column generation model. Eenzelfde kan berekend worden voor oplossing via het historische bibliotheek model. Om de tekst niet te overladen met grafieken worden deze laatste weergegeven in bijlage F. De expliciete waarden van de parameters na afronden voor elk van de data sets en modellen zijn terug te vinden in bijlage D en E.


61

Figuur 5.13: Vergelijking van het percentage combinatieverlies voor en na conventioneel afronden van de LP gerelaxeerde oplossing

Figuur 5.14: Vergelijking van het aantal gebruikte patronen voor en na conventioneel afronden van de LP gerelaxeerde oplossing


62

Figuur 5.15: Vergelijking van het percentage teveel geproduceerd voor en na conventioneel afronden van de LP gerelaxeerde oplossing

Door conventioneel afronden zullen er geen rollen versneden worden voor combinaties waarbij de te produceren hoeveelheden kleiner zijn dan een halve rollengte. In de praktijk wordt niet iedere maand, zoals gesimuleerd tijdens de experimenten, maar wel iedere week een nieuw snijplan opgesteld. Een tekort in de ene week zal deze behoefte verplaatsen naar de volgende week. Deze grotere behoefte zal de kans op een grotere patroonlengte in de volgende planningsperiode verhogen. Een groot voordeel van afronden van de resultaten bestaat erin dat het aantal gebruikte patronen sterk beperkt wordt. Dit minder aantal gebruikte patronen heeft een lager aantal omstellingen van de snijmachine en bijgevolg een lagere omstelkost. Na vergelijken van de parameters voor en na het afronden is het duidelijk dat het afronden slechts een beperkte invloed heeft op het combinatieverlies. Het aantal gebruikte patronen wordt drastisch beperkt door het conventioneel afronden van de LP relaxatie resultaten. Dit impliceert dat vele patronen slechts voor minder dan een halve rol gebruikt worden en bijgevolg na het afronden op nul gezet worden. De derde paramater toont aan dat deze drastische verlaging in het aantal gebruikte patronen echter niet zonder gevolgen blijft met betrekking tot de hoeveelheid teveel geproduceerd. Het percentage blijkt in de meeste gevallen negatief, dit wil zeggen dat door deze afronding niet meer aan alle vraag wordt voldaan. Dit verklaart waarom conventioneel afronden tekort schiet. Wil men een aanvaardbare oplossing uit de LP relaxatie bekomen dient men gebruik te maken van ad hoc afrondingen. Indien de vooropgestelde toleranties op artikelen teveel geproduceerd echter niet zo strikt dienen genomen te worden, zou men kunnen opteren om alles af te ronden naar boven. Hierbij dient men wel de bedenking te maken dat ook een artikel in voorraad houden geld kost.


5.3.5

63

Invloed van tolerantie op combinatieverlies

Om de invloed van de tolerantie op de geproduceerde hoeveelheden na te gaan bekijken we het bibliotheek model. Dit werd opgelost voor vijf verschillende tolerantiewaarden. Het model wordt opgelost voor de situatie waarbij men alle artikelen in de combinaties toelaat en dit voor tolerantiewaarden van 0.1%, 0.5%, 1%, 5% en 10%. In figuur 5.16 wordt per maand het verliespercentage van elk van deze tolerantiewaarden weergegeven. De numerieke resultaten worden weergegeven in bijlage E.

Figuur 5.16: Invloed van de tolerantie op het percentage combinatieverlies voor het oplossen met het bibliotheek model voor alle artikelen

Uit figuur 5.16 blijkt dat de tolerantie een beperkte, doch duidelijk merkbare invloed heeft op het combinatieverlies. Voor elke maand is een daling in combinatieverlies merkbaar voor toenemende tolerantiewaarden. Dit houdt dus in dat, indien het model meer vrijheid met betrekking tot de tolerantiewaarden krijgt, het model in staat zal zijn een betere oplossing te vinden naar combinatieverlies toe. Hier dient echter een afweging gemaakt te worden: aangezien bredere tolerantiegrenzen ook meer voorraad met zich meebrengen, hangt hier ook een prijskaartje aan vast. Een afweging tussen de voorraadkost en de kost van het verlies is hier aan de orde.


5.3.6

64

Vergelijking van beide modellen

Na verschillende invloeden te hebben bestudeerd, worden in dit deel de twee modellen onderling en met de historische data vergeleken De historische data worden weergegeven in figuur 5.17. Deze verschillende parameters werden gedefinieerd in hoofdstuk 4.1.4.

Figuur 5.17: Gegevens met betrekking tot het historische combinatieverlies binnen Agfa-Gevaert van 01/05/2009 tem 30/04/2010

In figuur 5.18 worden de twee methoden, ten opzichte van elkaar en ten opzichte van het historisch combinatieverlies, vergeleken op vlak van percentage combinatieverlies

Figuur 5.18: Vergelijking van het percentage combinatieverlies tussen de verschillende modellen en de historische waarde


65

Vergelijken we het percentage combinatieverlies van beide modellen dan zien we dat het column generation model een snijpatroon genereert met een lager percentueel combinatieverlies dan het bibliotheek model. Dit verschil is verklaarbaar doordat het column generation model niet beperkt is tot het kiezen van patronen uit een bibliotheek. Vergelijkt men de resultaten van de modellen met het gemiddelde percentueel combinatieverlies uit het verleden dan ziet men dat beide modellen een grote reductie van het combinatieverlies ten opzichte van deze historische waarde met zich meebrengen. Het historisch combinatieverlies bedraagt 3.5%, terwijl het column generation model snijplannen genereert met een gemiddeld combinatieverlies percentage van ongeveer 0.4% en bij het bibliotheek model is dit ongeveer 0.8%. Bij deze waarden dient men wel de opmerking te maken dat het model bij de combinatieopgave uitgaat van een ’ideaal model’. Zo wordt de beginvoorraad van de artikelen aangenomen in evenwicht te zijn en worden de aangeboden rollen foutvrij verondersteld. De historische waarde moet omwille van extra combinatieverliezen ten gevolge van fouten en stock-onevenwichten met enige voorzichtigheid benaderd worden. Een exact percentage van verbetering in combinatieverlies na invoering van één van de optimaliseringsmodellen is bijgevolg moeilijk te geven. Desalniettemin duiden de resultaten van deze modellen op een grote ruimte tot verbetering van deze combinatieverliezen. Het onderling verschil tussen het column generation model en het bibliotheek model is te verklaren doordat het bibliotheek model slechts uit een bepaald aantal combinaties kan combineren, terwijl het column generation elk mogelijk patroon kan creëren tijdens het oplossen van het knapsack probleem. In feite is de oplossing via het column generation model een ondergrens voor het bibliotheek model. Indien het bibliotheek model opgelost wordt met alle mogelijke combinaties in de bibliotheek zal dezelfde uitkomst als met het column generation model bekomen worden.

Hoofdstuk 6

Conclusies en suggesties voor verder onderzoek 6.1

Conclusies

In deze thesis werd de versnijdingsproblematiek met betrekking tot PCB film binnen de confectieafdelingen van Agfa-Gevaert besproken. Het confectieproces bestaat uit drie fazes. Een snijmachine versnijdt masterrollen tot banden. Een kapmachine kapt de gesneden banden vervolgens tot vellen. Een verpakkingslijn zorgt tenslotte voor de eindverpakking. Na de grondige studie van de literatuur omtrent soortgelijke problemen werden er twee modellen ontwikkeld. Voor het eerste model werd de techniek van column generation, beschreven door Gilmore & Gomory als basis genomen. Vervolgens werden enkele uitbreidingen aan dit basismodel toegevoegd om een model te krijgen dat aan alle vereisten van het specifieke praktische versnijdingsprobleem binnen Agfa-Gevaert voldeed. Het tweede model zal op basis van een combinatie van historische combinaties een snijplan genereren. Er werd voor gekozen de oplossingsmethode via de bibliotheek qua model zo eenvoudig mogelijk te houden. De intelligentie van dit model zit hem eigenlijk vooral in het voorbereiden van de inputgegevens. Alle combinaties uit het verleden moeten als inputgegevens aan het model aangeleverd worden. Dit gebeurt tijdens een uitgebreide pre-processing fase. Het column generation model heeft daarentegen enkel de afmetingen van en de vraag naar de verschillende artikelen nodig om vervolgens zelf patronen te genereren. De intelligentie van dit model zit hem veleer in het model zelf dan in het aanleveren van de gepaste data. Na uitvoerige analyse en bespreking van de verschillende methoden is duidelijk dat beide modellen zowel voordelen als nadelen bezitten. Het bibliotheek model is in staat de verscheidenheid van patronen te beperken. Door enkel keuzes toe te staan uit een databank van historische combinaties zullen enkel patronen die in het verleden reeds gebruikt geweest zijn in het snijplan voorkomen. Dit kan een voordeel inhouden naar het instellen van de snijmachine. De machine moet niet telkens op nieuwe snijbreedtes ingesteld worden wat voor 66

Hoofdstuk 6. Conclusies en suggesties voor verder onderzoek

67

een stuk standaardisatie van het instellen van de machine met zich meebrengt. Het column generation model zal voor elke iteratie op zoek gaan naar een nieuwe combinatie, onafhankelijk van het al of niet voorkomen van deze combinatie in het verleden. Hierdoor zal de snijmachine telkenmale op andere snijbreedtes moeten ingesteld worden. Zoals besproken kan dit instellen op telkens nieuwe waarden gezien worden als een nadeel. Doch zou het mogelijk moeten zijn om door eventueel enkele wijzigingen aan de snijmachine dit omstellen te vergemakkelijken. Indien er een vraag ontstaat naar een artikel dat historisch nog niet voorgekomen is, zal dit een aanpassing aan het bibliotheek model vergen. Aangezien dit artikel historisch gezien nog niet is voorgekomen zal het ook niet in de bibliotheek met combinaties voorkomen. Bijgevolg zal niet aan de behoefte van dit artikel kunnen voldaan worden door enkel combinaties vanuit de bibliotheek te gebruiken. Bij het ontstaan van een vraag naar een artikel dat historisch nog nooit voorgekomen is zal dus, alvorens een snijplan via het bibliotheek model te kunnen genereren, een uitbreiding van de bibliotheek noodzakelijk zijn. Er dienen enkele combinaties waarin dit nieuwe artikel verwerkt zit aan de bibliotheek te worden toegevoegd. Het column generation model ondervindt geen moeilijkheden bij het genereren van een snijplan voor nieuwe artikelen. Hier is er geen extra pre-processing noodzakelijk alvorens het snijplan te genereren. Door de grote rollengte en de kleine tolerantie op hoeveelheden teveel geproduceerd is het in de meeste gevallen niet mogelijk om via de modellen een snijplan te genereren met een integer aantal rollen per patroon zonder een tolerantie te overschrijden. In deze thesis werd de invloed van het afronden van de bekomen resultaten na LP relaxatie onderzocht. Door conventioneel afronden zullen er geen rollen versneden worden voor combinaties waarbij de te produceren hoeveelheden kleiner zijn dan een halve rollengte. In de praktijk wordt niet iedere maand, zoals gesimuleerd tijdens de experimenten, maar wel iedere week een nieuw snijplan opgesteld. Een tekort in de ene week zal deze behoefte verplaatsen naar de volgende week. Deze grotere behoefte zal de kans op een grotere patroonlengte in de volgende planningsperiode verhogen. Een groot voordeel van afronden van de resultaten bestaat erin dat het aantal gebruikte patronen sterk beperkt wordt. Dit minder aantal gebruikte patronen heeft een lager aantal omstellingen van de snijmachine en bijgevolg een lagere omstelkost. Er bestaan drie mogelijke manieren om de Wuxi artikelen te versnijden uit de beschikbare masterrollen. Men kan deze artikelen op zichzelf combineren, zonder ander PCB artikelen te betrekken in het combinatieprobleem. Indien men echter wel andere PCB artikelen bij het versnijdingsprobleem van de Wuxi artikelen betrekt kan men er voor kiezen om enkel deze artikelen die hun lengte of breedte delen met één van de Wuxi bandbreedtes samen met de Wuxi artikelen te combineren. In een derde situatie worden de Wuxi artikelen samen met alle andere PCB artikelen gecombineerd. Voor het column generation model is deze derde mogelijkheid duidelijk de beste met betrekking tot het minimaliseren van het combinatieverlies. Voor het bibliotheek model is het formuleren van de beste keuze iets complexer. De resultaten


68

van dit model hangen sterk af van de specifieke combinaties die zich in de bibliotheek bevinden. Zo zal ook de invloed op het combinatieverlies van het al dan niet samen combineren van de Wuxi artikelen samen met andere PCB artikelen afhangen van welke combinaties de bibliotheek voor deze artikelen bevat. Vergelijken we het percentage combinatieverlies van beide modellen dan zien we dat het column generation model een snijpatroon genereert met een lager percentueel combinatieverlies dan het bibliotheek model. Dit verschil is verklaarbaar doordat het column generation model niet beperkt is tot het kiezen van patronen uit een bibliotheek. Vergelijkt men de resultaten van de modellen met het gemiddelde percentueel combinatieverlies uit het verleden dan ziet men dat beide modellen een grote reductie van het combinatieverlies ten opzichte van deze historische waarde met zich meebrengen. Het historisch combinatieverlies bedraagt 3.5%, terwijl het column generation model snijplannen genereert met een gemiddeld combinatieverlies percentage van ongeveer 0.4% en bij het bibliotheek model is dit ongeveer 0.8%. Bij deze waarden dient men wel de opmerking te maken dat het model bij de combinatieopgave uitgaat van een ’ideaal model’. Zo wordt de beginvoorraad van de artikelen aangenomen in evenwicht te zijn en worden de aangeboden rollen foutvrij verondersteld. De historische waarde moet omwille van extra combinatieverliezen ten gevolge van fouten en stock-onevenwichten met enige voorzichtigheid benaderd worden. Een exact percentage van verbetering in combinatieverlies na invoering van één van de optimaliseringsmodellen is bijgevolg moeilijk te geven. Desalniettemin duiden de resultaten van deze modellen op een grote ruimte tot verbetering van deze combinatieverliezen.

6.2

Suggesties voor verder onderzoek

Deze thesis toont aan dat er nog ruimte is tot verbetering van de versnijdingsoptimalisatie met betrekking tot PCB film binnen de confectieafdeling van Agfa-Gevaert. In deze thesis worden er twee modellen ontwikkeld ter optimalisatie van dit versnijdingsprobleem. Verder onderzoek kan erin bestaan dit model uit te breiden zodanig dat ook de omstelkost in de doelfunctie ge¨ımplementeerd wordt. De omstelkost is de kost die gepaard gaat met het wijzigen van de posities van de snijmessen van de snijmachine. Verder kan er ook onderzoek gedaan worden naar andere factoren, naast het combineren op zich, die van invloed zijn op het percentuele combinatieverlies dat historisch geregistreerd werd binnen Agfa-Gevaert. In hoofdstuk 5.3.6 werden reeds enkele factoren aangehaald die mogelijk ook van invloed zijn op het grote verschil in combinatieverlies tussen enerzijds het historisch geregistreerde combinatieverlies en anderzijds het met de ontworpen modellen berekend theoretisch combinatieverlies. Met oog op het optimaliseren van het volledige versnijdingsproces in al zijn facetten zou het interessant zijn onderzoek uit te voeren naar deze factoren, ze te indentificeren en vervolgens hun invloed te quantificeren. Een andere mogelijke onderzoekspiste bestaat in het ontwikkelen van een heuristiek voor het


69

afronden van de resultaten verkregen na oplossing van de LP relaxatie van het model. Het conventioneel afronden heeft tot gevolg dat enkele producten niet geproduceerd worden. Er kan bijgevolg onderzoek gedaan worden naar een heuristiek die ,door een afweging te maken tussen de kost van een tekort enerzijds en de voorraadkost anderzijds, een zo goed mogelijke afronding van de resultaten genereert.

Bijlage A

Model opgelost met de Excel solver

Figuur A.1: Screenshot van model met de Excel solver

70

Bijlage A. Model opgelost met de Excel solver

Figuur A.2: Screenshot van model met de Excel solver

71

Bijlage B

AMPL code column generation model B.1

Het .RUN bestand

option solver cplexamp; option solution_round 6; model WUXI.mod; data WXC_1010.dat; let tolerantie := 0.01; let rol_lengte := 3730; let{a in ARTIKEL} demandstuks[a]:=demand[a] / (lengte[a]*breedte[a]); problem Cutting_Opt: make_1, make_2, number, stocklevel; option relax_integrality 1; option presolve 0; # --------------------------------# INITI¨ ELE PATRONEN # --------------------------------# _1:SMALLE ROL problem Band_Gen_1: use_L_1, use_B_1, brverlies_1, Reduced_Cost_1, Width_Limit_1, Breedte_verlies_1; option relax_integrality 0; option presolve 1; problem Pattern_Gen_1: stuksperband_B_1, stuksperband_L_1, bandverlies_1, RC_1, Length_Limit_1, Band_Verlies_1, Breedte_1, Lengte_1; option relax_integrality 0; option presolve 1; let aPAT_1 := 0; for {a let let let for

in ARTIKEL} { aPAT_1 := aPAT_1 + 1; aantal_1[a,aPAT_1] := floor(rol_lengte/lengte[a]) * floor(smalle_rol_breedte/breedte[a]); aantalinbreedte_1[a,aPAT_1] := floor(smalle_rol_breedte/breedte[a]); {i in 1..floor(smalle_rol_breedte/breedte[a])} { let snijbreedtes_1[aPAT_1,i] := breedte[a];}

72

73

Bijlage B. AMPL code column generation model

let {a2 in ARTIKEL: a2 <> a} aantal_1[a2,aPAT_1] := 0; let verlies_1[aPAT_1] := (rol_lengte * smalle_rol_breedte) - sum {a3 in ARTIKEL} (aantal_1[a3,aPAT_1] *lengte[a3] * breedte[a3]); let breedteverlies_1[aPAT_1] := smalle_rol_breedte - aantalinbreedte_1[a,aPAT_1] * breedte[a]; }; # _2:BREDE ROL problem Band_Gen_2: use_L_2, use_B_2, brverlies_2, Reduced_Cost_2, Width_Limit_2, Breedte_verlies_2; option relax_integrality 0; option presolve 1; problem Pattern_Gen_2: stuksperband_B_2, stuksperband_L_2, Band_Verlies_22, Breedte_2, Lengte_2; option relax_integrality 0; option presolve 1;

RC_2, Length_Limit_2, Band_Verlies_2,

let aPAT_2 := 0; for {a in ARTIKEL} { let aPAT_2 := aPAT_2 + 1; let aantal_2[a,aPAT_2] := floor(rol_lengte/lengte[a]) * floor(brede_rol_breedte/breedte[a]); let aantalinbreedte_2[a,aPAT_2] := floor(brede_rol_breedte/breedte[a]); for {i in 1..floor(brede_rol_breedte/breedte[a])} { let snijbreedtes_2[aPAT_2,i] := breedte[a];} let {a2 in ARTIKEL: a2 <> a} aantal_2[a2,aPAT_2] := 0; let verlies_2[aPAT_2] := (rol_lengte * brede_rol_breedte) - sum {a3 in ARTIKEL} (aantal_1[a3,aPAT_2] *lengte[a3] * breedte[a3]); let breedteverlies_2[aPAT_2] := brede_rol_breedte - aantalinbreedte_2[a,aPAT_2] * breedte[a]; };

# --------------------------------# LUS # --------------------------------let aPAT_1 := aPAT_1 + 1; let aPAT_2 := aPAT_2 + 1; let lus :=1; repeat { print "*********************HOOFDPROBLEEM*************************************"; solve Cutting_Opt; let resultaat[lus] := number; let stop:=0; if lus >5 then {if resultaat[lus] == resultaat [lus-5] then{ let stop := 4;}} let lus := lus + 1; let {a in ARTIKEL} price[a] := stocklevel[a].dual; # _1:SMALLE ROL print "***** SMALLE ROL *****"; let bandnummer_1:=1; solve Band_Gen_1; let breedteverlies_1[aPAT_1] := brverlies_1[aPAT_1]; # Indien zonder lengtevariatie < 0 --> patroon wegschrijven if Reduced_Cost_1 < -0.0001 then { let {a in ARTIKEL} aantal_1[a,aPAT_1] := (floor(rol_lengte/breedte[a])*use_L_1[a] + floor(rol_lengte/lengte[a])*use_B_1[a]); let aPAT_1 := aPAT_1 + 1; let breedteverlies_1[aPAT_1] := breedteverlies_1[aPAT_1-1]; print "*Nieuw patroon 1 zonder lengtevariatie *********";


} else {let stop:= stop + 1;}; # wegschrijven snijbreedtes repeat { for {a in ARTIKEL} { if use_L_1[a] > 0 then { let snijbreedtes_1[aPAT_1,bandnummer_1] := lengte[a]; let bandnummer_1 := bandnummer_1 + 1; let use_L_1[a] := use_L_1[a] - 1; } if use_B_1[a] > 0 then { let snijbreedtes_1[aPAT_1,bandnummer_1] := breedte[a]; let bandnummer_1 := bandnummer_1 + 1; let use_B_1[a] := use_B_1[a] - 1; } } } until sum{x in ARTIKEL} (use_L_1[x] + use_B_1[x]) = 0; # per band best mogelijke producten wegschrijven in param stuks let {a in ARTIKEL} stuks_1[a] := 0; for { i in 1..bandnummer_1 - 1} { let tel := i; let snijbreedtes_1[aPAT_1-1,i] := snijbreedtes_1[aPAT_1,i]; let ARTIKELSUBSET := {a in ARTIKEL: lengte[a] == snijbreedtes_1[aPAT_1,tel] or breedte[a] == snijbreedtes_1[aPAT_1,tel]}; let ARTIKELNIETL:= {a in ARTIKELSUBSET: lengte[a] <> snijbreedtes_1[aPAT_1,tel]}; let ARTIKELNIETB:= {a in ARTIKELSUBSET: breedte[a] <> snijbreedtes_1[aPAT_1,tel]}; solve Pattern_Gen_1; let {a in ARTIKELSUBSET} stuks_1[a] := stuks_1[a] + stuksperband_L_1[a] + stuksperband_B_1[a]; } # Indien met lengtevariatie < 0 --> patroon wegschrijven if (breedteverlies_1[aPAT_1] - sum{a in ARTIKEL} price[a] * stuks_1[a]) < -0.0001 then { let {a in ARTIKEL} aantal_1[a,aPAT_1] := stuks_1[a]; let aPAT_1 := aPAT_1 + 1; print "*Nieuw patroon 1 met lengtevariatie *********"; } else {let stop:= stop + 1;}; # _2:BREDE ROL print "***** BREDE ROL *****"; let bandnummer_2:=1; solve Band_Gen_2; let breedteverlies_2[aPAT_2] := brverlies_2[aPAT_2]; # Indien zonder lengtevariatie < 0 --> patroon wegschrijven if Reduced_Cost_2 < -0.0001 then { let {a in ARTIKEL} aantal_2[a,aPAT_2] := (floor(rol_lengte/breedte[a])*use_L_2[a] + floor(rol_lengte/lengte[a])*use_B_2[a]); let aPAT_2 := aPAT_2 + 1; let breedteverlies_2[aPAT_2] := breedteverlies_2[aPAT_2-1]; print "*Nieuw patroon 2 zonder lengtevariatie *********"; } else {let stop:= stop + 1;};

# wegschrijven snijbreedtes repeat {

74


for {a in ARTIKEL} { if use_L_2[a] > 0 then { let snijbreedtes_2[aPAT_2,bandnummer_2] := lengte[a]; let bandnummer_2 := bandnummer_2 + 1; let use_L_2[a] := use_L_2[a] - 1; } if use_B_2[a] > 0 then { let snijbreedtes_2[aPAT_2,bandnummer_2] := breedte[a]; let bandnummer_2 := bandnummer_2 + 1; let use_B_2[a] := use_B_2[a] - 1; } } } until sum{x in ARTIKEL} (use_L_2[x] + use_B_2[x]) = 0; # per band best mogelijke producten wegschrijven in param stuks let {a in ARTIKEL} stuks_2[a] := 0; for { i in 1..bandnummer_2 - 1} { let tel := i; # display tel; let snijbreedtes_2[aPAT_2-1,i] := snijbreedtes_2[aPAT_2,i]; let ARTIKELSUBSET := {a in ARTIKEL: lengte[a] == snijbreedtes_2[aPAT_2,tel] or breedte[a] == snijbreedtes_2[aPAT_2,tel]}; let ARTIKELNIETL:= {a in ARTIKELSUBSET: lengte[a] <> snijbreedtes_2[aPAT_2,tel]}; let ARTIKELNIETB:= {a in ARTIKELSUBSET: breedte[a] <> snijbreedtes_2[aPAT_2,tel]}; # display ARTIKELSUBSET; # display price; solve Pattern_Gen_2; let {a in ARTIKELSUBSET} stuks_2[a] := stuks_2[a] + stuksperband_L_2[a] + stuksperband_B_2[a]; # display snijbreedtes_2; # display stuksperband_L_2; display stuksperband_B_2; # display stuks_2; } # display stuks_2; # display snijbreedtes_2; # Indien met lengtevariatie < 0 --> patroon wegschrijven if (breedteverlies_2[aPAT_2] - sum{a in ARTIKEL} price[a] * stuks_2[a]) < -0.0001 then { # display breedteverlies_2[aPAT_2] - sum{a in ARTIKEL} price[a] * stuks_2[a]; let {a in ARTIKEL} aantal_2[a,aPAT_2] := stuks_2[a]; # display aantal_2; display stuks_2; let aPAT_2 := aPAT_2 + 1; print "*Nieuw patroon 2 met lengtevariatie *********"; } else {let stop:= stop + 1;}; # display stop;

} until stop >= 4; let aPAT_1 := aPAT_1 - 1; let aPAT_2 := aPAT_2 - 1; # Non INTEGER oplossing let combopp := (sum {p in PATROON_1} (sum{a in ARTIKEL}(aantal_1[a,p]* lengte[a] * breedte[a]) * make_1[p])) + (sum {n in PATROON_2}(sum{a in ARTIKEL}( aantal_2[a,n]* lengte[a] * breedte[a] )* make_2[n])); let verliesopp := 3730 * (sum {p in PATROON_1} (make_1[p]* breedteverlies_1[p]) + sum {n in PATROON_2} (make_2[n]* breedteverlies_2[n])); let perccombverl["NI"] := verliesopp * 100 / (combopp + verliesopp);

75


let somaantalrollen["NI"]:= sum{p in PATROON_1} make_1[p] + sum{p2 in PATROON_2} make_2[p2]; let aantalpatronen["NI"]:= sum {p in PATROON_1: make_1[p] <> 0} (1) + sum {p2 in PATROON_2: make_2[p2] <> 0} (1); let percoverschot["NI"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON_1} (aantal_1[a,p]* lengte[a] * breedte[a] * make_1[p])) + (sum {p2 in PATROON_2} (aantal_2[a,p2]* lengte[a] * breedte[a] * make_2[p2])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2]; # Non INTEGER oplossing afronden let {p in PATROON_1} make_1R[p] := round(make_1[p],0); let {p in PATROON_2} make_2R[p] := round(make_2[p],0); let combopp := (sum {p in PATROON_1} (sum{a in ARTIKEL} (aantal_1[a,p]* lengte[a] * breedte[a]) * make_1R[p])) + (sum {n in PATROON_2} (sum{a in ARTIKEL}( aantal_2[a,n]* lengte[a] * breedte[a] )* make_2R[n])); let verliesopp := 3730 * (sum {p in PATROON_1} (make_1R[p]* breedteverlies_1[p]) + sum {n in PATROON_2} (make_2R[n]* breedteverlies_2[n])); let perccombverl["NI_R"] := verliesopp * 100 / (combopp + verliesopp); let somaantalrollen["NI_R"]:= sum{p in PATROON_1} make_1R[p] + sum{p2 in PATROON_2} make_2R[p2]; let aantalpatronen["NI_R"]:= sum {p in PATROON_1: make_1R[p] <> 0} (1) + sum {p2 in PATROON_2: make_2R[p2] <> 0} (1); let percoverschot["NI_R"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON_1} (aantal_1[a,p]* lengte[a] * breedte[a] * make_1R[p])) + (sum {p2 in PATROON_2} (aantal_2[a,p2]* lengte[a] * breedte[a] * make_2R[p2])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2];

# Wegschrijven naar excel table NI_Make1 OUT "ODBC" "results.xls" "NI_Make1": [PATROON_1], make_1, breedteverlies_1; write table NI_Make1; table NI_Make2 OUT "ODBC" "results.xls" "NI_Make2": [PATROON_2], make_2, breedteverlies_2; write table NI_Make2; table Patroon1stuks OUT "ODBC" "results.xls" "Patroon1stuks": {p in PATROON_1} -> [PATROON_1], {a in ARTIKEL} ; write table Patroon1stuks; table Patroon1m2 OUT "ODBC" "results.xls" "Patroon1m2": {p in PATROON_1} -> [PATROON_1], {a in ARTIKEL} ; write table Patroon1m2; table Patroon2stuks OUT "ODBC" "results.xls" "Patroon2stuks": {p in PATROON_2} -> [PATROON_2], {a in ARTIKEL} ; write table Patroon2stuks; table Patroon2m2 OUT "ODBC" "results.xls" "Patroon2m2": {p in PATROON_2} -> [PATROON_2], {a in ARTIKEL} ; write table Patroon2m2; table NI_Stock OUT "ODBC" "results.xls" "NI_Stock": {a in ARTIKEL} -> [ARTIKEL], stock[a] + (sum {p in PATROON_1} aantal_1[a,p] * make_1[p]) + (sum {n in PATROON_2} aantal_2[a,n] * make_2[n])~(’stuksPRODUCED’) , demandstuks[a] ~(’stuksDemand’), (stock[a] + (sum {p in PATROON_1} aantal_1[a,p] * make_1[p])

76


+ (sum {n in PATROON_2} aantal_2[a,n] * make_2[n])) * lengte[a] * breedte[a]~(’m2PRODUCED’) , demandstuks[a] * lengte[a] * breedte[a] ~(’m2Demand’) ; write table NI_Stock; let aPAT_1 := aPAT_1 + 1; let aPAT_2 := aPAT_2 + 1;

option Cutting_Opt.relax_integrality 0; option Cutting_Opt.presolve 0; solve Cutting_Opt; let aPAT_1 := aPAT_1 - 1; let aPAT_2 := aPAT_2 - 1; # INTEGER oplossing let combopp := (sum {p in PATROON_1} (sum{a in ARTIKEL}(aantal_1[a,p]* lengte[a] * breedte[a]) * make_1[p])) + (sum {n in PATROON_2}(sum{a in ARTIKEL} ( aantal_2[a,n]* lengte[a] * breedte[a] )* make_2[n])); let verliesopp := 3730 * (sum {p in PATROON_1} (make_1[p]* breedteverlies_1[p]) + sum {n in PATROON_2} (make_2[n]* breedteverlies_2[n])); let perccombverl["I"] := verliesopp * 100 / (combopp + verliesopp); let somaantalrollen["I"]:= sum{p in PATROON_1} make_1[p] + sum{p2 in PATROON_2} make_2[p2]; let aantalpatronen["I"]:= sum {p in PATROON_1: make_1[p] <> 0} (1) + sum {p2 in PATROON_2: make_2[p2] <> 0} (1); let percoverschot["I"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON_1} (aantal_1[a,p]* lengte[a] * breedte[a] * make_1[p])) + (sum {p2 in PATROON_2} (aantal_2[a,p2]* lengte[a] * breedte[a] * make_2[p2])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2];

# Wegschrijven naar excel table Verlies OUT "ODBC" "results.xls" "CombVerl": {i in INT} -> [NonInt_of_Int], perccombverl, somaantalrollen, aantalpatronen, percoverschot ; write table Verlies; table I_Make1 OUT "ODBC" "results.xls" "I_Make1": [PATROON_1], make_1, breedteverlies_1; write table I_Make1; table I_Make2 OUT "ODBC" "results.xls" "I_Make2": [PATROON_2], make_2, breedteverlies_2; write table I_Make2; table I_Stock OUT "ODBC" "results.xls" "I_Stock": {a in ARTIKEL} -> [ARTIKEL], stock[a] + (sum {p in PATROON_1} aantal_1[a,p] * make_1[p]) + (sum {n in PATROON_2} aantal_2[a,n] * make_2[n])~(’PRODUCED’) , demandstuks[a] ~(’Demand’),(stock[a] + (sum {p in PATROON_1} aantal_1[a,p] * make_1[p]) + (sum {n in PATROON_2} aantal_2[a,n] * make_2[n])) * lengte[a] * breedte[a]~(’m2PRODUCED’) , demandstuks[a] * lengte[a] * breedte[a] ~(’m2Demand’) ; write table I_Stock;

77


B.2 set set set set

Het .MOD bestand ARTIKEL; ARTIKELSUBSET within ARTIKEL; ARTIKELNIETL within ARTIKEL; ARTIKELNIETB within ARTIKEL;

param param param param param param param

brede_rol_breedte > 0; smalle_rol_breedte > 0; rol_lengte > 0; tolerantie > 0; stop >=0; tel integer >=0; lus integer >=0;

param breedte{ARTIKEL} >= 0; param lengte{ARTIKEL} >= 0; param stock{ARTIKEL} >= 0; param minstock{ARTIKEL} >= 0; param maxstock{ARTIKEL} >= 0; param demand{ARTIKEL} >= 0; param demandstuks{ARTIKEL} >= 0; set ITERATIES := 1..lus; param resultaat{ITERATIES} >= 0; param combopp > 0; param verliesopp > 0; set INT := {"NI", "I", "NI_R"}; param perccombverl{INT} >= 0; param somaantalrollen{INT} >= 0; param aantalpatronen{INT} >= 0; param percoverschot{INT};

# _1:SMALLE ROL param aPAT_1 integer >= 0; set PATROON_1 := 1..aPAT_1; param verlies_1{PATROON_1} >=0; param aantal_1 {ARTIKEL,PATROON_1} integer >= 0; param stuks_1 {ARTIKEL} integer >= 0; param aantalinbreedte_1 {ARTIKEL,PATROON_1} integer >= 0; param bandnummer_1 integer >= 0; param snijbreedtes_1{PATROON_1, 1..5}; param breedteverlies_1{PATROON_1} >=0; var brverlies_1{PATROON_1} >=0; var bandverlies_1{PATROON_1} >=0; var make_1 {PATROON_1} integer >=0; var use_L_1 {ARTIKEL} integer >= 0; var use_B_1 {ARTIKEL} integer >= 0; var stuksperband_L_1 {ARTIKELSUBSET} integer >= 0; var stuksperband_B_1 {ARTIKELSUBSET} integer >= 0;

# _2:BREDE ROL param aPAT_2 integer >= 0; set PATROON_2 := 1..aPAT_2; param verlies_2{PATROON_2} >=0; param aantal_2 {ARTIKEL,PATROON_2} integer >= 0; param stuks_2 {ARTIKEL} integer >= 0;

78


param aantalinbreedte_2 {ARTIKEL,PATROON_2} integer >= 0; param bandnummer_2 integer >= 0; param snijbreedtes_2{PATROON_2, 1..5}; param breedteverlies_2{PATROON_2} >=0; var brverlies_2{PATROON_2} >=0; var bandverlies_2{PATROON_2} >=0; var make_2 {PATROON_2} integer >=0; var use_L_2 {ARTIKEL} integer >= 0; var use_B_2 {ARTIKEL} integer >= 0; var stuksperband_L_2 {ARTIKELSUBSET} integer >= 0; var stuksperband_B_2 {ARTIKELSUBSET} integer >= 0; param make_1R{PATROON_1} >=0; param make_2R{PATROON_2} >=0; # ----------------------# DOELFUNCTIE # ----------------------minimize number: sum {p in PATROON_1: p < aPAT_1} (make_1[p]* breedteverlies_1[p]) + sum {n in PATROON_2: n < aPAT_2} (make_2[n]*breedteverlies_2[n]); subject to stocklevel {a in ARTIKEL}: minstock[a] <= stock[a] + (sum {p in PATROON_1: p < aPAT_1} aantal_1[a,p] * make_1[p]) + (sum {n in PATROON_2: n < aPAT_2} aantal_2[a,n] * make_2[n]) - demandstuks[a] <= tolerantie * demandstuks[a];

# --------------------------------# 1* KNAPSACK SUBPROBLEM IN BREEDTE # --------------------------------param price {ARTIKEL} default 0.0; # _1:SMALLE ROL minimize Reduced_Cost_1: brverlies_1[aPAT_1] - sum{a in ARTIKEL} price[a] * (floor(rol_lengte/breedte[a]) *use_L_1[a]+ floor(rol_lengte/lengte[a])*use_B_1[a]); subject to Width_Limit_1: (sum {a in ARTIKEL} lengte[a] * use_L_1[a]) + (sum {a in ARTIKEL} breedte[a] * use_B_1[a]) <= smalle_rol_breedte; subject to Breedte_verlies_1: smalle_rol_breedte - sum {a in ARTIKEL} (lengte[a] * use_L_1[a]) - sum {a in ARTIKEL} (breedte[a] * use_B_1[a]) <= brverlies_1[aPAT_1];

# _2:BREDE ROL minimize Reduced_Cost_2: brverlies_2[aPAT_2] - sum{a in ARTIKEL} price[a] * (floor(rol_lengte/breedte[a])*use_L_2[a] + floor(rol_lengte/lengte[a])*use_B_2[a]); subject to Width_Limit_2: (sum {a in ARTIKEL} lengte[a] * use_L_2[a]) + (sum {a in ARTIKEL} breedte[a] * use_B_2[a]) <= brede_rol_breedte; subject to Breedte_verlies_2: brede_rol_breedte - sum {a in ARTIKEL} (lengte[a] * use_L_2[a]) - sum {a in ARTIKEL} (breedte[a] * use_B_2[a]) <= brverlies_2[aPAT_2];

79


80

# --------------------------------# 2* DEELPROBLEM IN LENGTE # --------------------------------# _1:SMALLE ROL minimize RC_1: 1 - sum{a in ARTIKELSUBSET} price[a] * (stuksperband_B_1[a]+ stuksperband_L_1[a]); subject to Length_Limit_1: (sum {a in ARTIKELSUBSET} lengte[a] * stuksperband_B_1[a]) + (sum {a in ARTIKELSUBSET} breedte[a] * stuksperband_L_1[a]) <= rol_lengte; subject to Band_Verlies_1{a2 in ARTIKELNIETB}: rol_lengte - sum {a in ARTIKELSUBSET}(stuksperband_L_1[a] * breedte[a]) - sum {a in ARTIKELSUBSET} (stuksperband_B_1[a] * lengte[a]) <=breedte[a2]; subject to Band_Verlies_11{a2 in ARTIKELNIETL}: rol_lengte - sum {a in ARTIKELSUBSET}(stuksperband_L_1[a] * breedte[a]) - sum {a in ARTIKELSUBSET} (stuksperband_B_1[a] * lengte[a]) <=lengte[a2]; subject to Breedte_1 {a in ARTIKELNIETB}: stuksperband_B_1[a] == 0; subject to Lengte_1 {a in ARTIKELNIETL}: stuksperband_L_1[a] == 0;

# _2:BREDE ROL minimize RC_2: 1 - sum{a in ARTIKELSUBSET} price[a] * (stuksperband_B_2[a]+ stuksperband_L_2[a]); subject to Length_Limit_2: (sum {a in ARTIKELSUBSET} lengte[a] * stuksperband_B_2[a]) + (sum {a in ARTIKELSUBSET} breedte[a] * stuksperband_L_2[a]) <= rol_lengte; subject to Band_Verlies_2{a2 in ARTIKELNIETB}: rol_lengte - sum {a in ARTIKELSUBSET}(stuksperband_L_2[a] * breedte[a]) - sum {a in ARTIKELSUBSET} (stuksperband_B_2[a] * lengte[a]) <=breedte[a2]; subject to Band_Verlies_22{a2 in ARTIKELNIETL}: rol_lengte - sum {a in ARTIKELSUBSET}(stuksperband_L_2[a] * breedte[a]) - sum {a in ARTIKELSUBSET} (stuksperband_B_2[a] * lengte[a]) <=lengte[a2]; subject to Breedte_2 {a in ARTIKELNIETB}: stuksperband_B_2[a] == 0; subject to Lengte_2 {a in ARTIKELNIETL}: stuksperband_L_2[a] == 0;

Bijlage C

AMPL code bibliotheek model C.1

Het .RUN bestand

option solver cplexamp; model bib.mod; data BXC_1010.DAT;

# Non INTEGER oplossing let tolerantie := 2; problem Bib_Opt: Make, total_loss, stocklevel; option relax_integrality 1; solve Bib_Opt; let combopp := sum{p in PATROON} (Make[p] * sum{a in ARTIKEL} (aantalm2perrol[a,p])); let verliesopp := sum{p in PATROON} (Make[p] * loss[p] * 3730); let perccombverl["NI"] := verliesopp * 100 / (combopp + verliesopp); let somaantalrollen["NI"]:= sum{p in PATROON} Make[p]; let aantalpatronen["NI"]:= sum {p in PATROON: Make[p] <> 0} 1; let percoverschot["NI"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2];

# Non INTEGER oplossing afronden let {p in PATROON} MakeR[p] := round(Make[p],0); let combopp := sum{p in PATROON} (MakeR[p] * sum{a in ARTIKEL} (aantalm2perrol[a,p])); let verliesopp := sum{p in PATROON} (MakeR[p] * loss[p] * 3730); let perccombverl["NI_R"] := verliesopp * 100 / (combopp + verliesopp); let somaantalrollen["NI_R"]:= sum{p in PATROON} MakeR[p]; let aantalpatronen["NI_R"]:= sum {p in PATROON: MakeR[p] <> 0} 1; let percoverschot["NI_R"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * MakeR[p])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2]; # Wegschrijven naar excel table NI_Make OUT "ODBC" "bib.xls" "NI_Make": [PATROON], Make, loss; write table NI_Make; table Patroonm2 OUT "ODBC" "bib.xls" "Patroon_m2": {p in PATROON} -> [PATROON], Make, {a in ARTIKEL} ; write table Patroonm2;

81

Bijlage C. AMPL code bibliotheek model

table Patroonstuks OUT "ODBC" "bib.xls" "Patroon_stuks": {p in PATROON} -> [PATROON], Make, {a in ARTIKEL} ; write table Patroonstuks; table NI_Stock OUT "ODBC" "bib.xls" "NI_Stock": {a in ARTIKEL} -> [ARTIKEL], stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p]))~(’PRODUCED_m2’) , demand[a] ~(’Demand’), stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p])) - demand[a] ~(’Eindstock_m2’); write table NI_Stock; # INTEGER oplossing option Bib_Opt.relax_integrality 0; option Bib_Opt.presolve 0; solve Bib_Opt; let combopp := sum{p in PATROON} (Make[p] * sum{a in ARTIKEL} (aantalm2perrol[a,p])); let verliesopp := sum{p in PATROON} (Make[p] * loss[p] * 3730); let perccombverl["I"] := verliesopp * 100 / (combopp + verliesopp); let somaantalrollen["I"]:= sum{p in PATROON} Make[p]; let aantalpatronen["I"]:= sum {p in PATROON: Make[p] <> 0} 1; let percoverschot["I"] := 100 * (sum {a in ARTIKEL} (stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p])) - demand[a])) / sum{a2 in ARTIKEL} demand[a2]; # Wegschrijven naar excel table Verlies OUT "ODBC" "bib.xls" "CombVerl": {i in INT} -> [NonInt_of_Int], perccombverl, somaantalrollen, aantalpatronen, percoverschot; write table Verlies; table Make OUT "ODBC" "bib.xls" "I_Make": [PATROON], Make, loss; write table Make; table Stock OUT "ODBC" "bib.xls" "I_Stock": {a in ARTIKEL} -> [ARTIKEL], stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p]))~(’PRODUCED_m2’) , demand[a] ~(’Demand’), stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] * Make[p])) - demand[a] ~(’Eindstock_m2’); write table Stock;

82

Bijlage C. AMPL code bibliotheek model

C.2

Het .MOD bestand

set ARTIKEL; set PATROON; param stock{ARTIKEL} >= 0; param lengte{ARTIKEL} >= 0; param breedte{ARTIKEL} >= 0; param minstock{ARTIKEL} >= 0; param maxstock{ARTIKEL} >= 0; param demand{ARTIKEL} >= 0; param loss{PATROON} >= 0; param aantalm2perrol{ARTIKEL,PATROON}>= 0; param tolerantie > 0; param combopp > 0; param verliesopp > 0; set INT := {"NI", "I", "NI_R"}; param perccombverl{INT} >= 0; param somaantalrollen{INT} >= 0; param aantalpatronen{INT} >= 0; param MakeR{PATROON} >=0; param percoverschot{INT}; var Make {p in PATROON}

integer >=0;

minimize total_loss: sum {p in PATROON} Make[p] * loss[p]; subject to stocklevel {a in ARTIKEL}: minstock[a] <= stock[a] + (sum {p in PATROON} (aantalm2perrol[a,p] <= tolerantie * demand[a]; subject to hoevpatroon {p in PATROON}: Make[p] * (Make[p] - 0.1) >= 0;

* Make[p])) - demand[a]

83

Bijlage D

Resultaten column generation model

Figuur D.1: Resultaten bekomen met column generation model, enkel Wuxi artikelen gecombineerd, tolerantie = 1%

84

Bijlage D. Resultaten column generation model

85

Figuur D.2: Resultaten bekomen met column generation model, enkel artikelen die lengte of breedte delen met een Wuxi bandbreedte gecombineerd, tolerantie = 1%

Figuur D.3: Resultaten bekomen met column generation model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 0.1%


86

Figuur D.4: Resultaten bekomen met column generation model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 0.5%

Figuur D.5: Resultaten bekomen met column generation model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 1%


87



Bijlage E

Resultaten historische bibliotheek model

Figuur E.1: Resultaten bekomen met bibliotheek model, enkel Wuxi artikelen gecombineerd, tolerantie = 1%

88

Bijlage E. Resultaten historische bibliotheek model

89

Figuur E.2: Resultaten bekomen met bibliotheek model, enkel artikelen die lengte of breedte delen met een Wuxi bandbreedte gecombineerd, tolerantie = 1%

Figuur E.3: Resultaten bekomen met bibliotheek model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 0.1%


90

Figuur E.4: Resultaten bekomen met bibliotheek model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 0.5%

Figuur E.5: Resultaten bekomen met bibliotheek model, alle artikelen met betrekking tot gietsoort gecombineerd, tolerantie = 1%


91



Bijlage F

Conventionele afronding van het bibliotheek model

Figuur F.1: Vergelijking van het percentage combinatieverlies voor en na conventioneel afronden van de LP gerelaxeerde oplossing

92

Bijlage F. Conventionele afronding van het bibliotheek model

93

Figuur F.2: Vergelijking van het aantal gebruikte patronen voor en na conventioneel afronden van de LP gerelaxeerde oplossing

Figuur F.3: Vergelijking van het percentage teveel geproduceerd voor en na conventioneel afronden van de LP gerelaxeerde oplossing

Bibliografie R. Alvares-Valdés, A. Paraj´ on & J. Tamarit (2002). A tabu search algorithm for large scale guillotine (un)constrained two-dimensional cutting problems. Computers & Operations Research, 29:925–947. H. Dyckhoff (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44:145–159. D. Fayard, M. Hifi & V. Zissimopoulos (1998). An efficient approach for large-scale twodimensional cutting stock problems. Journal of Operational Research Society, 49:1270– 1277. T. A. Feo & M. G. C. Resende (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133. P. C. Gilmore & R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859. P. C. Gilmore & R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - part ii. Operations Research, 11(6):863–888. P. C. Gilmore & R. E. Gomory (1964). Multistage cutting stock problems of two and more dimensions. Operations Research, 13:94–120. P. C. Gilmore & R. E. Gomory (1966). The theory and computation of knapsack functions. Operations Research, 14:1045–1074. F. Glover (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13:533–549. R. W. Haessler (1971). A heuristic programming solution to an nonlinear cutting stock problem. Management Science, 17:793–802. R. W. Haessler (1975). Controlling cutting pattern changes in one-dimensional trim problems. Operational research, 23:483–493. R. W. Haessler (1988). Selection and design of heuristic procedures for solving roll trim problems. Management Science, 34:1460–1471.

94

Bibliografie

95

R. W. Haessler & P. E. Sweeney (1991). Cutting stock problems and solutions procedures. European Journal of Operational Research, 54:141–150. M. Hifi, R. M’Hallah & T. Saadi (2009). Approximate and exact algorithms for the doubleconstrained two-dimensional guillotine cutting stock problem. Computational Optimization and Apllications, 42:303–326. A. Hinxman (1979). The trim-loss and assortment problems: A survey. European Journal of Operational Research, 5:8–18. L. V. Kantorovich (1960). Mathematical methods of organizing and planning production. Management Science, 6(4):336–442. V. Maniezzo & A. Carbonara (1999). Ant colony optimization: an overview. Knowledge and Data Engineering, 11:769–778. S. Martello & P. Toth (1990). Knapsack problems: algorithms and computer implementations. John Wiley & Sons. ISBN 0-471-92420-2. Wikipedia (the free encyclopedia). knapsack problem. http://en.wikipedia.org/.

Geï ntegreerde versnijding en productieplanning problemen

Recommend Documents