Search results for: heuristic approach

Authors: D.Venkatesan, K.Kannan, S. Raja Balachandar

Abstract:

In this paper a new Genetic Algorithm based on a heuristic operator and Centre of Mass selection operator (CMGA) is designed for the unbounded knapsack problem(UKP), which is NP-Hard combinatorial optimization problem. The proposed genetic algorithm is based on a heuristic operator, which utilizes problem specific knowledge. This center of mass operator when combined with other Genetic Operators forms a competitive algorithm to the existing ones. Computational results show that the proposed algorithm is capable of obtaining high quality solutions for problems of standard randomly generated knapsack instances. Comparative study of CMGA with simple GA in terms of results for unbounded knapsack instances of size up to 200 show the superiority of CMGA. Thus CMGA is an efficient tool of solving UKP and this algorithm is competitive with other Genetic Algorithms also.

Keywords: Genetic Algorithm, Unbounded Knapsack Problem, Combinatorial Optimization, Meta-Heuristic, Center of Mass

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

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 1608

Authors: Zeyu Zhang, Guisheng Yin, Ziying Zhang, Liguo Zhang

Abstract:

This paper mainly studies the path planning method based on ant colony optimization (ACO), and proposes heuristic integration ant colony optimization (HIACO). This paper not only analyzes and optimizes the principle, but also simulates and analyzes the parameters related to the application of HIACO in path planning. Compared with the original algorithm, the improved algorithm optimizes probability formula, tabu table mechanism and updating mechanism, and introduces more reasonable heuristic factors. The optimized HIACO not only draws on the excellent ideas of the original algorithm, but also solves the problems of premature convergence, convergence to the sub optimal solution and improper exploration to some extent. HIACO can be used to achieve better simulation results and achieve the desired optimization. Combined with the probability formula and update formula, several parameters of HIACO are tested. This paper proves the principle of the HIACO and gives the best parameter range in the research of path planning.

Keywords: Ant colony optimization, heuristic integration, path planning

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

Authors: N. Pritchard

Abstract:

Within architectural education, students arrive fore-armed with; their life-experience; knowledge gained from subject-based learning; their brains and more specifically their imaginations. The learning-by-doing that they embark on in studio-based/project-based learning calls for supervision that allows the student to proactively undertake research and experimentation with design solution possibilities. The degree to which this supervision includes direction is subject to debate and differing opinion. It can be argued that if the student is to learn-by-doing, then design decision making within the design process needs to be instigated and owned by the student so that they have the ability to personally reflect on and evaluate those decisions. Within this premise lies the problem that the student's endeavours can become unstructured and unfocused as they work their way into a new and complex activity. A resultant weakness can be that the design activity is compartmented and not holistic or comprehensive, and therefore, the student's reflections are consequently impoverished in terms of providing a positive, informative feedback loop. The construct proffered in this paper is that a supportive 'armature' or 'Heuristic-Framework' can be developed that facilitates a holistic approach and reflective learning. The normal explorations of architectural design comprise: Analysing the site and context, reviewing building precedents, assimilating the briefing information. However, the student can still be compromised by 'not knowing what they need to know'. The long-serving triad 'Firmness, Commodity and Delight' provides a broad-brush framework of considerations to explore and integrate into good design. If this were further atomised in subdivision formed from the disparate aspects of architectural design that need to be considered within the design process, then the student could sieve through the facts more methodically and reflectively in terms of considering their interrelationship conflict and alliances. The words facts and sieve hold the acronym of the aspects that form the Heuristic-Framework: Function, Aesthetics, Context, Tectonics, Spatial, Servicing, Infrastructure, Environmental, Value and Ecological issues. The Heuristic could be used as a Hermeneutic Model with each aspect of design being focused on and considered in abstraction and then considered in its relation to other aspect and the design proposal as a whole. Importantly, the heuristic could be used as a method for gathering information and enhancing the design brief. The more poetic, mysterious, intuitive, unconscious processes should still be able to occur for the student. The Heuristic-Framework should not be seen as comprehensive prescriptive formulaic or inhibiting to the wide exploration of possibilities and solutions within the architectural design process.

