Abstract: The Job-Shop Scheduling Problem (JSSP) is considered as one of the difficult combinatorial optimization problems and treated as a member of NP-complete problem class. In this paper, we consider JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. First, we develop a genetic algorithm (GA) based approach for solving JSSPs. We then introduce a number of priority rules such as partial reordering, gap reduction and restricted swapping to improve the performance of the GA. We run the GA incorporating these rules in a number of different ways. We solve 40 benchmark problems and compared their results with that of a number of well-known algorithms. We obtain optimal solutions for 27 problems, and the overall performance of our algorithms is quite encouraging.
Abstract: The Job-Shop Scheduling Problem (JSSP) is a well-known difficult combinatorial optimization problem. Many algorithms have been proposed for solving JSSP in the last few decades, including algorithms based on evolutionary techniques. However, there is room for improvement in solving medium to large scale problems effectively. In this paper, we present a Hybrid Genetic Algorithm (HGA) that includes a heuristic job ordering with a Genetic Algorithm. We apply HGA to a number of benchmark problems. It is found that the algorithm is able to improve the solution obtained by traditional genetic algorithm.
Abstract: The Job-Shop Scheduling Problem (JSSP) is one of the most critical combinatorial optimization problems. The objective of JSSP in this research is to minimize the makespan. In this paper, we propose two Genetic Algorithm (GA) based approaches for solving JSSP. Firstly, we design a simple heuristic to reduce the completion time of jobs on the bottleneck
machines that we call the reducing bottleneck technique (RBT). This heuristic was implemented in conjunction with a GA. Secondly; we propose to fill any possible gaps left in the simple GA solutions by the tasks that are scheduled later. We call this process the gap-utilization technique (GUT). With GUT, we also apply a swapping technique that deals only with the bottleneck job. We study 35 test problems with known solutions, using the existing GA and our proposed two algorithms. We obtain optimal solutions for 23 problems, and the solutions are very close for the rest.
Abstract: The candidate system highlights the modification of ordinary face recognition strategy. Real valued face pattern remove the undesirable changes of input due to the shifting and intensity variation. The two stage system developed by Modified KSOM technique allows identifying the face patterns at various poses. Modification developed in the determination of neighborhood size and consideration of existing patterns. Modified technique allows a high performance learning strategy and optimum stability of the network. Input of the system is a function of gray level. Former stage is concerned with the conversion of visual pattern into a raw format to process with the MKSOM network. The processed pattern is the input vector for neural network. The system also deals with performance measurement of the MKSOM with some other existing pattern recognition techniques. Modification made with the pattern of input which avoids the traditional binary input. This approach extremely minimize the learning time comparing with the existing pattern recognition system. By avoiding propagation, it is possible to minimize the computation and weight adoption. MKSOM maintains the individuality of patterns with its weight set.
Abstract: This paper presents a new heuristic algorithm for the Multiple-Choice Multi-Dimension Knapsack Problem (MMKP) in PRAM model. MMKP is a variant of the classical 0-1 knapsack problem, has a knapsack with
multidimensional capacity constraints, groups of items, each item having a utility value and multidimensional resource constraints. The problem is to maximize the total value of the items in the knapsack with the constraint of not exceeding the knapsack capacity. Since MMKP is an NP-Hard problem, its exact solution is not suitable for real time problems, so heuristic based approximation algorithms are developed. We present a parallel heuristic algorithm here that runs in O(log nl(log n + logm + log log l)) time in CRCW PRAM machine; taking O(n log n(log n + ml)) operations. Experimental results show that it achieves 95% optimal solution on average. This also means that we have a sequential heuristic running in O(n log n(log n + ml)) time which seems to be remarkable since M-HEU, a celebrated sequential heuristic although achieves 96% of optimal value, takes O(mn2l 2 ) running time.
Abstract: Allocation and reservation of resources, such as CPU cycles and I/O bandwidth of multimedia servers and link
bandwidth in the network, is essential to ensure Quality of Service (QoS) for multimedia services delivered over the Internet. In this paper, we have proposed a new semidistributed architecture for admission control and QoS
adaptation of multimedia sessions to maximize revenue from multimedia services for Distributed Video on Demand System (DVoDS). We have introduced the mapping of Utility Model - Distributed (UM-D) by semidistributed controller to the Multidimensional Multiplechoice Knapsack Problem (MMKP), a variant of the
classical 0-1 Knapsack Problem. An exact solution of MMKP, an NP-hard problem, is not applicable for the online admission control problem in the VoD System. Therefore we have applied heuristic, I-HEU for solving the MMKP for online real-time admission control and QoS adaptation. We have applied the admission control strategy described in the UM-D to the set of Media Server Farms providing streaming videos to users. The performance of semi-distributed architecture applied in a simulated environment over a set of Media Server Farm has been discussed detail using the experimental outcome.
Abstract: This paper describes a system to recognize handwritten Bangla characters using a two-stage classification approach, for a subset of the Bangla alphabet. In the first
stage, an unknown character is pre-classified into one of the two groups: complete and exhaustive characters. Then, in the second stage, members of the pre-classified group are further analyzed using a statistical classifier for final recognition. A recognition rate of around 75% was achieved for the first choice and more than 95% for the top three choices. The new approach of the system is to use the modified Kohonen’s SOM for better performance of the system and faster result. Self organizing network rapidly reduces the time complexity.
