An edge is a bisector of a simple path if it contains the middle point of the path. In this paper, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and the other uses O(nlog n) work. The one using O(n) work is more efficient but only applicable to unweighted trees. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n/sup 2/) work.

An efficient method of solving problems of classification and selection in an FMS, using a minimum spanning tree, is proposed. Computer simulation examples which show a satisfactory result are provided. The total computational time spent is economical. The application of the method to these classes of problems is promising.>

An approach that can dynamically solve the planning and scheduling problem in a flexible manufacturing system (FMS) is presented. This problem is formulated as the determination of an optimal routing assignment of p automated guided vehicles among m workstations in order to accomplish N tasks in an FMS. A useful task representation called workgraph is introduced to facilitate the latter computation; then the A* search algorithm, the minimax criterion, and source heuristic rules are used to solve this routing assignment problem dynamically. The approach obtains a near-optimal solution in moderate computation time, and, in addition, solves some dynamic situations so as to make the FMS more flexible.>

A system with a two-level structure (high and low level) for dynamically solving the problem of planning and scheduling in an FMS (flexible manufacturing system) is presented. The problem is first formulated as the determination of an optimal routing assignment of p automated guided vehicles (AGVs) among m workstations to accomplish N tasks, facing several possible dynamical situations, e.g. change of due date or breakdown of some workstation(s). A hierarchical system is then built to solve this optimization problem in a dynamical manner. The low-level structure aims to solve the AGV routing problem among workstations given a set of AND/OR graphs which represent tasks to be processed. On the other hand, the high-level structure, using a rule-based system, provides necessary data for low-level use and simultaneously determines principles concerning how to respond to the occurrence of some unexpected events. It is shown that a near-optimal solution can be derived with moderate computation time that allows operation in an FMS to be more flexible.>