Search results for: convex feasibility problem

Authors: Thanin Sitthiwirattham, Jiraporn Reunsumrit

Abstract:

We study the existence of positive solutions to the three points difference-summation boundary value problem. We show the existence of at least one positive solution if f is either superlinear or sublinear by applying the fixed point theorem due to Krasnoselskii in cones.

Keywords: Positive solution, Boundary value problem, Fixed point theorem, Cone.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1701

Authors: Julija Asmuss, Gunars Lauks, Viktors Zagorskis

Abstract:

We consider the problem of bandwidth allocation in a substrate network as an optimization problem for the aggregate utility of multiple applications with diverse requirements and describe a simulation scheme for dynamically adaptive bandwidth allocation protocols. The proposed simulation model based on Coloured Petri Nets (CPN) is realized using CPN Tools.

Keywords: Bandwidth Allocation Problem, Coloured Petri Nets, CPN Tools, Simulation

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1953

Authors: Siliang Wang, Minghui Wang

Abstract:

This work proposes a novel market-based air traffic flow control model considering competitive airlines in air traffic network. In the flow model, an agent based framework for resources (link/time pair) pricing is described. Resource agent and auctioneer for groups of resources are also introduced to simulate the flow management in Air Traffic Control (ATC). Secondly, the distributed group pricing algorithm is introduced, which efficiently reflect the competitive nature of the airline industry. Resources in the system are grouped according to the degree of interaction, and each auctioneer adjust s the price of one group of resources respectively until the excess demand of resources becomes zero when the demand and supply of resources of the system changes. Numerical simulation results show the feasibility of solving the air traffic flow control problem using market mechanism and pricing algorithms on the air traffic network.

Keywords: Air traffic control, Nonlinear programming, Marketmechanism, Route policy.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1802

Authors: Omar Farahat Hassanein, A. Samer Ezeldin

Abstract:

The construction industry is a very dynamic field. Every day new technologies and methods are developed to fasten the process and increase its efficiency. Hence, if a project uses fewer resources it will be more efficient.

This paper examines the recycling of concrete construction and demolition (C&D) waste to reuse it as aggregates in on-site applications for construction projects in Egypt and possibly in the Middle East. The study focuses on a stationary plant setting. The machinery set-up used in the plant is analyzed technically and financially.

The findings are gathered and grouped to obtain a comprehensive cost-benefit financial model to demonstrate the feasibility of establishing and operating a concrete recycling plant. Furthermore, a detailed business plan including the time and hierarchy is proposed. 

Keywords: Construction wastes, recycling, sustainability, financial model, concrete recycling, concrete life cycle.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3303

Authors: Wayan F. Mahmudy, Romeo M. Marian, Lee H. S. Luong

Abstract:

This paper and its companion (Part 2) deal with modeling and optimization of two NP-hard problems in production planning of flexible manufacturing system (FMS), part type selection problem and loading problem. The part type selection problem and the loading problem are strongly related and heavily influence the system-s efficiency and productivity. The complexity of the problems is harder when flexibilities of operations such as the possibility of operation processed on alternative machines with alternative tools are considered. These problems have been modeled and solved simultaneously by using real coded genetic algorithms (RCGA) which uses an array of real numbers as chromosome representation. These real numbers can be converted into part type sequence and machines that are used to process the part types. This first part of the papers focuses on the modeling of the problems and discussing how the novel chromosome representation can be applied to solve the problems. The second part will discuss the effectiveness of the RCGA to solve various test bed problems.

Keywords: Flexible manufacturing system, production planning, part type selection problem, loading problem, real-coded genetic algorithm

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2086

Authors: Bubaker M. F. Bushofa, Abdel Hafez A. Azab

Abstract:

This article is based on the technique which is called Discrete Parameter Tracking (DPT). First introduced by A. A. Azab [8] which is applicable for less order reference model. The order of the reference model is (n-l) and n is the number of the adjustable parameters in the physical plant. The technique utilizes a modified gradient method [9] where the knowledge of the exact order of the nonadaptive system is not required, so, as to eliminate the identification problem. The applicability of the mentioned technique (DPT) was examined through the solution of several problems. This article introduces the solution of a third order system with three adjustable parameters, controlled according to second order reference model. The adjustable parameters have great initial error which represent condition. Computer simulations for the solution and analysis are provided to demonstrate the simplicity and feasibility of the technique.

