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

Znaleziono wyników: 17

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Solving the Team Composition Problem in a Classroom
Manyà Felip, Negrete Santiago, Roig Carme, Soler Joan Ramon
Fundamenta Informaticae
|
2020
|
Vol. 174, nr 1
83--101
EN
Given a classroom containing a fixed number of students and a fixed number of tables that can be of different sizes, as well as a list of preferred classmates to sit with for each student, the team composition problem in a classroom (TCPC) is the problem of finding an assignment of students to tables in such a way that the preferences of students are maximally-satisfied. In this paper, we first formally define the TCPC, prove that it is NP-hard and define two different MaxSAT models of the problem, called maximizing and minimizing encoding. Then, we report on the results of an empirical investigation that show that solving the TCPC with MaxSAT solvers is a promising approach and provide evidence that the minimizing encoding outperforms the maximizing encoding. Finally, we illustrate how the proposed MaxSAT-based modeling approach is also well-suited for modeling other more complex team formation problems.
2
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.
3
Algorytmiczne oszacowania liczby chromatycznej grafu
Borowiecki P.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2008
|
T. 15
159-164
PL
Liczba chromatyczna grafu jest najmniejszą liczbą kolorów niezbędnych do pokolorowania jego wierzchołków w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. W ogólnym przypadku problem wyznaczenia liczby chromatycznej jest problemem NP-trudnym, stąd duże zainteresowanie parametrami graf owym i, które można wykorzystać do opisu oszacowań wartości liczby chromatycznej. W pracy tej omawiamy własności parametrów wywodzących się z pojęcia funkcji potencjału grafu oraz badamy ich powiązania z klasycznymi parametrami takimi jak liczba Welsha-Powella oraz liczba Szekeresa-Wilfa. Przedstawiamy także wyniki eksperymentalnego porównania dwóch znanych algorytmów sekwencyjnych z algorytmami porządkującymi wierzchołki według wartości funkcji potencjału.
EN
The chromatic number of a graph is the smallest number of colors required to color its vertices such that no two adjacent vertices share a color. In the general case determining the chromatic number of a graph is NP-hard, thus any graph invariants useful in bounding it are of great interest. Within this paper we discuss the properties of the invariants originating in the notion of a potential function. We study their interdependencies and the relationships to the classical Welsh-Powell and Szekeres- Wilf numbers. We also present the results of experimental comparison of two known sequential algorithms to the algorithms that use orderings of vertices with respect to their potentials.
4
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.
5
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.
6
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.
7
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.
8
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.
9
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.
10
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).
11
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.
12
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.
13
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).
14
Content available remote Designing of multi loop electric power network structures with the use of evolutionary algorithms
Parol M.
Archiwum Energetyki
|
2003
|
T. 32, nr 1/2
63-84
EN
Designing of optimal structure of multi loop electric power networks has been described in this paper. Networks of this type are typical for urban areas, where loop intermediate networks are very often built, both as MV networks and as LV networks. Multi loop network structure designing problem consists in determining of a set of loops with minimal total annual costs. The total annual costs include fixed (investment) costs, variable (operating) costs and supply-interruption costs. Optimization task taking into account only fixed costs meets classical formulation of the vehicle Routing Problem. However, when we take into account all three annual costs components that classical approach usually cannot be used. The optimization problem, similarly as the Vehicle Routing Problem, belongs to the class of very complicated mathematical problems in respect of computational effort (so called NP problems). In this type of problems with real sizes (big number of nodes and branches) it is suitable to use heuristic methods. Multi criterion optimization model is proposed in the paper. The aim of optimization process is: minimization of total annual network costs and maximization of the average grade of satisfaction function of consumers voltage deviations. In order to solve mathematical model of designing problem of optimal structure of multi loop electric power networks evolutionary algorithms and fuzzy numbers have been used. Computational experiments have been executed on the test problem. The comparison between the effects of evolutionary algorithm action and the artificial neural network has been made for this test. Obtained results show that evolutionary algorithm can be a useful tool for designing of multi loop electric power network optimal structure.
PL
W artykule opisano projektowanie optymalnych struktur wielopętlowych sieci elektroenergetycznych. Sieci tego typu są typowe dla obszarów miejskich, gdzie bardzo często buduje się sieci pętlowe przelotowe, zarówno jako sieci średnich napięć (SN), jak i sieci niskich napięć (nN). Projektowanie optymalnych struktur sieci elektroenergetycznych polega na znalezieniu takiego zbioru pętli, który minimalizuje całkowite koszty roczne pracy sieci. W skład kosztów rocznych wchodzą: koszty stałe, koszty zmienne oraz koszty związane z przerwami w dostawie energii elektrycznej. Zadanie optymalizacyjne biorące pod uwagę jedynie koszty stałe zgodne jest z klasycznym modelem problemu dostaw (ang. Vehicle Routing Problem). W przypadku uwzględniania wszystkich elementów składowych funkcji kosztów rocznych, to klasyczne podejście zazwyczaj nie może być zastosowane. Opisany problem optymalizacyjny, podobnie jak zadanie VRP, należy do klasy bardzo skomplikowanych zadań matematycznych, ze względu na wysiłek obliczeniowy (tzw. problemów NP- trudnych). Przy tego typu problemach o rzeczywistych rozmiarach (duża liczba węzłów i gałęzi) wskazane jest. stosowanie metod heurystycznych. W artykule zaproponowano model optymalizacji wielokryterialnej. Celem procesu optymalizacyjnego jest: minimalizacja całkowitych rocznych kosztów pracy sieci oraz maksymalizacja średniego stopnia spełnienia tzw. funkcji satysfakcji (przynależności) ze względu na odchylenia napięcia u odbiorców energii elektrycznej. W celu rozwiązania modelu matematycznego zadania projektowania optymalnych struktur wielopętlowej sieci elektroenergetycznej zastosowano technikę algorytmów ewolucyjnych oraz teorię liczb rozmytych. Przeprowadzono eksperymenty obliczeniowe na wybranym problemie testowym. Wykonane zostały także analizy porównawcze działania algorytmu ewolucyjnego i sztucznej sieci neuronowej dla testowanej sieci elektroenergetycznej. Uzyskane rezultaty pokazują, że algorytm ewolucyjny może być użytecznym narzędziem do projektowania optymalnych struktur wielopętlowych sieci elektroenergetycznych.
15
Content available Binary neural networks for N-queens problems and their VLSI implementations
Funabiki N., Kurokawa T., Ohta M.
Control and Cybernetics
|
2002
|
Vol. 31, no 2
271-296
EN
Combinatorial optimization problems compose an important class of matliematical problems that include a variety of practical applications, such as VLSI design automation, communication network design and control, job scheduling, games, and genome informatics. These problems usually have a large number of variables to be solved. For example, problems for VLSI design automation require several million variables. Besides, thieir computational complexity is often intractable due to NP-hardness. Neural networks have provided elegant solutions as approximation algorithms to these hard problems due to their natural parallelism and their affinity to hardware realization. Particularly, binary neural networks have great potential to conform to current digital VLSI design technology, because any state and parameter in binary neural networks are expressed in a discrete fashion. This paper presents our studies on binary neural networks to the N-queens problem, and the three different approaches to VLSI implementations focusing on the efficient realization of the synaptic connection networks. Reconfigurable devices such as CPLDs and FPGAs contribute the realization of a scalable architecture with the ultra high speed of computation. Based on the proposed architecture, more than several thousands of binary neurons can be realized on one FPGA chip.
16
Content available remote Optymalizacja struktur miejskich sieci niskiego napięcia metodami ewolucyjnymi
Baczyński D.
Archiwum Energetyki
|
2002
|
T. 31, nr 1/2
95-119
PL
W artykule przedstawiono metodę optymalizacji struktur miejskich sieci niskiego napięcia wykorzystującą algorytmy ewolucyjne. Z uwagi na złożoność zadania i wielkość przestrzeni rozwiązań, w której może być poszukiwane rozwiązanie zdecydowano się na przeszukiwanie tylko obszaru rozwiązań dopuszczalnych. W tym celu opracowano metody naturalnego kodowania zadań optymalizacji struktur i konfiguracji, jak również specjalizowane operatory genetyczne.
EN
In the paper, a method of optimizing low voltage network structure is presented, that utilizes evolutionary algorithms. Due to the complexity of this task and the extent of area in which solution can be found, only an acceptable solution area is sought. For this purpose, methods of natural coding of structure and configuration optimization problems were derived. Additionally, suitable, specialized genetic operators were proposed.
17
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.
first rewind previous Strona / 1 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ć.