25679945
A Comparison of GRASP and an Exact Method for Solving a Production and Delivery Scheduling Problem
In this paper we consider the production and delivery scheduling problem, a problem that deals with the selection of orders to be processed by a manufacturing plant and immediately delivered to the customer site. Orders have a fixed due date and must be prepared in a single plant with limited capacity. A limited number of vehicles are available for delivery. A ready-mix concrete manufacturing case study has motivated this research. We describe an exact method to find optimal solutions based on the construction of a graph that collects all feasible solutions. We also describe a greedy randomized adaptive search (GRASP) for the problem that finds good, though not necessarily optimal, solutions.
16750894
A Genetic Algorithm for Solving a Production and Delivery Scheduling Problem with Time Windows
This paper deals with the problem of selecting and scheduling a set of orders to be processed by a manufacturing plant and immediately delivered to the customer site. Constraints to be considered are the limited production capacity, the available number of vehicles and the time windows within which orders must be served. We describe the problem relating it to similar problems studied in the literature. A genetic algorithm to solve the problem is developed and tested empirically with randomly generated problems. Comparisons with an exact procedure and a tabu search procedure show that the method finds very good-quality solutions.
32636956
Viral System to Solve Optimization Problems: An Immune-Inspired Computational Intelligence Approach
This paper presents Viral System as a new immune-inspired computational intelligence approach to deal with optimization problems. The effectiveness of the approach is tested on the Steiner problem in networks a well known NP-Hard problem providing great quality solutions in the order of the best known approaches or even improving them.
206167311
Genetic algorithm for planning cable telecommunication networks
Abstract Optical fiber networks over synchronous digital hierarchy operating on ATM mode appear as one of the best alternatives for the new high-speed telecommunications networks. The network management requires planning studies so that the designed networks allow efficient operation in real time. A quantitative model evaluating the global topological design of an optical fiber network over synchronous digital hierarchy is described. The model includes the economic aspects involved in the project, the civil works, the capacity evaluation costs and the introduction of reliability conditions. A genetic approach based on the exploitation of the Kuhn–Tucker optimality conditions is proposed to solve the model.
32057483
An Evolutionary Algorithm for the Design of Hybrid Fiber Optic-Coaxial Cable Networks in Small Urban Areas
Telecommunication is one of the fastest growing business sectors. Future networks will need to integrate a wide variety of services demanding different qualities and capacities from the network. In this paper, network architecture based on hybrid fiber optic-coaxial cable (HFC) is proposed to develop cable integrated telematic services. An evolutionary algorithm is presented to solve the problem in suitable computation times when dealing with real times civil works problems. Finally we present the results over both problem library and real life scenarios.
7433683
Viral systems: A new bio-inspired optimisation approach
The paper presents a new approach to deal with combinatorial problems. It makes use of a biological analogy inspired by the performance of viruses. The replication mechanism, as well as the hosts' infection processes is used to generate a metaheuristic that allows the obtention of valuable results. The viral system (VS) theoretical context is described and it is applied to a library of medium-to-large-sized cases of the Steiner problem for which the optimal solution is known. The method is compared with the metaheuristics that have provided the best results for the Steiner problem. The VS provides better solutions than genetic algorithms and certain tabu search approaches. For the most sophisticated tabu search approaches (the best metaheuristic approximations to the Steiner problem solution) VS provides solutions of similar quality.
11189945
Reconfigurable Wormhole Networks: A Realistic Approach
The major problem in an interconnection network is related with the contention due to message blocking. In order to avoid this problem, many alternatives have been proposed in the literature, mainly adaptive routing, random routing and dynamic network reconfiguration. Our paper deals with dynamic reconfigurable networks. Reconfigurable networks are an alternative to reduce the negative effect that congestion produces on the performance of the network. Network reconfiguration can be done in different ways. Our researches are focused on dynamic reconfiguration. This technique consists basically of placing the different processors in the network in those positions which, at each computational moment and according to the existing communication pattern among them, are more adequate for the development of such computation.
14322005
Extending SRT for parallel applications in tiled-CMP architectures
Reliability has become a first-class consideration issue for architects along with performance and energy-efficiency. The increasing scaling technology and subsequent supply voltage reductions are increasing the susceptibility of architectures to soft errors. However, mechanisms to achieve full coverage to errors usually degrade performance in an unacceptable way for the majority of common users. Simultaneous and Redundantly Threaded (SRT) [13] is a fault tolerant architecture in which pairs of threads in a SMT core redundantly execute the same program instructions. In this paper, we study the under-explored architectural support of SRT to reliably execute shared-memory applications. We show how atomic operations induce a serialization point between master and slave threads. This bottleneck has an impact of 34% in execution speed for several parallel scientific benchmarks. We propose an alternative mechanism in which the L1 cache is updated by master's stores before verification reducing the overhead up to 21%. Our approach also outperforms other recent proposals such as DCC with a decrease of 8% in execution speed.
15130000
PEPE: A Trace-Driven Simulator to Evaluate Reconfigurable Multicomputer Architectures
Recent research on parallel systems with distributed memory has shown that the most difficult problem for system designers and users is related with the interconnection network. In this paper, we describe a programming and evaluating tool for multicomputers, named PEPE. It allows the execution of parallel programs and the evaluation of the network architecture. PEPE takes a parallel program as input and generates a communication trace obtained from this program. Next, PEPE simulates and evaluates the behaviour of a multicomputer architecture for this trace. The most important parameters of the multicomputer can be adjusted by the user. PEPE generates performance estimates and quality measures for the interconnection network. Another important feature of this tool is that it allows us to evaluate networks whose topology is reconfigurable. Reconfigurable networks are good alternatives to the classical approach. However, only recently this idea became the focus of much interest, due to technological developments (optical interconnection) that made it more viable. A reconfigurable network yields a variety of possible topologies for the network and enables the program to exploit this topological variety to speed up the computation.
1407913
A. novel approach to reduce L2 miss latency in shared-memory multiprocessors
Recent technology improvements allow multiprocessor designers to put some key components inside the processor chip, such as the memory controller, the coherence hardware and the network interface/router. In this work we exploit such integration scale, presenting a novel node architecture aimed at reducing the long L2 miss latencies and the memory overhead of using directories that characterize cc-NUMA machines and limit their scalability. Our proposal replaces the traditional directory with a novel three-level directory architecture and adds a small shared data cache to each of the nodes of a multiprocessor system. Due to their small size, the first-level directory and the shared data cache are integrated into the processor chip in every node. A taxonomy of the L2 misses, according to the actions performed by the directory to satisfy them is also presented. Using execution-driven simulations, we show significant L2 miss latency reductions (more than 60% in some cases). These important improvements translate into reductions of more than 30% in the application execution time in some cases.
810767
A novel approach to improve the performance of interconnection networks with hot-spots
Congestion in interconnection networks due to the presence of hot spots is an important and difficult problem that occurs in parallel machines. This problem has been studied in depth and different solutions for the case of multiprocessors with shared memory have been proposed. Current trends point towards the implementation of systems with physically distributed memory, either based on, message passing (multicomputers) or on a single shared memory address space (multiprocessors). Our paper is developed in this context. Up to now, proposals to improve the throughput of networks with hot-spots have focused on using virtual channels or adaptive algorithms. We present a novel solution based on reconfigurable networks. A reconfigurable network is one in which nodes can change their position depending on the communication pattern in order to diminish the congestion produced in the network and, therefore, increase its throughput. We studied this problem in two-dimensional k-ary n-cube networks using a deterministic routing algorithm and wormhole routing. In this paper the main features of a reconfigurable network are presented and the results obtained by simulation are shown. These results confirm that this technique is a very interesting one for systems with distributed memory, with applications to a great variety of problems.