Wyniki wyszukiwania - BazTech

1

Bin packing with restricted item fragmentation

Pieńkosz K.

Control and Cybernetics

|

2014

|

Vol. 43, no. 4

547--556

EN

In this paper we consider a generalization of the bin packing problem, in which it is permitted to fragment the items while packing them into bins. There is, however, a restriction that the size of each piece of the fragmented item cannot be smaller than a given parameter β An interesting aspect of such a model is that if β= 0, then the problem can be easily solved optimally. If β is large enough, meaning, in fact, that the fragmentation is not allowed, we get the classical bin packing problem, which is NP-hard in the strong sense. We present approximation algorithms for solving the problem and analyse their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented.

2

Auction Models Supporting End-to-End Connection Trading

Kołtyś K., Pieńkosz K., Toczyłowski E.

Journal of Telecommunications and Information Technology

|

2012

|

nr 2

55-62

EN

The paper concerns bandwidth allocation problem on the telecommunication market where there are many sellers and buyers. Sellers offer the bandwidth of telecommunication links. Buyers are interested in the purchase of the bandwidth of several links that makes up an end-to-end connection between two nodes of telecommunication network. We analyze three auction models supporting such a bandwidth exchange: NSP (network second price), BCBT (model for balancing communication bandwidth trading) and BCBT-CG which is a modification of BCBT that applies column generation technique. All of these models concern divisible network resources, treat bandwidth of telecommunication links as an elementary commodity offered for sale, and allow for purchasing bandwidth along multiple paths joining two telecommunication nodes. All of them also aim at maximizing the social welfare. Considered auction models have been compared in the respect of economic and computational efficiency. Experimental studies have been performed on several test instances based on the SNDlib library data sets.

3

Wybrane modele i metody optymalizacji alokacji zasobów

Pieńkosz K.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2010

|

z. 174

3-132

PL

Monografia dotyczy zagadnień związanych z efektywnym rozdziałem szeroko rozumianych zasobów. Prezentowane są metody optymalizacji dla problemów alokacji pojedynczego zasobu, zasobu dostępnego w porcjach o określonej wielkości oraz zestawu różnych rodzajów zasobów. Szczegółowo analizowane są właściwości modeli i algorytmów rozwiązywania dla problemów alokacji formułowanych jako zadania plecakowe, zadania pakowania i rozkroju oraz zagadnienia transportowe i dystrybucyjne. Klasyczne modele alokacji mają głównie charakter dyskretny, wykluczający możliwość częściowej realizacji zapotrzebowań, bądź ciągły z pełną swobodą przydziału zasobu. W pracy szczególną uwagę poświęcono analizie semi-ciągłych problemów rozdziału zasobów i algorytmom ich rozwiązywania. W modelach semi-ciągłych zakłada się, że wielkość przydzielanego zasobu nie może być mniejsza od wartości zadanego parametru β. Tego typu modele były dotychczas badane w literaturze w ograniczonym stopniu, pomimo ich istotnego znaczenia praktycznego i teoretycznego. Stanowią one uogólnienie klasycznych modeli alokacji. Poprzez możliwość wyboru wartości parametru β dostosowanej do rzeczywistych uwarunkowań, pozwalają wyznaczać bardziej elastyczne sposoby gospodarowania zasobami.

EN