Keywords: Adaptive Control System, Discrete Parameter Tracking, Discrete Time Model.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1044

Authors: Dariusz Barbucha, Piotr Jedrzejowicz

Abstract:

The paper proposes and validates a new method of solving instances of the vehicle routing problem (VRP). The approach is based on a multiple agent system paradigm. The paper contains the VRP formulation, an overview of the multiple agent environment used and a description of the proposed implementation. The approach is validated experimentally. The experiment plan and the discussion of experiment results follow.

Keywords: multi-agent systems, population-based methods, vehiclerouting problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2227

Authors: Anthony Wachs, Guillaume Vinay, Gilles Ferrer, Jacques Kouakou, Calin Dan, Laurence Girolami

Abstract:

An original Direct Numerical Simulation (DNS) method to tackle the problem of particulate flows at moderate to high concentration and finite Reynolds number is presented. Our method is built on the framework established by Glowinski and his coworkers [1] in the sense that we use their Distributed Lagrange Multiplier/Fictitious Domain (DLM/FD) formulation and their operator-splitting idea but differs in the treatment of particle collisions. The novelty of our contribution relies on replacing the simple artificial repulsive force based collision model usually employed in the literature by an efficient Discrete Element Method (DEM) granular solver. The use of our DEM solver enables us to consider particles of arbitrary shape (at least convex) and to account for actual contacts, in the sense that particles actually touch each other, in contrast with the simple repulsive force based collision model. We recently upgraded our serial code, GRIFF 1 [2], to full MPI capabilities. Our new code, PeliGRIFF 2, is developed under the framework of the full MPI open source platform PELICANS [3]. The new MPI capabilities of PeliGRIFF open new perspectives in the study of particulate flows and significantly increase the number of particles that can be considered in a full DNS approach: O(100000) in 2D and O(10000) in 3D. Results on the 2D/3D sedimentation/fluidization of isometric polygonal/polyedral particles with collisions are presented.

Keywords: Particulate flow, distributed lagrange multiplier/fictitious domain method, discrete element method, polygonal shape, sedimentation, distributed computing, MPI

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2095

Authors: Yasuhito Tanaka

Abstract:

We present a constructive proof of Tychonoff’s fixed point theorem in a locally convex space for uniformly continuous and sequentially locally non-constant functions.

Keywords: sequentially locally non-constant functions, Tychonoff’s fixed point theorem, constructive mathematics.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1485

Authors: Vahid Mohammadi Saffarzadeh, Pourya Jafarzadeh, Masoud Mazloom

Abstract:

This paper presents a hybrid approach for solving nqueen problem by combination of PSO and SA. PSO is a population based heuristic method that sometimes traps in local maximum. To solve this problem we can use SA. Although SA suffer from many iterations and long time convergence for solving some problems, By good adjusting initial parameters such as temperature and the length of temperature stages SA guarantees convergence. In this article we use discrete PSO (due to nature of n-queen problem) to achieve a good local maximum. Then we use SA to escape from local maximum. The experimental results show that our hybrid method in comparison of SA method converges to result faster, especially for high dimensions n-queen problems.

Keywords: PSO, SA, N-queen, CSP

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1662

Authors: Pankaj Dutta, Debjani Chakraborty

Abstract:

This paper investigates the effect of product substitution in the single-period 'newsboy-type' problem in a fuzzy environment. It is supposed that the single-period problem operates under uncertainty in customer demand, which is described by imprecise terms and modelled by fuzzy sets. To perform this analysis, we consider the fuzzy model for two-item with upward substitution. This upward substitutability is reasonable when the products can be stored according to certain attribute levels such as quality, brand or package size. We show that the explicit consideration of this substitution opportunity increase the average expected profit. Computational study is performed to observe the benefits of product's substitution.

Keywords: Fuzzy demand, Newsboy, Single-period problem, Substitution.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1401

Authors: Majid Abdolrazzagh-Nezhad, Salwani Abdullah

Abstract:

The job-shop scheduling problem (JSSP) is an important decision facing those involved in the fields of industry, economics and management. This problem is a class of combinational optimization problem known as the NP-hard problem. JSSPs deal with a set of machines and a set of jobs with various predetermined routes through the machines, where the objective is to assemble a schedule of jobs that minimizes certain criteria such as makespan, maximum lateness, and total weighted tardiness. Over the past several decades, interest in meta-heuristic approaches to address JSSPs has increased due to the ability of these approaches to generate solutions which are better than those generated from heuristics alone. This article provides the classification, constraints and objective functions imposed on JSSPs that are available in the literature.

Keywords: Job-shop scheduling, classification, constraints, objective functions.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1907

Authors: Rajeev, N. K. Raigar

Abstract:

In this study, one dimensional phase change problem (a Stefan problem) is considered and a numerical solution of this problem is discussed. First, we use similarity transformation to convert the governing equations into ordinary differential equations with its boundary conditions. The solutions of ordinary differential equation with the associated boundary conditions and interface condition (Stefan condition) are obtained by using a numerical approach based on operational matrix of differentiation of shifted second kind Chebyshev wavelets. The obtained results are compared with existing exact solution which is sufficiently accurate.

Keywords: Operational matrix of differentiation, Similarity transformation, Shifted second kind Chebyshev wavelets, Stefan problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1980

Authors: Bita Tadayon, Nasser Salmasi

Abstract:

This research deals with a flexible flowshop scheduling problem with arrival and delivery of jobs in groups and processing them individually. Due to the special characteristics of each job, only a subset of machines in each stage is eligible to process that job. The objective function deals with minimization of sum of the completion time of groups on one hand and minimization of sum of the differences between completion time of jobs and delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FFc / rj , Mj / irreg which has many applications in production and service industries. A mathematical model is proposed, the problem is proved to be NPcomplete, and an effective heuristic method is presented to schedule the jobs efficiently. This algorithm can then be used within the body of any metaheuristic algorithm for solving the problem.

Keywords: flexible flowshop scheduling, group processing, machine eligibility constraint, mathematical modeling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1811

Authors: Young-Jun You, Youn-Ju Jeong, Min-Su Park, Du-Ho Lee

Abstract:

Due to a lot of limited conditions, a large box type floating structure is inevitably constructed by connecting many pontoons. When a floating structure is made with concrete, concrete shear key with saw-teeth shape is often used to carry shear force. Match casting for the shear key and precise construction on a sea are very important for making separated two pontoons as one body but those are not easy work and may increase construction time and cost. To solve this problem, one-way shear key is studied in this paper for a connected part where there is some difference between upward and downward shear force. It has only one inclined plane and can resist shear force in one direction. Big shear force is resisted by concrete which forms an inclined plane and small shear force is resisted by steel bar. This system can reduce manufacturing cost of individual pontoon and construction time and cost for constructing a floating structure on a sea. In this paper, the feasibility study about one-way shear key system is performed by comparing with design example.

Keywords: Connection, floating container terminal, pontoon, pre-stressing, shear key.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3096

Authors: S. Balaji, V. Swaminathan, K. Kannan

Abstract:

The Maximum Weighted Independent Set (MWIS) problem is a classic graph optimization NP-hard problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the MWIS problem is to find a vertex set S V whose total weight is maximum subject to no two vertices in S are adjacent. This paper presents a novel approach to approximate the MWIS of a graph using minimum weighted vertex cover of the graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the proposed algorithm can yield better solutions than other existing algorithms found in the literature for solving the MWIS.

Keywords: weighted independent set, vertex cover, vertex support, heuristic, NP - hard problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2017

Authors: Joselito Medina Marin, Norberto Hernández Romero, Juan Carlos Seck Tuoh Mora, Erick S. Martinez Gomez

Abstract:

