Szczegóły publikacji
Opis bibliograficzny
Heurystyczny algorytm szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi — Heuristic algorithm of tasks scheduling for flexible assembly lines with parallel machines / Marek MAGIERA // Automatyka : półrocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica w Krakowie ; ISSN 1429-3447. — 2003 — t. 7 z. 1–2, s. 157–163. — Bibliogr. s. 163, Streszcz., Summ. — XV [piętnaste] międzynarodowe sympozjum „Zastosowania teorii systemów” : Zakopane'2003
Autor
Dane bibliometryczne
| ID BaDAP | 14305 |
|---|---|
| Data dodania do BaDAP | 2003-10-22 |
| Rok publikacji | 2003 |
| Typ publikacji | referat w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Automatyka/Automatics |
Abstract
The paper presents relaxation heuristic of tasks scheduling for flexible assembly lines with parallel machines and with intermediate buffers. Each assembly stage consists of one or several parallel machines. The flow is unidirectional. Each product loads no more than one machine of the assembly stage. The assembly sequences and the assignment of operations to assembly stages with limited working space are the starting point of the described heuristic. Linear mathematical models for tasks scheduling are used in the method. The schedule is divided into time intervals in the algorithm. Approximation to time criterion is used. A linear relaxation - based heuristic is created to reduce the CPU time required for mixed integer programming. The heuristic starts from the optimal solution of a linear relaxation of the mixed integer program. The rules of rounding of fractions to integers and the procedures of modification and verification of constructed heuristic in the following steps of algorithm are described. Results of computational experiments with the proposed heuristic algorithm are included. The computer processing times for heuristic and the algorithm with integer decision variables (optimal solution) are compared.
Streszczenie
W artykule przedstawiony został heurystyczny algorytm szeregowania operacji dla elastycznych linii montażowych (ELM) z maszynami równoległymi i z buforami międzystadialnymi. W takim wielostadialnym systemie przepływowym operacje wykonywane są na kolejnych maszynach, należących do poszczególnych stadiów - zbiorów maszyn pracujących równolegle. Produkt może pomijać niektóre stadia. W każdym ze stadiów produkt może obciążyć co najwyżej jedną maszynę, spośród maszyn pracujących równolegle. W algorytmie wykorzystany został model matematyczny szeregowania operacji dla ELM z maszynami równoległymi, w którym przydzielane są operacje montażowe do maszyn. W tym liniowym modelu (zawierającym binarne zmienne decyzyjne) zastosowana została funkcja, dzięki której można aproksymować minimalizację długości uszeregowania. Opracowana heurystyka służy do rozwiązania zadania sformułowanego w postaci wymienionego modelu matematycznego, w którym usunięte zostały warunki całkowitoliczbowości zmiennych decyzyjnych. Jest to więc heurystyka relaksacyjna. Dzięki zastosowaniu relaksacji zmiennych, zadanie szeregowania operacji rozwiązywane jest w czasie znacznie krótszym niż w przypadku rozwiązywania zadania programowania całkowitoliczbowego. Opisane są zasady zaokrąglania uzyskiwanych ułamkowych wyników do wartości całkowitych oraz reguły modyfikacji i weryfikacji budowanego w kolejnych iteracjach harmonogramu. Algorytm heurystyczny został przetestowany. Uzyskiwane rozwiązania heurystyczne porównane zostały z rozwiązaniami optymalnymi. W artykule zamieszczone są wyniki przeprowadzonych eksperymentów obliczeniowych.