**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**3561

# Search results for: NP-complete problem.

##### 3561 A Flexible Flowshop Scheduling Problem with Machine Eligibility Constraint and Two Criteria Objective Function

**Authors:**
Bita Tadayon,
Nasser Salmasi

**Abstract:**

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

##### 3560 A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks

**Authors:**
P.S.Prakash,
S.Selvan

**Abstract:**

**Keywords:**
feasible path,
multiple constraints,
path selection,
QoS routing

##### 3559 Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm

**Authors:**
T. Vigneswari,
M. A. Maluk Mohamed

**Abstract:**

Job Scheduling plays an important role for efficient utilization of grid resources available across different domains and geographical zones. Scheduling of jobs is challenging and NPcomplete. Evolutionary / Swarm Intelligence algorithms have been extensively used to address the NP problem in grid scheduling. Artificial Bee Colony (ABC) has been proposed for optimization problems based on foraging behaviour of bees. This work proposes a modified ABC algorithm, Cluster Heterogeneous Earliest First Min- Min Artificial Bee Colony (CHMM-ABC), to optimally schedule jobs for the available resources. The proposed model utilizes a novel Heterogeneous Earliest Finish Time (HEFT) Heuristic Algorithm along with Min-Min algorithm to identify the initial food source. Simulation results show the performance improvement of the proposed algorithm over other swarm intelligence techniques.

**Keywords:**
Grid Computing,
Grid Scheduling,
Heterogeneous
Earliest Finish Time (HEFT),
Artificial Bee colony (ABC)
Algorithm,
Resource Management.

##### 3558 Iterative Methods for An Inverse Problem

**Authors:**
Minghui Wang,
Shanrui Hu

**Abstract:**

An inverse problem of doubly center matrices is discussed. By translating the constrained problem into unconstrained problem, two iterative methods are proposed. A numerical example illustrate our algorithms.

**Keywords:**
doubly center matrix,
electric network theory,
iterative methods,
least-square problem.

##### 3557 Evolutionary Search Techniques to Solve Set Covering Problems

**Authors:**
Darwin Gouwanda,
S. G. Ponnambalam

**Abstract:**

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

##### 3556 Bi-linear Complementarity Problem

**Authors:**
Chao Wang,
Ting-Zhu Huang Chen Jia

**Abstract:**

In this paper, we propose a new linear complementarity problem named as bi-linear complementarity problem (BLCP) and the method for solving BLCP. In addition, the algorithm for error estimation of BLCP is also given. Numerical experiments show that the algorithm is efficient.

**Keywords:**
Bi-linear complementarity problem,
Linear complementarity
problem,
Extended linear complementarity problem,
Error
estimation,
P-matrix,
M-matrix.

##### 3555 A Method for Solving a Bi-Objective Transportation Problem under Fuzzy Environment

**Authors:**
Sukhveer Singh,
Sandeep Singh

**Abstract:**

A bi-objective fuzzy transportation problem with the objectives to minimize the total fuzzy cost and fuzzy time of transportation without according priorities to them is considered. To the best of our knowledge, there is no method in the literature to find efficient solutions of the bi-objective transportation problem under uncertainty. In this paper, a bi-objective transportation problem in an uncertain environment has been formulated. An algorithm has been proposed to find efficient solutions of the bi-objective transportation problem under uncertainty. The proposed algorithm avoids the degeneracy and gives the optimal solution faster than other existing algorithms for the given uncertain transportation problem.

**Keywords:**
Transportation problem,
efficient solution,
ranking function,
fuzzy transportation problem.

##### 3554 Bee Colony Optimization Applied to the Bin Packing Problem

**Authors:**
Kenza Aida Amara,
Bachir Djebbar

**Abstract:**

**Keywords:**
Bee colony optimization,
bin packing,
heuristic algorithm,
pretreatment.

##### 3553 Modeling Language for Machine Learning

**Authors:**
Tsuyoshi Okita,
Tatsuya Niwa

**Abstract:**

**Keywords:**
Formal language,
statistical inference problem,
reduction.

##### 3552 Transformation of Course Timetablinng Problem to RCPSP

**Authors:**
M. Ahmad,
M. Gourgand,
C. Caux

**Abstract:**

**Keywords:**
Course Timetabling,
Integer programming,
Combinatorial optimizations

