|
Description
1. Introduction
Robotic cells are used in many modern manufacturing systems. As they become more prevalent, using these cells efficiently becomes a competitive necessity. Previous studies of robotic cells have addressed three major factors: (i) cell design; (ii) sequencing of robotic moves; and (iii) optimal scheduling of the products or parts to be produced. In this paper, our focus is the sequencing of robot moves in a cell that produces identical parts. Specifically, we consider cyclic production in which a sequence of robot actions is repeated until the production target is met. The main result of this paper is a linear time (10/7)-approximation for the problem of finding an optimal cyclic solution.
A robotic cell consists of a number of machines served by a central robot. Each part is processed on each machine; each part follows the same order through these machines. A four-machine robotic cell is illustrated in Fig. 1. The robot arm rotates and moves linearly to handle the inter-machine movements of the parts. As in a classical flowshop, each part being processed passes successively from the input hopper (I) to machines [M.sub.1], [M.sub.2], [M.sub.3] and [M.sub.4], and finally to the output hopper (O).
2. Robotic cells in practice
Robotic cells are used in a wide variety of industries. Dominant areas of applications include semiconductor manufacturing and electroplating lines for a variety of products ranging from printed circuit boards to airplane wings, where parts are transferred between tanks of chemicals by hoists. Other applications include, but are not limited to, the classical functions of welding and machining, glass manufacturing and processing production of components for magnetic resonance imaging systems, automated pharmacy compounding, processing of nucleic acids and generation of compounds for tests in relevant biological screens. For a detailed discussion of these and other applications, we refer the reader to two recent and extensive surveys by Crama et al. (2000) and Dawande, Geismar, Sethi, and Sriskandarajah (2005). A considerable amount of work has been done on robotic cell flow shops with single gripper robots. In this area, also referred to as cyclic robotic flowshop scheduling, robotic cells can be partitioned into three types--no-wait, interval, free-pickup--based on the part pickup criterion used by the robot.
In no-wait cells, as soon as the machine completes processing a part, that part must be removed from the machine and transferred to the next machine (Agnetis, 2000; Levner et al., 1997). Such conditions are commonly seen in steel manufacturing or plastic molding, where the raw material must maintain a certain temperature, or in food canning to ensure freshness (see, e.g., Hall and Sriskandarajah (1996)). In interval robotic cells, each machine has a specific interval of time--a processing time window--for which a part can be processed on that machine. This is applicable, for example, for the Hoist Scheduling Problem on an electroplating line (Lei and Wang, 1994; Chen et al., 1998; Che et al., 2002). In free-pickup cells, the part may remain on the machine for any amount of time after its processing is completed until the robot unloads it. In this paper, we focus on free-pickup cells.
[FIGURE 1 OMITTED]
Most studies, including this one, address simple robotic cells, those in which each processing stage has only one machine. These contrast with robotic cells with parallel machines, in which at least one processing stage has more than one machine (see Herrmann et al. (2000) and Geismar et al. (2004) for more on parallel machines).
Dawande, Geismar, Sethi, and Sriskandarajah (2005) classify three types of cells differentiated by their robots' travel-time metrics:
1. In an additive travel-time cell, the time required for the robot to move between any two adjacent machines is the same for all adjacent pairs. For any non-adjacent pair, the robot travels a route that passes all intervening machines. Hence, the time required for the robot to move between any two non-adjacent machines is the sum of the movement times between those intervening pairs.
2. In a constant travel-time cell, the time required for the robot to move between any two machines is the same.
3. A Euclidean travel-time cell is more general than the other two. The only restrictions on movement times are that they are symmetric and that they obey the triangle inequality.
Our focus in this paper is on additive travel-time robotic cells with the free-pickup criterion. Figure 2 shows a robotic cell configuration, often used in electroplating applications, where the additive travel-time metric is a reasonable approximation. The robot is attached by a hoist to an overhead track. The robot moves linearly along the track; parts must successively undergo a sequence of operations in the electroplating process at tanks [M.sub.i], i = 1,..., n.
3. Relevance of an efficient cyclic solution
In practice, robotic cells are most often used in the repetitive production of identical parts. If each repetition leaves the cell in the exact same state as its state at the beginning of these actions, then one instance of the repeated moves is called a cycle. Repeating a cycle indefinitely yields a cyclic solution, in which case the cell is said to be operating in a steady state (rigorous definitions of cycle and steady state are provided in Section 4.2). Therefore, all that is needed to specify a cyclic solution is the sequence of robot actions in a cycle. Since we focus only on cells producing identical parts, no part scheduling issues arise. A k-unit cycle, k [greater than or equal to] 1, is a sequence of robot actions in which the cell returns to exactly the same state after producing k parts (Sethi et al., 1992).
[FIGURE 2 OMITTED]
From an optimization point of view, the objective function that concerns practitioners the most is that of maximizing the throughput--the long-term average number of completed parts placed into the output hopper per unit time. In addition to their prevalence in practice, the importance of cyclic solutions (also referred to as cyclic policies) is underlined by a recent result of Dawande, Geismar, and Sethi (2005), which states that there always exists a cyclic schedule that maximizes the throughput.
Table 1 summarizes the complexity status of obtaining optimal k-unit cyclic solutions in single gripper robot cells. We refer the reader to Dawande, Geismar, Sethi, and Sriskandarajah (2005) for a detailed discussion of these results.
Among cyclic solutions, 1-unit cycles are easiest to implement and control, and are a preferred choice among practitioners. Sethi et al. (1992) show that there are m! 1-unit cycles in a m-machine cell. In attempting to find a policy whose throughput is maximal, several studies address the conjecture postulated by Sethi et al. (1992): the policy of repeating an optimal 1-unit cycle is superior to any other policy. For additive travel-time robotic cells, Sethi et al. (1992) prove that 1-unit cycles dominate others in two-machine cells. Brauner and Finke (1999a, 1999b) and Crama and Van de Klundert (1999) verify this claim for additive travel-time cells with three machines. Brauner and Finke (1997) provide a counter-example to the conjecture for an additive travel-time cell with four machines. Dawande, Geismar, and Sethi (2005) provide a counter-example for a constant travel-time cell with four machines.
Thus, although 1-unit cyclic solutions are preferred by practitioners, the throughput obtained by an optimal 1-unit cycle is, in general, strictly less than that obtained by an optimal k-unit cycle over all k [greater than or equal to] 1. A key question, therefore, is how big can be the difference between the throughput of an optimal 1-unit cycle and an optimal cyclic solution. An important result of this paper is an improved bound on this difference for additive travel-time cells: we show that the per-unit cycle time of an optimal 1-unit cycle is within a factor of 10/7 of an optimal cyclic solution. Equivalently, the throughput of an optimal 1-unit cycle is at least 7/10 times the throughput of an optimal cyclic solution. In addition, we show that to guarantee this bound, we do not necessarily need an optimal 1-unit cycle; a specific 1-unit cyclic solution, constructed in linear time, guarantees this bound. This result improves the current best (3/2)-approximation guarantee (Geismar et al., 2005). We believe that practitioners will benefit from an efficiently computable 1-unit cyclic solution whose throughput is provably close to that of an optimal cyclic solution.
After discussing definitions and notations in Section 4, we derive preliminary results for additive travel-time cells (Section 5) and describe an important class of 1-unit cycles (Section 6). The algorithm and a proof of its bound are in Section 7. Conclusions and recommendations for future study are given in Section 8.
4. Definitions and Notations
In this section we provide the required definitions, notations, and basic properties for the study of robotic cells.
4.1. Cell data
A typical robotic cell contains m processing machines: [M.sub.1], [M.sub.2],..., [M.sub.m]. Let M = {1,2,..., m} be the set of indices of these machines. The robot obtains a part from the input device (I, also referred to as [M.sub.0]) and carries it for successive processing to [M.sub.1], [M.sub.2],..., [M.sub.m], and finally stores the processed part at the output device (O, also referred to as [M.sub.m+1]). The robot can hold only one part at a time. It is important to note, however, that the robot is not required to remain with each part... |
Looking for additional articles?
Click here
to search our database of over 3 million articles.
|
-approximation%20algorithm%20for%20an%20optimum%20cyclic%20solution%20in%20additive%20travel-time%20robotic%20cells.(author%20abstract)%20%20&position=1)