الگوریتم جستجو برای تیرها و مشکل تخصیص ظرفیت در سیستم های تولید انعطاف پذیر

This study considers the operation assignment and tool allocation problem in flexible manufacturing systems. A set of operations together with their required tools are selected so as to maximize the total weight. The machines have limited time and tool magazine capacities and the tools are available in limited quantities. We develop a beam search algorithm and obtain near optimal solutions for large size problems very quickly.

Flexible manufacturing systems (FMSs) are defined as the integrated systems of computer numerically controlled (CNC) machines connected with automated material handling mechanisms. They aim to combine flexibility of job shops and efficiency of flow lines through proper planning of operation assignments and tool allocations. In recent years, FMSs attract enormous attention both in industry and academia, due to its practical importance and technical challenge inherent in solving the associated problems. Moreover the high capital investment deserves extra attention via efficient planning techniques. Several problems are addressed in FMSs include, but not limited to, part selection, operation assignment and tool allocation. The operation assignment problem can be defined as the selection of the operations belonging to the selected part types so as to achieve some prespecified goals. In the FMS literature, the operation assignment problem is studied both in the absence and presence of tooling decisions. Toktay and Uzsoy, 1998, Akçalı et al., 2005 and Çatay et al., 2005 address the capacity allocation problem ignoring the tools. Toktay and Uzsoy (1998) assume that the machines can process a limited number of operations and they have limited time capacities. Their aim is to maximize the total assigned work. Akçalı et al. (2005) study the same problem, but they assume that each machine can process only a subset of operations. Çatay et al. (2005) allow machine duplications and aim to minimize the total cost due to capacity usages and machine purchases. Çatay et al. (2005) consider a capacity allocation problem that defines efficient tool procurement plans.

In this study, we consider an operation assignment and capacity allocation problem that arises in flexible manufacturing systems. We assume the automated machines have scarce time and tool magazine capacities and the tools are available in limited quantities. Our objective is to maximize the total weight of assigned operations. We develop a beam search algorithm for our problem. We apply several mechanisms like variable beam width technique and one step ahead look procedure. The results of our computational results with up to 500 operations and 16 machines have revealed that our beam search algorithm finds near optimal solutions in negligible solution times, and outperforms the existing algorithms in the literature. Therefore it is an attractive alternative to optimal solutions, in particular when the guarantee of optimality is not as essential. We are currently working on incorporating the tooling costs to our problem.