Heurystyczny algorytm szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi

• Autorzy: Magiera M.

Warianty tytułu

EN

Heuristic algorithm of tasks scheduling for flexible assembly lines with parallel machines

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

elastyczne linie montażowe; maszyny równoległe; heurystyka relaksacyjna

EN

flexible assembly lines; parallel machines; relaxation heuristic

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 157--163
• Opis fizyczny: Bibliogr. 6 poz., tab.

Twórcy

autor

Magiera M.

• Wydział Zarządzania, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Fourer R., Gay D., Kemighan B.: AMPL - A Modelling Language for Mathematical Programming. Boyd & Fraser Publishing Company 1993
• [2] Magiera M.: Analiza porównawcza dwóch dwupoziomowych metod sterowania przepływem produktów przez elastyczną linią montażową z maszynami równoległymi. Półrocznik AGH Automatyka, t. 7, z. 1-3, 2003
• [3] Santos D.L., Hunsucker J.L., Deal D.E.: Global lower bounds for flow shops with multiple processors. European Journal of Operational Research, vol. 80, 1995, 112-120
• [4] Sawik T.: Planowanie i sterowanie produkcji w elastycznych systemach montażowych. Warszawa, WNT 1996
• [5] Sawik T.: Badania operacyjne dla inżynierów zarządzania. Kraków, Wyd. AGH 1998
• [6] Schrage L., Cunningham K.: LINGO, Optimization Modelling Language. Chicago, LINDO Systems Inc. 1991