Keywords: Atomistic, hermeneutic, holistic, approach architectural design studio education.

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

Authors: N. Manavizadeh, M. Hosseini, M. Rabbani

Abstract:

In the last decades to supply the various and different demands of clients, a lot of manufacturers trend to use the mixedmodel assembly line (MMAL) in their production lines, since this policy make possible to assemble various and different models of the equivalent goods on the same line with the MTO approach. In this article, we determine the sequence of (MMAL) line, with applying the kitting approach and planning of rest time for general workers to reduce the wastages, increase the workers effectiveness and apply the sector of lean production approach. This Multi-objective sequencing problem solved in small size with GAMS22.2 and PSO meta heuristic in 10 test problems and compare their results together and conclude that their results are very similar together, next we determine the important factors in computing the cost, which improving them cost reduced. Since this problem, is NPhard in large size, we use the particle swarm optimization (PSO) meta-heuristic for solving it. In large size we define some test problems to survey it-s performance and determine the important factors in calculating the cost, that by change or improved them production in minimum cost will be possible.

Keywords: Mixed-Model Assembly Line, particle swarmoptimization, Multi-objective sequencing problem, MTO system, kitto-assembly, rest time

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

Authors: Heejung Lee

Abstract:

Performance management seems to be essential in business area and is also an exciting topic. Despite significant and myriads of research efforts, performance management guide today as a rigorous approach is still in an immature state and metrics are often selected based on intuitive and heuristic approach. In R&D side, the difficulty to guide the proper performance management is even more increasing due to the natural characteristics of R&D such as unique or domain-specific problems. In our approach, we present R&D performance management guide considering various characteristics of R&D side: performance evaluation objectives, dimensions, metrics, and uncertainties of R&D sector.

Keywords: Performance management, R&D, metrics.

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

Authors: Adel Bouchakhchoukha, Hakim Akeb

Abstract:

In this work, we propose a hybrid heuristic in order to solve the Team Orienteering Problem (TOP). Given a set of points (or customers), each with associated score (profit or benefit), and a team that has a fixed number of members, the problem to solve is to visit a subset of points in order to maximize the total collected score. Each member performs a tour starting at the start point, visiting distinct customers and the tour terminates at the arrival point. In addition, each point is visited at most once, and the total time in each tour cannot be greater than a given value. The proposed heuristic combines beam search and a local optimization strategy. The algorithm was tested on several sets of instances and encouraging results were obtained.

Keywords: Team Orienteering Problem, Vehicle Routing, Beam Search, Local Search.

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

Authors: Miloš Šeda

Abstract:

Resource-constrained project scheduling is an NPhard optimisation problem. There are many different heuristic strategies how to shift activities in time when resource requirements exceed their available amounts. These strategies are frequently based on priorities of activities. In this paper, we assume that a suitable heuristic has been chosen to decide which activities should be performed immediately and which should be postponed and investigate the resource-constrained project scheduling problem (RCPSP) from the implementation point of view. We propose an efficient routine that, instead of shifting the activities, extends their duration. It makes it possible to break down their duration into active and sleeping subintervals. Then we can apply the classical Critical Path Method that needs only polynomial running time. This algorithm can simply be adapted for multiproject scheduling with limited resources.

Keywords: Project management, resource-constrained scheduling, NP-hard problem, CPM, heuristic method.

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

Authors: Vijaya K. Srivastava, Davide Spinello

Abstract:

