Scheduling dual gripper robotic cell: One-unit cycles

We consider the scheduling problem of cyclic production in a bufferless dual-gripper robot cell processing a family of identical parts. The objective is to find an optimal sequence of robot moves so as to maximize the long-run average throughput rate of the cell. While there has been a considerable amount of research dealing with single-gripper robot cells, there are only a few papers devoted to scheduling in dual-gripper robotic cells. From the practical point of view, the use of a dual gripper offers the attractive prospect of an increase in the cell productivity. At the same time, the increase in the combinatorial possibilities associated with a dual-gripper robot severely complicates its theoretical analysis. The purpose of this paper is to extend the existing conceptual framework to the dual-gripper situation, and to provide some insight into the problem.We provide a notational and modelling framework for cyclic production in a dual-gripper robotic cell. Focusing on the so-called active cycles, we discuss the issues of feasibility and explore the combinatorial aspects of the problem. The main attention is on 1-unit cycles, i.e., those that restore the cell to the same initial state after the production of each unit. For an m-machine robotic cell served by a dual-gripper robot, we describe a complete family of 1-unit cycles, and derive an analytical formula to estimate their total number for a given m. In the case when the gripper switching time is sufficiently small, we identify an optimal 1-unit cycle. This special case is of particular interest as it reflects the most frequently encountered situation in real-life robotic systems. Finally, we establish the connection between a dual-gripper cell and a single-gripper cell with machine output buffers of one-unit capacity and compare the cell productivity for these two models.     

Approximate analysis of production systems

In this paper complex production systems are studied where a single product is manufactured and where each production unit stores its output in at most one buffer and receives its input from at most one buffer. The production units and the buffers may be connected nearly arbitrarily. The buffers are supposed to be of finite capacity and the goods flow is continuous. For such netwroks it is possible to estimate the throughput by applying repeated aggregation over the production units. The approximation appears to be best when the network shows some resemblance with a flow line.     

Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.     

Exact analysis of asymmetric random polling systems with single buffers and correlated input process

We introduce a simple approach for modeling and analyzing asymmetric random polling systems with single buffers and correlated input process. We consider two variations of single buffers system: the conventional system and the buffer relaxation system. In the conventional system, at most one customer may be resided in any queue at any time. In the buffer relaxation system, a buffer becomes available to new customers as soon as the current customer is being served. Previous studies concentrate on conventional single buffer system with independent Poisson process input process. It has been shown that the asymmetric system requires the solution ofm 2 ^m –1) linear equations; and the symmetric system requires the solution of 2 ^m–1–1 linear equations, wherem is the number of stations in the system. For both the conventional system and the buffer relaxation system, we give the exact solution to the more general case and show that our analysis requires the solution of 2 ^m –1 linear equations. For the symmetric case, we obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, loss probability, throughput, and the expected delay observed by a customer.     

On a synchronization queue with two finite buffers

In this paper, we consider a synchronization queue (or synchronization node) consisting of two buffers with finite capacities. One stream of tokens arriving at the system forms a Poisson process and the other forms a PH-renewal process. The tokens are held in the buffers until one is available from each flow, and then a group-token is instantaneously released as a synchronized departure. We show that the output stream of a synchronization queue is a Markov renewal process, and that the time between consecutive departures has a phase type distribution. Thus, we obtain the throughput of this synchronization queue and the loss probabilities of each type of tokens. Moreover, we consider an extended synchronization model with two Poisson streams where a departing group-token consists of several tokens in each buffer. This revised version was published online in June 2006 with corrections to the Cover Date.     

How to improve the performance of ATM multiplexers

We consider an ATM multiplexer with a finite or infinite buffer and stochastic output rate. There are independent, identical sources connected to this multiplexer which transmit fluid directly into the buffer. We show that the throughput of the multiplexer is increasing in the number of sources connected, where we scale the cell stream process in such a way that the mean and peak input rate stays unchanged. In the finite buffer case, the cell loss is decreasing in the number of sources connected. Hence more links improve the performance of ATM multiplexers. In the last part, we prove that correlations within cell stream processes have a negative effect on the performance of ATM multiplexers. These investigations provide easily computable lower bounds to performance measures.     

