Simple assembly line balancing

Simple assembly line balancing – podstawowy problem decyzyjny w planowaniu konfiguracji w swojej najbardziej podstawowej wersji. Spośród rodziny problemów Assembly Line Balancing jest on najlepiej znany i najlepiej zbadany. Mimo iż może on być zbyt uproszczony by oddać złożoność rzeczywistych problemów balansowania, to uchwytuje on główne aspekty. Wiele odmian bardziej ogólnych problemów są bezpośrednimi rozszerzeniami SALB lub przynajmniej wymagają rozwiązania problemu SALB w jakiejś postaci.

Opis problemu

Linia produkcyjna (assembly line) składa się z $m$ stacji roboczych (workstations) $1,\dots ,m$ ustawionych wzdłuż przenośnika taśmowego. Materiały (workpieces) są dokładane na taśmę po czym są przesuwane od stanowiska do stanowiska aż osiągną koniec linii. Pewien zbiór operacji jest wykonywanych na każdym materiale, który dochodzi do określonej stacji roboczej co odstęp czasu określony jako czas cyklu (cycle time).

W ogólności LBP polega na rozłożeniu zadań, które trzeba wykonać na materiale pomiędzy wszystkie stacje z uwzględnieniem pewnych celów. W tym celu praca którą należy wykonać na każdym materiale jest podzielona na zbiór $V={1,\dots ,n}$ elementarnych operacji nazwanych zadaniami (tasks). Zadania są niepodzielnymi jednostkami pracy i każdemu zadaniu jest przypisany czas wykonywania $t_{j}.$ W związku z technologicznymi i organizacyjnymi wymaganiami, zadania muszą być w określonej kolejności (precedence constraints).

Parametry wejściowe instancji SALP mogą być przedstawione za pomocą grafu pierwszeństwa (precedence graph). Ten graf składa się z węzłów odpowiadających zadaniom, wagi węzłów odpowiadają czasowi wykonania tych zadań, a krawędzie odpowiadają pierwszeństwu zadań.

Poprawne zbalansowanie linii, tj. przypisanie zadań do stacji, musi zapewniać, że pierwszeństwo zadań jest zachowane. Zbiór zadań przypisanych do stacji $k$ oznaczany jest jako $S_{k}$ określa obciążenie stacji (work load), suma czasów zadań $t(S_{k})$ nazywana jest czasem stacji (station time).

t(S_{k})={\sum _{j\in S_{k}}t_{j}}.

SALB zakłada że czas cyklu wszystkich stacji jest równe wartości c. Wszystkie stacje zaczynają swoje operacje w tym samym czasie oraz przekazują materiały w tym samym tempie. Czas stacji nie może być większy od czasu cyklu, ale może być wtedy stacja $k$ jest bezproduktywna przez pewien czas (idle time) równy $c-t(S_{k})$ w każdym cyklu.

Dla przykładu poprawne zbalansowanie dla zadań przedstawionych na powyższym rysunku dla $c=11$ i $m=5$ może wyglądać następująco $S_{1}=\{1,3\},$ $S_{2}=\{2,4\},$ $S_{3}=\{5,6\},$ $S_{4}=\{7,8\}$ i $S_{5}=\{9\}.$

Bibliografia

A classification of assembly line balancing problems. assembly-line-balancing.de. [zarchiwizowane z tego adresu (2011-05-17)]. (ang.), dostęp: 2009-03-13