Springen naar inhoud

Wafer-to-Wafer integration problem


  • Log in om te kunnen reageren

#1

wevelgem

    wevelgem


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 06 november 2012 - 18:38

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 V1, V2, … Vm, with each lot Vi 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 Vi. 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:
Bijlage  TvOO-case5wafer.docx   92,4K   38 maal gedownload
Bijlage  data_wafer.txt   5,66K   34 maal gedownload
Bijlage  wafer-to-wafer.pdf   77K   114 maal gedownloadBijlage  TDokka_approxwafer.pdf   532,27K   339 maal gedownload

Alvast bedankt

Bijgevoegde Bestanden


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

wevelgem

    wevelgem


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 10 november 2012 - 16:04

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

Veranderd door wevelgem, 10 november 2012 - 16:08


#3

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 10 november 2012 - 17:41

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures