Pewien algorytm konstrukcyjny dla problemu gniazdowego z operacjami wielomaszynowymi nierównocześnie wykorzystującymi maszyny

• Autorzy: Nowicki E. , Makuchowski M.

Warianty tytułu

EN

Some constructional algorithm for job-shop multimachine operations problem with non-simultaneously used machines

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważa się uogólniony problem gniazdowy z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Uogólnienie polega na zamodelowaniu operacji wielomaszynowych nierównocześnie wykorzystujących maszyny. Problem jest NP-trudny, co uzasadnia stosowanie algorytmów heurystycznych. W pracy przedstawia się pewien konstrukcyjny algorytm oparty na technice wstawień. Dodatkowo prezentuje się wyniki eksperymentów numerycznych oraz porównania z rezultatami dostarczanymi przez najlepsze znane z literatury algorytmy konstrukcyjne.

EN

The paper deals with the general job-shop problem of finding a minimum makespan. The generalization based on models multimachine operations with non-simultaneously used machines. The problem belongs to class NP-hard problems what justifies searching for heuristic algorithms. Some constructional algorithm is presented. Computational experiments are given and compared with the result yielded by the best algorithms discusses in the literature.

Słowa kluczowe

PL

algorytm typu wstaw; algorytmy konstrukcyjne; algorytmy heurystyczne

EN

algorithms; constructional algorithm; heuristic algorithms

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

Twórcy

autor

Nowicki E.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

autor

Makuchowski M.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Drozdowski M.: Scheduling multiprocessor task - An Overview. European Journal Operational Research, 94, 1996, 215-230
• [2] Grabowski J.: Sformułowanie i rozwiązanie zagadnienia kolejnościowego z równoległym wykorzystaniem maszyn. Archiwum Automatyki i Telemechaniki, 1978, 91-113
• [3] Kramer A.: Scheduling Multiprocessor Tasks on Dedicated Processors. Ph.D.-Thesis, Fachbereich Mathematik/Infomatik, Universitat Osnabruck 1995
• [4] Makuchowski M, Nowicki E.: Modele permutacyjno-grafowe problemów gniazdowych z operacjami wielomaszynowymi. Modelowanie i optymalizacja, metody i zastosowania. Warszawa, Akademicka Oficyna Wydawnicza EXIT 2002, VI1-V24
• [5] Makuchowski M., Nowicki E.: Operacje wielomaszynowe z nierównoczesnym użyciem maszyn w problemie gniazdowym. Komputerowo integrowane zarządzanie, tom II. Warszawa, WNT 2002, 114-123
• [6] Makuchowski M., Nowicki E.: Algorytm tabu dla problemu gniazdowego z operacjami wielomaszynowymi nierównocześnie wykorzystującymi maszyny. ZN Politechniki Śląskiej Automatyka, 134, Gliwice 2002, 287-297
• [7] Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Wrocław, Oficyna Wydawnicza Politechniki Wrocławskiej 1999
• [8] Pinedo M.: Scheduling: Theory, Algorithms, and Systems. Englewood Cliffs, Prentice Hall 1995
• [9] Sawik T.: Planowanie i sterowanie produkcji w elastycznych systemach montażowych. Warszawa, WNT 1996