**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1820

# Search results for: critical path

##### 1820 The Problem of Using the Calculation of the Critical Path to Solver Instances of the Job Shop Scheduling Problem

**Authors:**
Marco Antonio Cruz-Chávez,
Juan Frausto-Solís,
Fernando Ramos-Quintana

**Abstract:**

A procedure commonly used in Job Shop Scheduling Problem (JSSP) to evaluate the neighborhoods functions that use the non-deterministic algorithms is the calculation of the critical path in a digraph. This paper presents an experimental study of the cost of computation that exists when the calculation of the critical path in the solution for instances in which a JSSP of large size is involved. The results indicate that if the critical path is use in order to generate neighborhoods in the meta-heuristics that are used in JSSP, an elevated cost of computation exists in spite of the fact that the calculation of the critical path in any digraph is of polynomial complexity.

**Keywords:**
Job Shop,
CPM,
critical path,
neighborhood,
meta-heuristic.

##### 1819 The Effect of Critical Activity on Critical Path and Project Duration in Precedence Diagram Method

**Abstract:**

The additional relationships i.e., start-to-start, finish-to-finish, and start-to-finish, between activity in Precedence Diagram Method (PDM) provides a more flexible schedule than traditional Critical Path Method (CPM). But, changing the duration of critical activities in the PDM network will have an anomalous effect on the critical path and the project completion date. In this study, we classified the critical activities in two groups i.e., 1. activity on single critical path and 2. activity on multi-critical paths, and six classes i.e., normal, reverse, neutral, perverse, decrease-reverse and increase-normal, based on their effects on project duration in PDM. Furthermore, we determined the maximum float of time by which the duration each type of critical activities can be changed without effecting the project duration. This study would help the project manager to clearly understand the behavior of each critical activity on critical path, and he/she would be able to change the project duration by shortening or lengthening activities based on project budget and project deadline.

**Keywords:**
Construction project management,
critical path method,
project scheduling,
precedence diagram method.

##### 1818 The Same or Not the Same - On the Variety of Mechanisms of Path Dependence

**Authors:**
Jürgen Beyer

**Abstract:**

**Keywords:**
path dependence,
increasing returns,
historicalinstitutionalism,
lock-in.

##### 1817 Decomposition of Graphs into Induced Paths and Cycles

**Authors:**
I. Sahul Hamid,
Abraham V. M.

**Abstract:**

A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.

**Keywords:**
Path decomposition,
Induced path decomposition,
Induced path decomposition number.

##### 1816 Optimal and Critical Path Analysis of State Transportation Network Using Neo4J

**Authors:**
Pallavi Bhogaram,
Xiaolong Wu,
Min He,
Onyedikachi Okenwa

**Abstract:**

A transportation network is a realization of a spatial network, describing a structure which permits either vehicular movement or flow of some commodity. Examples include road networks, railways, air routes, pipelines, and many more. The transportation network plays a vital role in maintaining the vigor of the nation’s economy. Hence, ensuring the network stays resilient all the time, especially in the face of challenges such as heavy traffic loads and large scale natural disasters, is of utmost importance. In this paper, we used the Neo4j application to develop the graph. Neo4j is the world's leading open-source, NoSQL, a native graph database that implements an ACID-compliant transactional backend to applications. The Southern California network model is developed using the Neo4j application and obtained the most critical and optimal nodes and paths in the network using centrality algorithms. The edge betweenness centrality algorithm calculates the critical or optimal paths using Yen's *k*-shortest paths algorithm, and the node betweenness centrality algorithm calculates the amount of influence a node has over the network. The preliminary study results confirm that the Neo4j application can be a suitable tool to study the important nodes and the critical paths for the major congested metropolitan area.

**Keywords:**
Transportation network,
critical path,
connectivity reliability,
network model,
Neo4J application,
optimal path,
critical path,
edge betweenness centrality index,
node betweenness centrality index,
Yen’s k-shortest paths.

##### 1815 Using Multi-Thread Technology Realize Most Short-Path Parallel Algorithm

