Search results for: P versus NP problem
3682 An Algorithm for an Optimal Staffing Problem in Open Shop Environment
Authors: Daniela I. Borissova, Ivan C. Mustakerov
Abstract:
The paper addresses a problem of optimal staffing in open shop environment. The problem is to determine the optimal number of operators serving a given number of machines to fulfill the number of independent operations while minimizing staff idle. Using a Gantt chart presentation of the problem it is modeled as twodimensional cutting stock problem. A mixed-integer programming model is used to get minimal job processing time (makespan) for fixed number of machines' operators. An algorithm for optimal openshop staffing is developed based on iterative solving of the formulated optimization task. The execution of the developed algorithm provides optimal number of machines' operators in the sense of minimum staff idle and optimal makespan for that number of operators. The proposed algorithm is tested numerically for a real life staffing problem. The testing results show the practical applicability for similar open shop staffing problems.Keywords: Integer programming, open shop problem, optimal staffing.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 33183681 Memetic Algorithm Based Path Planning for a Mobile Robot
Authors: Neda Shahidi, Hadi Esmaeilzadeh, Marziye Abdollahi, Caro Lucas
Abstract:
In this paper, the problem of finding the optimal collision free path for a mobile robot, the path planning problem, is solved using an advanced evolutionary algorithm called memetic algorithm. What is new in this work is a novel representation of solutions for evolutionary algorithms that is efficient, simple and also compatible with memetic algorithm. The new representation makes it possible to solve the problem with a small population and in a few generations. It also makes the genetic operator simple and allows using an efficient local search operator within the evolutionary algorithm. The proposed algorithm is applied to two instances of path planning problem and the results are available.
Keywords: Path planning problem, Memetic Algorithm, Representation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17403680 Searching the Efficient Frontier for the Coherent Covering Location Problem
Authors: Felipe Azocar Simonet, Luis Acosta Espejo
Abstract:
In this article, we will try to find an efficient boundary approximation for the bi-objective location problem with coherent coverage for two levels of hierarchy (CCLP). We present the mathematical formulation of the model used. Supported efficient solutions and unsupported efficient solutions are obtained by solving the bi-objective combinatorial problem through the weights method using a Lagrangean heuristic. Subsequently, the results are validated through the DEA analysis with the GEM index (Global efficiency measurement).Keywords: Coherent covering location problem, efficient frontier, Lagrangian relaxation, data envelopment analysis.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 8093679 A New Algorithm for Determining the Leading Coefficient of in the Parabolic Equation
Authors: Shiping Zhou, Minggen Cui
Abstract:
This paper investigates the inverse problem of determining the unknown time-dependent leading coefficient in the parabolic equation using the usual conditions of the direct problem and an additional condition. An algorithm is developed for solving numerically the inverse problem using the technique of space decomposition in a reproducing kernel space. The leading coefficients can be solved by a lower triangular linear system. Numerical experiments are presented to show the efficiency of the proposed methods.Keywords: parabolic equations, coefficient inverse problem, reproducing kernel.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15813678 Decision Support System for Solving Multi-Objective Routing Problem
Authors: Ismail El Gayar, Ossama Ismail, Yousri El Gamal
Abstract:
This paper presented a technique to solve one of the transportation problems that faces us in real life which is the Bus Scheduling Problem. Most of the countries using buses in schools, companies and traveling offices as an example to transfer multiple passengers from many places to specific place and vice versa. This transferring process can cost time and money, so we build a decision support system that can solve this problem. In this paper, a genetic algorithm with the shortest path technique is used to generate a competitive solution to other well-known techniques. It also presents a comparison between our solution and other solutions for this problem.
Keywords: Bus scheduling problem, decision support system, genetic algorithm, operation planning, shortest path, transportation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15323677 Analysis Fraction Flow of Water versus Cumulative Oil Recoveries Using Buckley Leverett Method
Authors: Reza Cheraghi Kootiani, Ariffin Bin Samsuri
Abstract:
To derive the fractional flow equation oil displacement will be assumed to take place under the so-called diffusive flow condition. The constraints are that fluid saturations at any point in the linear displacement path are uniformly distributed with respect to thickness; this allows the displacement to be described mathematically in one dimension. The simultaneous flow of oil and water can be modeled using thickness averaged relative permeability, along the centerline of the reservoir. The condition for fluid potential equilibrium is simply that of hydrostatic equilibrium for which the saturation distribution can be determined as a function of capillary pressure and therefore, height. That is the fluids are distributed in accordance with capillary-gravity equilibrium. This paper focused on the fraction flow of water versus cumulative oil recoveries using Buckley Leverett method. Several field cases have been developed to aid in analysis. Producing watercut (at surface conditions) will be compared with the cumulative oil recovery at breakthrough for the flowing fluid.Keywords: Fractional Flow, Fluid Saturations, Permeability, Cumulative Oil Recoveries, Buckley Leverett Method.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 92533676 Optimal Control Problem, Quasi-Assignment Problem and Genetic Algorithm
Authors: Omid S. Fard, Akbar H. Borzabadi
Abstract:
In this paper we apply one of approaches in category of heuristic methods as Genetic Algorithms for obtaining approximate solution of optimal control problems. The firs we convert optimal control problem to a quasi Assignment Problem by defining some usual characters as defined in Genetic algorithm applications. Then we obtain approximate optimal control function as an piecewise constant function. Finally the numerical examples are given.Keywords: Optimal control, Integer programming, Genetic algorithm, Discrete approximation, Linear programming.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 12933675 Timetabling Communities’ Demands for an Effective Examination Timetabling Using Integer Linear Programming
Authors: N. F. Jamaluddin, N. A. H. Aizam
Abstract:
This paper explains the educational timetabling problem, a type of scheduling problem that is considered as one of the most challenging problem in optimization and operational research. The university examination timetabling problem (UETP), which involves assigning a set number of exams into a set number of timeslots whilst fulfilling all required conditions, has been widely investigated. The limitation of available timeslots and resources with the increasing number of examinations are the main reasons in the difficulty of solving this problem. Dynamical change in the examination scheduling system adds up the complication particularly in coping up with the demand and new requirements by the communities. Our objective is to investigate these demands and requirements with subjects taken from Universiti Malaysia Terengganu (UMT), through questionnaires. Integer linear programming model which reflects the preferences obtained to produce an effective examination timetabling was formed.
Keywords: Demands, educational timetabling, integer linear programming, scheduling, university examination timetabling problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 20093674 Collaboration of Multi-Agent and Hyper-Heuristics Systems for Production Scheduling Problem
Authors: C. E. Nugraheni, L. Abednego
Abstract:
This paper introduces a framework based on the collaboration of multi agent and hyper-heuristics to find a solution of the real single machine production problem. There are many techniques used to solve this problem. Each of it has its own advantages and disadvantages. By the collaboration of multi agent system and hyper-heuristics, we can get more optimal solution. The hyper-heuristics approach operates on a search space of heuristics rather than directly on a search space of solutions. The proposed framework consists of some agents, i.e. problem agent, trainer agent, algorithm agent (GPHH, GAHH, and SAHH), optimizer agent, and solver agent. Some low level heuristics used in this paper are MRT, SPT, LPT, EDD, LDD, and MON
Keywords: Hyper-heuristics, multi-agent systems, scheduling problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 21533673 Application of Functional Network to Solving Classification Problems
Authors: Yong-Quan Zhou, Deng-Xu He, Zheng Nong
Abstract:
In this paper two models using a functional network were employed to solving classification problem. Functional networks are generalized neural networks, which permit the specification of their initial topology using knowledge about the problem at hand. In this case, and after analyzing the available data and their relations, we systematically discuss a numerical analysis method used for functional network, and apply two functional network models to solving XOR problem. The XOR problem that cannot be solved with two-layered neural network can be solved by two-layered functional network, which reveals a potent computational power of functional networks, and the performance of the proposed model was validated using classification problems.Keywords: Functional network, neural network, XOR problem, classification, numerical analysis method.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13103672 Recovering the Boundary Data in the Two Dimensional Inverse Heat Conduction Problem Using the Ritz-Galerkin Method
Authors: Saeed Sarabadan, Kamal Rashedi
Abstract:
This article presents a numerical method to find the heat flux in an inhomogeneous inverse heat conduction problem with linear boundary conditions and an extra specification at the terminal. The method is based upon applying the satisfier function along with the Ritz-Galerkin technique to reduce the approximate solution of the inverse problem to the solution of a system of algebraic equations. The instability of the problem is resolved by taking advantage of the Landweber’s iterations as an admissible regularization strategy. In computations, we find the stable and low-cost results which demonstrate the efficiency of the technique.Keywords: Inverse problem, parabolic equations, heat equation, Ritz-Galerkin method, Landweber iterations.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 11933671 Effect of Abdominal Exercises versus Abdominal Supporting Belt on Post-Partum Abdominal Efficiency and Rectus Separation
Authors: Hanan S. El-Mekawy, Abeer M. Eldeeb, Marzouk A. El- Lythy, Adel F. El-Begawy
Abstract:
This study was conducted to determine the effect of abdominal exercises versus abdominal supporting belt on abdominal efficiency and inter-recti separation following vaginal delivery.30 primiparous post-natal women participated in this study. Their age ranged from (25 - 35) years and their BMI < 30 Kg/m2. Participants were assigned randomly into 2groups, participants of group (A) used abdominal belt from the 2nd day following delivery, till the end of puerperium (6 weeks), while participants of group (B) engaged into abdominal exercises program from the 2nd day following delivery for 6 weeks. The results of the present study revealed that although there was no statistical difference in waist circumference between both groups, participation in abdominal exercise program produced a pronounced reduction in waist/hip ratio, and inter-recti separation and also caused significant increase in abdominal muscles strength (peak torque, maximum repetition total work and average power) higher than the use of abdominal belt.Keywords: Abdominal exercise, Abdominal supporting belt, Postnatal abdominal weakness, Rectus Diastases.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 111323670 ATM Location Problem and Cash Management in Automated Teller Machines
Authors: M. Erol Genevois, D. Celik, H. Z. Ulukan
Abstract:
Automated Teller Machines (ATMs) can be considered among one of the most important service facilities in the banking industry. The investment in ATMs and the impact on the banking industry is growing steadily in every part of the world. The banks take into consideration many factors like safety, convenience, visibility, and cost in order to determine the optimum locations of ATMs. Today, ATMs are not only available in bank branches but also at retail locations. Another important factor is the cash management in ATMs. A cash demand model for every ATM is needed in order to have an efficient cash management system. This forecasting model is based on historical cash demand data which is highly related to the ATMs location. So, the location and the cash management problem should be considered together. This paper provides a general review on studies, efforts and development in ATMs location and cash management problem.Keywords: ATM location problem, cash management problem, ATM cash replenishment problem, literature review in ATMs.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 52583669 The Effect of Peer Support to Interpersonal Problem Solving Tendencies and Skills in Nursing Students
Authors: B. Özlük, A. Karaaslan
Abstract:
This study has been conducted as a supplementary and relationship seeking study with the purpose of measuring the tendency and success of support among peers amid nursing students studying at university in solving interpersonal problems. The population of the study (N:279) is comprised of nursing students who are studying at one state and one private university in the province of Konya, while its sample is comprised of 231 nursing students who agreed to take part in the study voluntarily. As a result of this study, it has been determined that the peer support and interpersonal problem solving characteristics among students were at medium levels and that the interpersonal problem solving skills of students studying in the third year were higher than those of first and second year students. While the interpersonal problem solving characteristics of students who are aged 20 and over were found to be higher, no difference could be determined in terms of the interpersonal problem solving skills and tendencies among students, based on their gender and where they reside. A positive – to a medium degree – and significant relationship was determined between peer support and interpersonal problem solving skills, and it is possible to say that as peer support increases, so do the skills and tendencies to solve problems.
Keywords: Interpersonal problem, nursing students, peer support, problem solving.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13683668 Inventing a Method of Problem Solving: The Natural Movement of the Mind to Solve a Problem
Authors: Amir Farkhonde
Abstract:
The major objective of this study was to devise a method for solving mathematical problems. Three concepts including faculty of understanding, faculty of guess, and free mind or beginner's mind provided the foundation for this method. An explanatory approach along with a hermeneutic process was taken in this study to support the assumption that mathematical knowledge is constantly developing and it seems essential for students to solve math problems on their own using their faculty of understanding (interpretive dialogue) and faculty of guess. For doing so, a kind of movement from the mathematical problem to mathematical knowledge should be adopted for teaching students a new math topic. The research method of this paper is review, descriptive and conception development. This paper first reviews the research findings on the NRICH’S project (NRICH is part of the family of activities in the Millennium Mathematics Project) with the aim that these findings form the theoretical basis of the problem-solving method. Then, the curriculum, the conceptual structure of the new method, how to design the problem and an example of it are discussed. In this way, students are immersed in the story of discovering and understanding the problem formula, and interpretive dialogue with the text continues by following the questions posed by the problem and constantly reconstructing the answer to find a formula or solution to solve the problem.
Keywords: Interpretive dialogue, NRICH, inventing, a method of problem solving.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2583667 Novel Nanomagnetic Beads Based - Latex Agglutination Assay for Rapid Diagnosis of Human Schistosomiasis Haematobium
Authors: Ibrahim Aly , Rabab Zalat, Bahaa EL Deen W. El Aswad, Ismail M. Moharm , Basam M. Masoud, Tarek Diab
Abstract:
The objective of the present study was to evaluate the novel nanomagnetic beads based–latex agglutination assay (NMB-LAT) as a simple test for diagnosis of S. haematobium as well as standardize the novel nanomagnetic beads based –ELISA (NMB-ELISA). According to urine examination this study included 85 S. haematobium infected patients, 30 other parasites infected patients and 25 negative control samples. The sensitivity of novel NMB-LAT was 82.4% versus 96.5% and 88.2% for NMB-ELISA and currently used sandwich ELISA respectively. The specificity of NMB-LAT was 83.6% versus 96.3% and 87.3% for NMB-ELISA and currently used sandwich ELISA respectively. In conclusion, the novel NMB-ELISA is a valuable applicable diagnostic technique for diagnosis of human schistosomiasis haematobium. The novel NMB-ELISA assay is a suitable applicable diagnostic method in field survey especially when followed by ELISA as a confirmatory test in query false negative results. Trials are required to increase the sensitivity and specificity of NMB-ELISA assay.
Keywords: Diagnosis, Latex agglutination, Nanomagnetic beads, Sandwich ELISA.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 30993666 A Case Study of Bee Algorithm for Ready Mixed Concrete Problem
Authors: W. Wongthatsanekorn, N. Matheekrieangkrai
Abstract:
This research proposes Bee Algorithm (BA) to optimize Ready Mixed Concrete (RMC) truck scheduling problem from single batch plant to multiple construction sites. This problem is considered as an NP-hard constrained combinatorial optimization problem. This paper provides the details of the RMC dispatching process and its related constraints. BA was then developed to minimize total waiting time of RMC trucks while satisfying all constraints. The performance of BA is then evaluated on two benchmark problems (3 and 5construction sites) according to previous researchers. The simulation results of BA are compared in term of efficiency and accuracy with Genetic Algorithm (GA) and all problems show that BA approach outperforms GA in term of efficiency and accuracy to obtain optimal solution. Hence, BA approach could be practically implemented to obtain the best schedule.
Keywords: Bee Colony Optimization, Ready Mixed Concrete Problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 29133665 Dynamic Slope Scaling Procedure for Stochastic Integer Programming Problem
Authors: Takayuki Shiina
Abstract:
Mathematical programming has been applied to various problems. For many actual problems, the assumption that the parameters involved are deterministic known data is often unjustified. In such cases, these data contain uncertainty and are thus represented as random variables, since they represent information about the future. Decision-making under uncertainty involves potential risk. Stochastic programming is a commonly used method for optimization under uncertainty. A stochastic programming problem with recourse is referred to as a two-stage stochastic problem. In this study, we consider a stochastic programming problem with simple integer recourse in which the value of the recourse variable is restricted to a multiple of a nonnegative integer. The algorithm of a dynamic slope scaling procedure for solving this problem is developed by using a property of the expected recourse function. Numerical experiments demonstrate that the proposed algorithm is quite efficient. The stochastic programming model defined in this paper is quite useful for a variety of design and operational problems.Keywords: stochastic programming problem with recourse, simple integer recourse, dynamic slope scaling procedure
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 16163664 Optimal Control of a Linear Distributed Parameter System via Shifted Legendre Polynomials
Authors: Sanjeeb Kumar Kar
Abstract:
The optimal control problem of a linear distributed parameter system is studied via shifted Legendre polynomials (SLPs) in this paper. The partial differential equation, representing the linear distributed parameter system, is decomposed into an n - set of ordinary differential equations, the optimal control problem is transformed into a two-point boundary value problem, and the twopoint boundary value problem is reduced to an initial value problem by using SLPs. A recursive algorithm for evaluating optimal control input and output trajectory is developed. The proposed algorithm is computationally simple. An illustrative example is given to show the simplicity of the proposed approach.Keywords: Optimal control, linear systems, distributed parametersystems, Legendre polynomials.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13113663 Learning Example of a Biomedical Project from a Real Problem of Muscle Fatigue
Authors: M. Rezki, A. Belaidi
Abstract:
This paper deals with a method of learning to solve a real problem in biomedical engineering from a technical study of muscle fatigue. Electromyography (EMG) is a technique for evaluating and recording the electrical activity produced by skeletal muscles (viewpoint: anatomical and physiological). EMG is used as a diagnostics tool for identifying neuromuscular diseases, assessing low-back pain and muscle fatigue in general. In order to study the EMG signal for detecting fatigue in a muscle, we have taken a real problem which touches the tramway conductor the handle bar. For the study, we have used a typical autonomous platform in order to get signals at real time. In our case study, we were confronted with complex problem to do our experiments in a tram. This type of problem is recurring among students. To teach our students the method to solve this kind of problem, we built a similar system. Through this study, we realized a lot of objectives such as making the equipment for simulation, the study of detection of muscle fatigue and especially how to manage a study of biomedical looking.
Keywords: EMG, health platform, conductor’s tram, muscle fatigue.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17243662 DNA Computing for an Absolute 1-Center Problem: An Evolutionary Approach
Authors: Zuwairie Ibrahim, Yusei Tsuboi, Osamu Ono, Marzuki Khalid
Abstract:
Deoxyribonucleic Acid or DNA computing has emerged as an interdisciplinary field that draws together chemistry, molecular biology, computer science and mathematics. Thus, in this paper, the possibility of DNA-based computing to solve an absolute 1-center problem by molecular manipulations is presented. This is truly the first attempt to solve such a problem by DNA-based computing approach. Since, part of the procedures involve with shortest path computation, research works on DNA computing for shortest path Traveling Salesman Problem, in short, TSP are reviewed. These approaches are studied and only the appropriate one is adapted in designing the computation procedures. This DNA-based computation is designed in such a way that every path is encoded by oligonucleotides and the path-s length is directly proportional to the length of oligonucleotides. Using these properties, gel electrophoresis is performed in order to separate the respective DNA molecules according to their length. One expectation arise from this paper is that it is possible to verify the instance absolute 1-center problem using DNA computing by laboratory experiments.Keywords: DNA computing, operation research, 1-center problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 14623661 Improvement of the Shortest Path Problem with Geodesic-Like Method
Authors: Wen-Haw Chen
Abstract:
This paper proposes a method to improve the shortest path problem on a NURBS (Non-uniform rational basis spline) surfaces. It comes from an application of the theory in classic differential geometry on surfaces and can improve the distance problem not only on surfaces but in the Euclidean 3-space R3 .Keywords: shortest paths, geodesic-like method, NURBS surfaces.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17683660 A Study of Cooperative Co-evolutionary Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem
Authors: Lee Yih Rou, Hishammuddin Asmuni
Abstract:
Flexible Job Shop Problem (FJSP) is an extension of classical Job Shop Problem (JSP). The FJSP extends the routing flexibility of the JSP, i.e assigning machine to an operation. Thus it makes it more difficult than the JSP. In this study, Cooperative Coevolutionary Genetic Algorithm (CCGA) is presented to solve the FJSP. Makespan (time needed to complete all jobs) is used as the performance evaluation for CCGA. In order to test performance and efficiency of our CCGA the benchmark problems are solved. Computational result shows that the proposed CCGA is comparable with other approaches.Keywords: Co-evolution, Genetic Algorithm (GA), Flexible JobShop Problem(FJSP)
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17883659 4D Flight Trajectory Optimization Based on Pseudospectral Methods
Authors: Kouamana Bousson, Paulo Machado
Abstract:
The optimization and control problem for 4D trajectories is a subject rarely addressed in literature. In the 4D navigation problem we define waypoints, for each mission, where the arrival time is specified in each of them. One way to design trajectories for achieving this kind of mission is to use the trajectory optimization concepts. To solve a trajectory optimization problem we can use the indirect or direct methods. The indirect methods are based on maximum principle of Pontryagin, on the other hand, in the direct methods it is necessary to transform into a nonlinear programming problem. We propose an approach based on direct methods with a pseudospectral integration scheme built on Chebyshev polynomials.Keywords: Pseudospectral Methods, Trajectory Optimization, 4DTrajectories
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 24113658 Optimization of Unweighted Minimum Vertex Cover
Authors: S. Balaji, V. Swaminathan, K. Kannan
Abstract:
The Minimum Vertex Cover (MVC) problem is a classic graph optimization NP - complete problem. In this paper a competent algorithm, called Vertex Support Algorithm (VSA), is designed to find the smallest vertex cover of a graph. The VSA is tested on a large number of random graphs and DIMACS benchmark graphs. Comparative study of this algorithm with the other existing methods has been carried out. Extensive simulation results show that the VSA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.Keywords: vertex cover, vertex support, approximation algorithms, NP - complete problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 24883657 Impact of the Existence of One-Way Functionson the Conceptual Difficulties of Quantum Measurements
Authors: Arkady Bolotin
Abstract:
One-way functions are functions that are easy to compute but hard to invert. Their existence is an open conjecture; it would imply the existence of intractable problems (i.e. NP-problems which are not in the P complexity class). If true, the existence of one-way functions would have an impact on the theoretical framework of physics, in particularly, quantum mechanics. Such aspect of one-way functions has never been shown before. In the present work, we put forward the following. We can calculate the microscopic state (say, the particle spin in the z direction) of a macroscopic system (a measuring apparatus registering the particle z-spin) by the system macroscopic state (the apparatus output); let us call this association the function F. The question is: can we compute the function F in the inverse direction? In other words, can we compute the macroscopic state of the system through its microscopic state (the preimage F -1)? In the paper, we assume that the function F is a one-way function. The assumption implies that at the macroscopic level the Schrödinger equation becomes unfeasible to compute. This unfeasibility plays a role of limit of the validity of the linear Schrödinger equation.Keywords: One-way functions, P versus NP problem, quantummeasurements.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13073656 Two Points Crossover Genetic Algorithm for Loop Layout Design Problem
Authors: Xu LiYun, Briand Florent, Fan GuoLiang
Abstract:
The loop-layout design problem (LLDP) aims at optimizing the sequence of positioning of the machines around the cyclic production line. Traffic congestion is the usual criteria to minimize in this type of problem, i.e. the number of additional cycles spent by each part in the network until the completion of its required routing sequence of machines. This paper aims at applying several improvements mechanisms such as a positioned-based crossover operator for the Genetic Algorithm (GA) called a Two Points Crossover (TPC) and an offspring selection process. The performance of the improved GA is measured using well-known examples from literature and compared to other evolutionary algorithms. Good results show that GA can still be competitive for this type of problem against more recent evolutionary algorithms.Keywords: Crossover, genetic algorithm, layout design problem, loop-layout, manufacturing optimization.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 8463655 Performance Analysis of MATLAB Solvers in the Case of a Quadratic Programming Generation Scheduling Optimization Problem
Authors: Dávid Csercsik, Péter Kádár
Abstract:
In the case of the proposed method, the problem is parallelized by considering multiple possible mode of operation profiles, which determine the range in which the generators operate in each period. For each of these profiles, the optimization is carried out independently, and the best resulting dispatch is chosen. For each such profile, the resulting problem is a quadratic programming (QP) problem with a potentially negative definite Q quadratic term, and constraints depending on the actual operation profile. In this paper we analyze the performance of available MATLAB optimization methods and solvers for the corresponding QP.Keywords: Economic dispatch, optimization, quadratic programming, MATLAB.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 9483654 The Knapsack Sharing Problem: A Tree Search Exact Algorithm
Authors: Mhand Hifi, Hedi Mhalla
Abstract:
In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.
Keywords: Branch and bound, combinatorial optimization, knap¬sack, knapsack sharing, heuristics, interval reduction.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15593653 A New Heuristic Approach for the Stock- Cutting Problems
Authors: Stephen C. H. Leung, Defu Zhang
Abstract:
This paper addresses a stock-cutting problem with rotation of items and without the guillotine cutting constraint. In order to solve the large-scale problem effectively and efficiently, we propose a simple but fast heuristic algorithm. It is shown that this heuristic outperforms the latest published algorithms for large-scale problem instances.
Keywords: Combinatorial optimization, heuristic, large-scale, stock-cutting.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1682