Browsing by Author "Wang, Ching-Cheng"

Now showing 1 - 5 of 5
  • Thumbnail Image
    The effect of the dependency in the Markov renewal arrival process on the various performance measures of an exponential server queue
    Patuwo, Butje Eddy (Virginia Polytechnic Institute and State University, 1989)
    The thesis of this paper is to investigate how the dependency in the arrival process affects the queueing performance measures. The Markov renewal arrival process (MRAP) was chosen as the arrival process. This choice was made because many of the typical arrival processes can be obtained as special cases of the MRAP. But the main reason behind this choice is that the interarrival times of the MRAP are dependent. We assume that the queue is a single server queue with exponential service time and the investigation was carried out numerically because no analytical solution was available. There are 5 parameters of the arrival process used in this investigation: the traffic intensity (ρ), the squared coefficient of variation (scν), the serial correlation defined by the lag-1 correlation (corr) plus the rate ξ and the coefficient of skewness (𝛾). Here are the performance measures of the MR/M/1 queue we investigate: the expected queue length at arbitrary times (L𝓽), the standard deviation (σ) of the queue length at arbitrary times and the caudal characteristic η. The other performance measures such as: the expected queue length at arrival time, the waiting time, the sojourn time, etc. can be easily obtained from L𝓽. We compare these performance measures against those of the corresponding GI/M/1 queue. When the lag-1 correlation of the arrival process is negative (this means that the lags of the serial correlation alternate in signs), the Lt of the MR/M/1 queue is smaller (but not by much) than the L𝓽 of the GI/M/1 queue. Therefore, we focus our attention to the MR/M/1 queue with positive serial correlation. The results are presented using graphs. We find that the coefficient of skewness of the arrival process (𝛾) plays an important role. The L𝓽 curve decreases rapidly as 𝛾 increases and after certain values of 𝛾 called the turning region, the L𝓽 curves Hatten. This important observation indicates that to the left of the turning region, the L𝓽 is almost insensitive to the dependency in the arrival process. However, to the right of the turning region, the L𝓽 is sensitive to the positive serial correlation in the arrival process. Highly correlated arrival process (large corr and ξ) can cause the L𝓽 to be significantly larger than the L𝓽 for the uncorrelated queue. For the MR/M/1 queue, the magnitude of the standard deviation σ is larger than the corresponding L𝓽. However, the shapes of the σ curves are similar to those of the L𝓽 curves. So, all of the conclusions drawn for the L𝓽 also apply to the standard deviation σ. For the M/M/1 queue, the caudal characteristic η equals to the traffic intensity ρ (η=ρ). For the uncorrelated Gl/M/1 queue, one would expect that when scν<1.0, η<ρ (i.e., the queue would behave like a H/M/1 queue) and when scν>1.0, η>ρ (i.e., the queue would behave like a H/M/1 queue). Our results indicates that this is not necessarily true. We found again that the coefficient of skewness (𝛾) plays an important role. For the uncorrelated GI/M/1 queue with scν>1.0, η can be smaller than ρ when 𝛾 is large enough. For the correlated MR/M/1 queue, even for scν<1.0, a low 𝛾 value combined with the positive serial correlation can cause η to be larger than ρ. On the other hand, scν>1.0 does not necessarily results in η>ρ. A large value of 𝛾 can cause η to be smaller than ρ, even for the queue with highly correlated interarrival times.
  • Thumbnail Image
    A general robot path verification simulation system: GRPVSS
    Li, Chungwuu (Virginia Tech, 1987-08-24)
    Collision-detection is a critical task for off-line robot path planning. A general robot path verification simulation system, GRPVSS, applicable for all industrial robots with open-looped links, is created to verify the intended robot path. The manipulator and obstacles are modeled by convex polyhedra to reduce the computation burden required by the collision detection algorithm. As a kinematic simulator, GRPVSS employs motion-time profiles or ideal trapezoid profiles which describe the position-vs-time relation of an individual joint, to generate the robot working trajectory. This approach makes the to-be-verified working path closer to the real one. Both point-to-point(PTP) and continuous path(CP) operations can be simulated by GRPVSS. Collision detection is conducted by performing geometric interference detection between the static configurations of the expanded moving robot and the static obstacles at each simulation step. Inn this case, the resolution of a simulation is critical to path verification. Simulations with low resolution take the risk of undetected collisions, while simulations with high resolution consume too much computing time. GRPVSS computes and employs the lowest resolution level that yields 100% path verification for the specified tolerances of manipulator dimensions. The tolerance value is specified by the user but should not be specified smaller than the positioning accuracy of the simulated industrial robot. The links of the manipulator are expanded by the amount of tolerance. GRPVSS is a graphic simulator. A systematic control supervisor is constructed for the simulator to request input and to proceed all functions interactively with users. The robot motion of a simulated path is animated on a 3-D graphical screen. A11 collision configurations and related information of the simulated path are stored in a file and shown on the screen. The graphical display works on graPHIGS, one of the 3-D graphical software packages published by IBM.
  • Thumbnail Image
    A geometric programming based procedure to design bridge superstructures
    Mehrotra, Anuj (Virginia Tech, 1988-06-21)
    The routine procedure for designing bridge superstructures relies heavily on the past experience of the designer and is extremely time consuming and costly to try out alternative designs. Typically, a designer is more concerned about satisfying the design requirements laid down by the American Association of State Highway and Transportation Officials (AASHTO) than in coming up with the best possible design from the economic point of view. Thus, application of suitable mathematical programming techniques to determine optimal designs can result in tremendous savings. In this thesis, a procedure based on Generalized Geometric Programming (GGP) is developed to optimally design and select bridge superstructures. The bridge superstructure design problems are formulated as GGP problems incorporating all the design considerations as specified by AASHTO and the Virginia Department of Transportation (VDOT). A primal based algorithm is used in which, the resulting optimization problems are transformed to the solution of a series of Linear Programming problems that are easy to solve. A computer implementation of the algorithm is also developed. The software is extremely versatile and user friendly. It provides several options to help determine the optimal solution under varying design conditions, and is implemented on several representative problems provided by VDOT. Comparison of the resulting optimal with the existing designs promises huge savings in terms of both cost and effort. The methodology that is developed can be used to solve other Engineering Designs Problems as well.
  • Thumbnail Image
    An integrated approach to the optimal sequencing of robot operations in a workcell
    Desai, Chetan J. (Virginia Tech, 1988-02-01)
    In this research we develop an integrated approach to optimally sequence robot operation in a workcell. The workcell represents a f1owshop operation with multiple robots transporting jobs among machines. A buffer of infinite capacity is available ahead of each machine. A robot transports jobs from buffers to machines and from machines to buffers. The robots used in the system are 5 jOint cylindrical coordinate robots. All the robots are identical in design and capability. For the type of robot used in this study its closed form inverse kinematic solution is known. The objective is to determine the sequence of robot operations so as to minimize the total time needed to complete all jobs (known as makespan). The integrated approach consists of determining optimal robot task sequences using a branch and bound procedure. and a graphical simulation procedure to display the robots as they perform transport operation. The branch and bound algorithm, which is an implicit enumeration scheme, is used to derive several near optimal robot task sequences. For the branch and bound algorithm. each node is a transport operation. Lower bound on the makespan is machine based and is computed at each node for further branching. The graphical simulation is used to detect interference among robots which is hard to be incorporated in the branch and bound procedure. Infeasible robot sequences are discarded and other solutions from the branch and bound procedure are displayed using the graphical simulation procedure to determine a near optimal and feasible sequence. The integrated approach is implemented on a prototype system. A command driven general purpose graphics system MOVIE.BYU is used for the graphical simulation of the robotic workcell and robot motion. The entire system is available in an integrated environment. A powerful programming language Rexx is used to manage various programs and data. Also, intermediate Rexx programs are generated during execution to allow MOVIE.BYU to edit and display animation data on the Tektronix 41XX series of terminals. The entire system is flexible and modular to be able to be used for various different applications.
  • Thumbnail Image
    Special versus standard algorithms for large-scale harvest scheduling problems
    Liu, Chiun-Ming (Virginia Tech, 1988-12-15)
    This thesis is concerned with structure exploitation and the design of algorithms for solving large-scale harvest scheduling problems. We discover that the harvest scheduling problem involving area constraints possesses a network structure. In Model I-Form 1, the network constraints form a separable block diagonal structure, which permits one to solve for the decision variables belonging to each individual area constraints as independent knapsack problems. In Model II-Form 1, the network constraints constitute a longest path problem, and a Longest Path Algorithm is developed to solve this problem in closed form. The computational time for this scheme is greatly reduced over that for the revised simplex method. The Dantzig-Wolfe algorithm is coded and tuned to solve general Model II problems, taking advantage of the Longest Path Algorithm in the subproblem step, and using the revised simplex method to solve the master problems. Computational results show that the algorithm solves problems to within one percent accuracy far more efficiently than the revised simplex method using MPS III. Both the CPU time and number of iterations for the Dantzig-Wolfe algorithm are less than those for the MPS III, depending on the problem size. Results also suggest that the Dantzig-Wolfe algorithm makes rapid advances in the initial iterations, but has a slow convergence rate in the final iterations. A Primal-Dual Conjugate Subgradient Algorithm is also coded and tuned to solve general Model II problems. Results show that the computational effort is greatly affected by the number of side constraints. If the number of side constraints is restricted, the Primal-Dual Conjugate Subgradient Algorithm can give a more efficient algorithm for solving harvest scheduling problems. Overall, from a storage requirement viewpoint, the Primal-Dual Conjugate Subgradient Algorithm is best, followed by the Dantzig-Wolfe algorithm and then the revised simplex method. From a computational efficiency viewpoint, if the optimality criterion is suitably selected, the Dantzig-Wolfe algorithm is best, provided that the number of side constraints are not too many, followed by the revised simplex method and then the Primal-Dual Conjugate Subgradient Algorithm.