**Authors:**
Chang-le Lu,
Yong Chen

**Abstract:**

**Keywords:**
Dijkstra algorithm,
parallel algorithms,
multi-thread
technology,
most short-path,
ratio.

##### 1814 An UML Statechart Diagram-Based MM-Path Generation Approach for Object-Oriented Integration Testing

**Authors:**
Ruilian Zhao,
Ling Lin

**Abstract:**

MM-Path, an acronym for Method/Message Path, describes the dynamic interactions between methods in object-oriented systems. This paper discusses the classifications of MM-Path, based on the characteristics of object-oriented software. We categorize it according to the generation reasons, the effect scope and the composition of MM-Path. A formalized representation of MM-Path is also proposed, which has considered the influence of state on response method sequences of messages. .Moreover, an automatic MM-Path generation approach based on UML Statechart diagram has been presented, and the difficulties in identifying and generating MM-Path can be solved. . As a result, it provides a solid foundation for further research on test cases generation based on MM-Path.

**Keywords:**
MM-Path,
Message Sequence,
Object-Oriented Integration Testing,
Response Method Sequence,
UML Statechart Diagram.

##### 1813 Induced Acyclic Path Decomposition in Graphs

**Authors:**
Abraham V. M.,
I. Sahul Hamid

**Abstract:**

**Keywords:**
Cycle decomposition,
Induced acyclic path decomposition,
Induced acyclic path decomposition number.

##### 1812 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

##### 1811 The Traffic Prediction Multi-path Energy-aware Source Routing (TP-MESR)in Ad hoc Networks

**Authors:**
Su Jin Kim,
Ji Yeon Cho,
Bong Gyou Lee

**Abstract:**

**Keywords:**
Ad hoc,
energy-aware,
multi-path,
routing protocol,
traffic prediction.

##### 1810 Module and Comodule Structures on Path Space

**Abstract:**

*kQ*, there is a trivial

*kQ*-module structure determined by the multiplication of path algebra

^{a}*kQ*and a trivial

^{a }*kQ*-comodule structure determined by the comultiplication of path coalgebra

^{c}*kQ*. In this paper, on path space

^{c}*kQ*, a nontrivial

*kQ*-module structure is defined, and it is proved that this nontrivial left

^{a}*kQ*-module structure is isomorphic to the dual module structure of trivial right

^{a}*kQ*-comodule. Dually, on path space

^{c}*kQ*, a nontrivial

*kQ*-comodule structure is defined, and it is proved that this nontrivial right

^{c}*kQ*-comodule structure is isomorphic to the dual comodule structure of trivial left

^{c}*kQ*-module. Finally, the trivial and nontrivial module structures on path space are compared from the aspect of submodule, and the trivial and nontrivial comodule structures on path space are compared from the aspect of subcomodule.

^{a}**Keywords:**
Quiver,
path space,
module,
comodule,
dual.

##### 1809 A Review on Comparative Analysis of Path Planning and Collision Avoidance Algorithms

**Authors:**
Divya Agarwal,
Pushpendra S. Bharti

**Abstract:**

Autonomous mobile robots (AMR) are expected as smart tools for operations in every automation industry. Path planning and obstacle avoidance is the backbone of AMR as robots have to reach their goal location avoiding obstacles while traversing through optimized path defined according to some criteria such as distance, time or energy. Path planning can be classified into global and local path planning where environmental information is known and unknown/partially known, respectively. A number of sensors are used for data collection. A number of algorithms such as artificial potential field (APF), rapidly exploring random trees (RRT), bidirectional RRT, Fuzzy approach, Purepursuit, A* algorithm, vector field histogram (VFH) and modified local path planning algorithm, etc. have been used in the last three decades for path planning and obstacle avoidance for AMR. This paper makes an attempt to review some of the path planning and obstacle avoidance algorithms used in the field of AMR. The review includes comparative analysis of simulation and mathematical computations of path planning and obstacle avoidance algorithms using MATLAB 2018a. From the review, it could be concluded that different algorithms may complete the same task (i.e. with a different set of instructions) in less or more time, space, effort, etc.

