Wafer-to-Wafer integration problem

[wevelgem]

Beste,

Ik ben een 1ste-jaars masterstudent en als opdracht voor het vak "Toepassingen van operationeel onderzoek" hebben we een optimalisatie oefening gekregen.

Het probleem gaat als volgt:

We are given m sets of different wafers, called wafer lots, say V₁, V₂, … V_m, with each lot V_i containing n wafers.. The new production technique WtW now means that we are going to construct n stacks, where a stack is nothing else but a collection of m wafers, one from each lot V_i. How to measure the quality of a stack? The m wafers making up a stack can be seen as being superimposed on top of each other. Thus, m corresponding dies (those that lie on top of each other) in the individual wafers correspond to a single position in the stack. A position in this stack can be either good or bad, depending upon whether all dies corresponding to that position are good, or when at least one of these dies is bad. This means that bad dies of different wafers that are in the same position contribute only once (negatively) to the quality of a stack. In other words, the number of positions in the stack that have a bad die (coming from one of the wafers in the stack) is in fact the quality of a stack.

Onze probleeminstantie betreft m=21,n=16,p=16. Met andere woorden, we hebben 21 loten, bestaande uit 16 wafers. Elke wafer bevat 16 dies. De bedoeling is om uit elk lot een wafer te nemen en zo, na opeenstapeling, een minimum aantal slechte "die positions" te hebben, overheen alle geconstrueerde stacks.

Via opzoekingswerk zijn we tot de constatie gekomen dat ons probleem niet exact oplosbaar is. Hiertoe moeten we dus een heuristiek gebruiken, namelijk de volgende:

Iterative Matching heuristic

Input: K wafer lots maps L = {L1, . . . ,LK} each with N wafers.

Output: A mapping from wafer to 3D integration stack.

// start with the first lot as the “seed” lot

1. let Ls = L1

2. let L = L−{L1} 3. while |L| > 1:

// gbest holds the number of good die

4. let gbest = 0

5. for each Lj ∈ L:

// calculate the number of good die from

// optimally matching lots Ls and Lj

6. let gj = G(Lj ⊙Ls)

7. if gj ≥ gbest then

// bj is the index of the best lot

8. let gbest = gj

9. let bj = j

10. let Ls = Ls⊙Lbj

11. let L = L−{Lbj }

Onze prof prefereert het programma Cplex. Aangezien onze groep niet echt 'programmeertalent' bevat, had ik gedacht om in dit forum eventueel oplossingen te vinden.

Mijn vraag is dus: Is het mogelijk om een programmacode (alle programma's toegelaten) te schrijven voor deze heuristiek?

Voor eventueel meer info (+ papers betreffende dit probleem), zie volgende bestanden:

TvOO-case5wafer

(92.4 KiB) 162 keer gedownload

data_wafer

(5.66 KiB) 111 keer gedownload

wafer-to-wafer

(77 KiB) 249 keer gedownload

TDokka_approxwafer

(532.27 KiB) 494 keer gedownload

Alvast bedankt

[wevelgem]

Eventueel een makkelijker deelprobleem:

Gegeven volgende 3 wafer lots, bestaande uit elk 3 wafers. Elke wafer heeft 10 dies (1 staat voor een slechte die, 0 voor een goede die). De bedoeling is dus om telkens 1 wafer uit elk lot te combineren, zodat het totaal aantal bad dies (1'tjes) geminimaliseerd wordt.

lot .................Item 1 ......................Item 2 ................................... Item 3

1 ................ 1 0 0 1 1 0 0 0 0 0 .............. 0 0 1 0 0 0 1 0 0 0 ............. 0 1 0 0 0 0 1 1 0 0

2 .................0 0 0 0 1 0 0 0 1 0 ............. 0 0 1 0 0 1 0 0 1 0 .............1 1 0 0 0 0 1 0 0 1

3 ..................1 1 0 0 0 0 0 0 0 0................. 0 0 0 0 0 0 0 0 0 1 ...........0 0 0 0 0 0 1 1 0 0

Een voorbeeld van een toewijzing: alle eerste items in stack 1 plaatsen, alle tweede items in stack 2 en alle derde items in stack 3. Zo heeft elke geconstrueerde stack, 5 bad postions.

De vraag is nu: is het mogelijk om een programmacode te schrijven waardoor bij dit toewijzingsprobleem de optimale oplossing wordt verkregen?

Alvast bedankt

[Xenion]

Dit lijkt mij een combinatorial optimization probleem. Je zegt dat het niet mogelijk is om de optimale oplossing te vinden. Het is zeker wel mogelijk aangezien je simpelweg alle mogelijke combinaties kan uitproberen, maar gezien de aard van het probleem is het gauw niet meer haalbaar als de parameters te groot worden.

Je hebt blijkbaar al een benaderingsalgoritme gevonden dat je zou kunnen proberen.

Opmerking moderator

Het is echter niet de bedoeling van dit forum (en eigenlijk geen enkel ander forum) om kant en klare oplossingen te bieden. Het programmeren zal je dus echt wel zelf moeten doen.