The Flow Shop Scheduling Problem (FSSP) is a typical problem that is faced by production planning managers in Flexible Manufacturing Systems (FMS). This problem consists in finding the optimal scheduling to carry out a set of jobs, which are processed in a set of machines or shared resources. Moreover, all the jobs are processed in the same machine sequence. As in all the scheduling problems, the makespan can be obtained by drawing the Gantt chart according to the operations order, among other alternatives. On this way, an FMS presenting the FSSP can be modeled by Petri nets (PNs), which are a powerful tool that has been used to model and analyze discrete event systems. Then, the makespan can be obtained by simulating the PN through the token game animation and incidence matrix. In this work, we present an adaptive PN to obtain the makespan of FSSP by applying PN analytical tools.

Keywords: Flow-shop scheduling problem, makespan, Petri nets, state equation.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1718

Authors: K. C. Meher, R. K. Swain, C. K. Chanda

Abstract:

This paper gives an intuition regarding glowworm swarm optimization (GSO) technique to solve dynamic economic dispatch (DED) problems of thermal generating units. The objective of the problem is to schedule optimal power generation of dedicated thermal units over a specific time band. In this study, Glowworm swarm optimization technique enables a swarm of agents to split into subgroup, exhibit simultaneous taxis towards each other and rendezvous at multiple optima (not necessarily equal) of a given multimodal function. The feasibility of the GSO method has been tested on ten-unit-test systems where the power balance constraints, operating limits, valve point effects, and ramp rate limits are taken into account. The results obtained by the proposed technique are compared with other heuristic techniques. The results show that GSO technique is capable of producing better results.

Keywords: Dynamic economic dispatch, Glowworm swarm optimization, Luciferin, Valve–point loading effect, Ramp rate limits.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1301

Authors: Kamil Aida-zade, C. Ardil

Abstract:

In this paper, some problem formulations of dynamic object parameters recovery described by non-autonomous system of ordinary differential equations with multipoint unshared edge conditions are investigated. Depending on the number of additional conditions the problem is reduced to an algebraic equations system or to a problem of quadratic programming. With this purpose the paper offers a new scheme of the edge conditions transfer method called by conditions shift. The method permits to get rid from differential links and multipoint unshared initially-edge conditions. The advantage of the proposed approach is concluded by capabilities of reduction of a parametric identification problem to essential simple problems of the solution of an algebraic system or quadratic programming.

Keywords: dynamic objects, ordinary differential equations, multipoint unshared edge conditions, quadratic programming, conditions shift

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1444

Authors: K. -H. Yang

Abstract:

Supplier selection problem is one of the important issues of supply chain problems. Two categories of methodologies include qualitative and quantitative approaches which can be applied to supplier selection problems. However, due to the complexities of the problem and lacking of reliable and quantitative data, qualitative approaches are more than quantitative approaches. This study considers operational cost and supplier’s reliability factor and solves the problem by using a quantitative approach. A mixed integer programming model is the primary analytic tool. Analyses of different scenarios with variable cost and reliability structures show that the effectiveness of this approach to the supplier selection problem.

Keywords: Mixed integer programming, quantitative approach, supplier’s reliability, supplier selection.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2532

Authors: Ali A. Sayadi, Thomas R. Neitzert, G. Charles Clifton

Abstract:

Lightweight concrete is being used in the construction industry as a building material in its own right. Ultra-lightweight concrete can be applied as a filler and support material for the manufacturing of composite building materials. This paper is about the development of a stable and reproducible ultra-lightweight concrete with the inclusion of poly-lactic acid (PLA) beads and assessing the feasibility of PLA as a lightweight aggregate that will deliver advantages such as a more eco-friendly concrete and a non-petroleum polymer aggregate. In total, sixty-three samples were prepared and the effectiveness of mineral admixture, curing conditions, water-cement ratio, PLA ratio, EPS ratio and perlite ratio on compressive strength of perlite concrete are studied. The results show that PLA particles are sensitive to alkali environment of cement paste and considerably shrank and lost their strength. A higher compressive strength and a lower density was observed when expanded polystyrene (EPS) particles replaced PLA beads. In addition, a set of equations is proposed to estimate the water-cement ratio, cement content and compressive strength of perlite concrete.

