Search results for: Quadratic assignment problem

Authors: Yongzhong Wu, Ping Ji

Abstract:

This paper proposes a genetic algorithm based on a new replacement strategy to solve the quadratic assignment problems, which are NP-hard. The new replacement strategy aims to improve the performance of the genetic algorithm through well balancing the convergence of the searching process and the diversity of the population. In order to test the performance of the algorithm, the instances in QAPLIB, a quadratic assignment problem library, are tried and the results are compared with those reported in the literature. The performance of the genetic algorithm is promising. The significance is that this genetic algorithm is generic. It does not rely on problem-specific genetic operators, and may be easily applied to various types of combinatorial problems.

Keywords: Quadratic assignment problem, Genetic algorithm, Replacement strategy, QAPLIB.

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

Authors: Y. Fathi, B. Karimi, S. M. J. Mirzapour Al-e-Hashem

Abstract:

Cross-docking includes receiving products supplied by a set of suppliers, unloading them from inbound trucks (ITs) at strip doors, consolidating and handling these products to stack doors based on their destinations, loading them into outbound trucks (OTs); then, delivering these products to customers. An effective assignment of the trucks to the doors would enhance the advantages of the cross-docking (e.g. reduction of the handling costs). This paper addresses the truck-to-door assignment problem in a cross-dock in which assignment of the ITs to the strip doors as well as assignment of the OTs to the stacks doors is determined so that total material handling cost in the cross-dock is minimized. Capacity constraints are applied for the ITs, OTs, strip doors, and stack doors. We develop a Quadratic Programming (QP) to formulate the problem. To solve it, the model is coded in LINGO software to specify the best assignment of the trucks to the doors.

Keywords: Cross-docking, truck-to-door assignment, supply chain, quadratic programming.

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

Authors: Mohammed Salem Alzahrani

Abstract:

In this paper the optimality of the solution of an existing real word assignment problem known as the seat assignment problem using Seat Assignment Method (SAM) is discussed. SAM is the newly driven method from three existing methods, Hungarian Method, Northwest Corner Method and Least Cost Method in a special way that produces the easiness & fairness among all methods that solve the seat assignment problem.

Keywords: Assignment Problem, Hungarian Method, Least Cost Method, Northwest Corner Method, Seat Assignment Method (SAM), A Real Word Assignment Problem.

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

Authors: Xiang Zhang, David Rey, S. Travis Waller

Abstract:

Stochastic User Equilibrium (SUE) model is a widely used traffic assignment model in transportation planning, which is regarded more advanced than Deterministic User Equilibrium (DUE) model. However, a problem exists that the performance of the SUE model depends on its error term parameter. The objective of this paper is to propose a systematic method of determining the appropriate error term parameter value for the SUE model. First, the significance of the parameter is explored through a numerical example. Second, the parameter calibration method is developed based on the Logit-based route choice model. The calibration process is realized through multiple nonlinear regression, using sequential quadratic programming combined with least square method. Finally, case analysis is conducted to demonstrate the application of the calibration process and validate the better performance of the SUE model calibrated by the proposed method compared to the SUE models under other parameter values and the DUE model.

Keywords: Parameter calibration, sequential quadratic programming, Stochastic User Equilibrium, traffic assignment, transportation planning.

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

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 895

Authors: Ahmet Tekcan, Arzu Özkoç

Abstract:

Let D = 1 be a positive non-square integer and let δ = √D or 1+√D 2 be a real quadratic irrational with trace t =δ + δ and norm n = δδ. Let γ = P+δ Q be a quadratic irrational for positive integers P and Q. Given a quadratic irrational γ, there exist a quadratic ideal Iγ = [Q, δ + P] and an indefinite quadratic form Fγ(x, y) = Q(x−γy)(x−γy) of discriminant Δ = t 2−4n. In the first section, we give some preliminaries form binary quadratic forms, quadratic irrationals and quadratic ideals. In the second section, we obtain some results on γ, Iγ and Fγ for some specific values of Q and P.

Keywords: Quadratic irrationals, quadratic ideals, indefinite quadratic forms, extended modular group.

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

Authors: Amit Kumar, Anila Gupta, Amarpreet Kaur

Abstract:

In this paper, a new method is proposed to find the fuzzy optimal solution of fuzzy assignment problems by representing all the parameters as triangular fuzzy numbers. The advantages of the pro-posed method are also discussed. To illustrate the proposed method a fuzzy assignment problem is solved by using the proposed method and the obtained results are discussed. The proposed method is easy to understand and to apply for finding the fuzzy optimal solution of fuzzy assignment problems occurring in real life situations.

Keywords: Fuzzy assignment problem, Ranking function, Triangular fuzzy numbers.

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

Authors: Tarek M. Mahmoud

Abstract:

Selecting the routes and the assignment of link flow in a computer communication networks are extremely complex combinatorial optimization problems. Metaheuristics, such as genetic or simulated annealing algorithms, are widely applicable heuristic optimization strategies that have shown encouraging results for a large number of difficult combinatorial optimization problems. This paper considers the route selection and hence the flow assignment problem. A genetic algorithm and simulated annealing algorithm are used to solve this problem. A new hybrid algorithm combining the genetic with the simulated annealing algorithm is introduced. A modification of the genetic algorithm is also introduced. Computational experiments with sample networks are reported. The results show that the proposed modified genetic algorithm is efficient in finding good solutions of the flow assignment problem compared with other techniques.

Keywords: Genetic Algorithms, Flow Assignment, Routing, Computer network, Simulated Annealing.

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

Authors: Mohammed Salem Alzahrani

Abstract:

In this paper, student admission process is studied to optimize the assignment of vacant seats with three main objectives. Utilizing all vacant seats, satisfying all programs of study admission requirements and maintaining fairness among all candidates are the three main objectives of the optimization model. Seat Assignment Method (SAM) is used to build the model and solve the optimization problem with help of Northwest Coroner Method and Least Cost Method. A closed formula is derived for applying the priority of assigning seat to candidate based on SAM.

Keywords: Admission Process Model, Assignment Problem, Hungarian Method, Least Cost Method, Northwest Corner Method, Seat Assignment Method (SAM).

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

Authors: Qing Lyu, Hang Zhu

Abstract:

Various flows in the network require to go through different types of middlebox. The improper placement of network middlebox and path assignment for flows could greatly increase the network latency and also decrease the performance of network. Minimizing the total end to end latency of all the ows requires to assign path for the incoming flows. In this paper, the flow path assignment problem in regard to the placement of various kinds of middlebox is studied. The flow path assignment problem is formulated to a linear programming problem, which is very time consuming. On the other hand, a naive greedy algorithm is studied. Which is very fast but causes much more latency than the linear programming algorithm. At last, the paper presents a heuristic algorithm named FPA, which takes bottleneck link information and estimated bandwidth occupancy into consideration, and achieves near optimal latency in much less time. Evaluation results validate the effectiveness of the proposed algorithm.

Keywords: Latency, Fast path assignment, Bottleneck link.

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

Authors: Gaurav Kumar, Rakesh Kumar Bajaj

Abstract:

The primary objective of the paper is to propose a new method for solving assignment problem under uncertain situation. In the classical assignment problem (AP), z_pqdenotes the cost for assigning the qth job to the pth person which is deterministic in nature. Here in some uncertain situation, we have assigned a cost in the form of composite relative degree F_pq instead of  and this replaced cost is in the maximization form. In this paper, it has been solved and validated by the two proposed algorithms, a new mathematical formulation of IVIF assignment problem has been presented where the cost has been considered to be an IVIFN and the membership of elements in the set can be explained by positive and negative evidences. To determine the composite relative degree of similarity of IVIFS the concept of similarity measure and the score function is used for validating the solution which is obtained by Composite relative similarity degree method. Further, hypothetical numeric illusion is conducted to clarify the method’s effectiveness and feasibility developed in the study. Finally, conclusion and suggestion for future work are also proposed.

Keywords: Assignment problem, Interval-valued Intuitionistic Fuzzy Sets, Similarity Measures, score function.

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

Authors: B. M. Mohan, Sanjeeb Kumar Kar

Abstract:

In this paper a unified approach via block-pulse functions (BPFs) or shifted Legendre polynomials (SLPs) is presented to solve the linear-quadratic-Gaussian (LQG) control problem. Also a recursive algorithm is proposed to solve the above problem via BPFs. By using the elegant operational properties of orthogonal functions (BPFs or SLPs) these computationally attractive algorithms are developed. To demonstrate the validity of the proposed approaches a numerical example is included.

Keywords: Linear quadratic Gaussian control, linear quadratic estimator, linear quadratic regulator, time-invariant systems, orthogonal functions, block-pulse functions, shifted legendre polynomials.

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

Authors: Xiu Liu, Shouming Zhong, Xiuyong Ding

Abstract:

This paper focuses on the quadratic stabilization problem for a class of uncertain impulsive switched systems. The uncertainty is assumed to be norm-bounded and enters both the state and the input matrices. Based on the Lyapunov methods, some results on robust stabilization and quadratic stabilization for the impulsive switched system are obtained. A stabilizing state feedback control law realizing the robust stabilization of the closed-loop system is constructed.

Keywords: Impulsive systems, switched systems, quadratic stabilization, robust stabilization.

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

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 1423

Authors: S. Kavitha, Nirmala P. Ratchagar

Abstract:

This paper presents the novel deterministic dynamic programming approach for solving optimization problem with quadratic objective function with linear equality and inequality constraints. The proposed method employs backward recursion in which computations proceeds from last stage to first stage in a multi-stage decision problem. A generalized recursive equation which gives the exact solution of an optimization problem is derived in this paper. The method is purely analytical and avoids the usage of initial solution. The feasibility of the proposed method is demonstrated with a practical example. The numerical results show that the proposed method provides global optimum solution with negligible computation time.

Keywords: Backward recursion, Dynamic programming, Multi-stage decision problem, Quadratic objective function.

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

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 1247

Authors: V. Ramnarain-Seetohul, J. Abdool Karim, A. Amir

Abstract:

Almost all universities include some form of assignment in their courses. The assignments are either carried out in either in groups or individually. To effectively manage these submitted assignments, a well-designed assignment submission system is needed, hence the need for an online assignment submission system to facilitate the distribution, and collection of assignments on due dates. The objective of such system is to facilitate interaction of lecturers and students for assessment and grading purposes. The aim of this study was to create a web based online assignment submission system for University of Mauritius. The system was created to eliminate the traditional process of giving an assignment and collecting the answers for the assignment. Lecturers can also create automated assessment to assess the students online. Moreover, the online submission system consists of an automatic mailing system which acts as a reminder for students about the deadlines of the posted assignments. System was tested to measure its acceptance rate among both student and lecturers.

Keywords: Assignment, assessment, online, submission

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

Authors: Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

Keywords: Timetabling problem, mathematical programming model, hybrid algorithm, simulated annealing.

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

Authors: Belkacem Brahmi, Mohand Ouamer Bibi

Abstract:

In this paper, we present a new method for solving quadratic programming problems, not strictly convex. Constraints of the problem are linear equalities and inequalities, with bounded variables. The suggested method combines the active-set strategies and support methods. The algorithm of the method and numerical experiments are presented, while comparing our approach with the active set method on randomly generated problems.

Keywords: Convex quadratic programming, dual support methods, active set methods.

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

Authors: Gishantha Thantulage, Tatiana Kalganova, Manissa Wilson

Abstract:

Ant Colony Algorithms have been applied to difficult combinatorial optimization problems such as the travelling salesman problem and the quadratic assignment problem. In this paper gridbased and random-based ant colony algorithms are proposed for automatic 3D hose routing and their pros and cons are discussed. The algorithm uses the tessellated format for the obstacles and the generated hoses in order to detect collisions. The representation of obstacles and hoses in the tessellated format greatly helps the algorithm towards handling free-form objects and speeds up computation. The performance of algorithm has been tested on a number of 3D models.

Keywords: Ant colony algorithm, Automatic hose routing, tessellated format, RAPID.

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

Authors: Mohd Amaluddin Yusoff

Abstract:

In this paper, we consider the design of pulse shaping filter using orthogonal Hermite-Rodriguez basis functions. The pulse shaping filter design problem has been formulated and solved as a quadratic programming problem with linear inequality constraints. Compared with the existing approaches reported in the literature, the use of Hermite-Rodriguez functions offers an effective alternative to solve the constrained filter synthesis problem. This is demonstrated through a numerical example which is concerned with the design of an equalization filter for a digital transmission channel.

Keywords: channel equalization filter, Hermite-Rodriguez, pulseshaping filter, quadratic programming.

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

Authors: Muthu Solayappan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.

Keywords: unconstrained binary quadratic programming, perturbation, interior point methods

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

Authors: Halil Ibrahim Demir, Caner Erden, Mumtaz Ipek, Ozer Uygun

Abstract:

Traditionally, the three important manufacturing functions, which are process planning, scheduling and due-date assignment, are performed separately and sequentially. For couple of decades, hundreds of studies are done on integrated process planning and scheduling problems and numerous researches are performed on scheduling with due date assignment problem, but unfortunately the integration of these three important functions are not adequately addressed. Here, the integration of these three important functions is studied by using genetic, random-genetic hybrid, simulated annealing, random-simulated annealing hybrid and random search techniques. As well, the importance of the integration of these three functions and the power of meta-heuristics and of hybrid heuristics are studied.

Keywords: Process planning, weighted scheduling, weighted due-date assignment, genetic search, simulated annealing, hybrid meta-heuristics.

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

Authors: Taisir Eldos, Aws Kanan, Waleed Nazih, Ahmad Khatatbih

Abstract:

Chemical Reaction Optimization (CRO) is an optimization metaheuristic inspired by the nature of chemical reactions as a natural process of transforming the substances from unstable to stable states. Starting with some unstable molecules with excessive energy, a sequence of interactions takes the set to a state of minimum energy. Researchers reported successful application of the algorithm in solving some engineering problems, like the quadratic assignment problem, with superior performance when compared with other optimization algorithms. We adapted this optimization algorithm to the Printed Circuit Board Drilling Problem (PCBDP) towards reducing the drilling time and hence improving the PCB manufacturing throughput. Although the PCBDP can be viewed as instance of the popular Traveling Salesman Problem (TSP), it has some characteristics that would require special attention to the transactions that explore the solution landscape. Experimental test results using the standard CROToolBox are not promising for practically sized problems, while it could find optimal solutions for artificial problems and small benchmarks as a proof of concept.

Keywords: Evolutionary Algorithms, Chemical Reaction Optimization, Traveling Salesman, Board Drilling.

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

Authors: S. Raja Balachandar, K.Kannan

Abstract:

This paper presents a heuristic approach to solve the Generalized Assignment Problem (GAP) which is NP-hard. It is worth mentioning that many researches used to develop algorithms for identifying the redundant constraints and variables in linear programming model. Some of the algorithms are presented using intercept matrix of the constraints to identify redundant constraints and variables prior to the start of the solution process. Here a new heuristic approach based on the dominance property of the intercept matrix to find optimal or near optimal solution of the GAP is proposed. In this heuristic, redundant variables of the GAP are identified by applying the dominance property of the intercept matrix repeatedly. This heuristic approach is tested for 90 benchmark problems of sizes upto 4000, taken from OR-library and the results are compared with optimum solutions. Computational complexity is proved to be O(mn2) of solving GAP using this approach. The performance of our heuristic is compared with the best state-ofthe- art heuristic algorithms with respect to both the quality of the solutions. The encouraging results especially for relatively large size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems.

Keywords: Combinatorial Optimization Problem, Generalized Assignment Problem, Intercept Matrix, Heuristic, Computational Complexity, NP-Hard Problems.

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

Authors: Salam Saudagar, Ankit Kamboj, Niraj Mohan, Satgounda Patil, Nilesh Powar

Abstract:

Task Assignment and Scheduling is a challenging Operations Research problem when there is a limited number of resources and comparatively higher number of tasks. The Cost Management team at Cummins needs to assign tasks based on a deadline and must prioritize some of the tasks as per business requirements. Moreover, there is a constraint on the resources that assignment of tasks should be done based on an individual skill level, that may vary for different tasks. Another constraint is for scheduling the tasks that should be evenly distributed in terms of number of working hours, which adds further complexity to this problem. The proposed greedy approach to solve assignment and scheduling problem first assigns the task based on management priority and then by the closest deadline. This is followed by an iterative selection of an available resource with the least allocated total working hours for a task, i.e. finding the local optimal choice for each task with the goal of determining the global optimum. The greedy approach task allocation is compared with a variant of Hungarian Algorithm, and it is observed that the proposed approach gives an equal allocation of working hours among the resources. The comparative study of the proposed approach is also done with manual task allocation and it is noted that the visibility of the task timeline has increased from 2 months to 6 months. An interactive dashboard app is created for the greedy assignment and scheduling approach and the tasks with more than 2 months horizon that were waiting in a queue without a delivery date initially are now analyzed effectively by the business with expected timelines for completion.

Keywords: Assignment, deadline, greedy approach, hungarian algorithm, operations research, scheduling.

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

Authors: Ahmet Tekcan

Abstract:

Let F(x, y) = ax2 + bxy + cy2 be a positive definite binary quadratic form with discriminant Δ whose base points lie on the line x = -1/m for an integer m ≥ 2, let p be a prime number and let Fp be a finite field. Let EF : y2 = ax3 + bx2 + cx be an elliptic curve over Fp and let CF : ax3 + bx2 + cx ≡ 0(mod p) be the cubic congruence corresponding to F. In this work we consider some properties of positive definite quadratic forms, elliptic curves and cubic congruences.

Keywords: Binary quadratic form, elliptic curves, cubic congruence.

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

Authors: Darwin Gouwanda, S. G. Ponnambalam

Abstract:

Set covering problem is a classical problem in computer science and complexity theory. It has many applications, such as airline crew scheduling problem, facilities location problem, vehicle routing, assignment problem, etc. In this paper, three different techniques are applied to solve set covering problem. Firstly, a mathematical model of set covering problem is introduced and solved by using optimization solver, LINGO. Secondly, the Genetic Algorithm Toolbox available in MATLAB is used to solve set covering problem. And lastly, an ant colony optimization method is programmed in MATLAB programming language. Results obtained from these methods are presented in tables. In order to assess the performance of the techniques used in this project, the benchmark problems available in open literature are used.

Keywords: Set covering problem, genetic algorithm, ant colony optimization, LINGO.

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

Authors: Debajyoti Mishra, Urmila Bhanja

Abstract:

In this paper, a novel fuzzy approach is developed while solving the Dynamic Routing and Wavelength Assignment (DRWA) problem in optical networks with Wavelength Division Multiplexing (WDM). In this work, the effect of nonlinear and linear impairments such as Four Wave Mixing (FWM) and amplifier spontaneous emission (ASE) noise are incorporated respectively. The novel algorithm incorporates fuzzy logic controller (FLC) to reduce the effect of FWM noise and ASE noise on a requested lightpath referred in this work as FWM aware fuzzy dynamic routing and wavelength assignment algorithm. The FWM crosstalk products and the static FWM noise power per link are pre computed in order to reduce the set up time of a requested lightpath, and stored in an offline database. These are retrieved during the setting up of a lightpath and evaluated online taking the dynamic parameters like cost of the links into consideration.

Keywords: Amplifier spontaneous emission (ASE), Dynamic routing and wavelength assignment, Four wave mixing (FWM), Fuzzy rule based system (FRBS).

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

Authors: Mian Tahir Aftab, Muhammad Umer, Riaz Ahmad

Abstract:

This article proposes an Ant Colony Optimization (ACO) metaheuristic to minimize total makespan for scheduling a set of jobs and assign workers for uniformly related parallel machines. An algorithm based on ACO has been developed and coded on a computer program Matlab®, to solve this problem. The paper explains various steps to apply Ant Colony approach to the problem of minimizing makespan for the worker assignment & jobs scheduling problem in a parallel machine model and is aimed at evaluating the strength of ACO as compared to other conventional approaches. One data set containing 100 problems (12 Jobs, 03 machines and 10 workers) which is available on internet, has been taken and solved through this ACO algorithm. The results of our ACO based algorithm has shown drastically improved results, especially, in terms of negligible computational effort of CPU, to reach the optimal solution. In our case, the time taken to solve all 100 problems is even lesser than the average time taken to solve one problem in the data set by other conventional approaches like GA algorithm and SPT-A/LMC heuristics.

Keywords: Ant Colony Optimization (ACO), Genetic algorithms (GA), Makespan, SPT-A/LMC heuristic.

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