We consider single part-type problems. Since all parts produced are identical, it is sufficient to determine the sequence of moves performed by the robot. The processing constraints define the cell to be a flowshop. The objective is the minimization of the steady-state cycle time to produce a part, or equivalently the maximization of the throughput rate. We study the problem of scheduling robot moves in dual gripper robot cells functioning in a bufferless environment. We develop an analytical framework for studying dual gripper robotic cells and examine the cycle time advantage of using a dual gripper rather than a single gripper robot. It is shown that an m-machine dual gripper robot cell can have at most double the productivity of its single gripper counterpart. We also propose a practical heuristic algorithm to compare productivity for given cell data. Computational testing of the algorithm on realistic problem instances is also described.

Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission time assumption, that is, the message transmission times between all pairs of vertices are equal. In this paper, we investigated the broadcast problem under four more general transmission time assumptions. In addition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any vertex to receive the message), (2) the average time to receive the message (both with and without ready times at the vertices), (3) the weighted average time to receive the message, and (4) the cycle time. Of the 20 problems thus generated, four admit polynomial time algorithms, 15 are (in the equivalent recognition version) unary NP-complete, and the complexity status of one remains open. All these results are proved, and heuristics with an attainable constant worst-case performance ratio are provided for two of the problems for which polynomial time algorithms are not found. © 1998 John Wiley & Sons, Inc. Networks 32:233–253, 1998

Abstract The complexity of many combinatorial algorithms is directly related to the number of upsets (filters) in an underlying partial order or, equivalently, to the number of downsets (ideals) that are the complements of upsets. In this paper, we investigate the expected number of upsets in randomly generated two‐dimensional partial orders and present a number of new results, together with simple combinatorial proofs of some known results. As an application of our results, we show that some well‐known algorithms for precedence constrained scheduling have nonpolynomial expected time and storage complexity.

Given two geometric sets A and B, it is said that A is containable in B provided A is isometric to a subset of B. Containability induces a partial order on any set of geometric figures, such as rectangles in the plane. A recent result states that for the set of rectangles in the plane, the containability partial order is of countably infinite dimension. In this paper the rectangle result is extended to other families of geometric figures and to a partial order obtained from quadratic polynomials.

Abstract An algorithm for selecting the kth smallest element of a distributed file using shout‐echo communication primitives is presented. It is shown that, for large values of k (e. g., the median), the proposed algorithm improves the existing upperbound.

The problem of sorting a file distributed over a number of sites of a communication network is examined. Two versions of this problem are investigated; distributed solution algorithms are presented; and their communication complexity analyzed both in the worst and in the average case. The worst case bounds are shown to be sharp, with respect to order of magnitude, for large files.