**Keywords:**
Autonomous mobile robots,
obstacle avoidance,
path planning,
and processing time.

##### 1808 An Improved Transfer Logic of the Two-Path Algorithm for Acoustic Echo Cancellation

**Abstract:**

**Keywords:**
Acoustic echo cancellation,
Echo return lossenhancement (ERLE),
Two-path algorithm,
Transfer logic

##### 1807 Three-Dimensional Off-Line Path Planning for Unmanned Aerial Vehicle Using Modified Particle Swarm Optimization

**Authors:**
Lana Dalawr Jalal

**Abstract:**

**Keywords:**
Obstacle Avoidance,
Particle Swarm Optimization,
Three-Dimensional Path Planning Unmanned Aerial Vehicles.

##### 1806 Efficient Hardware Implementation of an Elliptic Curve Cryptographic Processor Over GF (2 163)

**Authors:**
Massoud Masoumi,
Hosseyn Mahdizadeh

**Abstract:**

A new and highly efficient architecture for elliptic curve scalar point multiplication which is optimized for a binary field recommended by NIST and is well-suited for elliptic curve cryptographic (ECC) applications is presented. To achieve the maximum architectural and timing improvements we have reorganized and reordered the critical path of the Lopez-Dahab scalar point multiplication architecture such that logic structures are implemented in parallel and operations in the critical path are diverted to noncritical paths. With G=41, the proposed design is capable of performing a field multiplication over the extension field with degree 163 in 11.92 s with the maximum achievable frequency of 251 MHz on Xilinx Virtex-4 (XC4VLX200) while 22% of the chip area is occupied, where G is the digit size of the underlying digit-serial finite field multiplier.

**Keywords:**
Elliptic curve cryptography,
FPGA implementation,
scalar point multiplication.

##### 1805 Induced Graphoidal Covers in a Graph

**Authors:**
K. Ratan Singh,
P. K. Das

**Abstract:**

An induced graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ, every edge of G is in exactly one path in ψ and every member of ψ is an induced cycle or an induced path. The minimum cardinality of an induced graphoidal cover of G is called the induced graphoidal covering number of G and is denoted by ηi(G) or ηi. Here we find induced graphoidal cover for some classes of graphs.

**Keywords:**
Graphoidal cover,
Induced graphoidal cover,
Induced graphoidal covering number.

##### 1804 An Approach to the Solving Non-Steiner Minimum Link Path Problem

**Authors:**
V. Tereshchenko,
A. Tregubenko

**Abstract:**

In this study we survey the method for fast finding a minimum link path between two arbitrary points within a simple polygon, which can pass only through the vertices, with preprocessing.

**Keywords:**
Minimum link path,
simple polygon,
Steiner points,
optimal algorithm.

##### 1803 Memetic Algorithm Based Path Planning for a Mobile Robot

**Authors:**
Neda Shahidi,
Hadi Esmaeilzadeh,
Marziye Abdollahi,
Caro Lucas

**Abstract:**

In this paper, the problem of finding the optimal collision free path for a mobile robot, the path planning problem, is solved using an advanced evolutionary algorithm called memetic algorithm. What is new in this work is a novel representation of solutions for evolutionary algorithms that is efficient, simple and also compatible with memetic algorithm. The new representation makes it possible to solve the problem with a small population and in a few generations. It also makes the genetic operator simple and allows using an efficient local search operator within the evolutionary algorithm. The proposed algorithm is applied to two instances of path planning problem and the results are available.

**Keywords:**
Path planning problem,
Memetic Algorithm,
Representation.

##### 1802 Thermal Analysis of the Current Path from Circuit Breakers Using Finite Element Method

**Authors:**
Adrian T. Plesca

**Abstract:**

**Keywords:**
Current path,
power circuit breakers,
temperature
distribution,
thermal analysis.

##### 1801 Induced Acyclic Graphoidal Covers in a Graph

**Authors:**
K. Ratan Singh,
P. K. Das

**Abstract:**

