Elastyczny problem gniazdowy

$\mathcal{J} = \{1,2,...,n\}$ – zbiór zadań

$\mathcal{M} = \{1,2,...,m\}$ – zbiór maszyn

$\mathcal{O} = \{1,2,...,o\}$ – zbiór operacji

Zadanie to ciąg operacji występujących zgodnie z porządkiem technologicznym. Zbiór operacji $\mathcal{O}$ można więc rozbić na ciągi odpowiadające zadaniom.

Operacja może być wykonywana na pewnym podzbiorze maszyn. Musi natomiast być wykonana bez przerywania na jednej z nich, a czas jej wykonania zależy od wydajności przydzielonej maszyny.

Elastyczny problem gniazdowy

• przydzielić operacje do maszyn
• wyznaczyć kolejność wykonywania operacji na maszynach (zgodnie z relacją porządku technologicznego)
• zoptymalizować pewne kryterium

$\mathcal{M}^i \in \mathcal{M}\ \ (i \in \mathcal{O})$ – zbiór maszyn na których można wykonać operację $i$

$\mu_i \in \mathcal{M}^i\ (i \in \mathcal{O})$ – maszyna przydzielona do operacji $i$

$\mathcal{O}^l = \{i \in \mathcal{O} : \mu_i=l\}$ – zbiór operacji przydzielonych do maszyny $l$

$\pi_l$ – pewna permutacja elementów ze zbioru $\mathcal{O}^l$

$\Pi_l$ – zbiór wszystkich permutacji elementów $\mathcal{O}^l$

$\pi = (\pi_1, \pi_2, ..., \pi_m)$ – kolejność wykonywania operacji na maszynach (konkatenacja ciągów $\pi_i \in \Pi_i$ dla $i \in \mathcal{M}$)

$\Phi$ – zbiór wszystkich takich $\pi$

$\pi \in \Phi$ jednoznacznie określa przydział operacji do maszyn, a także kolejność wykonywania operacji.

Rozwiązanie $\pi \in \Phi$ może być reprezentowane przez graf skierowany $\mathcal{H}(\pi) = (\mathcal{V}, \mathcal{E}(\pi))$.

Wierzchołkami grafu $\mathcal{H}(\pi)$ są operacje ($\mathcal{V} = \mathcal{O}$). Waga wierzchołka $i$ jest równa $p_{v,\mu_i}$, czyli czasowi wykonania operacji $v$ na maszynie $\mu_i$.

Zbiór łuków grafu jest sumą zbiorów $\mathcal{E}(\pi) = \mathcal{R} \cup \mathcal{K}(\pi)$.

$\mathcal{R} = \bigcup\limits_{j=1}^n \bigcup\limits_{i=1}^{o_j-1} \{\ (\ \hat{j}_i,\ \hat{j}_{i+1}\ )\ \}\ $

gdzie $o_j$ jest liczbą operacji zadania $j$, a $\hat{j} $ jest ciągiem operacji zadania $j$ w porządku technologicznym. Zawiera łuki reprezentujące porządek technologiczny.

$\mathcal{K}(\pi) = \bigcup\limits_{k=1}^m \bigcup\limits_{i=1}^{|\mathcal{O}^k|-1} \{\ (\ \pi_k(i),\ \pi_k(i+1)\ )\ \}$

Zawiera łuki łączące operacje wykonywane na tej samej maszynie, a zatem reprezentujące kolejność $\pi_k$ operacji na maszynie $k$ (dla $k \in \mathcal{M} $)

Cykliczny elastyczny problem gniazdowy

Ustalony zbiór zadań MPS (ang. minimal part set) jest wykonywany wielokrotnie. Zakładamy, że w każdym z MPS-ów, na każdej maszynie operacje są wykonywane w takiej samej kolejności, zatem kolejność wykonywania operacji może być reprezentowana przez $\pi \in \Phi$ dla pierwszego MPS-a.

Harmonogram nazywiemy cyklicznym jeśli każda operacja jest kolejno wykonywana po upływie czasu cyklu.

Dla ustalonego $\pi \in \Phi$, niech $S^k_i$ oznacza termin rozpoczęcia wykonywania operacji $i$ na maszynie $\mu_i$ w $k$-tym cyklu. Jeśli harmonogram jest cykliczny, wtedy

$S^k_{\pi(i)} = S^1_{\pi(i)} + (k-1)\cdot T(\pi),$

gdzie $T(\pi)$ jest czasem cyklu i zależy od $\pi$.