The book investigates resource allocation problems. We present models and methods fbr effective allocation of resources among competing activities. Classical discrete optimization models assume that if a resource is allocated to an activity then its demand must be fully satisfied. In continuous models, it is allowed to allocate a very small amount of resource. The main subject of the monograph are semi-continuous models which can be seen as a generalization of the classical discrete and continuous approaches. In semi-continuous models, the amount of resource allocated to an activity cannot be smaller than a given parameter β. In the case when only a single resource is available, the Semi-Continuous Knapsack Problem is formulated and its structural properties are analyzed. As a result, a procedure is developed which enables to fix the optimal values of some variables and transforms the resulting problem of reduced size into the Cardinality Constrained Knapsack Problem. Next, two classes of approximation algorithms are proposed and their performance in the worst case is analyzed. For multi resource allocation problems with uniform resources, the One-Dimensional Semi-Continuous Bin Packing model is formulated. We describe several approximation algorithms for solving such problem and analyze their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented. The Two-Dimensional Bin Packing Problem is discussed only for the discrete case concerning cutting stock process. The application of an approximation algorithm exploiting bottom-up approach and the best-first strategy is described. General multi resource allocation problems are considered in the context of the General Assignment Problem, Transportation Problem and Capacitated Facility Location Problem. The semi-continuous model is discussed mainly for the Transportation Problem. The conditions for existing feasible solutions of semi-continuous model arę formulated. Moreover, an exact algorithm is developed for a special case concerning two resources and sufficiently small β. For the Capacitated Facility Location Problem a Lagrangian heuristic is described and the possibility of its application to the semi-continuous model is discussed.

4

Heurystyczne algorytmy ograniczonej alokacji zasobu

Pieńkosz K.

Przegląd Elektrotechniczny

|

2008

|

R. 84, nr 9

89-92

PL

W komórkach żywych organizmów zachodzi wiele procesów biochemicznych podlegających skomplikowanym mechanizmom regulacji. Jednym z nich jest proces produkcji cząsteczek mRNA, zachodzący w jądrze komórkowym. Z praktycznego punktu widzenia jest to proces dyskretny. W niektórych przypadkach może być on jednak opisywany modelami ciągłymi. W niniejszej pracy pokazane są warunki, w jakich zarówno opis dyskretny, jak i ciągły prowadzą do takich samych jakościowo wyników.

EN

In the paper a variant of the continuous knapsack problem is considered in which no more than a specified number of variables are allowed to be positive. Two heuristic algorithms are proposed to solve the problem. Some results of the worst-case performance analysis for these algorithms are provided.

5

Właściwości rozwiązań problemu plecakowego z ograniczoną podzielnością elementów

Pieńkosz K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 144

189-195

PL

W pracy jest rozpatrywany wariant problemu plecakowego, w którym dopuszcza się podział elementów podczas pakowania przy zastrzeżeniu, że waga umieszczanych w plecaku fragmentów nie może być mniejsza niż zadany parametr [beta]. Analizowane są właściwości rozwiązań optymalnych takiego problemu. Sformułowano warunki opłacalności pakowania poszczególnych elementów, co w wielu przypadkach umożliwia znaczącą redukcję wymiaru rozpatrywanego zadania.

EN

In the paper the semi-continuous variant of the knapsack problem is considered in which items may be fragmented into smaller pieces while putting them into the knapsack. Fragmentation is however subjected to the restriction that the weight of each piece cannot be smaller than the given parameter [beta]. In the paper the properties of the semi-continuous knapsack problem are investigated. It is shown how the optimal values of some variables may be fixed in advance and thus the size of the problem may be reduced.

6

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

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.

7

Metoda rozwiązywania problemu dystrybucyjnego z wykorzystaniem relaksacji Lagrange'a

Pieńkosz K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

277-286

PL

W pracy jest rozważany wielotowarowy, dwustopniowy problem dystrybucyjny, w którym należy określić miejsca lokalizacji punktów dystrybucyjnych i zasięg ich odbiorców, tak aby minimalizować sumaryczne koszty transportu i dystrybucji pomiędzy producentami i klientami. Zaproponowano efektywną metodę rozwiązywania wykorzystującą relaksację Lagrange'a i strukturalne cechy problemu. Metoda ta wyznacza zazwyczaj rozwiązania suboptymalne, ale podaje też wartości dolnych oszacowań, co pozwala ocenić jakość tych rozwiązań.

EN

In the paper a multi-commodity two-stage distribution problem is considered in which the location of distribution centers and customers assignment is searched, so that the total distribution and transportation cost between plants and customers is minimised. An effective solution method based on Lagrangian relaxation and structural properties of the problem is proposed. It usually generates suboptimal solutions but gives lower bounds as well which allow to estimate the quality of such solutions.