Critical node method and its applications.
Item
-
Title
-
Critical node method and its applications.
-
Identifier
-
AAI9732978
-
identifier
-
9732978
-
Creator
-
Sun, Zhaolun.
-
Contributor
-
Adviser: Emre Veral
-
Date
-
1997
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Business Administration, Management | Operations Research | Engineering, Industrial
-
Abstract
-
In this research, a new method, called critical node method (CNM), is developed based on the well known critical path method (CPM).;A CNM based procedure for project scheduling (PS) is developed which maintains the advantages of the CPM, while eliminating its drawbacks. Moreover, the CNM procedure makes scheduling and updating simpler. The new procedure identifies not only the conventional critical path, but also the critical path from every node to the sink node. With newly defined slacks, updating a project involves little effort.;In addition, CNM based procedures are developed to solve the following problems: (a) the shortest path (SP) problem, (b) resource constrained project scheduling (RCPS) problems, and (c) assembly line balancing (ALB) problems. Procedures developed for PS and SP problems are accurate. Their special features are discussed, and complexity analysis is conducted to show that they are more efficient than existing procedures.;Since RCPS and ALB problems are NP-Complete, heuristic procedures based on CNM are developed. There is no searching or back tracking involved in either procedure, therefore they belong to the group of the most efficient procedures.;To test the quality of the solutions reached by CNM based procedures, this study examines a large amount of data, including the most widely used benchmark problem sets. Examination identifies an ill structure existing among many test problems, especially the computer generated ones. Therefore, only test problems without this ill structure are used to test CNM based heuristic procedures. The test results show that CNM based procedures are simple, efficient, and give very good solutions compared to other heuristics.;Although not presented in this paper, the CNM can also be applied to solve the following problems: (a) the minimum spanning tree problem, (b) the minimum cut-maximum flow problem, and (c) the scheduling problem in parallel computing. We believe that chances are good for finding new applications in other areas with future research.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
