Wyniki wyszukiwania - BazTech

1

Harmonogramowanie zadań w warunkach zakłóceń

Kalinowski K.

Inżynieria Maszyn

|

2009

|

R. 14, z. 3

49-67

PL

W artykule przedstawiono problematykę harmonogramowania i reharmonogramowania produkcji w systemach wytwórczych charakteryzujących się dyskretnym przepływem produkcji. Proponowane rozwiązania dedykowane są systemom, w których realizowana jest zmienna produkcja wieloasortymentowa. Omówiono przyjęty model systemu ze szczegółowym opisem zleceń produkcyjnych oraz zasobów. Zaprezentowano metodę zapisu wielowariantowego procesu technologicznego, użytecznego w sytuacji, gdy realizacja zlecenia produkcyjnego jest możliwa z zastosowaniem różnych technologii, zasobów, narzędzi lub oprzyrządowania. Pokazano sposób wyboru wariantu operacji w zależności od przyjętych kryteriów. Wielowariantowy proces technologiczny jest szczególnie istotny podczas reharmonogramowania produkcji - pozwala w krótkim czasie wyznaczyć alternatywny sposób realizacji zleceń w przypadku wystąpienia zakłóceń. W dalszej części pracy omówiono strategie harmonogramowania dla zleceń oraz procedurę tworzenia harmonogramu. Przedstawiono również podstawowe wskaźniki stosowane przy ocenie rozwiązań, zarówno w procesie harmonogramowania jak i reharmonogramowania produkcji oraz metodę oceny wielokryterialnej używaną przy wyborze harmonogramu do realizacji. Przybliżono techniki stosowane przy adaptacji harmonogramów do zmiennych warunków produkcyjnych. Zaprezentowano również system harmonogramowania i reharmonogramowania produkcji KbRS, który opracowano na podstawie rozwijanej metodyki.

EN

This article presents issues of production scheduling and rescheduling in manufacturing systems characterized by discrete production flow. The proposed solution is dedicated for enterprises that realize multi-assortment and changeable production. The adopted model of the system, a description of production orders and manufacturing resources is discussed. The model of multivariant technological process that enables to realize production orders with alternatives is presented. The objective for selecting a variant of operation depending on the adopted criteria is also considered. It is very important at the production rescheduling stage as well - it allows, in the short term, to designate an alternative method of production order execution in case of disruption. Next, the strategies for scheduling, basic factors used in assessing possible schedules and the method of multicriterial schedule evaluation are discussed in this work. The techniques of rescheduling applied for schedule adaptation to changing production conditions are described. The production scheduling and rescheduling system (KbRS) is shown as an implementation of developed methodology.

2

Heurystyczny algorytm szeregowania zadań w systemie maszyn równoległych z równoczesnym rozdziałem zasobów

Buchalski Z.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2005

|

T. 9, z. 1-2

37-45

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki eksperymentów obliczeniowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed numerical experiment for basis of proposed heuristic algorithm are presented.

3

Metoda tabu w problemach szeregowania zadań produkcyjnych.

Nowicki E.

Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Monografie

|

1999

|

Vol. 101, nr 27

3-252

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.