Abstract: This paper considers a scheduling problem in flexible
flow shops environment with the aim of minimizing two important
criteria including makespan and cumulative tardiness of jobs. Since
the proposed problem is known as an Np-hard problem in literature,
we have to develop a meta-heuristic to solve it. We considered
general structure of Genetic Algorithm (GA) and developed a new
version of that based on Data Envelopment Analysis (DEA). Two
objective functions assumed as two different inputs for each Decision
Making Unit (DMU). In this paper we focused on efficiency score of
DMUs and efficient frontier concept in DEA technique. After
introducing the method we defined two different scenarios with
considering two types of mutation operator. Also we provided an
experimental design with some computational results to show the
performance of algorithm. The results show that the algorithm
implements in a reasonable time.
Abstract: Assembly line balancing is a very important issue in
mass production systems due to production cost. Although many
studies have been done on this topic, but because assembly line
balancing problems are so complex they are categorized as NP-hard
problems and researchers strongly recommend using heuristic
methods. This paper presents a new heuristic approach called the
critical task method (CTM) for solving U-shape assembly line
balancing problems. The performance of the proposed heuristic
method is tested by solving a number of test problems and comparing
them with 12 other heuristics available in the literature to confirm the
superior performance of the proposed heuristic. Furthermore, to
prove the efficiency of the proposed CTM, the objectives are
increased to minimize the number of workstation (or equivalently
maximize line efficiency), and minimizing the smoothness index.
Finally, it is proven that the proposed heuristic is more efficient than
the others to solve the U-shape assembly line balancing problem.
Abstract: This paper presents a new heuristic algorithm for the classical symmetric traveling salesman problem (TSP). The idea of the algorithm is to cut a TSP tour into overlapped blocks and then each block is improved separately. It is conjectured that the chance of improving a good solution by moving a node to a position far away from its original one is small. By doing intensive search in each block, it is possible to further improve a TSP tour that cannot be improved by other local search methods. To test the performance of the proposed algorithm, computational experiments are carried out based on benchmark problem instances. The computational results show that algorithm proposed in this paper is efficient for solving the TSPs.
Abstract: Application of Expert System in the area of agriculture would take the form of Integrated Crop Management decision aids and would encompass water management, fertilizer management, crop protection systems and identification of implements. In order to remain competitive, the modern farmer often relies on agricultural specialists and advisors to provide information for decision-making. An expert system normally composed of a knowledge base (information, heuristics, etc.), inference engine (analyzes knowledge base), and end user interface (accepting inputs, generating outputs). Software named 'CROP-9-DSS' incorporating all modern features like, graphics, photos, video clippings etc. has been developed. This package will aid as a decision support system for identification of pest and diseases with control measures, fertilizer recommendation system, water management system and identification of farm implements for leading crops of Kerala (India) namely Coconut, Rice, Cashew, Pepper, Banana, four vegetables like Amaranthus, Bhindi, Brinjal and Cucurbits. 'CROP-9-DSS' will act as an expert system to agricultural officers, scientists in the field of agriculture and extension workers for decision-making and help them in suggesting suitable recommendations.
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.
Abstract: Sudoku is a kind of logic puzzles. Each puzzle consists
of a board, which is a 9×9 cells, divided into nine 3×3 subblocks
and a set of numbers from 1 to 9. The aim of this puzzle is to
fill in every cell of the board with a number from 1 to 9 such
that in every row, every column, and every subblock contains each
number exactly one. Sudoku puzzles belong to combinatorial problem
(NP complete). Sudoku puzzles can be solved by using a variety of
techniques/algorithms such as genetic algorithms, heuristics, integer
programming, and so on. In this paper, we propose a new approach for
solving Sudoku which is by modelling them as block-world problems.
In block-world problems, there are a number of boxes on the table
with a particular order or arrangement. The objective of this problem
is to change this arrangement into the targeted arrangement with the
help of two types of robots. In this paper, we present three models
for Sudoku. We modellized Sudoku as parameterized multi-agent
systems. A parameterized multi-agent system is a multi-agent system
which consists of several uniform/similar agents and the number of
the agents in the system is stated as the parameter of this system. We
use Temporal Logic of Actions (TLA) for formalizing our models.
Abstract: In this study, we are interested in the economic lot
scheduling problem (ELSP) that considers manufacturing of the
serviceable products and remanufacturing of the reworked products. In
this paper, we formulate a mathematical model for the ELSP with
reworks using the basic period approach. In order to solve this
problem, we propose a search algorithm to find the cyclic multiplier ki
of each product that can be cyclically produced for every ki basic
periods. This research also uses two heuristics to search for the optimal
production sequence of all lots and the optimal time length of the basic
period so as to minimize the average total cost. This research uses a
numerical example to show the effectiveness of our approach.
Abstract: The concept of order reduction by least-squares moment matching and generalised least-squares methods has been extended about a general point ?a?, to obtain the reduced order models for linear, time-invariant dynamic systems. Some heuristic criteria have been employed for selecting the linear shift point ?a?, based upon the means (arithmetic, harmonic and geometric) of real parts of the poles of high order system. It is shown that the resultant model depends critically on the choice of linear shift point ?a?. The validity of the criteria is illustrated by solving a numerical example and the results are compared with the other existing techniques.
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.
Abstract: Virtualization-based server consolidation has been
proven to be an ideal technique to solve the server sprawl problem by
consolidating multiple virtualized servers onto a few physical servers
leading to improved resource utilization and return on investment. In
this paper, we solve this problem by using existing servers, which are
heterogeneous and diversely preferred by IT managers. Five practical
consolidation rules are introduced, and a decision model is proposed to
optimally allocate source services to physical target servers while
maximizing the average resource utilization and preference value. Our
model can be regarded as a multi-objective multi-dimension
bin-packing (MOMDBP) problem with constraints, which is strongly
NP-hard. An improved grouping generic algorithm (GGA) is
introduced for the problem. Extensive simulations were performed and
the results are given.
Abstract: In this research, the flow pattern influence on
performance of a micro PEMFC was investigated
experimentally. The investigation focused on the impacts of
bend angels and rib/channel dimensions of serpentine flow
channel pattern on the performance and investigated how they
improve the performance. The fuel cell employed for these
experiments was a micro single PEMFC with a membrane of
1.44 cm2 Nafion NRE-212. The results show that 60° and 120°
bend angles can provide the better performances at 20 and 40
sccm inlet flow rates comparing to that the conventional design.
Additionally, wider channel with narrower rib spacing gives
better performance. These results may be applied to develop
universal heuristics for the design of flow pattern of micro
PEMFC.
Abstract: In this research, we have developed a new efficient
heuristic algorithm for the dynamic facility layout problem with
budget constraint (DFLPB). This heuristic algorithm combines two
mathematical programming methods such as discrete event
simulation and linear integer programming (IP) to obtain a near
optimum solution. In the proposed algorithm, the non-linear model
of the DFLP has been changed to a pure integer programming (PIP)
model. Then, the optimal solution of the PIP model has been used in
a simulation model that has been designed in a similar manner as the
DFLP for determining the probability of assigning a facility to a
location. After a sufficient number of runs, the simulation model
obtains near optimum solutions. Finally, to verify the performance of
the algorithm, several test problems have been solved. The results
show that the proposed algorithm is more efficient in terms of speed
and accuracy than other heuristic algorithms presented in previous
works found in the literature.
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.
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.
Abstract: Fuzzy Cognitive Maps (FCMs) is a causal graph, which shows the relations between essential components in complex systems. Experts who are familiar with the system components and their relations can generate a related FCM. There is a big gap when human experts cannot produce FCM or even there is no expert to produce the related FCM. Therefore, a new mechanism must be used to bridge this gap. In this paper, a novel learning method is proposed to construct causal graph based on historical data and by using metaheuristic such Tabu Search (TS). The efficiency of the proposed method is shown via comparison of its results of some numerical examples with those of some other methods.
Abstract: Asynchronous Transfer Mode (ATM) is widely used
in telecommunications systems to send data, video and voice at a
very high speed. In ATM network optimizing the bandwidth through
dynamic routing is an important consideration. Previous research
work shows that traditional optimization heuristics result in suboptimal
solution. In this paper we have explored non-traditional
optimization technique. We propose comparison of two such
algorithms - Genetic Algorithm (GA) and Tabu search (TS), based on
non-traditional Optimization approach, for solving the dynamic
routing problem in ATM networks which in return will optimize the
bandwidth. The optimized bandwidth could mean that some
attractive business applications would become feasible such as high
speed LAN interconnection, teleconferencing etc. We have also
performed a comparative study of the selection mechanisms in GA
and listed the best selection mechanism and a new initialization
technique which improves the efficiency of the GA.
Abstract: Summarizing skills have been introduced to English
syllabus in secondary school in Malaysia to evaluate student-s comprehension for a given text where it requires students to employ several strategies to produce the summary. This paper reports on our effort to develop a computer-based summarization assessment system
that detects the strategies used by the students in producing their
summaries. Sentence decomposition of expert-written summaries is
used to analyze how experts produce their summary sentences. From
the analysis, we identified seven summarizing strategies and their
rules which are then transformed into a set of heuristic rules on how
to determine the summarizing strategies. We developed an algorithm
based on the heuristic rules and performed some experiments to
evaluate and support the technique proposed.
Abstract: Today, money laundering (ML) poses a serious threat
not only to financial institutions but also to the nation. This criminal
activity is becoming more and more sophisticated and seems to have
moved from the cliché of drug trafficking to financing terrorism and
surely not forgetting personal gain. Most international financial
institutions have been implementing anti-money laundering solutions
(AML) to fight investment fraud. However, traditional investigative
techniques consume numerous man-hours. Recently, data mining
approaches have been developed and are considered as well-suited
techniques for detecting ML activities. Within the scope of a
collaboration project for the purpose of developing a new solution for
the AML Units in an international investment bank, we proposed a
data mining-based solution for AML. In this paper, we present a
heuristics approach to improve the performance for this solution. We
also show some preliminary results associated with this method on
analysing transaction datasets.
Abstract: The Maximum Weighted Independent Set (MWIS)
problem is a classic graph optimization NP-hard problem. Given an
undirected graph G = (V, E) and weighting function defined on the
vertex set, the MWIS problem is to find a vertex set S V whose total
weight is maximum subject to no two vertices in S are adjacent. This
paper presents a novel approach to approximate the MWIS of a graph
using minimum weighted vertex cover of the graph. Computational
experiments are designed and conducted to study the performance
of our proposed algorithm. Extensive simulation results show that
the proposed algorithm can yield better solutions than other existing
algorithms found in the literature for solving the MWIS.
Abstract: The physical methods for RNA secondary structure prediction are time consuming and expensive, thus methods for computational prediction will be a proper alternative. Various algorithms have been used for RNA structure prediction including dynamic programming and metaheuristic algorithms. Musician's behaviorinspired harmony search is a recently developed metaheuristic algorithm which has been successful in a wide variety of complex optimization problems. This paper proposes a harmony search algorithm (HSRNAFold) to find RNA secondary structure with minimum free energy and similar to the native structure. HSRNAFold is compared with dynamic programming benchmark mfold and metaheuristic algorithms (RnaPredict, SetPSO and HelixPSO). The results showed that HSRNAFold is comparable to mfold and better than metaheuristics in finding the minimum free energies and the number of correct base pairs.