Exact Solution to Tandem Fluid Queues with Controlled Input

We consider a tandem fluid system composed of multiple buffers connected in a series. The first buffer receives input from a number of independent homogeneous on-off sources and each buffer provides input to the next buffer. The active (on) periods and silent (off) periods follow general and exponential distribution, respectively. Furthermore, the generally distributed active periods are controlled by an exponential timer. Under this assumption, explicit expressions for the distribution of the buffer content for the first buffer fed by a single source is obtained for the fluid queue driven by discouraged arrivals queue and infinite server queue. The buffer content distribution of the subsequent buffers when the first buffer is fed by multiple sources are found in terms of confluent hypergeometric functions. Numerical results are illustrated to compare the trend of the average buffer content for the models under consideration.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

带有缓冲器串行生产线的Harris链结构分析

本文以随机过程中的一类特殊的Ｍａｒｋｏｖ链（Ｈａｒｒｉｓ常返Ｍａｒｋｏｖ链）为工具，研究离散事件动态系统（ＤＥＤＳ）中的典型情况之一：带有缓冲器的串行生产线．求得了各缓冲器中产品数的联合稳态分布，产品在各台机器上受阻时间的联合稳态分布，以及受阻时间的强大数定律和产品在各台机器加工完时刻的极限行为．     

Regenerative pull (Kanban) production control policies

A production system consists of a set of parallel robotic cells manufacturing parts for several distinct work stations. The stations order parts from these cells and withdraw parts from their buffers only at the rate and at the time of consumption. The desired decision vector provides for the instantaneous number of cells assigned to produce parts for each work station. Two novel tractable and optimal regenerative pull (‘Kanban’) control policies are formulated: one policy minimizes the weighted starvation penalty, while the other maximizes the weighted throughputs per unit time. Following these regenerative policies the production schedules are re-evaluated at each decision epoch to mitigate the effects of processing time variability.Several important properties regarding the inherent interaction between the structure of the optimal policy, the performance of the system and the desired allocation of productive capabilities among the manufacturing resources are examplified. It is shown that the optimal policy attempts to marginally assign as much of the cells capacity as possible to certain critical part types. Substantial changes in the structure of the optimal policy, resulting either from incrementing the number of cells or from increasing their capacity, are also identified. More generally, attention is drawn to the qualitative behavior of the optimal pull control policy in certain manufacturing systems with stochastic processing rates.     

Remark on minimization of depth of Boolean circuits

It is shown that Lozhkin’s method (1981) for minimization of the depth of formulas with a bounded number of changing types of elements in paths from input to output and Hoover-Klawe-Pippenger’s method (technical report in 1981, journal publication in 1984) for minimization of the depth of circuits with unbounded branching by insertion of trees from buffers with bounded branching of outputs for each buffer are dual to each other and can be proved by one and the same method.     

The stochastic behavior of a buffer with non-identical input lines

A system consisting of a buffer, N input lines leading to it and one line leading out is considered. Successive active and idle periods on the input lines constitute an alternating renewal process of a special kind. While in previous work the case of identical input lines was considered, the present paper gives a solution to the general case of non-identical input lines. This provides a tool for the analysis of arbitrarily complicated networks of buffers. The paper contains results regarding the traffic pattern on the output lineas well as the content of the buffer and the maximum content of the buffer during intervals of non-emptiness.     

Bandwidth allocation and access control in high-speed networks

The problem of bandwidth allocation and access regulation arises in the congestion control of Broadband ISDN networks. This paper assumes that a single user, described by an on-off fluid model, is connected to the network via a leaky bucket access control mechanism. The bandwidth allocated to this user and the leaky bucket parameters are to be selected so as to guarantee a negotiated level of delay probability at the access point and packet loss probability in the network which is modelled as an output buffer. The design problem is to minimize the allocated bandwidth subject to service guarantees and stability conditions for the input and output buffers. We provide a desirable feasible solution to the design problem. The paper studies the effect of non-conforming users on the network performance using the leaky bucket access control corresponding to this feasible solution. We provide expressions that quantify the impact of the leaky bucket parameters in access regulation and the worst-case queueing behavior at the output buffer. Finally, we discuss the extension of this methodology to the multiple leaky buckets case.This research was supported in part by IBM Research Contract No. 1374.     