##### 3551 How to Build and Evaluate a Solution Method: An Illustration for the Vehicle Routing Problem

**Authors:**
Nicolas Zufferey

**Abstract:**

The vehicle routing problem (VRP) is a famous combinatorial optimization problem. Because of its well-known difficulty, metaheuristics are the most appropriate methods to tackle large and realistic instances. The goal of this paper is to highlight the key ideas for designing VRP metaheuristics according to the following criteria: efficiency, speed, robustness, and ability to take advantage of the problem structure. Such elements can obviously be used to build solution methods for other combinatorial optimization problems, at least in the deterministic field.

**Keywords:**
Vehicle routing problem,
Metaheuristics,
Combinatorial optimization.

##### 3550 Seat Assignment Problem Optimization

**Authors:**
Mohammed Salem Alzahrani

**Abstract:**

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

##### 3549 The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm

**Authors:**
Mhand Hifi,
Hedi Mhalla,
Mustapha Michaphy

**Abstract:**

In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.

**Keywords:**
combinatorial optimization,
max-min optimization,
knapsack,
heuristics,
problem reduction

##### 3548 A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

**Authors:**
Zohreh O. Akbari

**Abstract:**

**Keywords:**
Clique problem,
Deterministic Polynomial-time
Algorithm,
Equality of P and NP Complexity Classes.

##### 3547 Optimization by Ant Colony Hybryde for the Bin-Packing Problem

**Authors:**
Ben Mohamed Ahemed Mohamed,
Yassine Adnan

**Abstract:**

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

**Keywords:**
Ant colony algorithm,
bin-packing problem,
heuristics methods.

##### 3546 Optimal Facility Layout Problem Solution Using Genetic Algorithm

**Authors:**
Maricar G. Misola,
Bryan B. Navarro

**Abstract:**

Facility Layout Problem (FLP) is one of the essential problems of several types of manufacturing and service sector. It is an optimization problem on which the main objective is to obtain the efficient locations, arrangement and order of the facilities. In the literature, there are numerous facility layout problem research presented and have used meta-heuristic approaches to achieve optimal facility layout design. This paper presented genetic algorithm to solve facility layout problem; to minimize total cost function. The performance of the proposed approach was verified and compared using problems in the literature.

**Keywords:**
Facility Layout Problem,
Genetic Algorithm,
Material Handling Cost,
Meta-heuristic Approach.

##### 3545 Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm

**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.

##### 3544 Stochastic Programming Model for Power Generation

**Authors:**
Takayuki Shiina

**Abstract:**

**Keywords:**
electric power capacity expansion problem,
integerprogramming,
L-shaped method,
stochastic programming

##### 3543 On Optimum Stratification

**Authors:**
M. G. M. Khan,
V. D. Prasad,
D. K. Rao

**Abstract:**

In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.

**Keywords:**
Auxiliary variable,
Dynamic programming technique,
Nonlinear programming problem,
Optimum stratification,
Uniform distribution.

##### 3542 Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)

**Authors:**
Buthainah Fahran Al-Dulaimi,
Hamza A. Ali

**Abstract:**

The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.

**Keywords:**
Genetic algorithms,
traveling salesman problem solving,
optimization.

##### 3541 Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations

**Authors:**
Liudmyla Koliechkina,
Olena Dvirna

**Abstract:**

**Keywords:**
Discrete set,
linear combinatorial optimization,
multi-objective optimization,
multipermutation,
Pareto solutions,
partial permutation set,
permutation,
structural graph.

##### 3540 P-ACO Approach to Assignment Problem in FMSs

**Authors:**
I. Mahdavi,
A. Jazayeri,
M. Jahromi,
R. Jafari,
H. Iranmanesh

**Abstract:**

One of the most important problems in production planning of flexible manufacturing system (FMS) is machine tool selection and operation allocation problem that directly influences the production costs and times .In this paper minimizing machining cost, set-up cost and material handling cost as a multi-objective problem in flexible manufacturing systems environment are considered. We present a 0-1 integer linear programming model for the multiobjective machine tool selection and operation allocation problem and due to the large scale nature of the problem, solving the problem to obtain optimal solution in a reasonable time is infeasible, Paretoant colony optimization (P-ACO) approach for solving the multiobjective problem in reasonable time is developed. Experimental results indicate effectiveness of the proposed algorithm for solving the problem.

