Extremely Modular Systems (EMSs) are comprised of as few types of modules as possibleand allow creating structurally sound free-form structures that are not constrained bya regular tessellation of space. Truss-Z is the first EMS introduced, and its purpose isto create free-form pedestrian ramps and ramp networks in any given environment. Thispaper presents an overview of various multi-objective optimization methods applied toTruss-Z structures.
The problem of performing software tests using Testing-as-a-Service cloud environment is considered and formulated as an~online cluster scheduling on parallel machines with total flowtime criterion. A mathematical model is proposed. Several properties of the problem, including solution feasibility and connection to the classic scheduling on parallel machines are discussed. A family of algorithms based on a new priority rule called the Smallest Remaining Load (SRL) is proposed. We prove that algorithms from that family are not competitive relative to each other. Computer experiment using real-life data indicated that the SRL algorithm using the longest job sub-strategy is the best in performance. This algorithm is then compared with the Simulated Annealing metaheuristic. Results indicate that the metaheuristic rarely outperforms the SRL algorithm, obtaining worse results most of the time, which is counter-intuitive for a metaheuristic. Finally, we test the accuracy of prediction of processing times of jobs. The results indicate high (91.4%) accuracy for predicting processing times of test cases and even higher (98.7%) for prediction of remaining load of test suites. Results also show that schedules obtained through prediction are stable (coefficient of variation is 0.2–3.7%) and do not affect most of the algorithms (around 1% difference in flowtime), proving the considered problem is semi-clairvoyant. For the Largest Remaining Load rule, the predicted values tend to perform better than the actual values. The use of predicted values affects the SRL algorithm the most (up to 15% flowtime increase), but it still outperforms other algorithms.
W artykule przedstawiono algorytm mrówkowy opracowany w celu rozwiązywania zadań globalnej optymalizacji dyskretnej układów prętowych w postaci kratownic. Zastosowane podejście opiera się na algorytmie mrówkowym z funkcją kary, w którym zastosowano ewolucyjną optymalizację strukturalną w celu uwzględnienia optymalizacji topologicznej konstrukcji. Przedstawiony przykład numeryczny ilustruje skuteczność zaproponowanej metody optymalizacji.
EN
The paper presents an Ant Colony Optimization (ACO) algorithm designed to solve global discrete optimization problems of bar systems in the form of trusses. Proposed approach is based on the ACO algorithm with a penalty function in which evolutionary structural optimization has been applied to deal with the topological optimization of trusses. Presented numerical example illustrates the effectiveness of the proposed discrete optimization method.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper a construction scheduling problem – namely flowshop – with minimizing the sum of penalties for exceeding the deadline of building structures completion is considered. The problem is illustrated by the investment task concerning the implementation of twelve apartment buildings forming a part of a new housing estate. Uncertain parameters of the system are represented either by fuzzy numbers or random variables, whereas random variables have normal or the Erlang distribution. Since even the deterministic version of the problem is strongly NP-hard, the approximate algorithm based on the tabu search method was used to its solution. The performed computational experiments showed large solution resistance against any potential interference of parameters of the problem.
W artykule przedstawiony został nowoczesny system obliczeń rozproszonych, umożliwiający łatwe wykorzystanie dostępnych zasobów obliczeniowych przedsiębiorstwa. Opracowany system pozwala na przygotowanie planów produkcji w oparciu o różne modele matematyczne. Do rozwiązania problemów został wykorzystany rozproszony algorytm genetyczny z różnymi reprezentacjami chromosomu oraz operatorami genetycznymi, dostosowanymi do specyfiki danego problemu. W ten sposób wykazana została uniwersalność zaproponowanego systemu i jego zdolność do rozwiązywania rzeczywistych problemów zarządzania produkcją.
EN
The article presents a modern system of distributed computing, allowing easy use of available computational resources of the company. The developed system allows for the generation of production plans based on various mathematical models. A distributed genetic algorithm with different solution representations and different genetic operators tailored to the specific problem is used to solve the problems. In this way, the universality of the proposed system and its ability to solve real problems of production management were demonstrated.
A metaheuristic proposed by us recently, Ant Colony Optimization (ACO) hybridized with socio-cognitive inspirations, turned out to generate interesting results compared to classic ACO. Even though it does not always find better solutions to the considered problems, it usually finds sub-optimal solutions usually. Moreover, instead of a trial-and-error approach to configure the parameters of the ant species in the population, in our approach, the actual structure of the population emerges from predefined species-to-species ant migration strategies. Experimental results of our approach are compared against classic ACO and selected socio-cognitive versions of this algorithm.
In the paper, a problem of scheduling operations in the cyclic flexible job shop system is considered. A new, very fast method of determining the cycle time for any order of tasks on machines is also presented. It is based on the analysis of the paths in the graph representing the examined problem. The theorems concerning specific properties of the graph are proven and used in the construction of the heuristic algorithm searching the solutions space by using the so-called golf neighborhood, which is generated in a way similar to the game of golf, which helps to intensify and diversify calculations. The conducted computational experiments fully confirmed the effectiveness of the proposed method. The proposed methods and properties can be adapted and used in the construction of local search algorithms for solving many other optimization problems.
KOALA has been created with the idea of C++ library templates, implementing a broad set of procedures in the fields of algorithmic graph theory and network problems in discrete optimization. During the C2 NIWA project, a library has been greatly extended, the code refactored and enclosed with the internet service available in the public repository of the project. Today it contains interconnected educational materials in the form of Wikibook, documentation and sample codes, a multifunctional web-based application for edition of graphs, a collection of over 100 web services which offers a library of selected procedures to be run on the BeesyCluster system.
This paper deals with some computational study of multi-criteria optimization in fuel distribution problem. We consider vehicle routing problem, e.g. routing of a fleet of tank trucks, for one of the famous polish petroleum companies. For the purpose of solving this problem, we developed the random search algorithm, which explores the broad range of feasible sets of routes and searches for non-dominated multi-criteria solutions. The problem is examined on real data, which contains distances between 50 petrol stations and one central warehouse (refinery). Obtained results indicate, that it is possible to obtain single solution and satisfy both optimization criteria. Based on the analysis of the collected data, we formulate a number of proposals useful in future for construction of algorithms for multi-criteria fuel distribution optimization.
In this paper a multi-criteria approach to the 3-dimensions bin packing problem is considered. The chosen maximization criteria are the number and the total volume of the boxes loaded into the container. Existing solution representation and decoding method are applied to the problem. Next, two metaheuristic algorithms, namely simulated annealing and genetic algorithm are developed using the TOPSIS method for solution evaluation. Both algorithms are then used to obtain approximations of the Pareto front for a set of benchmarks from the literature. Despite the fact that both criteria work in favor of each other, we managed to obtain multiple solutions in many cases, proving that lesser number of boxes can lead to better utilization of the container volume and vice versa. We also observed, that the genetic algorithms performs slightly better in our test both in the terms of hyper-volume indicator and number of non-dominated solutions.
Artykuł dotyczy istotnej w ostatnim czasie problematyki planowania zrównoważonego rozwoju transportu pasażerskiego w ramach jednostek terytorialnych ze szczególnym uwzględnieniem transportu regionalnego (obejmującego przekraczanie granic powiatów). Zagadnienia planowania i optymalizacji publicznego transportu zbiorowego ze względu na kierunki jego rozwoju wymagają wnikliwego podejścia do jego planowania, jak i oceny. Problem badawczy stanowiło opracowanie spójnej metodyki umożliwiającej planowanie zrównoważonego rozwoju transportu w ramach jednostek terytorialnych. Opracowana metodyka składa się z czterech etapów merytorycznych: pozyskiwania dostępnych danych i dokumentów formalnych, kompleksowych badań ruchu, przetworzenia danych oraz optymalizacji oferty PTZ. Po ich przeprowadzeniu możliwe jest sporządzenie planu zrównoważonego rozwoju PTZ. Nowatorski walor stanowi tutaj procedura optymalizacyjna realizowana w ramach etapu czwartego. Jest ona prowadzona w dwóch zasadniczych krokach: optymalizacji najkorzystniejszych pod względem czasu połączeń oraz autorskiej metody heurystycznej wybierającej linie PTZ ze zbioru rozwiązań dopuszczalnych. Zaproponowana procedura ta została zaimplementowana w uniwersalnym narzędziu, pozwalającym na wspomnianą optymalizację.
EN
This article deals with what is currently considered a matter of increasing importance, i.e. the issues of planning sustained public transport used by passengers within territorial units as well as this used by people who travel across several counties. Due to the directions of its development, planning and optimization of public transport calls for an inquisitive approach both towards planning and its evaluation. The research problem was to develop a concise methodology of planning of sustained transport development within territorial units. The prepared methodology consists of four essential stages: acquiring data and formal documents, conducting all-embracing traffic studies, data processing, and finally, optimizing the PTZ offer. Having completed all these stages, a plan of sustained development of PTZ can be prepared. The innovative optimization procedure used at the fourth stage of the study is carried out in two steps: optimization of the most time-efficient connections and preparing a heuristic authorial methodology for choosing PTZ lines from the set of allowed solutions. The developed procedure was implemented into a universal tool which allows the aforesaid optimization.
The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree. While doing this, all possible realizations of the edge costs should be taken into account. This issue belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation method and adapted to the analysed problem has been proposed. The paper also contains the results of numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms known in the literature. The research is based on a large number of various test examples taken from the literature.
This article presents an integrated approach to optimize the different functions in a supply chain on strategic tactical and operational levels. The integrated supply chain model has been formulated as a cost minimization problem in the form of MILP (Mixed Integer Linear Programming). The costs of production, transport, distribution and environmental protection were adopted as optimization criteria. Timing, volume, capacity and mode of transport were also taken into account. The model was implemented in the LINGO package. The implementation model and the numerical tests are presented and discussed. The numerical experiments were carried out using sample data to show the possibilities of practical decision support and optimization of the supply chain.
In this paper, we present the application of the Differential Evolution (DE) algorithm to solving the combinatorial problem. The advantage of the DE algorithm is its capability of avoiding so-called "local minima" within the considered search space. Thanks to the special operator of the adaptive mutation, it is possible to direct the searching process within the solution space. The DE algorithm applies the selection operator that selects from the child population only the offspring with the greater value of the fitness function in comparison to their parents. An algorithm applied to a combinatorial optimization problem: Sudoku puzzle is presented. Sudoku consists of a nine by nine grid, divided into nine three by three boxes. Each of the eighty-one squares should be filled in with a number between one and nine. In this article we show, that the mutation schema has significant impact on the quality of created solution.
PL
W artykule przedstawimy propozycję zastosowania algorytmu ewolucji różnicowej do rozwiązywania problemów kombinatorycznych. Przewagą ewolucji różnicowej jest zdolność do unikania optimów lokalnych w przestrzeni przeszukiwań. Specjalny operator mutacji pozwala ukierunkować proces poszukiwań rozwiązania. W ewolucji różnicowej stosowany jest operator selekcji, który promuje tylko najlepiej przystosowane osobniki z populacji rodziców i potomków. Przedstawimy zastosowanie opisanego algorytmu do problemu rozwiązywania Sudoku. Sudoku składa się z planszy 9 na 9, podzielonej na 9 sekcji -każda o rozmiarze 3 na 3 elementy. Każda z 81 kratek powinna zostać wypełniona wartością z przedziału 1 do 9. W artykule pokażemy, że ewolucja różnicowa pozwala na rozwiązywanie Sudoku.
A basic resource allocation problem with uncertain costs has been discussed. The problem is to minimize the total cost of choosing exactly p items out of n available. The uncertain item costs are specified as a discrete scenario set and the minmax criterion is used to choose a solution. This problem is known to be NP-hard, but several approximation algorithms exist. The aim of this paper is to investigate the quality of the solutions returned by these approximation algorithms. According to the results obtained, the randomized algorithms described are fast and output solutions of good quality, even if the problem size is large.
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.
Problem optymalizacji rozdziału palet jest jednym z wielu problemów optymalizacyjnych pojawiających się we współcześnie funkcjonujących centrach dystrybucyjnych. Jest jednak jednym z kluczowych problemów poza optymalizacją tras, optymalizacją rozmieszczenia zapasów w magazynach wysokiego składowania itp. Dodatkowo należy podkreślić, że problem optymalizacji rozdziału palet obejmuje horyzont krótkookresowy np. dobę. W artykule przedstawiony został model matematyczny optymalizacji rozdziału palet oraz jego implementacja. Przedstawiono również przykłady liczbowe optymalizacji. Jako środowisko implementacjii rozwiązania modelu zaproponowano deklaratywne środowisko programowania w logice z ograniczeniami CLP (Constraint Logic Programming).
EN
Problem of optimizing the allocation of pallets is one of many problems in modern distribution centers. It is one of very important problems, except for e.g. routing optimization, space optimization etc. Additionally, it should be noted that the problem of optimizing the allocation of pallets for routes and trucks is a short-run horizon, e.g. every day, process. The optimization and implementation model of that problem is presented in this paper. A solution of this model for numerical examples is also described. As a solution the environment constraint logic programming (CLP) environment has been used. CLP combines the declarative logic based programming with specialized constraint solving methods from artificial intelligence, Operations Research (OR) and mathematics. It allows the clear and concise expression of a wide class of combinatorial problems together with their efficient solution. In parallel with ongoing research in this field, CLP is now increasingly used to tackle real world decision making problems.
20
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In many decision making problems, the facility location and route design subproblems are commonly approached separately. This standard practice results in conceptually simpler models, but it often turns out to be too constraining and inaccurate. We propose a mathematical modeling framework of a wide applicability that enriches the locational analysis with the routing aspect, and leads to joint location-routing binary optimization problem. The usefulness of this general framework is presented through an application example in a merchandise delivery of online shopping companies (business-to-consumer e-commerce). Other applications for logistic systems as well as for computer systems are also described and justified. The main advantage of the proposed approach comes out from the precise contrasting suppliers' and consumers' needs. Moreover, if a repeated relocation of facilities is under consideration then taking the long-term planning horizon into account is necessary to obtain realistic and competitive results. Static and dynamic versions of the optimization problem are introduced for which the heuristic solution algorithm based on the Lagrange relaxation and the dynamic programming approach are respectively presented.
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ć.