Keywords: Perlite concrete, poly-lactic acid, expanded polystyrene, concrete.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2211

Authors: Flur R. Ismagilov, Vyacheslav E. Vavilov, Denis V. Gusakov

Abstract:

This paper is devoted to solve the problem of increasing the electrification of aircraft engines by installing a synchronous generator at high pressure shaft. Technical solution of this problem by various research centers is discussed. A design solution of the problem was proposed. To evaluate the effectiveness of the proposed cooling system, thermal analysis was carried out in ANSYS software.

Keywords: Flur R. Ismagilov, Vyacheslav E. Vavilov, Denis V. Gusakov

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1245

Authors: Lianglin Xiong, Shouming Zhong, Mao Ye

Abstract:

This paper addresses the stabilization issues for a class of uncertain switched neutral systems with nonlinear perturbations. Based on new classes of piecewise Lyapunov functionals, the stability assumption on all the main operators or the convex combination of coefficient matrices is avoid, and a new switching rule is introduced to stabilize the neutral systems. The switching rule is designed from the solution of the so-called Lyapunov-Metzler linear matrix inequalities. Finally, three simulation examples are given to demonstrate the significant improvements over the existing results.

Keywords: Switched neutral system, piecewise Lyapunov functional, nonlinear perturbation, Lyapunov-Metzler linear matrix inequality.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1640

Authors: Y. Abdelrazig

Abstract:

Evolutionary optimization methods such as genetic algorithms have been used extensively for the construction site layout problem. More recently, ant colony optimization algorithms, which are evolutionary methods based on the foraging behavior of ants, have been successfully applied to benchmark combinatorial optimization problems. This paper proposes a formulation of the site layout problem in terms of a sequencing problem that is suitable for solution using an ant colony optimization algorithm. In the construction industry, site layout is a very important planning problem. The objective of site layout is to position temporary facilities both geographically and at the correct time such that the construction work can be performed satisfactorily with minimal costs and improved safety and working environment. During the last decade, evolutionary methods such as genetic algorithms have been used extensively for the construction site layout problem. This paper proposes an ant colony optimization model for construction site layout. A simple case study for a highway project is utilized to illustrate the application of the model.

Keywords: Construction site layout, optimization, ant colony.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3089

Authors: A. Shirzadeh Chaleshtari, Sh. Shadrokh

Abstract:

Renewable and non-renewable resource constraints have been vast studied in theoretical fields of project scheduling problems. However, although cumulative resources are widespread in practical cases, the literature on project scheduling problems subject to these resources is scant. So in order to study this type of resources more, in this paper we use the framework of a resource constrained project scheduling problem (RCPSP) with finish-start precedence relations between activities and subject to the cumulative resources in addition to the renewable resources. We develop a branch and bound algorithm for this problem customizing precedence tree algorithm of RCPSP. We perform extensive experimental analysis on the algorithm to check its effectiveness and performance for solving different instances of the problem in question.

Keywords: Resource constrained project scheduling problem, cumulative resources, branch and bound algorithm, precedence tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2887

Authors: Bin Cai, Shilong Wang, Haibo Hu

Abstract:

The job shop scheduling problem (JSSP) is well known as one of the most difficult combinatorial optimization problems. This paper presents a hybrid genetic algorithm for the JSSP with the objective of minimizing makespan. The efficiency of the genetic algorithm is enhanced by integrating it with a local search method. The chromosome representation of the problem is based on operations. Schedules are constructed using a procedure that generates full active schedules. In each generation, a local search heuristic based on Nowicki and Smutnicki-s neighborhood is applied to improve the solutions. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.

Keywords: Genetic algorithm, Job shop scheduling problem, Local search, Meta-heuristic algorithm

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1637

Authors: Pricillia Priska Sianita

Abstract:

An aesthetic facial profile is one of the goals in Orthodontics treatment. However, this is not easily achieved, especially in patients with Class II Division 1 malocclusion who have the clinical characteristics of convex profile and significant skeletal discrepancy due to mandibular growth deficiency. Malocclusion with skeletal problems require proper treatment timing for growth stimulation, and it must be done in early age and in need of good cooperation from the patient. If this is not done and the patient has passed the growth period, the ideal treatment is orthognathic surgery which is more complicated and more painful. The growth stimulation of skeletal malocclusion requires a careful cephalometric evaluation ranging from diagnosis to determine the parts that require stimulation to post-treatment evaluation to see the success achieved through changes in the measurement of the skeletal parameters shown in the cephalometric analysis. This case report aims to describe skeletal changes cephalometrically that were achieved through orthodontic treatment in growing period. Material and method: Lateral Cephalograms, pre-treatment, and post-treatment of cases of Class II Division 1 malocclusion is selected from a collection of cephalometric radiographic in a private clinic. The Cephalogram is then traced and measured for the skeletal parameters. The result is noted as skeletal condition data of pre-treatment and post-treatment. Furthermore, superimposition is done to see the changes achieved. The results show that growth stimulation through orthodontic treatment can solve the skeletal problem of Class II Division 1 malocclusion and the skeletal changes that occur can be verified through cephalometric analysis. The skeletal changes have an impact on the improvement of patient's facial profile. To sum up, the treatment timing on a skeletal malocclusion is very important to obtain satisfactory results for the improvement of the aesthetic facial profile, and skeletal changes can be verified through cephalometric evaluation of pre- and post-treatment.

Keywords: Cephalometric evaluation, Class II Division 1 malocclusion, growth stimulation, skeletal changes, skeletal problems.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1104

Authors: Sayyed R Mousavi

Abstract:

The Far From Most Strings Problem (FFMSP) is to obtain a string which is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are said to be far if their hamming distance is greater than or equal to a given positive integer. FFMSP belongs to the class of sequences consensus problems which have applications in molecular biology. The problem is NP-hard; it does not admit a constant-ratio approximation either, unless P = NP. Therefore, in addition to exact and approximate algorithms, (meta)heuristic algorithms have been proposed for the problem in recent years. On the other hand, in the recent years, hybrid algorithms have been proposed and successfully used for many hard problems in a variety of domains. In this paper, a new metaheuristic algorithm, called Constructive Beam and Local Search (CBLS), is investigated for the problem, which is a hybridization of constructive beam search and local search algorithms. More specifically, the proposed algorithm consists of two phases, the first phase is to obtain several candidate solutions via the constructive beam search and the second phase is to apply local search to the candidate solutions obtained by the first phase. The best solution found is returned as the final solution to the problem. The proposed algorithm is also similar to memetic algorithms in the sense that both use local search to further improve individual solutions. The CBLS algorithm is compared with the most recent published algorithm for the problem, GRASP, with significantly positive results; the improvement is by order of magnitudes in most cases.

Keywords: Bioinformatics, Far From Most Strings Problem, Hybrid metaheuristics, Matheuristics, Sequences consensus problems.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1716

Authors: J. Cheeneebash, V. Beeharry, A. Gopaul

Abstract:

The aim of this paper is to express the input-output matrix as a linear ordering problem which is classified as an NP-hard problem. We then use a Tabu search algorithm to find the best permutation among sectors in the input-output matrix that will give an optimal solution. This optimal permutation can be useful in designing policies and strategies for economists and government in their goal of maximizing the gross domestic product.

Keywords: Input-Output matrix, linear ordering problem, Tabusearch.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1474

Authors: Adam Roman

Abstract:

Finding synchronizing sequences for the finite automata is a very important problem in many practical applications (part orienters in industry, reset problem in biocomputing theory, network issues etc). Problem of finding the shortest synchronizing sequence is NP-hard, so polynomial algorithms probably can work only as heuristic ones. In this paper we propose two versions of polynomial algorithms which work better than well-known Eppstein-s Greedy and Cycle algorithms.

Keywords: Synchronizing words, reset sequences, Černý Conjecture

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1574