Metoda tabu w problemach szeregowania zadań produkcyjnych.

• Autorzy: Nowicki E.

Warianty tytułu

EN

Tabu search method in job scheduling problems.

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawia się metodologię projektowania i konstrukcji efektywnych algorytmów popraw dla obszernej klasy problemów szeregowania zadań produkcyjnych o średnim i dużym rozmiarze, bazując na ogólnym szkielecie techniki tabu i wykorzystując przy tym szereg nowych metod. Skuteczność tych metod została potwierdzona dowiedzionymi własnościami teoretycznymi i wynikami wszechstronnych badań testowych. W pracy można wyodrębnić dwie części. W pierwszej części prezentuje się poszczególne elementy techniki tabu, zwracając głównie uwagę na nowe metody, takie jak; konstrukcja pamięci krótkoterminowej opartej na oryginalnym pojęciu atrybutów rozwiązania i ruchu, strategia przeglądania sąsiedztw bazująca na pojęciu reprezentantów oraz techniki intensyfikacji i dywersyfikacji poszukiwań wykorzystując tzw. metodę skoku powrotnego. Następnie proponuje się reprezentacje rozwiązań dla wielu problemów szeregowania, określa ruchy, ich własności oraz metodologię konstrukcji odpowiednich dla nich atrybutów wraz z przedstawieniem efektywnych czasowo metod określających status danego ruchu. Wszystkie te elementy połączone w całość pozwalają na zbudowanie ogólnego oryginalnego schematu poszukiwań, który umożliwia projektowanie efektywnych algorytmów popraw z punktu widzenia jakości produkowanych rozwiązań oraz czasu obliczeń. W drugiej części pracy, korzystając z ogólnego narzędzia przedstawionego w części pierwszej, podaje szczegółową metodologię projektowania algorytmów popraw wraz z konkretnymi algorytmami dla poszczególnych grup problemów szeregowania zadań produkcyjnych. Przy wyborze tych grup kierowano się przede wszystkim ich praktyczną przydatnością oraz aktualnym stanem badań. W szczególności skupiono się na klasycznych zagadnieniach, do których należą problem przepływowy, gniazdowy i otwarty. Następnie rozważono problemy przepływowe z dodatkowymi ograniczeniami, takimi, jak: limitowana liczba palet oraz ograniczona pojemność buforów. Z kolei badano problem gniazdowy z maszynami wielofunkcyjnymi oraz niezerowymi czasami transportu i przezbrojeń. Na koniec skupiono się na problemie gniazdowym z operacjami wielomaszynowymi. Dla każdej grupy problemów podano oryginalne modele grafowe szczególnie przydatne przy konstrukcji algorytmów popraw, wykazano ich własności, skonstruowano sąsiedztwa oraz podano efektywne czasowe metody ich przeglądania. Dodatkowo w celu generowania rozwiązań początkowych zaproponowano szereg nowych algorytmów konstrukcyjnych; dal niektórych z nich oprócz analizy eksperymentalnej przeprowadzono także analizę najgorszego przypadku. Dla wszystkich analizowanych grup zagadnień przeprowadzono badania testowe algorytmów popraw bazujących na zaprezentowanych metodach. Do badań wykorzystano szereg przykładów adekwatnych dla danej grupy zagadnień i powszechnie wykorzystanych w literaturze do badania każdej nowej generacji algorytmów. Otrzymane wyniki wskazują na znaczną przewagę proponowanych tutaj algorytmów w stosunku do najlepszych algorytmów stosowanych dotychczas i to zarówno w aspekcie jakości produkowanych rozwiązań, jak i czasu obliczeń. W przypadku problemów, dla których są znane algorytmy popraw, proponowane algorytmy produkują rozwiązania od kilku do kilkunastu procent lepsze, w czasie od kilkunastu do kilkudziesięciu razy krótszym na komputerach o porównywalnej mocy obliczeniowej. Z kolei dla problemów, dla których nie ma w literaturze algorytmów popraw, proponowane algorytmy poprawiają rozwiązania dostarczane przez algorytmy konstrukcyjne, od kilkunastu do kilkudziesięciu procent w sensie wartości funkcji celu. Do otrzymania takich rozwiązań potrzebują one od kilku sekund do kilkunastu minut (w zależności od typu problemu i rozmiaru badanych instalacji) czasu pracy komputera klasy PC.

EN

The book presents the methodology of designing and constructing efficient local search algorithms recommended for medium- and large-size instances of a broad class pf job scheduling problems. The methodology is based on the general tabu search scheme extended next in the creative way by introduced new methods. The efficiency f the proposed methods has been confirmed by their theoretical properties as well as by the wide, careful experimental research. The books consists principally of two parts. The first part presents details of the tabu search technique, taking chiefly account of new original methods: short-term memory based on the notion of attributes of solution and move, strategy of the single neighbourhood search with the notion of representatives, intensification and diversification strategies with the use of back jumps on the search trajectory. After the introduction to extended tabu search approach, there have been proposed combinatorial representations of solutions for those scheduling problems that have been considered the most frequent. For these representations there have been presented moves, their characteristic properties, methodology of constructing suitable attributes, and efficient algorithms for tabu status examination. All these elements composed properly allow us to introduce a new general and original scheme of the local search which, in order, allow us to design solution algorithms efficient from two points of view: the quality of generated solutions and algorithm's running time. In the second part of the book, by applying the general tool introduced and developed in the former part, there has been presented detailed methodology of designing local search algorithms as well as practical implementations of such algorithms constructed for various groups of job scheduling problems. The selection of problems considered has been made taking attention of their practical applicability and the current state of scheduling research. In particular, consideration have been focused on classic versions of scheduling problems known as flow-, job- and open-shop. Further, these basic models have been extended by adding some real-life constraints. Precisely, the flow-shop problem has been analysed in the context of the limited number of pallets and the limited size of intermediate machine buffers; the job-shop problem has been considered in the in the context of multipurpose machines, transport times and set-up times; operations performed on multiple have also been considered. For each group problems, original models (very useful in the construction of local search algorithms) have been shown, the peculiar properties have been proved, the neighbourhoods constructed and efficient search methods given. Additionally, for the aim of generating starting solutions, there have been proposed several new constructive algorithms, for which experimental analyses as well as the worst case analyses have been carried out. Computer tests have been carried out for all improving algorithms designed for analysed groups of problems. Tests have been performed with the use of many common benchmark test instances known in the literature, adequate for each group. The results obtained show the superiority of the proposed algorithms over the best known ones taking account of both quality of generated solutions as well as running time. In the case of problems for which improving methods are known, the algorithms proposed provide solutions that are better by a few to over ten per cent at a time from 10 to 100 times shorter as compared to computers of comparable speed. For problems for which there are no improving algorithms in the literature, the algorithms designed improve solutions obtained from constructive algorithms in the range of a dozen to several dozen per cent in terms of the goal function value. In order to obtained such solutions they need from a few seconds to a dozen or so minutes (depending on the type of problem and instance size) of a PC running time.

Słowa kluczowe

PL

dyskretny system produkcyjny; szeregowanie; algorytm popraw; metoda tabu

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Monografie
• Rocznik: 1999
• Tom: Vol. 101, nr 27
• Strony: 3--252
• Opis fizyczny: Bibliogr. 206 poz., rys. 28, tab. 19

Twórcy

autor

Nowicki E.

• Instytut Cybernetyki Technicznej Politechniki Wrocławskiej, Janiszewskiego 1/17, 50-372 Wrocław