| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 4 / 4
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Optimization methods for solving transportation problems on networks
Katja Prnaver, 2011, doktorska disertacija

Opis: In this thesis we study problems from real situations, which can be applied to network graphs and solved using mathematical graph theory. We start with the problem of oriented network design. The problem originates from networks, where the flow over the arcs is important and many times limited with the capacity of the networks. There are several techniques and results on the problem of assigning the flow through the network channels. In our problem, we try to find the optimal network structure, which could be used in the design phase of the network. With metaheuristics, we search for optimal network structures for a given number of nodes. We define triangle neighborhood and compare the results of the algorithm with the conjecture by Choplin et al. [8]. Further, we study the problem of order picking and order batching in block structured warehouses. For order picking problem, we present the extension of a dynamic programming algorithm by Ratliff and Rosenthal [42], which enables the development of an algorithm for an unlimited number of blocks. In order to achieve this, a new presentation of states and transitions of dynamic programming algorithm is given. We prove that the resulting path is optimal for the given structure. We compare the optimal path lengths to the results found in literature and also investigate the impact of warehouse layout parameters onto the routing. Closely related to the problem of order picking, we investigate the order batching problem. We discuss the variation of the order batching problem with time windows and present the algorithmic approach to solving the problem. The previously presented optimal path algorithm is applied in the algorithm to ensure even better quality of results. We introduce the evaluation function of a batch and compare the results of the algorithm with the test data from the literature as well as with data from the real warehouse. We conclude by summarizing the results and stating some possible extensions and further work.
Ključne besede: graph theory, networks, optimization, shortest path problem, traveling salesman problem, algorithms, metaheuristics, order batching
Objavljeno: 03.06.2011; Ogledov: 3664; Prenosov: 144
.pdf Celotno besedilo (925,86 KB)

2.
An optimal permutation routing algorithm for full-duplex hexagonal mesh networks
Ignasi Sau Walls, Janez Žerovnik, 2006

Opis: In the permutation routing problem, each processor is the origin of at most one packet and each processor is the destination of no more than one packet. We study this problem in an hexagonal network (that is, a finite convex subgraph of a triangular grid), a widely used network in practical applications. We use the addressing scheme described by F.G. Nocetti, I. Stojmenovic and J. Zhang (2002, IEEE Trans. on Parallel and Distrib. Systems). In this paper, a distributed optimal routing algorithm for full-duplex hexagonal mesh networks is presented. Furthermore, we prove that this algorithm is oblivious and translation invariant.
Ključne besede: mathematics, hexagonal networks, permutation routing, shortest path, distributed algorithm, communication networks, oblivious algorithm
Objavljeno: 10.07.2015; Ogledov: 350; Prenosov: 19
URL Povezava na celotno besedilo

3.
Graphʼs theory approach for searching the shortest routing path in RIP protocol
Saša Klampfer, Jože Mohorko, Žarko Čučej, Amor Chowdhury, 2012, izvirni znanstveni članek

Opis: Routing is a problem domain with an infinite number of final-solutions. One of the possible approaches to solving such problems is using graph theory. This paper presents mathematical analysis methodologies based on circular graphs for solving a shortest path routing problem. The problem is focused on searching for the shortest path within a circular graph. Such a search coincides with the network routing problem domain. In this paper, we introduce in the detail all necessary parts needed to understand such an approach. This includes: definition of the routing problem domain, introduction to circular graphs and their usage, circular graphʼs properties, definition of walks through a circular graph, searching and determining the shortest path within a circular graph, etc. The state of the art routing methods, implemented in contemporary highly sophisticated routers, includes well-known weight-based algorithms and distance-vectors-based algorithms. The proposed solution can be placed between the two abovementioned methods. Each of these known methods strives for optimal results, but each of them also has its own deficiencies, which should be rectified with the proposed new method. This theoretically presented method is argued by a practical example and compared with the RIP (Routing Information Protocol) technique, where we look for the shortest path and possible walks through a specified circular graph.
Ključne besede: circular graphs, shortest path, graph diameter, walk through, CIGRP, connectivity matrix, network topology, symmetry, fully connected graph
Objavljeno: 10.07.2015; Ogledov: 875; Prenosov: 37
URL Povezava na celotno besedilo

4.
An optimal permutation routing algorithm on full-duplex hexagonal networks
Ignasi Sau Walls, Janez Žerovnik, 2008, izvirni znanstveni članek

Opis: In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm for full-duplex hexagonal networks, using the addressing scheme described by Nocetti et al. Furthermore, we prove that this algorithm is oblivious and translation invariant.
Ključne besede: mathematics, hexagonal networks, permutation routing, shortest path, distributed algorithm, communication networks, oblivious algorithm
Objavljeno: 10.07.2015; Ogledov: 388; Prenosov: 47
.pdf Celotno besedilo (535,46 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 0.11 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici