Ograniczanie wyników
Czasopisma help
Autorzy help
Lata help
Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 25

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote Exact and approximation algorithms for joint routing and flow rate optimization
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.
EN
This paper discusses the issue of determining the longest simple chain in a graph by using a heuristic algorithm - a genetic algorithm. A method enabling the effective determination of the longest chain in any connected, undirected graph without loops.
PL
W artykule rozpatrzono problem wyznaczania najdłuższego łańcucha prostego w grafie wykorzystującą algorytm heurystyczny – algorytm genetyczny. Przedstawiono metodę umożliwiającą efektywne wyznaczanie najdłuższego łańcucha w dowolnym grafie spójnym, nieskierowanym, bez pętli.
EN
The problem of loading unit formation is computationally complex in nature. This article presents a heuristic algorithm of forming unit loads, which can be applied to unit load arrangement on unit load devices. This method accounts for dimensional, mass and load-bearing strength of loading units and loading devices. Moreover, the rotation of packages about a 90° vertical axis has been made possible. In this algorithm, the bearing surface of each packing unit is entirely supported. This guarantees the stability of additional unit load layers. A sample calculation of the arrangement of 30-unit loads is presented in this article.
EN
In recent years elastic optical networks have been perceived as a prospective choice for future optical networks due to better adjustment and utilization of optical resources than is the case with traditional wavelength division multiplexing networks. In the paper we investigate the elastic architecture as the communication network for distributed data centers. We address the problems of optimization of routing and spectrum assignment for large-scale computing systems based on an elastic optical architecture; particularly, we concentrate on anycast user to data center traffic optimization. We assume that computational resources of data centers are limited. For this offline problems we formulate the integer linear programming model and propose a few heuristics, including a meta-heuristic algorithm based on a tabu search method. We report computational results, presenting the quality of approximate solutions and efficiency of the proposed heuristics, and we also analyze and compare some data center allocation scenarios.
EN
Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.
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.
PL
W pracy przedstawiono proste metody pozwalające na szybkie wyznaczenie wielkości produkcji w poszczególnych okresach dla znanego harmonogramu przezbrojeń dla problemów z grupy zadań planowania wielkości i szeregowania partii produkcyjnych. Przedmiotem badań było zadanie planowania wielkości i szeregowania partii produkcyjnych z maszynami równoległymi. Przedstawiono zasadę działania algorytmów oraz zinterpretowano wyniki uzyskane za pomocą opracowanych metod heurystycznych dla zadania planowania wielkości i szeregowania partii produkcyjnych z maszynami równoległymi. Porównano je ze znanymi rozwiązaniami optymalnymi.
EN
In this paper several simple heuristics algorithms for the lot-sizing and scheduling problem with paral-lel machines are presented. The algorithms were developed for a situation when a pre-definied changeov-ers schedule is known in advance. Computational experiments were conducted both with MIP model and the algorithms. Results obtained with newly developed heuristics algorithms were compared to the one achieved from the MIP model.
PL
Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.
EN
The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.
9
Content available remote Dynamic classification of tasks in condition of unit and small batch production
EN
In the process of unit and small batch production a very important aspect is the amount of time from production setup to availability to the customer. In spite of applying modern management techniques, setup time still plays an important part in the production cycle time. In the examined companies the relationship between changeover time to processing time was significant. The above research inspired the author to prepare a method of setup time reduction through the appropriate arrangement of tasks in the operational production plan. The appropriate arrangement meant considering the similarity of parts from the point of view of carried out operation. The similarity of parts facilitates setup time reduction, which translate into smaller lot sizes, reduced in-process inventories, shorter lead time and higher throughput. The method was validated in conditions of the production practice for unit and small batch production. The presented method is one of the elements of a computer aided management system for small and medium enterprises (SME).
PL
Rozważany jest problem rozdziału zasobów dyskretnych, w którym zasadniczym celem jest równoważenie obciążenia zasobowego. W problemie tym czynności projektu są szeregowane w taki sposób, by me naruszyć ograniczeń kolejnościowych i linii krytycznej dla całego projektu przy jednoczesnej minimalizacji funkcji celu odzwierciedlającej zmiany poziomu wykorzystania zasobów. Przedstawiono trzy klasy takich funkcji oraz zaproponowano pewne podejścia heurystyczne.
EN
Resource leveling problem is considered. The main objective of this problem is to minimize the fluctuations of the resource usage profiles. There are two types of constraints in this problem: a deadline for the entire project as well as precedence constraints between pairs of projects' activities. Three classes of objective functions are distinguished. Some heuristics are proposed to solve the problem.
PL
Własności blokowe są z powodzeniem stosowane do usuwania ruchów nierokujących poprawy dla wielu otoczeń stosowanych w algorytmach popraw dla problemów szeregowania. W pracy, dla ogólnego problemu przepływowego, zaproponowano nowy sposób przeglądania otoczenia, który pozwala na eliminację znacznie większego zbioru ruchów. W celu sprawdzenia efektywności metody przeprowadzono eksperyment komputerowy na instancjach Taillarda.
EN
The block properties are successfully applied to a priory eliminate non promising moves from the neighborhood for many local search algorithm of solving scheduling problems. In this paper, for the general flowshop problem, it presents new method of searching the neighborhood, which gives rise to eliminate highly greater set of moves. To validate efficiency of the proposed method, computational experiment have been executed on a well-known Taillard's benchmarks.
PL
Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych w dyskretnym systemie produkcyjnym. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki badań numerycznych wykonanych na bazie zaproponowanego algorytmu heurystycznego.
EN
In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resource's units to m parallel machines in discrete production system is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of numerical experiments for basis of proposed heuristic algorithm are presented.
PL
Praca porusza problem analizy wyniku balansu linii montażowej. W literaturze można znaleźć kilka miar opisujących jakość uzyskiwanych rezultatów. Należą do nich: wydajność linii, czas linii oraz współczynnik gładkości linii. Wszystkie jednak dotyczą oceny balansu całej linii i niestety, nie pozwalają na szczegółową analizę poszczególnych stacji montażowych. Autor wprowadza zatem kolejny współczynnik wydajności dotyczący pojedynczych stacji i umożliwiający dokonanie oceny balansu linii na poziomie kolejnych stanowisk.
EN
The paper considers the analysis of final result of assembly line balancing problem. Some measures are described in the literature: line efficiency, time of the line and smoothness index. All of them show the quality of whole line balance and they don't allow to analyze only the station balance. Author introduces the next measure: station efficiency index which allows to observe the station balance and helps to improve the balance of the whole assembly process.
14
Content available remote Algorytm ewolucyjny szeregowania zadań na jednej maszynie
PL
W artykule zaprezentowano algorytm strategii ewolucyjnej do szeregowania zadań na jednej maszynie przy kryterium minimalizacji ważonej sumy wyprzedzeń i opóźnień. Z problemami takimi można się coraz częściej spotkać w praktyce, gdyż narastająca konkurencja wymusza rygorystyczne dotrzymywanie terminów dostarczania wyrobów klientom. Wyniki badań wykazały, że proponowany algorytm może być wykorzystywany jako efektywne narzędzie planowania operatywnego produkcji, m.in. w zakładach odlewniczych.
EN
This paper focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to symmetric earliness and tardiness penalties. The justification for this approach is that in JIT environment, an idea! schedule corresponds to one where all jobs complete precisely at their corresponding due dates. A non-specialized and non-hybridized evolutionary strategy (ES) is proposed for solving this problem. The computational experiment shows that the proposed heuristic perform well and can be used as a planning tool in foundries. Many aspects of the developed ES are quite general and can be adopted to more realistic assumptions.
PL
W życiu codziennym spotykamy się z różnego rodzaju problemami heurystycznymi. Do ich rozwiązania możemy stosować istniejące już deterministyczne metody optymalizacji. Istnieje jednak wiele zdarzeń kombinatorystycznych o niezwykle wysokiej złożoności obliczeniowej, dla których deterministyczne metody rozwiązania nie są do zaakceptowania, ponieważ ich złożoność i koszt obliczeniowy przekracza możliwości obliczeniowe najszybszych nawet komputerów. Wtedy dla inżyniera, pragnącego w rozsądnym czasie znaleźć rozwiązanie jeżeli nie optymalne, to przynajmniej suboptymalne, odpowiednim narzędziem stają się metody heurystyczne. Szukanie rozwiązania za ich pomocą sprowadza się do wygenerowania i zastosowania zbioru reguł kierujących procesem przeszukiwania przestrzeni rozwiązań. Istnieje kilka różnych paradygmatów pozwalających na generowanie szeregu algorytmów heurystycznych. Paradygmaty te nazywane są metaheurystykami, ponieważ nie definiują konkretnych algorytmów ale opisują ogólne podejścia. W ramach takiego podejścia istnieje możliwość szerokiego wariantowania poszczególnych reguł, co w rezultacie prowadzi do różnych algorytmów należących jednak do wspólnej rodziny (zob. np. [13]). [...]
PL
Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Zakłada się, że występuje stałość przydziału zasobów do maszyn w czasie wykonywania całego zbioru zadań. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki eksperymentów obliczeniowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.
EN
In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. We assume, that is constancy of resources allocation to machines in processing time all tasks set. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed numerical experiment for basis of proposed heuristic algorithm are presented.
PL
Standard MRP II nie zapewnia optymalności ani realizowalności generowanych zleceń produkcyjnych. W celu zapewnienia ich realizowalności zaproponowano algorytm heurystyczny.
EN
MRP II standard does not assure optimum values and feasibility of generated orders. For achieving feasible shop orders the heuristic algorithm has been suggested.
PL
W artykule przedstawiono nowe modele matematyczne szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi. Uwzględniony został przypadek, w którym między stadiami znajdują się bufory międzystadialne, oraz sytuacja, gdy nie ma tych buforów i ich rolę pełnią maszyny. W celu skrócenia czasu rozwiązywania zadań szeregowania operacji opracowano heurystyki relaksacyjne. Artykuł zawiera wyniki przeprowadzonych eksperymentów obliczeniowych.
EN
The paper describes new mixed integer programming models for operation scheduling for flexible assembly lines with parallel machines. The assembly line with intermediate buffers and the configuration without intermediate buffers are considered. Relaxation heuristics are proposed to reduce CPU time required for mixed integer programming. Results of computational experiment with the proposed MIP models and heuristics are included.
PL
Przedstawiona praca porusza problem planowania ścieżki robota mobilnego w środowisku pomieszczeń zamkniętych, bazujący na geometrycznej reprezentacji otoczenia. Przedstawiono algorytm wyznaczania bezkolizyjnej ścieżki, wykorzystujący ideę dekompozycji przestrzeni. Główny nacisk położono na heurystyczne metody wyznaczania segmentów ścieżki zbliżającej robot do zadanego punktu.
EN
Path planning problem for a mobile robot operating in a human-made environment is considered in this paper. Collision free path search algorithm based on space decomposition method is described. Heuristic methods of goal approaching are discussed.
PL
Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Zakłada się, że występuje stałość przydziału zasobów do maszyn w czasie wykonywania całego zbioru zadań. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki eksperymentów obliczeniowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.
EN
In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. We assume, that is constancy of resources allocation to machines in processing time all tasks set. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed numerical experiment for basis of proposed heuristic algorithm are presented.
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ć.