This paper presents performance of two robust gradient-based heuristic optimization procedures based on 3ⁿ enumeration and tunneling approach to seek global optimum of constrained integer problems. Both these procedures consist of two distinct phases for locating the global optimum of integer problems with a linear or non-linear objective function subject to linear or non-linear constraints. In both procedures, in the first phase, a local minimum of the function is found using the gradient approach coupled with hemstitching moves when a constraint is violated in order to return the search to the feasible region. In the second phase, in one optimization procedure, the second sub-procedure examines 3ⁿ integer combinations on the boundary and within hypercube volume encompassing the result neighboring the result from the first phase and in the second optimization procedure a tunneling function is constructed at the local minimum of the first phase so as to find another point on the other side of the barrier where the function value is approximately the same. In the next cycle, the search for the global optimum commences in both optimization procedures again using this new-found point as the starting vector. The search continues and repeated for various step sizes along the function gradient as well as that along the vector normal to the violated constraints until no improvement in optimum value is found. The results from both these proposed optimization methods are presented and compared with one provided by popular MS Excel solver that is provided within MS Office suite and other published results.

Keywords: Constrained integer problems, enumerative search algorithm, Heuristic algorithm, tunneling algorithm.

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

Authors: Gianpaolo Ghiani, Emanuela Guerriero, Emanuele Manni, Alessandro Romano

Abstract:

In this article, we deal with a variant of the classical course timetabling problem that has a practical application in many areas of education. In particular, in this paper we are interested in high schools remedial courses. The purpose of such courses is to provide under-prepared students with the skills necessary to succeed in their studies. In particular, a student might be under prepared in an entire course, or only in a part of it. The limited availability of funds, as well as the limited amount of time and teachers at disposal, often requires schools to choose which courses and/or which teaching units to activate. Thus, schools need to model the training offer and the related timetabling, with the goal of ensuring the highest possible teaching quality, by meeting the above-mentioned financial, time and resources constraints. Moreover, there are some prerequisites between the teaching units that must be satisfied. We first present a Mixed-Integer Programming (MIP) model to solve this problem to optimality. However, the presence of many peculiar constraints contributes inevitably in increasing the complexity of the mathematical model. Thus, solving it through a general-purpose solver may be performed for small instances only, while solving real-life-sized instances of such model requires specific techniques or heuristic approaches. For this purpose, we also propose a heuristic approach, in which we make use of a fast constructive procedure to obtain a feasible solution. To assess our exact and heuristic approaches we perform extensive computational results on both real-life instances (obtained from a high school in Lecce, Italy) and randomly generated instances. Our tests show that the MIP model is never solved to optimality, with an average optimality gap of 57%. On the other hand, the heuristic algorithm is much faster (in about the 50% of the considered instances it converges in approximately half of the time limit) and in many cases allows achieving an improvement on the objective function value obtained by the MIP model. Such an improvement ranges between 18% and 66%.

Keywords: Heuristic, MIP model, Remedial course, School, Timetabling.

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

Authors: Muhammad Naeem, Syed Ismail Shah, Habibullah Jamal

Abstract:

In this paper, a simple heuristic genetic algorithm is used for Multistage Multiuser detection in fast fading environments. Multipath channels, multiple access interference (MAI) and near far effect cause the performance of the conventional detector to degrade. Heuristic Genetic algorithms, a rapidly growing area of artificial intelligence, uses evolutionary programming for initial search, which not only helps to converge the solution towards near optimal performance efficiently but also at a very low complexity as compared with optimal detector. This holds true for Additive White Gaussian Noise (AWGN) and multipath fading channels. Experimental results are presented to show the superior performance of the proposed techque over the existing methods.

Keywords: Genetic Algorithm (GA), Multiple AccessInterference (MAI), Multistage Detectors (MSD), SuccessiveInterference Cancellation.

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

Authors: Vahid Hajipour, Samira V. Noshafagh, Reza Tavakkoli-Moghaddam

Abstract:

This article proposes a novel Pareto-based multiobjective meta-heuristic algorithm named non-dominated ranking genetic algorithm (NRGA) to solve multi-facility location-allocation problem. In NRGA, a fitness value representing rank is assigned to each individual of the population. Moreover, two features ranked based roulette wheel selection including select the fronts and choose solutions from the fronts, are utilized. The proposed solving methodology is validated using several examples taken from the specialized literature. The performance of our approach shows that NRGA algorithm is able to generate true and well distributed Pareto optimal solutions.

Keywords: Non-dominated ranking genetic algorithm, Pareto solutions, Multi-facility location-allocation problem.

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

Authors: Satish Kumar, Arun Kumar Gupta, Pankaj Chandna

Abstract:

In the modern manufacturing systems, the use of thermal cutting techniques using oxyfuel, plasma and laser have become indispensable for the shape forming of high quality complex components; however, the conventional chip removal production techniques still have its widespread space in the manufacturing industry. Both these types of machining operations require the positioning of end effector tool at the edge where the cutting process commences. This repositioning of the cutting tool in every machining operation is repeated several times and is termed as non-productive time or airtime motion. Minimization of this non-productive machining time plays an important role in mass production with high speed machining. As, the tool moves from one region to the other by rapid movement and visits a meticulous region once in the whole operation, hence the non-productive time can be minimized by synchronizing the tool movements. In this work, this problem is being formulated as a general travelling salesman problem (TSP) and a genetic algorithm approach has been applied to solve the same. For improving the efficiency of the algorithm, the GA has been hybridized with a noble special heuristic and simulating annealing (SA). In the present work a novel heuristic in the combination of GA has been developed for synchronization of toolpath movements during repositioning of the tool. A comparative analysis of new Meta heuristic techniques with simple genetic algorithm has been performed. The proposed metaheuristic approach shows better performance than simple genetic algorithm for minimization of nonproductive toolpath length. Also, the results obtained with the help of hybrid simulated annealing genetic algorithm (HSAGA) are also found better than the results using simple genetic algorithm only.

Keywords: Non-productive time, Airtime, 2.5 D milling, Laser cutting, Metaheuristic, Genetic Algorithm, Simulated Annealing.

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

Authors: Phakhapong Thanitakul, Worawat Sa-ngiamvibool, Apinan Aurasopon, Saravuth Pothiya

Abstract:

This paper presents an improved ant colony optimization (IACO) for solving the reliability redundancy allocation problem (RAP) in order to maximize system reliability. To improve the performance of ACO algorithm, two additional techniques, i.e. neighborhood search, and re-initialization process are presented. To show its efficiency and effectiveness, the proposed IACO is applied to solve three RAPs. Additionally, the results of the proposed IACO are compared with those of the conventional heuristic approaches i.e. genetic algorithm (GA), particle swarm optimization (PSO) and ant colony optimization (ACO). The experimental results show that the proposed IACO approach is comparatively capable of obtaining higher quality solution and faster computational time.

Keywords: Ant colony optimization, Heuristic algorithm, Mixed-integer nonlinear programming, Redundancy allocation problem, Reliability optimization.

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

Authors: Miloš Šeda

Abstract:

Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.

Keywords: Boolean algebra, Karnaugh map, Quine-McCluskey method, set covering problem, genetic algorithm.

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

Authors: K.H. Yang

Abstract:

After the terrorist attack on September 11, 2001 in U.S., the container security issue got high attention, especially by U.S. government, which deployed a lot of measures to promote or improve security systems. U.S. government not only enhances its national security system, but allies with other countries against the potential terrorist attacks in the future. For example CSI (Container Security Initiative), it encourages foreign ports outside U.S. to become CSI ports as a part of U.S. anti-terrorism network. Although promotion of the security could partly reach the goal of anti-terrorism, that will influence the efficiency of container supply chain, which is the main concern when implementing the inspection measurements. This paper proposes a quick estimation methodology for an inspection service rate by a berth allocation heuristic such that the inspection activities will not affect the original container supply chain. Theoretical and simulation results show this approach is effective.

