PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 24

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  problem NP-trudny
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote Integration of polynomials over n-dimensional simplices
Rouigueb Abdenebi, Maiza Mohamed, Tkourt Abderahmane, Cherchour Imed
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
157--163
EN
Integrating an arbitrary polynomial function f of degree D over a general simplex in dimension n is well-known in the state of the art to be NP-hard when D and n are allowed to vary, but it is time-polynomial when D or n are fixed. This paper presents an efficient algorithm to compute the exact value of this integral. The proposed algorithm has a time-polynomial complexity when D or n are fixed, and it requires a reasonable time when the values of D and n are less than 10 using widely available standard calculators such as desktops.
2
Content available remote Exact and approximation algorithms for joint routing and flow rate optimization
Junosza-Szaniawski Konstanty, Nogalski Dariusz
Annals of Computer Science and Information Systems
|
2019
|
Vol. 20
29--36
EN
This paper addresses comparison of algorithms for a version of the NUM problem. The joint formulation of routing and transmission rate control within the multi-user and single-path setting is assumed within the NUM. Since problem is NP-hard, the efficient heuristics are designed, implemented and compared experimentally with other existing heuristics and exact linear programming solver. The linear approximation is applied for nonlinear utility function. The results of experiments demonstrate a trade-off between computing time and precision of goal value.
3
Content available remote Correlation clustering: Let all the flowers bloom!
Aszalós László, Bakó Mária
Annals of Computer Science and Information Systems
|
2019
|
Vol. 20
21--28
EN
Correlation clustering is a NP-hard problem, and for large signed graphs finding even just a good approximation of the optimal solution is a hard task. In this article we examine the effect of ranking of the nodes and process them in order of ranks. We present that based on the rate of positive edges in the graph we should use different optimization methods. We show that all the building blocks of our methods are needed under certain circumstances.
4
Content available remote Hybridization of the optimization process as an alternative way to find approximate solutions for NP-hard problems
Rozenberg L., Rychcicki R.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 2
59-62
EN
This paper presents the results of calculations that demonstrate the possibility of using hybrid optimization method (with variable structure) for determining the approximate solutions to NP-hard problems. The Travelling Salesman Problem (TSP) is a classic combinatorial optimization subject, which has found widespread use in practice. Simple in definition, have remained hard to solve for many years. Not only an efficient solution would yield benefits in a substantial amount of routing problems, but it would also affect planning and logistics in a positive way.
PL
W prezentowanym artykule pokazano możliwość wykorzystania hybrydy optymalizacyjnej do uzyskania przybliżonego rozwiązania zadania NP-trudnego, czyli problemu obliczeniowego o ponad wykładniczym zapotrzebowaniu na moc obliczeniową. Do badań wybrano znany od wielu lat problem komiwojażera, którego od lat nie udało się ostatecznie rozwiązać. Wybór ten jednak umożliwił uzyskanie pokaźnego materiału porównawczego.
5
Algorytm hybrydowy wielokrotnego startu dla rozwiązywania problemu sekwencyjnego uporządkowania
Widuch J., Klyta A.
Studia Informatica
|
2014
|
Vol. 35, nr 1
29--55
PL
Problem sekwencyjnego uporządkowania (SOP) jest podobny do asymetrycznego problemu komiwojażera. Celem jest wyznaczenie w skierowanym grafie ważonym ścieżki Hamiltona o minimalnej wadze, przy dodatkowym spełnieniu relacji pierwszeństwa wierzchołków. W niniejszej pracy zaprezentowano algorytm hybrydowy wielokrotnego startu rozwiązywania problemu SOP. Algorytm ten jest połączeniem algorytmów symulowanego wyżarzania i lokalnej optymalizacji. Dodatkowo przedstawiono wyniki przeprowadzonych badań eksperymentalnych.
EN
The sequential ordering problem (SOP) is similar to the asymmetric traveling salesman problem. The goal is to find a minimum weight Hamiltonian path on a directed weighted graph satisfying precedence relationships among the vertices. In the paper, a multistart hybrid algorithm to solving SOP is presented. The algorithm based on simulated annealing algorithm and local optimization method. Apart from that results of experimental tests are presented.
6
Problem gniazdowy z ograniczeniem bez czekania. Równoległe algorytmy tabu
Makuchowski M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
175-181
PL
W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.
EN
This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.
7
Problem gniazdowy z ograniczeniem bez czekania. Algorytmy konstrukcyjne
Makuchowski M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
167-173
PL
W pracy opisana jest pewna procedura konstrukcji rozwiązania dla problemu gniazdowego z ograniczeniem bez czekania. Pokazano także sposób jej wykorzystania do budowy bardzo wydajnych algorytmów zarówno konstrukcyjnych, jak i popraw. W pracy prezentuje się algorytmy konstrukcyjne, bazujące na wspomnianej procedurze. Ich efektywność przebadano na dobrze znanych w literaturze przykładach testowych.
EN
This paper describes some solution constructive procedure dedicated to a job shop problem with the no-wait constraint and a makespan criterion. Very efficient heuristic algorithms based on the presented procedure are discussed. The efficiency of the algorithms is tested on well-known literature benchmarks.
8
Metoda analizy minimów lokalnych do rozwiązywania permutacyjnych problemów optymalizacyjnych
Bożejko W., Rajba P., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
19-24
PL
W pracy przedstawiono metodę konstrukcji algorytmów rozwiązywania problemów optymalizacyjnych opartą na analizie minimów lokalnych. Najlepsze cechy tych minimów są dziedziczone przez następną populację rozwiązań. Wykonano eksperymenty obliczeniowe, które potwierdziły efektywność proponowanej metody.
EN
In the paper we present a method of algorithms construction based on analyzing local minima for solving optimization problems. The best properties of these minima are succeeded by a next generation of solutions. Computational experiments, which has been done, affirmed the efficiency of the proposed method.
9
Harmonogramowanie statyczne zależnych zadań obliczeniowych w homogenicznym systemie wieloprocesorowym
Banul A., Wala K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
13-18
PL
Przedstawiono model formalny statycznego problemu harmonogramowania zależnych zadań obliczeniowych w homogenicznym systemie wieloprocesorowym. Opisano sześć algorytmów konstrukcyjnych harmonogramowania, a następnie, biorąc pod uwagę szereg ważnych kryteriów oceny jakości, zaprezentowano wyniki badań komputerowych ich efektywności.
EN
A formal model of static scheduling problem of dependent computational tasks in homogeneous multiprocessor system is presented. We give a description of six constructive scheduling algorithms and than, taking into account a number of important efficiency criteria, we picture the results of computational investigations of their performance.
10
Algorytm podziału i ograniczeń dla problemu rozkroju niegilotynowego
Kierkosz I., Łuczak M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
158-166
PL
W pracy przedstawiono algorytm optymalizacji rozkroju prostokątnej płyty na szereg prostokątnych elementów przy założeniu cięcia niegilotynowego oraz ograniczeniu na liczbę powtórzeń danego typu elementów w generowanych wzorach rozkroju. W proponowanym algorytmie przeszukiwanie przestrzeni dopuszczalnych rozwiązań odbywa się w oparciu o metodę podziału i ograniczeń. W pracy zamieszczono również wyniki obliczeń dla przykładowych zadań rozkroju dwuwymiarowego.
EN
The paper presents an algorithm for two-dimensional non-guillotine cutting stock problem. The problem consists in cutting many rectangular pieces, from a single rectangular sheet in such a way that the amount of trim loss is minimized. Moreover, there is a constraint on the maximum number of each type of piece that is to be produced. The proposed algorithm is based on a branch and bound method. Numerical examples to illustrate the proposed algorithm are solved.
11
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
Nadolski A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
99-105
PL
W pracy rozważamy złożoność obliczeniową szeregowania zadań w cylindrycznym systemie przepływowym. Konstruujemy algorytm wielomianowy dla problemu dwumaszynowego oraz wykazujemy, że problem staje się NP-trudny przy szeregowaniu na trzech maszynach oraz na dwóch maszynach przy wymuszeniu braku obustronnych przestojów.
EN
We consider the scheduling problem in a cylindrical flow shop to minimize the cycle time. We provide a polynomial time algorithm in the case of two processors and prove that the problem becomes NP-hard in the case of three processors. Moreover, we show that scheduling with no-wait and no-idle constraints is NP-hard in the case of two processors.
12
Szeregowanie zadań z najwcześniejszymi i najpóźniejszymi terminami zakończenia
Bożejko W., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
27-32
PL
W pracy przedstawiamy algorytm przybliżony oparły na metodzie przeszukiwania z tabu dla rozwiązywania problemu szeregowania na jednej maszynie zadań, z najwcześniejszymi i najpóźniejszymi terminami zakończenia. W procedurze przeglądania sąsiedztwa (ograniczonego przez eliminację "złych" rozwiązań) stosujemy, jako kryterium wyboru, górne ograniczenie wartości funkcji celu (rozwiązując problem "bez przestojów maszyny").
EN
In the paper we present an algorithm which is based on the tabu method to solving single machine scheduling problem with earliness and tardiness penalties. We apply an upper bound as the criterion in the neighborhood searching (solving "no idle" problem).
13
Metoda zadań zastępczych do rozwiązywania NP-trudnych problemów szeregowania
Dudek-Dyduch E., Dutkiewicz L.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
57-66
PL
W artykule przedstawiona jest heurystyczna metoda służąca do rozwiązywania skomplikowanych problemów szeregowania. Polega ona na tym, że w każdym stanie procesu decyzja podejmowana jest na podstawie specjalnie skonstruowanego zastępczego zadania optymalizacji. Metoda opisana jest na bazie modelu algebraiczno-logicznego. Opisany został też NP-trudny problem udostępniania pól eksploatacyjnych oraz algorytm jego rozwiązania oparty na proponowanej metodzie.
EN
The paper deals with a heuristic method for complex scheduling problems. According to this method a substitution optimization task is created in each state of the decision process. The method is described with the use of an algebraic-logical model. An NP-hard problem of preparing access to exploitation fields and algorithm for this problem based on the method is also described.
14
Jednomaszynowy problem szeregowania zadań z przezbrojeniami
Bożejko W., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
21-26
PL
W pracy przedstawiamy algorytm populacyjny rozwiązywania jednomaszynowego problemu szeregowania zadań z przezbrojeniami, w którym należy zminimalizować sumę kosztów opóźnień. W literaturze jest on oznaczany przez 1 | s[ij] | sigma w[i]T[i] należy do klasy problemów silnie NP-trudnych. Wykonaliśmy obliczenia na reprezentatywnej grupie danych testowych, a otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze. Dla wielu przykładów uzyskaliśmy poprawę najlepszych rozwiązań.
EN
In the paper we propose a population-based algorithm for solving single machine scheduling problem with total tardiness criterion and sequence-dependent setup times. It is represented by 1 | s[ij] | sigma w[i]T[i] in literature and it belongs to the strongly NP-hard class. Calculations on the representative group of benchmark instances were done and results were compared with the best known from literature. Obtained solutions were better than benchmark ones in many instances.
15
Efektywność algorytmu ewolucyjnego wykorzystującego mechanizm różnicowania
Chmiel W., Kadłuczka P., Jędrusik S.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
33-44
PL
Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmu ewolucyjnego, wykorzystującego operatory różnicujące. Bazują one na warunkowej wartości oczekiwanej funkcji celu rozwiązań częściowo ustalonych. Badania testowe wykonano dla standardowych zadań testowych kwadratowego zagadnienia przydziału (QAP).
EN
The paper presents our work on implementation and evaluation of evolutionary algorithm using diversification operators. They are based on expected conditional value of objective function for partially fixed solutions. The experiments were performed for standard test problems of quadratic assignment problems (QAP).
16
Content available remote Application of intelligent search strategy in the branch and bound method with the use of the example of cost optimization for an electric power network with high load variability
Oprzędkiewicz I.
Archiwum Energetyki
|
2001
|
T. 30, nr 1/2
3-18
EN
Cost optimization for losses in an electric power network with high load variability is a NP-hard. In problems of this category it is of relevance to devise effective algorithms, which will enable us to promptly find a solution. Obtaining a precise solution in this case is very difficult, since even a minor growth of the problem's volume results in an exponential increase in the calculation time. The chief method in search of optimal solutions to NP-hard problems is the branch and bound method. The paper deals with an analysis of effectiveness improvement formulae of the algorithm based on that method, through the reduction of the search path in the sub-problem tree. A method has been presented, in which the decision to select the sub-problem for analysis depends on the hitherto course of calcultions. As a criterion for this selection the assessment of the usability of the defined selection principles has been assumed (closely related with the problem being resolved). The algorithm is complimented by a meta-heuristics module, which is used to improve the currently known as the best solution.
PL
Optymalizacja kosztów strat w sieci elektroenergetycznej o dużej zmienności obciążenia jest zagadnieniem NP-trudnym. W problemach tej klasy duże znaczenie ma opracowanie efektywnych algorytmów, które pozwalają szybko znaleźć rozwiązanie. Uzyskanie rozwiązania dokładnego jest w tym przypadku bardzo trudne, gdyż niewielki wzrost rozmiaru problemu powoduje wykładniczy wzrost czasu obliczeń. Podstawową metodą poszukiwania optymalnych rozwiązań problemów NP-trudnych jest metoda podziału i ograniczeń. W pracy zajęto się badaniem i analizą metod poprawy efektywności algorytmu opartego na tej metodzie poprzez skrócenie drogi przeszukiwania w drzewie podproblemów. Przedstawiono metodę, w której decyzja o wyborze podproblemu do analizy zależy od dotychczasowego przebiegu obliczeń. Jako kryterium wyboru przyjęto ocenę przydatności zdefiniowanych reguł wyboru (ściśle związanych z rozwiązywanym zagadnieniem). Algorytm uzupełniono dodatkowym modułem zawierającym metaheurystykę i wspomagającym proces wyznaczania wartości odcinających.
17
Szeregowanie zadań w systemach silnie uwarunkowanych czasowo metodą cyklicznego obciążenia
Nawrocki J. R., Czajka A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
169-179
PL
W artykule przedstawione są wyniki badań dotyczących zastosowania metody minimalizacji obciążeń cyklicznych do szeregowania zadań silnie uwarunkowanych czasowo o okresach tworzących postęp binarny. Pokazano, że problem taki jest silnie NP-trudny i w związku z tym algorytm o złożoności wielomianowej nie istnieje. W tej sytuacji zaproponowana została prosta heurystyka zachłanna, która - jak wynika z przeprowadzonych eksperymentów obliczeniowych - zachowuje się lepiej od innych tego typu znanych heurystyk. Zastosowana do szeregowania zadań w samolocie F-16 dała w bardzo krótkim czasie optymalne rozwiązanie.
EN
In the paper scheduling hard real-time by minimising periodic loading is studied. It is assumed that task periods belong to a binary geometrical progression. It is shown that such a problem is strongly NP-hard. Thus, a simple greedy heuristics is proposed, which - due some computational experiments - is pretty effective and better than other greedy heuristics for the periodic loading problem. Applied to scheduling tasks for F-16 the heuristics returned an optimal solution in a very short time.
18
Szeregowanie zadań na procesorach dedykowanych bez przestojów
Giaro K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
133-144
PL
W praktycznym szeregowaniu zadań dość często spotykamy się z koniecznością zapewnienia nieprzerwanej pracy poszczególnym podmiotom naszego systemu. Szeregowanie takie nazywa się szeregowaniem bez przestojów. Zadaniem tej pracy jest zasygnalizowanie skali trudności obliczeniowej, jaką wymusza powyższe założenie. Wykażemy, że szereg podstawowych problemów decyzyjnych i optymalizacyjnych dotyczących istnienia lub najprostszych parametrów harmonogramu w szeregowaniu bez przestojów staje się NP-trudny, nawet dla systemów o grafach szeregowannia tak prostych jak ścieżka i cykl. Rozważania nasze będą dotyczyć modeli open show, flow shop oraz systemu zadań dwuprocesorowych.
EN
In practical task scheduling it is sometimes required that the elements of a system perform consecutively. Such a scheduling is called scheduling without waiting periods or no-wait and/or no-idle. In this article we study the complexity of some simplified scheduling problems of this kind. In particular, we show that many trivial questions about scheduling become NP-hard, even if the scheduling graph of a system is path, or a cycle. Our consideration concern the following models: open shop, flow shop and 2-procesor tasks system.
19
Modele szeregowania zadań i wózków w elastycznych przepływowych systemach obsługi
Błażewicz J., Pawlak G.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 124
9-17
PL
W artykule przedstawiono modele szeregowania zadań i wózków w elastycznych systemach produkcyjnych. Analiza wstępna obejmuje krótki przegląd literatury obrazujący intensywne badania w tej dziedzinie w ciągu ostatnich lat. W szczególności rozpatrywane były modele z przepływowym systemem obsługi zadań. Ze względu na zastosowany system transportowy można wyróżnić dwie grupy modeli - z acyklicznym i cyklicznym ruchem wózków. Szczególną uwagę poświęcono tym drugim. Scharakteryzowano model cyklicznego systemu przepływowego oraz zaproponowano algorytmy minimalizujące liczbę wózków dla zadanego uszeregowania na maszynach.
EN
In the paper the models of scheduling tasks and vehicles in Flexible Manufacturing Systems have been presented. The introduction contains short literature overview of the subject of particular interest are flexible flow shop models. Due to the transportation system applied to one can divide the models into acyclic and cyclic vehicle routing models. Four the latter, the algorithms minimizing a number of vehicles, for a given schedule, have been presented.
20
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.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.