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?

Beste,

Een pseudocode kan ik niet formuleren maar in gewone mensentaal wel.
De heuristiek gaat namelijk als volgt:

Eerst neem je de eerste 2 wafer lots van 16 wafers, en die probeer je zo goed mogelijk met elkaar te combineren.
Je neemt bvb de eerste wafer van wafer lot 1, en combineert deze met de 15de wafer van wafer lot 2.
Dit wordt ook wel het '2D assignment problem' genoemd.

Dan neem je de geconstrueerde wafer stack (bestaande uit 16 combinaties van 2 wafers), en probeert die zo optimaal mogelijk toe te wijzen aan de derde wafer lot.
Het resultaat is een wafer stack (bestaande uit 16 combinaties van 3 wafers).

Volgende stap is dan die wafer stack gaan combineren met de 4de wafer lot.

Dit herhaal je tot de 21ste wafer lot.

Het resultaat is dan 16 geconstrueerde wafer stacks, telkens met 21 wafers boven elkaar.

Hopelijk is dit een beetje duidelijk (en is dit voldoende om het te programmeren)
Alvast bedankt