Asymptotic scheduling

We deal with the following scheduling problem: a finite set of jobs is given and each job consists in the execution of an infinite number of tasks. A task is a sequence of operations and each operation requires a specific machine. A machine can process only one operation at a time and preemption is not allowed. Performance measures of the processing system involve fixing a time horizon T, counting the number of tasks completed within T for each job and maximizing a specified function of these numbers to estimate the throughput of the schedule. Whilst computing the throughput for a given T is in general an extremely difficult problem, it is shown in this paper that the limit, as T tends to infinity, of the average throughput (i.e. the throughput divided by T) can be easily computed via Linear Programming under fairly mild conditions. This quantity, which may be called the asymptotic throughput, can be used to assess a bound on performance measures of real systems. Buffers play a crucial role and buffer sizes can be taken care of in assessing the system performance. Mathematics Subject Classification (2000):90B35, 90C05, 90C27, 90C90     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.     

Partial Pooling in Tandem Lines with Cooperation and Blocking

For a tandem line of finite, single-server queues operating under the production blocking mechanism, we study the effects of pooling several adjacent stations and the associated servers into a single station with a single team of servers. We assume that the servers are cross-trained (so that they can work at several different stations) and that two or more servers can cooperate on the same job. For such a system, we provide sufficient conditions on the service times and sizes of the input and output buffers at the pooled station under which pooling will decrease the departure time of each job from the system (and hence increase the system throughput). We also show that pooling decreases the total number of jobs in the system at any given time and the sojourn time of each job in the system if the departure time of each job from the system is decreased by pooling and there is an arrival stream at the first station. Moreover, we provide sufficient conditions under which pooling will improve the holding cost of each job in the system incurred before any given time, and extend our results to closed tandem lines and to queueing networks with either a more general blocking mechanism or probabilistic routing. Finally, we present a numerical study aimed at quantifying the improvements in system performance obtained through pooling and at understanding which stations should be pooled to achieve the maximum benefit. Our results suggest that the improvements gained by pooling may be substantial and that the bottleneck station should be among the pooled stations in order to obtain the greatest benefit. AMS subject classification: 90B22     

Development of a model for a two-station serial transfer line subject to machine and buffer failure

In modern automated production lines, it is common to connect pairs of machines with mechanical storage devices in order to provide buffering between processing stations. Since these devices are mechanical, they are prone to failure. Previous research concerning the analytical modeling of a class of production lines, the serial transfer line, assumes that these buffers are completely reliable. The concept of an unreliable buffer is introduced and an analytic model of a two machine line with an unreliable buffer is developed. It is proposed that this model will form the foundation for an analytic model of the more complex K > 2 machine serial transfer line with unreliable buffers.     

Representation and analysis of transfer lines with machines that have different processing rates

A transfer line is a tandem production system, i.e. a series of machines separated by buffers. Material flows from outside the system to the first machine, then to the first buffer, then to the second machine, the second buffer, and so forth. In some earlier models, buffers are finite, machines are unreliable, and the times that parts spend being processed at machines are equal at all machines. In this paper, a method is provided to extend a decomposition method to large systems in which machines are allowed to take different lengths of time performing operations on parts. Numerical and simulation results are provided.     

On modelling the maximum workload allocation for parallel unrelated machines with setups

Consider a manufacturing process in which a group of machines (or people) perform a single operation on a number of different parts. The processing time depends on both the part and the machine. In addition, each machine requires significant setup time between processing different part types. The problem consists of obtaining a feasible allocation of parts to machines such that the makespan (i.e. greatest machine workload) is minimized. We present two equivalent 0–1 models. The first model arises by considering the assignment of individual parts to machines. It is amenable to Lagrangian decomposition techniques. The second model is more hierarchical in nature; it considers the two options of assigning an entire part type to a single machine, or of splitting the type across machines. The second model is more amenable than the first to branch-and-bound techniques. We report about our computational experience for finding lower bounds of the optimal solution by appending violated cuts and, ultimately, obtaining the optimal solution of real-life problems.