Graf cykliczny

Dla ustalonego rozwiązania $\pi \in \Phi$ niech $\mathcal{H}(\pi) = (\mathcal{V}, \mathcal{E}(\pi))$ będzie grafem reprezentującym to rozwiązanie.

Niech $\mathcal{H}^l(\pi) = (\mathcal{V}^l, \mathcal{E}^l(\pi))$ będzie grafem reprezentującym rozwiązanie $\pi$ dla $l$-tego MPS-a ($l = 1, 2, ..., m+1$).

Zbiór wierzchołków

$\mathcal{V}^l = \{v+(l-1)\cdot o : v \in \mathcal{V} \}$.

Zbiór łuków

$\mathcal{E}^l = \{ (v,u) : (u+(l-1)\cdot o, v+(l-1)\cdot o) \in \mathcal{E}\}$.

Zdefiniujemy jeszcze pomocnicze podzbiory zbioru $\mathcal{V}^l$:

$\mathcal{A}^l = \{v\in\mathcal{V}^l : v=\pi_j(1)+(l-1)\cdot o \land j \in \mathcal{M}\}$,

który zawiera pierwsze operacje wykonywane przez poszczególne maszyny w $l$-tym MPS-ie oraz

$\mathcal{B}^l = \{v\in\mathcal{V}^l : v=\pi_j(n_j)+(l-1)\cdot o \land j \in \mathcal{M}\}$,

który zawiera ostatnie operacje.

Grafem cyklicznym, dla ustalonej permutacji $\pi\in\Phi$, nazwiemy graf $\mathcal{G}^\oplus = (\mathcal{V}^\oplus, \mathcal{E}^\oplus(\pi))$.

Zbiór wierzchołków grafu $\mathcal{G}^\oplus$ definiujemy jako

$\mathcal{V}^\oplus = \mathcal{V}^1\ \cup\ \mathcal{V}^2\ \cup\ ...\ \cup\ \mathcal{V}^{m+1}$

Zbiór łuków grafu $\mathcal{G}^\oplus$ definiujemy jako

$\mathcal{E}^\oplus(\pi) = \mathcal{E}^1(\pi)\cup\mathcal{E}^2(\pi)\cup\ ...\ \cup\mathcal{E}^{m+1}(\pi)\cup\mathcal{W}$,

gdzie zbiór $\mathcal{W}$ zawiera łuki łączące ostatnią operację określonego MPS-a z pierwszą operacją kolejnego MPS-a wykonywaną na tej samej maszynie:

$\mathcal{W} = \{(u,v)\in\mathcal{B}^l\times\mathcal{A}^{l+1} :\mu_u=\mu_v,\ l=1,2,...,m\}$.

Wyzanaczanie minimalnego czasu cyklu dla danego rozwiązania problemu CFJS

Zadanie polega na wyznaczeniu minimalnego czasu cyklu dla ustalonej kolejności wykonywania operacji na maszynach ($\pi \in \Phi$).

Niech $a \in \mathcal{A}^1$ będzię wierzchołkiem odpowiadającym pierwszej operacji wykonywanej na pewnej maszynie w pierwszym MPS-ie. Poprzez $a^l$ oznaczmy wierzchołek odpowiadający tej samej operacji wykonywaną w $l$-tym MPS-ie. Zatem z definicji grafu cyklicznego $a^l = a+(l-1)\cdot o$.

Niech $L^l(a,a^l)$ będzie długością najdłuższej drogi w grafie $\mathcal{G}^\oplus(\pi)$ z wierzchołka $a$ do wierzchołka $a^l$ (dla $l = 2,3,...,m+1$).

Niech $\lambda$ będzie macierzą o wymiarach $m\times m$. Elementy tej macierzy definiujemy następująco:

$\lambda_{a,l} = L^{l+1}(a,a^{l+1})\ /\ l$,

gdzie, $a\in \mathcal{A}^1$, oraz $l = 1,2,...,m$.

Wartość maksymalnego elementu macierzy $\lambda$ oznaczmy:

\[\begin{aligned} \Lambda^*(\pi) = \max\limits_{\upsilon \in A^1} \max\limits_{2 \leq l \leq \eta} \left\{ \lambda_{\upsilon, l}\right\}. \end{aligned} \]

Dla ustalonej permutacji $\pi \in \Phi$ wartość $\Lambda^*(\pi)$ jest szukanym minimalnym czasem cyklu.