Minimization of tool switches for a flexible manufacturing machine with slot assignment of different tool sizes.

1. Introduction and literature review

The concept of flexibility has become a key consideration in the design, operation and management of manufacturing systems. In a survey by Sethi and Sethi (1990) they define flexibility in manufacturing as being able to reconfigure manufacturing resources in order to efficiently produce different products of acceptable quality. In addition, they note that at least 50 different terms for various types of flexibility can be found in the manufacturing literature.

A FMS (Flexible Manufacturing System) consists of a number of numerically controlled machines, linked by an automated material handling device, that perform the operations required to manufacture parts. The tools that are required by these operations are stored in a limited capacity tool magazine attached to each machine. An automated tool interchanging device enables the machine to interchange tools very quickly. The Tool Management problem is a generic name for various problems concerned with tool sequencing/loading/switching and setups minimization.

FMS environments are very common in the printed circuit board (PCB) assembly industry and in metal-based industries. Bard (1988) mentions a problem in the electronics industry in which an automated placement machine produces several types of PCBs. For each type of PCB, a certain collection of component feeders must be placed on the machine before boards of that type can be produced. As the machine can only hold a limited number of feeders, it is usually necessary to replace some feeders when switching from the production of one type of board to another board type. Exchanging feeders is a time consuming operation and it is therefore important to determine a production sequence for the board types that minimizes the number of "feeder setups". Identifying the feeders with tools constitutes an instance of the job sequencing and tool loading problem described below.

An example of a FMS in a metal-based industry can be found in Tatikonda and Stietz (1994). The FMS consists of three machining centers, each of which has a tool magazine with a capacity of 320 tools, which achieves a time of 4.5 seconds for the tool selection and 3 seconds for the tool changes. The capacity of 320 tools allows for tool redundancy thereby minimizing downtime due to tool unavailability.

An essential feature of a FMS is the fast tool interchanging capability. This capability allows us to reduce the number of costly setup changes while producing with the tools available in the magazine. When it becomes necessary to add tools to the tool magazine to allow new operations, the machine sometimes has to be shut down while the tools are replaced, after which the machine may resume production. The performance of a FMS may therefore be considerably improved by reducing the occurrences of these setups. The problem becomes especially crucial when the time needed to change a tool is significant with respect to the processing time of the parts, or when many small batches of different parts must be processed in succession. Jain et al. (1996) observed that for high mix PCB shops at Hewlett-Packard, it was not unusual to find that over 50% of the production time was spent in setup operations. The setup times typically ranged from 1 to 5 hours, with an estimate of line downtime cost of over $1000 an hour. Moreover, if capacity limitations of the line limited sales of high demand products, this cost could rise to over $10 000 per hour.

Crama and Van de Klundert (1999) identified four basic tool management problems, which were derived from the general tool management model. In the tool switching problem, given a collection of jobs, a processing sequence for the jobs and a loading strategy for the tool magazine has to be found so as to minimize the total number of switches, see for example, Bard (1988), Tang and Denardo (1988a), Crama et al. (1994) and Hertz et al. (1998). In the tool loading problem, given a collection of jobs and a processing sequence for these jobs, one needs to find a loading strategy for the tool magazine so as to minimize the total number of switches, see for example, Crama et al. (1994). The problem of finding the weighted minimum number of switches, i.e., when there is a weight given to each tool, can be solved efficiently, see Privault and Finke (1995). The batch selection problem is concerned with a collection of jobs for which one needs to find the largest subset (batch) of jobs that can be processed without tool switches, see for example, Goldschmidt et al. (1994) and Crama (1997). The job grouping problem is concerned with sequencing the jobs that are scheduled to be processed and loading tools in the magazine in order to minimize the total number of switching instants, see for example, Tang and Denardo (1988b) and Crama and Oerlemans (1994).

An additional related problem is the physical placement of tools in the magazine, known as the DSA, the Dynamic Storage Allocation problem, see for example, Chen et al. (2002). The question addressed in this case is how to allocate blocks so that they do not intersect with each other while the used storage size is as small as possible.