Keywords: Berth allocation, Container, Heuristic, Inspection.

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

Authors: Truong Quang Dang Khoa, Masahiro Nakagawa

Abstract:

In this paper, a novel associative memory model will be proposed and applied to memory retrievals based on the conventional continuous time model. The conventional model presents memory capacity is very low and retrieval process easily converges to an equilibrium state which is very different from the stored patterns. Genetic Algorithms is well-known with the capability of global optimal search escaping local optimum on progress to reach a global optimum. Based on the well-known idea of Genetic Algorithms, this work proposes a heuristic rule to make a mutation when the state of the network is trapped in a spurious memory. The proposal heuristic associative memory show the stored capacity does not depend on the number of stored patterns and the retrieval ability is up to ~ 1.

Keywords: Artificial Intelligent, Soft Computing, NeuralNetworks, Genetic Algorithms, Hopfield Neural Networks, andAssociative Memories.

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

Authors: A. Charlangsut, N. Rugthaicharoencheep, S. Auchariyamet

Abstract:

Network reconfiguration is an operation to modify the network topology. The implementation of network reconfiguration has many advantages such as loss minimization, increasing system security and others. In this paper, two topics about the network reconfiguration in distribution system are briefly described. The first topic summarizes its impacts while the second explains some heuristic optimization techniques for solving the network reconfiguration problem.

Keywords: Network Reconfiguration, Optimization Techniques, Distribution System

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

Authors: J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura

Abstract:

In this paper a combination approach of two heuristic-based algorithms: genetic algorithm and tabu search is proposed. It has been developed to obtain the least cost based on the split-pipe design of looped water distribution network. The proposed combination algorithm has been applied to solve the three well-known water distribution networks taken from the literature. The development of the combination of these two heuristic-based algorithms for optimization is aimed at enhancing their strengths and compensating their weaknesses. Tabu search is rather systematic and deterministic that uses adaptive memory in search process, while genetic algorithm is probabilistic and stochastic optimization technique in which the solution space is explored by generating candidate solutions. Split-pipe design may not be realistic in practice but in optimization purpose, optimal solutions are always achieved with split-pipe design. The solutions obtained in this study have proved that the least cost solutions obtained from the split-pipe design are always better than those obtained from the single pipe design. The results obtained from the combination approach show its ability and effectiveness to solve combinatorial optimization problems. The solutions obtained are very satisfactory and high quality in which the solutions of two networks are found to be the lowest-cost solutions yet presented in the literature. The concept of combination approach proposed in this study is expected to contribute some useful benefits in diverse problems.

Keywords: GAs, Heuristics, Looped network, Least-cost design, Pipe network, Optimization, TS

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

Authors: Sufian Ashraf Mazhari, Surendra Kumar

Abstract:

This paper compares the heuristic Global Search Techniques; Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Generalized Pattern Search, genetic algorithm hybridized with Nelder–Mead and Generalized pattern search technique for tuning of fuzzy PID controller for Puma 560. Since the actual control is in joint space ,inverse kinematics is used to generate various joint angles correspoding to desired cartesian space trajectory. Efficient dynamics and kinematics are modeled on Matlab which takes very less simulation time. Performances of all the tuning methods with and without disturbance are compared in terms of ITSE in joint space and ISE in cartesian space for spiral trajectory tracking. Genetic Algorithm hybridized with Generalized Pattern Search is showing best performance.

Keywords: Controller tuning, Fuzzy Control, Genetic Algorithm, Heuristic search, Robot control.

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

Authors: S. S. Bendib, L. W. Mouss, S. Kalla

Abstract:

This paper proposes a self-organization-based approach for real-time systems design. The addressed issue is the mapping of an application onto an architecture of heterogeneous processors while optimizing both makespan and reliability. Since this problem is NP-hard, a heuristic algorithm is used to obtain efficiently approximate solutions. The proposed approach takes into consideration the quality as well as the diversity of solutions. Indeed, an alternate treatment of the two objectives allows to produce solutions of good quality while a self-organization approach based on the neighborhood structure is used to reorganize solutions and consequently to enhance their diversity. Produced solutions make different compromises between the makespan and the reliability giving the user the possibility to select the solution suited to his (her) needs.

