Maximale Anzahl von Rechtecken in Kreis

29.03.2016, 15:52

freshmanjohn

Maximale Anzahl von Rechtecken in Kreis

Meine Frage:
Hallo zusammen,
ich sitze vor folgender Optimierungsaufgabe:
Auf einem kreisförmigen Wafer mit 100mm Durchmesser sollen möglichst viele Strukturen der Größe 6405µm x 3005µm platziert werden. Zum Waferrand soll überall ein Mindestabstand von 5mm bestehen. Der Abstand zwischen 2 Strukturen soll immer mindestens 200µm betragen. Eine weitere Bedingung ist, dass die Strukturen nur in geraden Reihen und Spalten platziert werden dürfen, da die Trennung mit einer Säge erfolgt, die nur durch den ganzen Wafer schneiden kann.
Die Fragestellung lautet: Wie viel Strukturen haben maximal auf dem Wafer platz?

Über Hinweise oder Lösungsvorschläge wäre ich dankbar =)

Meine Ideen:
- Betrachtung eines Viertelkreises
- Halben Abstand zwischen den Strukturen zur Strukturgröße addieren
- Reihen und Spalten sind Rechtecke mit quantisierten Abmessungen als Vielfache der Strukturgrößen
- Gesamtanzahl als Funktion von Reihen- und Spaltengröße optimieren

29.03.2016, 16:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von freshmanjohn
- Halben Abstand zwischen den Strukturen zur Strukturgröße addieren

Ja, aber das an allen vier Begrenzungskanten. Wir betrachten dann Rechtecke mit den Abmessungen
$\begin{align*} a=6605~\mu m \end{align*}$ und $\begin{align*} b=3205~\mu m \end{align*}$ .

Zitat:

Original von freshmanjohn
- Betrachtung eines Viertelkreises

Jein: Es gibt vier Möglichkeiten für die Symmetrie einer optimalen Packung der Strukturen:

- Im Waferzentrum liegt eine Struktur
- Im Waferzentrum liegen zwei Strukturen beiderseits der x-Achse (diese ist Schnittlinie)
- Im Waferzentrum liegen zwei Strukturen beiderseits der y-Achse (diese ist Schnittlinie)
- Im Waferzentrum liegen vier Strukturen, d.h. in jedem Quadranten jeweils eine anliegend, x- und y-Achse sind beides Schnittlinien.

Anscheinend willst du nur die letzte dieser vier Varianten betrachten - es ist aber nicht zwingend, dass dort die optimale Strukturenanzahl zu finden ist, dies kann auch in einem der drei anderen Fälle passieren. Das ist einzeln zu checken.

P.S.: Ich bekomme maximale Anzahl 268 heraus, erreichbar mit Variante 2.

29.03.2016, 18:01

freshmanjohn

Auf diesen Beitrag antworten »

Danke für deine schnelle Antwort.

Den Punkt mit der Rechteckgröße und den möglichen Symmetrien habe ich verstanden.

Aber wie komme ich den auf die für mein Problem geeignete Symmetrie ohne das Problem für alle Symmetriearten zu lösen?

Dein Ergebnis mit 268 Strukturen klingt plausibel - kannst du mir deinen Ansatz bitte skizzieren?

29.03.2016, 19:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von freshmanjohn
Aber wie komme ich den auf die für mein Problem geeignete Symmetrie ohne das Problem für alle Symmetriearten zu lösen?

Weiß ich auch nicht - ich kenne nur die aufwändige mit-Variante.

29.03.2016, 21:01

freshmanjohn

Auf diesen Beitrag antworten »

Okay - kannst du mir dann die wichtigsten Rechenschritte für die Rechnung auf den ganzen Wafer erklären?

29.03.2016, 21:03

HAL 9000

Auf diesen Beitrag antworten »

Nochmal übersichtsmäßig die Daten:

$\begin{align*} a=6.605~mm \end{align*}$ ... Strukturlänge (mit Zusatzrand)
$\begin{align*} b=3.205~mm \end{align*}$ ... Strukturbreite (mit Zusatzrand)
$\begin{align*} d = 0.1~mm \end{align*}$ ... Breite Zusatzrand
$\begin{align*} r = 45~mm \end{align*}$ ... Kreisradius, innerhalb dessen die Strukturen liegen müssen

Zunächst Variante 4, da liegen die Strukturen sowohl an x- als auch y-Koordinatenachse an. In Zeile $\begin{align*} k \end{align*}$ , beginnend mit Zeile 1 anliegend an der x-Achse, mögen genau $\begin{align*} n_k \end{align*}$ Strukturen im ersten Quadranten liegen. Dann muss nach Pythagoras gelten

$\begin{align*} (n_ka-d)^2 + (kb-d)^2 \leq r^2\quad (*) \end{align*}$ , umgestellt $\begin{align*} n_k \leq \frac{1}{a}\left( \sqrt{r^2 - (kb-d)^2} + d \right) \end{align*}$ ,

also $\begin{align*} n_k = \left\lfloor \frac{1}{a}\left( \sqrt{r^2 - (kb-d)^2} + d \right) \right\rfloor \end{align*}$ . Das ganze für $\begin{align*} k=1,2,\ldots \end{align*}$ solange wie $\begin{align*} r^2 - (kb-d)^2 > 0 \end{align*}$ gilt.

$\begin{align*} \sum_{k=1}^{k_e} n_k \end{align*}$ ist dann die Anzahl der Strukturen im ersten Quadrant, $\begin{align*} 4\cdot \sum_{k=1}^{k_e} n_k \end{align*}$ dann für den gesamten Kreiswafer. Kannst du nun ausrechnen: zu Fuß, mit einem Skript, Excel, CAS, ... , wie du willst.

--------------------

Bei den Varianten 1..3 ist nun das Strukturgebilde versetzt zu betrachten: Um $\begin{align*} \frac{a}{2} \end{align*}$ in x-Richtung und/oder $\begin{align*} \frac{b}{2} \end{align*}$ in y-Richtung, je nach Fall. Das hat natürlich Einfluss auf die Pythagoras-(Un)gleichung, die ist jeweils zu modifizieren. Wenn dir (*) nicht klar ist, mach dir eine passende Skizze.

30.03.2016, 16:53

HAL 9000

Auf diesen Beitrag antworten »

Für Freunde der Sprache (!) Postscript noch ein kleines Bildchen vom fertigen Wafer:

[attach]41247[/attach]

Neue Frage »

Antworten »

Maximale Anzahl von Rechtecken in Kreis

Verwandte Themen