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

Znaleziono wyników: 8

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Poszukiwanie rozwiązań problemu plecakowego z wykorzystaniem algorytmu genetycznego
Handzel Z., Gajer M.
Elektronika : konstrukcje, technologie, zastosowania
|
2014
|
Vol. 55, nr 2
45-46
PL
Tematyka artykułu dotyczy wykorzystania techniki obliczeniowej opartej na zastosowaniu algorytmów genetycznych na potrzeby rozwiązania zagadnienia plecakowego. W artykule zaproponowano wykorzystanie binarnego sposobu kodowania rozwiązań na materiale genetycznym ewoluujących osobników. Szerzej omówiono zagadnienia związane z obliczaniem wartości funkcji dopasowania i realizacją operacji selekcji turniejowej.
EN
The topic of the paper is about using computational technique based on genetic algorithms for the purpose of rucksack problem solution. In the paper we propose to use binary system of coding of the solutions on the genetic material of evolving individuals. We discuss in detail the issues related to calculating the values of fitness function and realizations of tournament selection.
2
Content available remote Pierwszy problem milenijny : czy NP = P?
Pacholski L.
Roczniki Polskiego Towarzystwa Matematycznego. Seria 2: Wiadomości Matematyczne
|
2004
|
[Z] 40
1-21
3
Content available remote Heurystyczny algorytm projektowania sieci elektroenergetycznej typu drzewo Steinera
Schiff K.
Elektrotechnika i Elektronika
|
2001
|
T. 20, z. 2
97--99
PL
W artykule tym zaprezentowano algorytm wyznaczania drzewa Steinera о złożoności obliczeniowej rzędu О(n3) bazujący na algorytmie Warshalla-Floyda wyznaczania najkrótszych ścieżek pomiędzy wszystkimi wierzchołkami grafu i nа algorytmie Sollina rozpinania drzewa о minimalnej wadze nа wierzchołkach grafu. Pojęcie punktów Steinera zostało jednak zmodyfikowane, gdyż w ich skład oprócz wierzchołków, które muszą znaleźć się w rozwiązaniu, dołączono w trakcie działania algorytmu wierzchołki, którе nie musiały znaleźć się w rozwiązaniu zgodnie z początkowymi założeniami.
EN
In this paper algorithm for Steineг tree network design with time complexity О(n3) is presented, which is based оn Warshall—Floyd shortes path algorithms and Sollin spaning trees algorithms, but the notion of Steiner point is modificated.
4
Rozwiązywanie problemu dostawy za pomocą algorytmu przeszukiwania Tabu.
Szołtysek M.
Zeszyty Naukowe. Informatyka / Politechnika Śląska
|
1999
|
z. 37
209-221
PL
Problem dostawy jest przykładem złożonej optymalizacji kombinatorycznej i należy do grupy problemów NP-zupełnych. Zastosowanie algorytmu przeszukiwania tabu (ang. Tabu Search, TS) do rzwiązywania innyh problemów tej klasy przyniosło dobre rezultaty. Dlatego podjęto próbę zaadoptowania przeszukiwania tabu do rozwiązywania problemu dostawy. W pracy przedstawiono wyniki działania wybranych modyfikacji algorytmu przeszukiwania tabu do rozwiązywania problemu dostawy dla zbiorów danych wejściowych o różnych rozmiarach.
EN
The Delivery Problem is a difficult combinatorial optimization problem that belongs to the NP-complete group. Since the Tabu Search algorithm is suitable for solving the problems of this class, we have tried to adopt this algorithm to the delivery problem. In the paper the results of some modifications of the tabu search algorithm for solving the delivery problem for the sets of various sizes are presented.
5
Rozwiązywanie problemu dostawy za pomocą algorytmów mrówkowych.
Skórczyński A.
Zeszyty Naukowe. Informatyka / Politechnika Śląska
|
1999
|
z. 37
287-295
PL
Problem dostawy jest przykładem złożonej optymalizacji kombinatorycznej i należy do grupy problemów NP -zupełnych. Rodzina algorytmów mrówkowych dokonale sobie radzi ze złożonymi problemami tej grupy. Podjęto próbę zaadoptowania algorytmów mrówkowych do rozwiązywania problemu dostawy. W niniejszej pracy przedstawiono wyniki działania wybranych modyfikacji algorymów mrówkowych do rozwiązywania problemu dostawy dla zbiorów danych wejściowych o różnych rozmiarach.
EN
The delivery problem is an example of a complex combinatorial optimization which belongs to the NP-complete group. The family of an algorithms is suitable for solving the problem of this group. We have tried to adopt some an algorithms to the delivery problem. In this paper we present the results of some an algorithms for soloving the delivery problem for the sets of various sizes.
6
Nowa reprezentacja maszynowa grafu dysjunkcyjnego dla problemu szeregowania w ogólnym systemie obsługi
Błażewicz J., Pesch E., Sterna M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
45-54
PL
W pracy przedstawiono nową reprezentację maszynową grafu dysjunkcyjnego dla problemu szeregowania w ogólnym systemie obsługi - macierz grafu, charakteryzującą się korzystną złożonością pamięciową i wysoką efektywnością czasową procedur ją obsługujących. Łączy ona zalety trzech klasycznych reprezentacji struktur grafowych: macierzy sąsiedztwa, listy poprzedników i listy następników, umożliwiając łatwy dostęp do różnego rodzaju informacji opisujących operacje w ogólnym systemie obsługi.
EN
This paper is concerned with a new time and memory efficient representation of the disjunctive graph - the graph matrix, used for describing instances of the job shop scheduling problem. The proposed data structure combines advantages of the classical graph representations like a neighborhood matrix and predecessors' and successors' lists delivering combined information on a job shop and enabling easy manipulation of the problem data.
7
Minimizing the maximum completion time for the deteriorating jobs with ready times'
Bachman A., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
33-44
EN
In this paper we consider the single machine problem with the maximum completion time criterion. Job processing time is described by a nondecreasing, linear function dependent on the job processing start time. Job ready time is also given for each job. We assume, that for each job, its processing time deterioration begins at its ready time. Each job is available for the time not smaller than its ready time. The job processing time consists of two parts: one is constant and the other one: variable, start time dependent. The variable part is characterised by the growth rate, which describes how fast the job processing time deteriorate. If the job begins exactly at its ready time, its processing time is equal only to its constant part. In this paper, for the problem mentioned above, we present the NP-completeness proof. We also present two heuristic algorithms. The first heuristic algorithm bases on the adjacent jobs interchanging and the second one on the extended Jackson's rule. In this paper we compare presented algorithms basing on the computational results.
PL
W pracy rozpatrywany jest jednomaszynowy problem minimalizacji czasu zakończenia wykonywania zadań czasowo zależnych przy zadanych terminach dostępności. Założono, że wydłużenie czasu wykonywania zadania, opisanego funkcją liniową, następuje od momentu jego dostępności. Zostało pokazane, że powyższy problem jest NP-zupełny. Przedstawiono dwa algorytmy rozwiązujące rozpatrywany problem w sposób przybliżony.
8
Minimalizacja maksymalnej nieterminowości dla zadań czasowo zależnych
Bachman A., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
23-31
PL
W pracy rozpatrywano jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji maksymalnej nieterminowości wykonania. Założono, że czas wykonywania zadania, dany w postaci liniowej, niemalejącej funkcji terminu rozpoczęcia wykonywania składa się z dwóch części: stałej i zmiennej. Stała część, niezależna od terminu rozpoczęcia, określa pewną minimalną długość czasu wykonywania zadania, wynikającą z uwarunkowań technologicznych. Natomiast zmienna część, charakteryzowana przez czynnik wzrostu, opisuje wpływ terminu rozpoczęcia wykonywania na wydłużenie zadania. Pokazano, że przy tak scharakteryzowanym modelu jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji maksymalnej nieterminowości jest NP-zupełny.
EN
The paper deals with the single machine scheduling problem, where the job processing time is given as a linear, nondecreasing function dependent on the processing start time. The function describing the job processing time consists of two parts, where one is constant and describes the minimal time required to complete the job if its starting moment is equal to zero. The second part, characterized by the growth rate, describes how fast the job processing time deteriorate. We showed that such a described problem for the maximum lateness criterion is NP-complete by reducing to it NP-complete Partition Problem.
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ć.