به حداقل رساندن تعداد لحظات ابزار تعویض در سیستم های تولید انعطاف پذیر

In this study, we address a part-type sequencing and tool switching problem arising in Flexible Manufacturing Systems. We consider the single machine problem of minimizing the number of tool switching instants. We propose two tabu search approaches to find high-quality solutions. Our computational results reveal that both tabu search approaches produce optimal or near-optimal solutions in reasonable times

In Flexible Manufacturing Systems (FMS), tool management decisions play a crucial role in achieving high productivity. In these systems, various operations can be performed on the Computer Numerical Control (CNC) machines provided that their required tools are loaded on the machines’ tool magazines. In cases where the total number of tool slots required by all part types is larger than the tool magazine capacity, tool loadings or switchings between the processing of the part types become inevitable. Tool loading or switching usually consumes time and therefore may delay the planned production. Even though the tool magazine capacities of the CNC machines have increased by the advances in new technologies, the tool types required to process part types have also increased due to the advances in the part complexity. The importance of the tool management in automated manufacturing systems has been discussed in many articles, some noteworthy of which are due to Kiran and Krason (1988), Gray et al. (1993) and Crama (1997). Tool switching problem is an important concern for the effective tool management and this importance has been recognized in automated manufacturing literature for several years. The relevant research has considered two objectives: minimizing the number of tool switches and minimizing the number of tool switching instants. Minimizing the number of tool switches is a relevant objective when the tool switching time is significant compared to the processing times. Crama et al. (1994) show that minimizing the number of tool switches problem is strongly NP-hard. Tang and Denardo (1988a) show that the problem is polynomially solvable when the part-type sequence is given. Several procedures for solving this problem are proposed in the literature, most noteworthy of which are due to Hertz et al. (1998), Bard (1988) and Laporte et al. (2004). Al-Fawzan and Sultan (2002) provide a tabu search (TS) approach to minimizing the number of tool switches problem. Minimizing the number of tool switching instants is an appropriate objective for the production environments where the machines have to be shut down during the tool interchanges or the associated tool magazines are allowed to be interchanged only at the beginning of each shift, i.e., instant. In such a case, the set up cost for stopping the production may reduce the time spent for the individual tool switches. Moreover, when the automatic tool interchanging device can switch a number of tools simultaneously or when the tool switch time is independent of the number of tool switches, minimizing the number of tool switching instants represents the production environment better than minimizing the number of tool switches. The simulation results of Katayama (1994) under typical FMS configurations have verified that simultaneous tool switches are advantageous if the production period is relatively low; otherwise, sequential tool switches are preferable. In case of short production periods, the load of any shift can be reduced by relatively frequent tool switches although simultaneous tool switches avoid such unnecessary set up operations. In the literature, the number of tool switching instants problem is referred to as job grouping problem as well. The problem is particularly important when the tool loading times are long or when many small batches of different parts must be consecutively processed. Such cases are mentioned in Hirabayashi et al. (1984) and Finke and Kusiak (1987) for the metal cutting industry. Moreover, when the tools are heavy, exchanging them requires considerable effort as mentioned in Blazewicz et al. (1988). The problem has also applications in the electronics industry as discussed in Bard (1988) and Hirvikorpi et al. (2005). In electronics manufacturing, several printed circuit boards each requiring a set of feeders are grouped and loaded on an automated placement machine that can hold a limited number of feeders. Bard (1988) and Hirvikorpi et al. (2005) mention that the feeder exchanging is a time-consuming operation; hence, grouping printed circuit boards is crucial for minimizing the number of feeder setups. Tang and Denardo (1988b) mention that the number of tool switching instants problem is a general case of the classical bin packing problem, and hence it is NP-hard in the strong sense. They propose a branch and bound procedure to find the optimal solution and an upper bounding procedure to find a feasible solution. Crama and Oerlemans (1994) give the set covering formulation of the problem. They propose a column generation approach to solve the Linear Programming relaxation of this formulation and find a lower bound. Then, Denizel (2003) develops a Lagrangean decomposition-based lower bounding procedure and uses the lower bound in a branch and bound algorithm. She reports the superior performance of her algorithm over that of Tang and Denardo (1988b). However, her computations are limited to the problems with up to 30 part types. In this paper, we consider the minimum number of tool switching instants problem for which we develop two TS procedures using two different encodings. We verify the quality of the TS procedures on the several problem instances, and find near-optimal solutions for the large-sized problem instances. The rest of the paper is organized as follows. In Section 2, we define our notation, state our main assumptions and give mathematical representation of the problem. In 3 and 4, we discuss our solution procedures and the results of our computational experiments, respectively. In Section 5, we conclude the study by pointing out some possible directions for future research.

In this study, we address the number of tool switching instants problem on a single CNC machine in FMS environments. In order to deal with the flat search space of the problem, two different TS approaches are proposed; the first one is based on a tie breaking and the second one uses an alternative encoding. The results of our computational tests have revealed that both TS algorithms produce high-quality approximate solutions in reasonable times on the test problems. Our results could be extended to the arbitrary tool slot requirements cases and parallel machine environments. Tool sharing between the machines could also be considered in parallel machine environments.