**Keywords:**
Graphoidal cover,
Induced acyclic graphoidal cover,
Induced acyclic graphoidal covering number.

##### 1800 Path Planning of a Robot Manipulator using Retrieval RRT Strategy

**Authors:**
K. Oh,
J. P. Hwang,
E. Kim,
H. Lee

**Abstract:**

**Keywords:**
Path planning,
RRT,
6 DOF manipulator,
SVM.

##### 1799 Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks

**Authors:**
Siliang Wang,
Minghui Wang,
Jun Hu

**Abstract:**

**Keywords:**
pruning method,
stochastic,
time-varying networks,
optimal path planning.

##### 1798 Optimizing Network Latency with Fast Path Assignment for Incoming Flows

**Abstract:**

**Keywords:**
Latency,
Fast path assignment,
Bottleneck link.

##### 1797 Mobile Robot Path Planning Utilizing Probability Recursive Function

**Authors:**
Ethar H. Khalil,
Bahaa I. Kazem

**Abstract:**

**Keywords:**
Mobile robot,
path planning,
Bezier curve.

##### 1796 An Improved Dynamic Window Approach with Environment Awareness for Local Obstacle Avoidance of Mobile Robots

**Authors:**
Baoshan Wei,
Shuai Han,
Xing Zhang

**Abstract:**

**Keywords:**
Adaptive control,
dynamic window approach,
environment aware,
local obstacle avoidance,
mobile robots.

##### 1795 Retraction Free Motion Approach and Its Application in Automated Robotic Edge Finishing and Inspection Processes

**Authors:**
M. Nemer,
E. I. Konukseven

**Abstract:**

**Keywords:**
Offline programming,
CAD-based tools,
edge deburring,
edge scanning,
path generation.

##### 1794 Improving Survivability in Wireless Ad Hoc Network

**Authors:**
Seyed Ali Sadat Noori,
Elham Sahebi Bazaz

**Abstract:**

**Keywords:**
Wireless Ad Hoc Networks,
Reliability,
Routing,
Disjoint Path

##### 1793 Tool Path Generation and Manufacturing Process for Blades of a Compressor Rotor

**Abstract:**

**Keywords:**
5-axis machining,
tool orientation,
lead and tilt angles,
tool path generation.

##### 1792 Fast Return Path Planning for Agricultural Autonomous Terrestrial Robot in a Known Field

**Authors:**
Carlo Cernicchiaro,
Pedro D. Gaspar,
Martim L. Aguiar

**Abstract:**

The agricultural sector is becoming more critical than ever in view of the expected overpopulation of the Earth. The introduction of robotic solutions in this field is an increasingly researched topic to make the most of the Earth's resources, thus going to avoid the problems of wear and tear of the human body due to the harsh agricultural work, and open the possibility of a constant careful processing 24 hours a day. This project is realized for a terrestrial autonomous robot aimed to navigate in an orchard collecting fallen peaches below the trees. When it receives the signal indicating the low battery, it has to return to the docking station where it will replace its battery and then return to the last work point and resume its routine. Considering a preset path in orchards with tree rows with variable length by which the robot goes iteratively using the algorithm D*. In case of low battery, the D* algorithm is still used to determine the fastest return path to the docking station as well as to come back from the docking station to the last work point. MATLAB simulations were performed to analyze the flexibility and adaptability of the developed algorithm. The simulation results show an enormous potential for adaptability, particularly in view of the irregularity of orchard field, since it is not flat and undergoes modifications over time from fallen branch as well as from other obstacles and constraints. The D* algorithm determines the best route in spite of the irregularity of the terrain. Moreover, in this work, it will be shown a possible solution to improve the initial points tracking and reduce time between movements.

**Keywords:**
Path planning,
fastest return path,
agricultural terrestrial robot,
autonomous,
docking station.

##### 1791 Integer Programming Model for the Network Design Problem with Facility Dependent Shortest Path Routing

**Authors:**
Taehan Lee

**Abstract:**

**Keywords:**
Integer programming,
multicommodity network
design,
routing,
shortest path.