The paper discusses a two-machine flow shop problem with minimization of the sum of tardiness costs, being a a generalization of the popular NP-hard single-machine problem with this criterion. We propose the introduction of new elimination block properties allowing for accelerating the operation of approximate algorithms of local searches, solving this problem and improving the quality of solutions determined by them.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
This work is focused on parallel simulation of electron-electron interactions in materials with non-trivial topological order (i.e. Chern insulators). The problem of electron-electron interaction systems can be solved by diagonalizing a many-body Hamiltonian matrix in a basis of configurations of electrons distributed among possible single particle energy levels – the configuration interaction method. The number of possible configurations exponentially increases with the number of electrons and energy levels; 12 electrons occupying 24 energy levels corresponds to the dimension of Hilbert space about 106 . Solving such a problem requires effective computational methods and highly efficient optimization of the source code. The work is focused on many-body effects related to strongly interacting electrons on flat bands with non-trivial topology. Such systems are expected to be useful in study and understanding of new topological phases of matter, and in further future they can be used to design novel nanomaterials. Heterogeneous architecture based on GPU accelerators and MPI nodes will be used for improving performance and scalability in parallel solving problem of electron-electron interaction systems
The subject of this work is the new idea of blocks for the cyclic flow shop problem with setup times, using multiple patterns with different sizes determined for each machine constituting optimal schedule of cities for the traveling salesman problem (TSP). We propose to take advantage of the Intel Xeon Phi parallel computing environment during so-called ’blocks’ determination basing on patterns, in effect significantly improving the quality of obtained results.
W pracy przedstawiono komputerowy system wspomagający harmonogramowanie przedsięwzięć budowlanych. Dotyczy on montażu kompozytowych belek obiektu mostowego. Aplikacja komputerowa obejmuje moduły: harmonogramowania prac budowlanych, harmonogramowania transportu belek przy montażu konstrukcji mostowych oraz moduł harmonogramowania w warunkach niepewności.
EN
This article describes a computerized system used to support the scheduling of construction projects. It relates to the construction of composite beams in a bridge structure. The computer application includes modules for scheduling of construction works, scheduling of transportation of beams for construction of the bridge structures, and a module for scheduling in conditions of uncertainty.
In this paper we consider a multi-machine scheduling problem with setup times, which is determined in the literature as the flexible job shop problem. It belongs to the strongly NP-complete complexity class. We propose an algorithm based on the tabu search method. The new elimination criteria were used in the construction process of blocks of the critical path.
In the paper we propose a new framework for the distributed tabu search algorithm designed to be executed with the use of a multi-GPU cluster, in which cluster of nodes are equipped with multicore GPU computing units. The proposed methodology is designed specially to solve difficult discrete optimization problems, such as a flexible job shop scheduling problem, which we introduce as a case study used to analyze the efficiency of the designed synchronous algorithm.
W pracy jest rozpatrywany silnie NP-trudny hybrydowy problem szeregowania zadań z równoległymi maszynami, zwany w literaturze elastycznym problemem gniazdowym. Głównym celem pracy jest wskazanie metody przeglądania otoczeń, dla złożonych problemów optymalizacji dyskretnej, z wykorzystaniem środowiska obliczeń równoległych. Aby proces ten przyśpieszyć, zastosowano szacowanie wartości funkcji celu (zamiast liczenia wartości dokładnej). Pozwoliło to znacznie przyśpieszyć obliczenia przy niewielkim pogorszeniu się wartości wyznaczanych rozwiązań.
EN
The aim of this paper is to show how to determine the neigh-borhood of the complex diserete optimization problem and how to search it in the parallel environment, this being illustrated by an example of the hybrid scheduling, more precisely a flexible job shop problem. We present a parallel single-walk approach in this respect. A theoretical analysis based on PRAM model of parallel computing has been made. We propose a cost-optimal method of neighborhood generation parallelization.
W pracy rozpatrywany jest ogólny problem kolejnościowy z równoległymi maszynami (flexible job shop problem), w którym dany jest zbiór zadań oraz zbiór maszyn. Maszyny tego samego typu (rodzaju), tj. o tych samych własnościach funkcjonalnych (które jednak mogą mieć różne parametry techniczne, takie jak na przykład wydajność) tworzą gniazdo. Do rozwiązania problemu proponujemy podejście dwupoziomowe - meta2heurystykę. Algorytm równoległy testowany jest na 128-procesorowej karcie GPU.
EN
We consider a double-level metaheuristic optimization algorithm in this paper. The algorithm proposed here includes two major modules: the machine selection module, which is executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, so we call this method meta2heuristics. We carry out computational experiment using 128-processors Graphics Processing Unit (GPU).
W pracy rozpatrujemy permutacyjny problem przepływowy będący jednym z najtrudniejszych problemów kombinatorycznych. Dla zamodelowa-nia specyficznych własności pojawiających się w praktycznych problemach harmonogramowania przedsięwzięć budowlanych zastosowaliśmy czasy transportu o ujemnej wartości. Przedstawiamy algorytm jego rozwiązywania oparty na metodzie tabu search.Wykonano wiele obliczeń dla trudnych przykładów o dużych rozmiarach zamieszczonych w pracy Taillard [14]. Otrzymane wyniki obliczeniowe porównano z powszechnie obecnie stosowanym algorytmem konstrukcyjnym NEH ([13]), wynikami dokładnego algorytmu B&B oraz najlepszymi znanymi w literaturze rozwiązaniami.
EN
In this paper we consider a permutational flow shop problem which is one of the difficult combinatorial problems. A negative times of transports have been using to model a specific constraints of the problem. We propose a tabu search approach. Tests were done for a Taillard [14] benchmarks. Obtained results were compared to constructive algorithm NEH ([13]), exact B&B algorithm and the best known results from literature.
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ć.