Makespan FPS – Emotin

Harmonogramowanie produkcji z użyciem algorytmów sztucznej inteligencji w modelu FPS (Flow Permutation Shop)

Streszczenie

Artykuł ma na celu pokazać możliwości zastosowania wybranych algorytmów sztucznej inteligencji do tworzenia harmonogramów produkcji. W pierwszej części przedstawiono model matematyczny oraz zademonstrowano implementację modelu w arkuszu kalkulacyjnym Excel. W drugiej części zastosowano algorytm genetyczny pozwalający konstruować harmonogramy bliskie optymalnym.

1. Podstawowe pojęcia

2. Model matematyczny

Model matematyczny dla $F^*||C_{\max}$ (Flow Permutation Shop):
$n$ – liczba zamówień, $m$ – liczba maszyn.

$\begin{tabular}{cccl} $\min C_{\max}$ &&&\\ $C_{\max}$ & $\geq$ & $S_{m,j} + p_{m,j}$ & $j=1,\ldots,n,$\\ $S_{i+1,j}$ & $\geq$ & $S_{i,j} + p_{i,j}$ & $j=1,\ldots,n,$, $i=1,\ldots,m-1,$\\ $S_{1,i}$ & $\geq$ & 0 & $j=1,\ldots,n,$\\ $S_{i,k}$ & $\geq$ & $S_{i,j} + p_{i,j},$ &\\ \textrm{lub}&&&\\ $S_{i,j}$ & $\geq$ & $S_{i,k} + p_{i,k}$ &$i=1,\ldots,m,$, $j=1,\ldots,n-1,$, $k=j+1,\ldots,n.$\\ \end{tabular}$

Stosując zmienne zero-jedynkowe model ten możemy zapisać równoważnie jako

$\begin{tabular}{cccl} $\min C_{\max}$ &&&\\ $C_{\max}$ & $\geq$ & $S_{m,j} + p_{m,j}$ & $j=1,\ldots,n,$\\ $S_{i+1,j}$ & $\geq$ & $S_{i,j} + p_{i,j}$ & $j=1,\ldots,n,$, $i=1,\ldots,m-1,$\\ $S_{1,i}$ & $\geq$ & 0 & $j=1,\ldots,n,$\\ $M z_{j,k}$ & $\geq$ & $S_{i,j} + p_{i,j} - S_{i,k},$ & $i=1,\ldots,m,$, $j=1,\ldots,n-1,$, $k=j+1,\ldots,n,$\\ $M(1-z_{j,k})$ & $\geq$ & $S_{i,k} + p_{i,k} - S_{i,k}$ &$i=1,\ldots,m,$, $j=1,\ldots,n-1,$, $k=j+1,\ldots,n,$ \end{tabular}$

gdzie $M\gg 0$ oraz
$z_{j,k}=\left\{ \begin{array}{ll} 1& \textrm{zlecenie } j \textrm{ poprzedza } k,\\ 0 & \textrm{w p. w.} \end{array}\right.$

3. Algorytmy genetyczne

4. Zastosowanie algorytmu genetycznego do harmonogramowania produkcji

5. Literatura
[1] Program akademicki Columbia University LEKIN
[2] Google Optimization Tools Jop Shop Problem
[3] The Job-Shop Problem, the disjunctive model and benchmark data
[4] Mathematical models for job-shop scheduling problems with routing and process plan flexibility