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

• Autorzy: Pieńkosz K.

Warianty tytułu

EN

A comparison of the discrete optimisation methods in the case of the generalised assignment problem

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

programowanie w logice ograniczeń; procesy dyskretne

EN

constraint logie programming

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 1999
• Tom: T. 3, z. 1
• Strony: 281--287
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Pieńkosz K.

• Instytut Automatyki i Informatyki Stosowanej Politechniki Warszawskiej