Keywords: Embedded real-time systems design, makespan, reliability, self-organization, compromises.

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

Authors: Maha ALjohani, James Blustein

Abstract:

Communicating users' needs, goals and problems help designers and developers overcome challenges faced by end users. Personas are used to represent end users’ needs. In our research, creating personas allowed the following questions to be answered: Who are the potential user groups? What do they want to achieve by using the service? What are the problems that users face? What should the service provide to them? To develop realistic personas, we conducted a focus group discussion with undergraduate and graduate students and also interviewed a university librarian. The personas were created to help evaluating the Institutional Repository that is based on the DSpace system. The profiles helped to communicate users' needs, abilities, tasks, and problems, and the task scenarios used in the heuristic evaluation were based on these personas. Four personas resulted of a focus group discussion with undergraduate and graduate students and from interviewing a university librarian. We then used these personas to create focused task-scenarios for a heuristic evaluation on the system interface to ensure that it met users' needs, goals, problems and desires. In this paper, we present the process that we used to create the personas that led to devise the task scenarios used in the heuristic evaluation as a follow up study of the DSpace university repository.

Keywords: Heuristic Evaluation, Institutional Repositories, User Experience, Human Computer Interaction, User Profiles, Personas, Task Scenarios, Heuristics.

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

Authors: Swapnoneel Roy, Ashok Kumar Thakur, Minhazur Rahman

Abstract:

The Block Sorting problem is to sort a given permutation moving blocks. A block is defined as a substring of the given permutation, which is also a substring of the identity permutation. Block Sorting has been proved to be NP-Hard. Until now two different 2-Approximation algorithms have been presented for block sorting. These are the best known algorithms for Block Sorting till date. In this work we present a different characterization of Block Sorting in terms of a transposition cycle graph. Then we suggest a heuristic, which we show to exhibit a 2-approximation performance guarantee for most permutations.

Keywords: Block Sorting, Optical Character Recognition, Genome Rearrangements, Sorting Primitives, ApproximationAlgorithms

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

Authors: Noboru Abe, Yoshinori Amai, Toshinori Nakatake, Sumio Masuda, Kazuaki Yamaguchi

Abstract:

We consider the problem of placing labels of the points on a plane. For each point, its position, the size of its label and a priority are given. Moreover, several candidates of its label positions are prespecified, and each of such label positions is assigned a priority. The objective of our problem is to maximize the total sum of priorities of placed labels and their points. By refining a labeling algorithm that can use these priorities, we propose a new heuristic algorithm which is more suitable for treating the assigned priorities.

Keywords: Map labeling, greedy algorithm, heuristic algorithm, priority.

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

Authors: Guang Zeng, Jin Huang, Zicai Li

Abstract:

In this paper, we research the standard 13-point difference schemes for solving the biharmonic equation. Heuristic method is applied to judging the stability of multi-level difference schemes of the biharmonic equation. It is showed that the standard 13-point difference schemes are stable.

Keywords: Finite-difference equation, computational stability, hirt method.

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

Authors: Farhad Kolahan, Vahid Kayvanfar

Abstract:

In this paper we address a multi-objective scheduling problem for unrelated parallel machines. In unrelated parallel systems, the processing cost/time of a given job on different machines may vary. The objective of scheduling is to simultaneously determine the job-machine assignment and job sequencing on each machine. In such a way the total cost of the schedule is minimized. The cost function consists of three components, namely; machining cost, earliness/tardiness penalties and makespan related cost. Such scheduling problem is combinatorial in nature. Therefore, a Simulated Annealing approach is employed to provide good solutions within reasonable computational times. Computational results show that the proposed approach can efficiently solve such complicated problems.