**Keywords:**
Flexible manufacturing system,
Production planning,
Machine tool selection,
Operation allocation,
Multiobjective optimization,
Metaheuristic.

##### 3539 A Comparison of Exact and Heuristic Approaches to Capital Budgeting

**Authors:**
Jindřiška Šedová,
Miloš Šeda

**Abstract:**

**Keywords:**
Capital budgeting,
knapsack problem,
GAMS,
heuristic method,
genetic algorithm.

##### 3538 Transfer Knowledge from Multiple Source Problems to a Target Problem in Genetic Algorithm

**Authors:**
Tami Alghamdi,
Terence Soule

**Abstract:**

To study how to transfer knowledge from multiple source problems to the target problem, we modeled the Transfer Learning (TL) process using Genetic Algorithms as the model solver. TL is the process that aims to transfer learned data from one problem to another problem. The TL process aims to help Machine Learning (ML) algorithms find a solution to the problems. The Genetic Algorithms (GA) give researchers access to information that we have about how the old problem is solved. In this paper, we have five different source problems, and we transfer the knowledge to the target problem. We studied different scenarios of the target problem. The results showed that combined knowledge from multiple source problems improves the GA performance. Also, the process of combining knowledge from several problems results in promoting diversity of the transferred population.

**Keywords:**
Transfer Learning,
Multiple Sources,
Knowledge
Transfer,
Domain Adaptation,
Source,
Target.

##### 3537 Optimization Using Simulation of the Vehicle Routing Problem

**Authors:**
Nayera E. El-Gharably,
Khaled S. El-Kilany,
Aziz E. El-Sayed

**Abstract:**

**Keywords:**
Discrete event system simulation,
optimization using simulation,
vehicle routing problem.

##### 3536 Tabu Search to Draw Evacuation Plans in Emergency Situations

**Authors:**
S. Nasri,
H. Bouziri

**Abstract:**

Disasters are quite experienced in our days. They are caused by floods, landslides, and building fires that is the main objective of this study. To cope with these unexpected events, precautions must be taken to protect human lives. The emphasis on disposal work focuses on the resolution of the evacuation problem in case of no-notice disaster. The problem of evacuation is listed as a dynamic network flow problem. Particularly, we model the evacuation problem as an earliest arrival flow problem with load dependent transit time. This problem is classified as NP-Hard. Our challenge here is to propose a metaheuristic solution for solving the evacuation problem. We define our objective as the maximization of evacuees during earliest periods of a time horizon T. The objective provides the evacuation of persons as soon as possible. We performed an experimental study on emergency evacuation from the tunisian children’s hospital. This work prompts us to look for evacuation plans corresponding to several situations where the network dynamically changes.

**Keywords:**
Dynamic network flow,
Load dependent transit time,
Evacuation strategy,
Earliest arrival flow problem.

##### 3535 Avoiding Pin Ball Routing Problem in Network Mobility Hand-Off Management

**Authors:**
M. Dinakaran,
P. Balasubramanie

**Abstract:**

**Keywords:**
Mobile IP,
Pinball routing problem,
NEMO

##### 3534 Optimal Capacitor Placement in Distribution Feeders

**Authors:**
N. Rugthaicharoencheep,
S. Auchariyamet

**Abstract:**

**Keywords:**
Capacitor Placement,
Distribution Systems,
Optimization Techniques

##### 3533 Reconstruction of Binary Matrices Satisfying Neighborhood Constraints by Simulated Annealing

**Authors:**
Divyesh Patel,
Tanuja Srivastava

**Abstract:**

This paper considers the NP-hard problem of reconstructing binary matrices satisfying exactly-1-4-adjacency constraint from its row and column projections. This problem is formulated into a maximization problem. The objective function gives a measure of adjacency constraint for the binary matrices. The maximization problem is solved by the simulated annealing algorithm and experimental results are presented.

**Keywords:**
Discrete Tomography,
exactly-1-4-adjacency,
simulated annealing.

##### 3532 Vibration Base Identification of Impact Force Using Genetic Algorithm

**Authors:**
R. Hashemi,
M.H.Kargarnovin

**Abstract:**

**Keywords:**
Genetic Algorithm,
Inverse problem,
Optimization,
Vibration.