Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: constraint logie programming

Sortuj według:

Ogranicz wyniki do:

Porównanie metod optymalizacji procesów dyskretnych na przykładzie uogólnionego zadania przydziału

Pieńkosz K.

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

1999

T. 3, z. 1

281-287

W pracy rozpatrywane są różne podejścia do rozwiązywania uogólnionego zadania przydziału w sposób dokładny. W uogólnionym zadaniu przydziału rozpatruje się zbiór zadań do wykonania oraz zbiór zasobów (maszyn) o ograniczonych dostępnościach. Każdemu zadaniu należy przydzielić jeden z wybranych zasobów rezerwując wymaganą ilość czasu jego dostępności. Celem jest takie przydzielenie zadań do zasobów, aby nie przekroczyć dostępności poszczególnych zasobów i minimalizować (bądź maksymalizować) sumaryczne koszty przydziału. Przedstawione zagadnienie jest problemem 7VP-trudnym i nawet przy umiarkowanej liczbie zadań i zasobów pojawiają się trudności z jego rozwiązywaniem. Rozwiązując uogólnione zadanie przydziału badano efektywność stosunkowo nowego podejścia optymalizacji dyskretnej jakim jest programowanie w logice ograniczeń (ang. constraint logie programming). Użyto do tego celu oprogramowania firmy ILOG. Otrzymane rezultaty i czasy rozwiązywania porównano z klasycznymi metodami optymalizacji, tzn. specjalizowaną metodą podziału i oszacowań oraz całkowitoliczbo-wym programowaniem liniowym. Eksperymenty obliczeniowe i porównania metod zostały przeprowadzone na danych zaczerpniętych z literatury.

Different approaches to the exact solution of the generalised assignment problem are considered in the paper. The generalised assignment problem is the problem of finding an assignment of a set of capacity constrained resources (machines) to a set of jobs such that each job is assigned to exactly one resource. The objective is to minimise (or maximise) the total costs of assignment subject to the capacities of the resources. The problem is known to be NP-hard, and it is hard form a computational point of view even for a moderate number of jobs and resources. The efficiency of the constraint logic programming which is a relatively new approach to discrete optimisation has been examined by solving the generalised assignment problem. ILOG software has been applied for these experiments. Results of computations have been compared with the classical optimisation methods, i.e. a specialised branch and bound method and integer programming. Computational experiments and comparison has been performed on the test problems taken from the literature.