Keywords: Makespan, Parallel machines, Scheduling, Simulated Annealing

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

Authors: R.A.Mahdavinejad

Abstract:

In this paper, multi-processors job shop scheduling problems are solved by a heuristic algorithm based on the hybrid of priority dispatching rules according to an ant colony optimization algorithm. The objective function is to minimize the makespan, i.e. total completion time, in which a simultanous presence of various kinds of ferons is allowed. By using the suitable hybrid of priority dispatching rules, the process of finding the best solution will be improved. Ant colony optimization algorithm, not only promote the ability of this proposed algorithm, but also decreases the total working time because of decreasing in setup times and modifying the working production line. Thus, the similar work has the same production lines. Other advantage of this algorithm is that the similar machines (not the same) can be considered. So, these machines are able to process a job with different processing and setup times. According to this capability and from this algorithm evaluation point of view, a number of test problems are solved and the associated results are analyzed. The results show a significant decrease in throughput time. It also shows that, this algorithm is able to recognize the bottleneck machine and to schedule jobs in an efficient way.

Keywords: Job shops scheduling, Priority dispatching rules, Makespan, Hybrid heuristic algorithm.

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

Authors: Manas Ranjan Kabat, Manoj Kumar Patel, Chita Ranjan Tripathy

Abstract:

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to quality of service (QoS) delay constraint. To support delay constrained multicast communications, computer networks need to guarantee an upper bound end-to-end delay from the source node to each of the destination nodes. This is known as multicast delay problem. On the other hand, if the same message fails to arrive at each destination node at the same time, there may arise inconsistency and unfairness problem among users. This is related to multicast delayvariation problem. The problem to find a minimum cost multicast tree with delay and delay-variation constraints has been proven to be NP-Complete. In this paper, we propose an efficient heuristic algorithm, namely, Economic Delay and Delay-Variation Bounded Multicast (EDVBM) algorithm, based on a novel heuristic function, to construct an economic delay and delay-variation bounded multicast tree. A noteworthy feature of this algorithm is that it has very high probability of finding the optimal solution in polynomial time with low computational complexity.

Keywords: EDVBM, Heuristic algorithm, Multicast tree, QoS routing, Shortest path.

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

Authors: H. Bouhamed, A. Rebai, T. Lecroq, M. Jaoua

Abstract:

The objective of our work is to develop a new approach for discovering knowledge from a large mass of data, the result of applying this approach will be an expert system that will serve as diagnostic tools of a phenomenon related to a huge information system. We first recall the general problem of learning Bayesian network structure from data and suggest a solution for optimizing the complexity by using organizational and optimization methods of data. Afterward we proposed a new heuristic of learning a Multi-Entities Bayesian Networks structures. We have applied our approach to biological facts concerning hereditary complex illnesses where the literatures in biology identify the responsible variables for those diseases. Finally we conclude on the limits arched by this work.

Keywords: Data-organization, data-optimization, automatic knowledge discovery, Multi-Entities Bayesian networks, score merging.

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

Authors: Kyaw Myo Lin, Pyone Lai Swe, Khine Zin Oo

Abstract:

In this paper, an approach combining analytical method for the distributed generator (DG) sizing and meta-heuristic search for the optimal location of DG has been presented. The optimal size of DG on each bus is estimated by the loss sensitivity factor method while the optimal sites are determined by Particle Swarm Optimization (PSO) based optimal reactive power dispatch for minimizing active power loss. To confirm the proposed approach, it has been tested on IEEE-30 bus test system. The adjustments of operating constraints and voltage profile improvements have also been observed. The obtained results show that the allocation of DGs results in a significant loss reduction with good voltage profiles and the combined approach is competent in keeping the system voltages within the acceptable limits.

Keywords: Analytical approach, distributed generations, optimal size, optimal location, optimal reactive power dispatch, particle swarm optimization algorithm.

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