A common assumption in the literature on the tool loading and switching problems is that each tool occupies one slot in the tool magazine. Yet, it is common for a tool to occupy several slots. In metal-based industries, this property is applicable to big tools (Stecke, 1983) or to tools that are kept as a kit (Matzliach and Tzur, 2000). In PCB assembly, this property is applicable to components of different sizes, which occupy more than one feeder slot (Jain et al., 1996; Gronalt et al., 1997; Gunther et al., 1998).

Previous work on the tool loading or switching problems with tools that may occupy more than one slot in the magazine is relatively limited. The problem is mentioned in Stecke (1983), Shanker and Tzen (1985) and Jain et al. (1996) but none of them includes a comprehensive treatment of the problem. Gunther et al. (1998) discussed the machine loading problem (sequencing the jobs). They used component commonality between any pair of jobs as an estimate for the set-up effort incurred when switching between the job pair, which allowed them to model the problem in a standard approach derived for the traveling salesman problem. Gronalt et al. (1997) discussed the complementary problem, i.e., given a job sequence, they addressed the tool loading problem (which they call component set-up) and the slot loading problem (which they call feeder assignment). Their heuristic applies a recursive approach between the component set-up and the feeder assignment problems. More recently, Matzliach and Tzur (2000) addressed the tool loading problem (i.e., when the job sequence is given) with tools that may occupy more than one slot, but with no consideration to their physical location. They proved that the problem is NP-complete and suggested two heuristic procedures.

The problem addressed in this paper is the tool switching problem, in which each tool may occupy more than one slot in the magazine. Machines process parts automatically by using a limited capacity tool magazine. Tools that are not in the magazine are kept in the tool storage area. If a tool that is needed for a certain processing operation is not in the magazine, a tool switch must occur before the job can be processed, a time/cost consuming operation. Thus, one has to decide on three types of decisions, namely, how to select the jobs' sequence (machine loading), which tools to switch before each processing operation (tool loading) and where to locate each tool in the magazine (slot loading). The objective is to minimize the number of tool switches, where planning and scheduling are done off-line, prior to production. Since each tool can consume several (unrestricted) magazine slots, a tool placement in the magazine takes into account the current physical location of the other tools in the magazine. We refer to the latter consideration as slot assignment. We present an integer programming formulation for the problem, and suggest a heuristic procedure for its solution. The concept and focus of our heuristic is completely new, however, some procedures within it are based on previously proposed approaches. We then conduct a numerical study in which we solve a collection of tool switching problems, both via our suggested heuristic, as well as via previously suggested approaches from the literature, adjusted by us to handle the case of tools that may occupy more than one slot.

The paper is organized as follows: in Section 2 we specify the problem's assumptions and formally state the problem. In Section 3 we describe our solution procedure and in Section 4 we report on a numerical study. We conclude in Section 5.

2. Problem assumptions and formulations

In this section we state the assumptions and specify the parameters that define the problem. The complete integer programming formulation is given in Appendix A. The assumptions are:

1. There is a set of jobs to be processed. Each job requires a specific set of tools.

2. No job requires a set of tools that occupies more slots than available in the magazine.

3. Before a certain job can be processed, its required set of tools has to be placed in the magazine. If not all the tools are in the magazine, then a tool switch must occur.

4. Planning is done off-line, for the fixed set of jobs, ignoring the effect of the rolling horizon caused by the initial and final tool and slot assignments.

5. The cost/time associated with the placement or removal (rearrangement of slots) of tools is independent of the next job scheduled for processing.

6. The cost/time associated with the placement or removal (rearrangement of slots) of tools is independent of their size.

7. The time needed for start-up at the beginning of processing and for shutdown at the end of processing is fixed. Therefore, tool switches that occur before or after the processing of the set of jobs are ignored.

8. No tool maintenance operation is required during the process, in particular not one that requires a tool switch.

9. The secondary storage site for tools that are not currently in the tool magazine has an unlimited capacity.

10. Each tool occupies a given number of slots, independent of the presence of other tools. Thus, the possibility of tools that partly overlap is ignored.

2.1. Parameters

N = number of jobs that need to be processed; jobs are designated by the index j;

M = number of tools; tools are designated by the index i;

C = capacity (number of slots) of the tool magazine; Slots are designated by the index k.

The index n designates instants. Instant n is the point in time at which the nth job has completed processing, but before any tool switches occur. B is a vector of length M, whose ith entry [b.sub.i] represents the number of magazine slots required by tool …