The assignment of work uniformly, across an available group of processors, represent an important problem in parallel computing. The efficiency of the workload balancing is obtained by a proper partitioning strategy, which is a challenging task. Partitioning is an important concept connected to various other problems in modern computing field and also an extensively-studied problem in graph-based analysis. The computational graph in parallel computing model defines units of computations (or tasks) as nodes and data dependencies (or communications) between units as edges. A k-way graph balanced partitioning algorithm is proposed, with the objectives of partitioning the graph nodes into k equal sized disjoint components, while minimizing the number of edges crossing between components. This edge partition model is suggestive for mapping computations to processors, while reducing the interprocessors communications. The partitioning problem turned out to be a NP-hard problem of combinatorial optimization, so we proposed a Genetic Algorithm with fuzzy adaptation of parameters for determining optimal partitions within a reasonable amount of time. The performance of the partitions was assessed based on two performance metrics, namely density and conductance. Based on randomly generated application workflows, experiments with different values of k were performed to demonstrate computational capabilities of the proposed algorithm.
The optimization of production systems processes is driven by the international competition and the manufacturing technological advances. In recent years, more attention has been given to assess the potential advantages of using the innovative technology to elaborate different scheduling solution procedures in order to balance production efficiency and obtain high levels of productivity. Computerized scheduling systems for process operations can be used to achieve high system utilization: to identify and eliminate weaknesses and avoid unscheduled failures and resource waste. In this study, we extend the general scheduling framework to model a specific machine-scheduling problem that characterizes real industrial frameworks with more complex functional demands: precedence-constrained tasks, individual processing times of operations on different machines and communication cost between tasks that are not assigned to the same machine. The specificity of this problem generates an increased complexity and needs higher computational effort compared to a classical task-scheduling problem. The problem is modeled as a Mixed Integer-Linear Programming (MILP) formulation and is solved using a Particle Swarm Optimization approach - a heuristic population-based global optimization method that performs well in difficult multi-objective optimization problems arising in computer science and engineering. The proposed workflow task scheduling and allocation algorithm was tested on several randomly generated test instances. Experiments have shown valid scheduling results: minimum schedule lengths were obtained, while task-precedence constraints are fulfilled. We also noticed good computational experience even when problem size was increased.
This paper aims to investigate graph-related telecommunication problems from a conceptual modelling point of view, based on the argument that a wide range of efficient algorithms for these computational problems can be framed within three design paradigms, namely Backtracking, Divide and Conquer and Greedy approach. First of all, such an abstract design technique represents a general problem-solving template that can be used for a broad range of problems in a large variety of applications domains, whose resolution will thus materialize in specific instances of that procedure; the procedure shall be further implemented in any programming language. Secondly, it is important because it guides the researchers in the field and facilitates the development of new and useful algorithms for other graph-structured computational problems.
This study aims at providing an efficient method to solve the statistical file merging issue: merging two or more files containing distinct datasets, from different sources, where the items of the datasets do not overlap (the percentage of units that are common to all datasets is insignificant). The problem is modeled as a network transportation problem and is solved using an adaptive Genetic Algorithm based on fuzzy logic controller, which dynamically calibrates algorithm parameters. This evolutionary technique is convenient for large-scale optimization problems with a significant number of variables and logical constraints. It also provides researchers in the fields of statistics and optimization a valuable instrument for achieving a correct balance between the quality of solutions and the processing time. This is a critical demand in most of the practical optimization problems. Numerical experiments on selected test instances validate this generalized merging approach and proves that the results of this file merging simulation can be extrapolated for better integration of various datasets generated by numerous government, administrative and statistical agencies. Apart from better central financial reporting for example, this will help to expand cooperation between private sector and government institutions.
In a collaborative organization, the partner selection problem consists of selecting the best combination of partners capable to accomplish all the project tasks, considering both quantitative and qualitative critical factors. The problem here considers a project that can be divided into a number of sub-projects (business processes or tasks) and for each task, several candidates are possible. Due to the existing relationships between tasks, this can be seen as a network structure containing a set of potential partners connected with each other. The process is modeled as a multi-criteria optimization problem that requires trade-offs between contradictory criteria: internal and collaboration costs, processing time and risk of failure.
Due to the non-linearity and large scale of the problem (considerable number of alternatives and different criteria), global powerful optimization techniques are needed. In this study, we have implemented a multi-objective particle swarm optimization algorithm, augmented with an additional fuzzy controller for tuning algorithm parameters in order to determine an effective approximation of the Pareto front.
Computational results have shown that the algorithm is able to produce high-quality solutions for all tested instances. Moreover, the algorithm is very flexible and able to obtain non-dominated alternative solutions for different scenarios and alternatives in the design of virtual enterprises.
Partitioning is one of the biggest challenges in computer-aided design for VLSI circuits (very large-scale integrated circuits). This work address the min-cut balanced circuit partitioning problem– dividing the graph that models the circuit into almost equal sized k sub-graphs while minimizing the number of edges cut i.e. minimizing the number of edges connecting the sub-graphs. The problem may be formulated as a combinatorial optimization problem. Experimental studies in the literature have shown the problem to be NP-hard and thus it is important to design an efficient heuristic algorithm to solve it. The approach proposed in this study is a parallel implementation of a genetic algorithm, namely an island model. The information exchange between the evolving subpopulations is modeled using a fuzzy controller, which determines an optimal balance between exploration and exploitation of the solution space. The results of simulations show that the proposed algorithm outperforms the standard sequential genetic algorithm both in terms of solution quality and convergence speed. As a direction for future study, this research can be further extended to incorporate local search operators which should include problem-specific knowledge. In addition, the adaptive configuration of mutation and crossover rates is another guidance for future research.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.