Conference Papers
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506
Browse
3 results
Search Results
Item Hybrid heuristic shifting bottleneck procedure for parallel-machine job-shop scheduling using GPU(Institute of Electrical and Electronics Engineers Inc., 2015) Vilasagarapu, S.; Guddeti, G.In this paper, we implement the Parallel-Machine Job Shop Scheduling Problem (JSSP) using the modified shifting bottleneck procedure along with the heuristic Tabu search algorithm. JSSP has several real-time applications such as product manufacturing units, real-world train scheduling problem etc., Since JSSP is an NP hard problem, an optimal solution may not exist hence with the help of heuristic algorithm we try to find the approximate solution. Experimental results demonstrate that the modified shifting bottleneck procedure (SBP) shows better results than the existing SBP. And also with the help of meta-heuristic algorithm, the JSSP for larger instances can be solved easily. Results also demonstrate that GPU based Tabu search is on an average 1.8 times faster than CPU based Tabu search. © 2015 IEEE.Item Range assignment with k-power levels in a Wireless Sensor Network(Institute of Electrical and Electronics Engineers Inc., 2018) Lakshmi, M.P.; Shetty D, S.D.Energy minimization in Wireless Sensor Network (WSN) has gained the attention of several researchers because of its diverse applications in the real world. Optimization in power assignment increases the lifetime of a network. Available sensor nodes operate with a set of discrete power levels in which each sensor node can be assigned with one of the power levels from the given set. Dual power assignment problem was studied by researchers in which only two power levels are available for assignment in a WSN. As the Dual power assignment problem is proved to be NP-hard, several approximation algorithms were proposed. We consider k-power level assignment problem for a given set of sensor nodes with the objective of minimizing the total power assigned to the network provided each sensor node is assigned a power level only from the given set. We propose two heuristic algorithms; one is based on Euclidean Minimum Spanning Tree (MST) and the other is an Incremental Heuristic which runs in polynomial time. We present the simulation results to compare and analyze the proposed algorithms. We also conduct the experiments for various number of nodes by varying the number of power levels. © 2018 IEEE.Item Improved Algorithm for Minimum Power 2-Connected Subgraph Problem in Wireless Sensor Networks(Institute of Electrical and Electronics Engineers Inc., 2018) Lakshmi, M.; Shetty D, D.A Wireless Sensor Network (WSN) consists of small sensor nodes which communicate with each other using wireless radio channel and are used to monitor certain environmental parameters. Since the nodes are powered by a small battery of limited capacity, it is important to minimize the energy consumption in a WSN. By using an appropriate topology the energy utilization of the network can be minimized which results in an increased lifetime of a WSN. In practice, the transmission power of a sensor node can be tuned to obtain a required topology that satisfies certain connectivity constraints and this problem is known as Range Assignment Problem. For a given network, a reduced topology is constructed satisfying some connectivity constraints like k-connectivity, bounded diameter etc. Fault tolerance addresses the issue of node or link failure which aims at k-connectivity so that, the network has at least k vertex disjoint paths between any two nodes of the network. With the motivation of achieving fault tolerant network with minimum transmission energy, we consider Minimum power 2-connected subgraph (MP2CS) problem which is proved to be NP-hard. A polynomial time heuristic is proposed in this paper for the MP2CS problem and simulation is performed to compare with the existing algorithm. © 2018 IEEE.