The partitioning of a rectangular grid graph with weighted vertices into p connected components such that the component of smallest weight is as heavy as possible (the max-min problem) is considered. It is shown that the problem is NP-hard for rectangles with at least three rows. A shifting algorithm is given which approximates the optimal solution. Bounds for the relative error are determined under a posteriori hypotheses. A further shifting algorithm is also given which allows for error estimates under a priori hypotheses and for asymptotic error estimates. A similar approach can be taken with the problem of finding the partition whose largest component is as small as possible (the min-max problem). The case of rectangles with two rows has a polynomial algorithm and is dealt with in another paper. © 1998 John Wiley & Sons, Inc. Networks 32: 115–125, 1998

This paper deals with models for flow management problems in flexible assembly systems (FASs). The system consists of a set of machines that must perform the assembly of a number of parts, possibly of different types. Each part type requires a set of operations; the precedence relations among the operations are specified by an assembly tree. Machines are provided with limited-capacity tool magazines and a finite buffer for holding parts. Each machine can be tooled to perform only a particular subset of the operations required by the whole process. One problem is that of finding a feasible assignment of operations to machines and a feasible schedule of the subassemblies in order to minimize the completion time of all of the parts. In this paper, the problem is analysed as a case of pipelined assembly, i.e., when the FAS is characterized by a serial transportation system (flow line) and there exist a dominating path in the assembly tree. We present polynomial-time dynamic programming algorithms for solving the problem for both single-type and multi-type production.>

In a frequent practical situation one possesses inconsistent fragmentary data concerning some industrial process or natural phenomenon. It is an interesting and reasonable task to assess what the most concise way to store or transmit them would be. The authors consider the zero-error case of the problem, i.e., we would like to save all the data incorporating them into the most concise but necessarily alternative consistent data structures. More precisely, we want to find a set of alternatives which requires the minimum total storage place. From the mathematical viewpoint the model is information-theoretic and gives a common framework to deal with many combinatorial problems in the theory of extremal hypergraphs. From the practical viewpoint the interest of the mathematical theory is to produce new information measures capturing the inconsistency in the data.>

The authors deal with the problem of part flow management in a class of assembly systems characterized by a serial transportation system connecting the workstations. The system assembles a number of identical units, each requiring a set of operations. Each operation is performed by a workstation and each workstation can perform any operation. The problem consists of assigning the operations to the workstations to maximize some productivity index of the system. Usually, a tree-like precedence relationship exists among the operations (assembly tree). The problem is analyzed for the case in which a dominating path on the assembly tree exists. A polynomial time dynamic programming algorithm is presented for the optimal assignment of operations to workstations.>

Some optimization models for the problem of tool management in flexible manufacturing cells are presented. The cell considered consists of two machines (working centers) in charge of executing a set of part programs. The tools required by the machining operations are located in a central tool magazine and are moved to the machines by a tool handling system consisting of two shuttles and one robot. The robot picks and places the tools from/in the magazine; each shuttle exchanges the tools with the robot and with the machine. The problem is to synchronize the robot and shuttle moves in order to maximize the cell productivity (minimize the machines' idle time). Two different models are proposed for the situation in which a configuration of tools in the magazine is given and in which a budget for tool purchasing is fixed.>

Abstract In the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpillars.

The problem of part routing and scheduling in flexible manufacturing systems is considered with the goal of increasing the throughput. The flexible system considered is strongly characterized by the inclusion of assembly among the manufacturing operations to be performed on a mix of part batches. In particular, the logic structure of some basic decision problems is indicated through a set of combinatorial models. Two basic assembly problems characterized by batches of large and small size, respectively, are analyzed.>