دانلود ترجمه مقاله فن آوری گروهی و مدل صحیح در شکل گیری سلول

بخشی از ترجمه:

علیرقم تاریخچه ی بزرگ مسئله ی تشکیل سلول(CF) و وجود ١٢ روش برای آن، روش های کمی وجود داشته اند که به صورت صریح به بهینه سازی اهداف تشکیل سلول بپردازند. این روش ها معمولاٌ منجر به فرمولاسیون های خود سرانه ای شده که میتواند فقط به صورت هیروستیک برای نمونه های تجربی حل شود. در مقابل، ما نشان داده ایم که CF را میتوان به صورت صریح و به وسیله ی مسئله ی چندبرشی کمینه مدل سازی کرد و بهیگی آنرا در عمل حل کرد(برای نمونه های متوسط اندازه). ما چندین محدودیت در دنیای واقعی را در نظر میگیریم که میتواند در داخل فرمول پیشنهادی بکار گرفته شده و نتایجی آزمایشی را با داده های تولید واقعی ایجاد کند.
١. مقدمه
تشکیل سلول(CF)، یک گام کلیدی در پیاده سازی تکنولوژی گروه میباشد که اصل آن در مهندسی صنعتی و به وسیله ی Mitrofanov(١٩٩۶) و Burbidge(١٩۶١) ارائه شد، و پیشنهاد شد که بخش های مشابه را باید به طرق مشابه پردازش کرد. در بسیاری از زمینه های عمومی، مسئله ی CF را میتوان به صورت زیر فرمول بندی کرد. در یک مجموعه ی محدود داده شده از ماشین ها و بخش هایی که باید در داخل یک بازه ی زمانی خاص پردازش شود، هدف گروه بندی ماشین ها در داخل سلول های سازنده (از این رو نام مسئله ) و بخش ها در داخل خانواده های محصول میباشد، به گونه ای که هر خانواده ی محصول در داخل یک سلول پردازش شود. به طور برابر ، این هدف را میتوان به صورت کمینه سازی میزان حرکت بین سلولی- جریان بخش هایی که بین سلول ها حرکت میکنند، فرمول بندی مجدد کرد. این میزان را میتوان به وسیله ی تعداد بخش ها، حجم کلی آنها بایان کرد، که بسته به حرکت خاصی برای CF میباشد. برای مثال، در صورتی که سلول ها به صورت کم و بیش توزیع شده باشند، ضروری است تا هزینه های انتقال را که بسته به حجم است و نه تعداد بخش ها، کاهش داد.

بخشی از مقاله انگلیسی:

Abstract Despite the long history of the cell formation problem (CF) and availability of dozens of approaches, very few of them explicitly optimize the objective of cell formation. These scarce approaches usually lead to intractable formulations that can be solved only heuristically for practical instances. In contrast, we show that CF can be explicitly modelled via the minimum multicut problem and solved to optimality in practice (for moderately sized instances). We consider several real-world constraints that can be included into the proposed formulations and provide experimental results with real manufacturing data. Keywords Cell formation · Group technology · Minimum multicut Mathematics Subject Classification 05C70 · ۹۰C35 · ۹۰C11 1 Introduction Cell formation (CF) is a key step in implementation of group technology—a paradigm in industrial engineering developed by Mitrofanov (1966) and Burbidge (1961), and D. Krushinsky (B) Department of Operations, University of Groningen, P. O. Box 800, 9700 AV Groningen, The Netherlands e-mail: d.krushinsky@rug.nl B. Goldengorin LATNA, Laboratory of Algorithms and Technologies for Networks Analysis and Department of Applied Mathematics and Informatics, Nizhny Novgorod branch of The National Research University Higher School of Economics, B. Pecherskaya, 25/12, 603155 Nizhny Novgorod, Russia e-mail: bgoldengorin@hse.ru 123 324 D. Krushinsky, B. Goldengorin suggesting that similar parts should be processed in a similar way. In the most general setting, the (unconstrained) CF problem can be formulated as follows. Given finite sets of machines and parts that must be processed within a certain time period, the objective is to group machines into manufacturing cells (hence the name of the problem) and parts into the product families such that each product family is processed mainly within one cell. Equivalently, this objective can be reformulated as minimization of what is usually referred to as the amount of intercell movement—the flow of parts travelling between the cells. This amount can be expressed via the number of parts, their total volume or mass, depending on the particular motivation for CF. For example, if cells are spatially distributed it may become important to reduce transportation costs that depend on the mass or volume rather than on the number of parts. Throughout the decades the problem has gained a lot of attention resulting in hundreds of papers and dozens of approaches that use all the variety of tools ranging from intuitive iterative methods (e.g., McCormick et al. 1972; King 1980; Wei and Kern 1989) to neural networks (e.g., Kaparthi and Suresh 1992; Yang and Yang 2008), evolutionary algorithms (e.g., Adil and Rajamani 2000; Filho and Tiberti 2006) and mixed-integer programming (e.g., Chen and Heragu 1999; Bhatnagar and Saddikuti 2010); an overview can be found in Selim et al. (1998). Despite all this variety, to the best of our knowledge, there is no tractable approach that explicitly optimizes the mentioned above goal. In particular, all the available approaches have at least one of the following drawbacks: • the model itself is an approximation to the original problem; • the model is solved by a heuristic procedure. To illustrate the first point we would like to mention that it is a common practice to reduce the size of the problem by considering only relations between machines instead of considering machine-part relations. Such a framework is quite beneficial due to the fact that the number of machines is quite limited (usually less than 100) while the number of parts can be magnitudes larger. This point will be clearly illustrated below by means of an industrial example. The reduction is usually implemented by introducing a machine–machine similarity measure that can be based on the similarity of sets of parts that are processed by a pair of machines, on similarity of manufacturing sequences of these parts, etc. Literature reports several similarity measures, an overview can be found in Yin and Yasuda (2006). However, all of them are based on intuitive considerations and there is no strict reasoning why one of them is better than another. If such an inexact similarity measure is further plugged into some model, then the whole model is nothing more than an approximation to the original problem. Finally, the resulting model often appears to be NP-hard and its authors are forced to use heuristic solution methods further deteriorating the solution quality. The purpose of this paper is to formulate an exact model for the CF problem, flexible enough to allow additional practically motivated constraints and solvable in acceptable time at least for moderately sized realistic instances. The paper is organized as follows. In the next section we discuss the exact model for cell formation, show that it is equivalent to the minimum multicut problem and discuss its computational complexity. In Sects. 3 and 4 we motivate and present two MILP formulations for the problem. Section 5 is focused on additional constraints that 123 Exact model for CF in GT 325 may be introduced into the model, while Sect. 6 provides results of experiments with real manufacturing data. Section 7 summarizes the paper with a brief discussion of the obtained results and further research directions. 2 The essence of the cell formation problem In this section we formalize the CF problem given two types of the input data and show how it can be modelled via the minimum multicut problem. For the rest of this paper let sets I = {1,…, m} and J = {1,…,r} enumerate machines and parts, respectively, and let p denote the number of cells. Quite often, the input data for the CF problem is given by an m ×r binary machinepart incidence matrix (MPIM) A = [ai j] where ai j = 1 only if part j needs among others machine i, see Fig. 1a. Given such an input, the problem is equivalent (see, e.g., Burbidge 1991) to finding independent permutations of rows and columns that turn A to an (almost) block-diagonal form and minimize the number of out-of-block ones, also known as exceptional elements. The diagonal blocks correspond to cells, and the number of exceptional elements reflects the amount of intercell movement, see Fig. 1b. Given such an interpretation, the problem is similar to the biclustering problem (see, e.g., Madeira and Oliveira 2004). Though for the general biclustering problem there exist efficient exact methods (see, e.g., DiMaggio et al. 2008), they are hardly applicable to CF because most of them allow each row or column to belong to more than one cluster (see, e.g., Madeira and Oliveira 2004), while for CF the issue of non-overlapping blocks is critical. In addition, as we show further in this section, block-diagonalisation does not exactly minimise the intercell movement as it ignores operational sequences. Though the well known block-diagonal interpretation is easy to perceive, we will consider the problem from a completely different, yet insightful, viewpoint. Without any loss of generality one can associate with matrix A an undirected bipartite graph G(I ∪ J, E) by simply treating A as an incidence matrix of G. Note, that such an interpretation was also considered for the biclustering problem. Taking into account that each nonzero element of A corresponds to an edge in G, it is not hard Fig. 1 An example of a machine-part incidence matrix (MPIM): a raw data, b block-diagonalized form (blocks are highlighted). Zero entries are not shown for clarity 123 326 D. Krushinsky, B. Goldengorin to understand that diagonal blocks of A correspond to disjoint nonempty subgraphs G1,…, G p of G. Consider now the set of edges E corresponding to exceptional elements and observe that each edge from E has its endpoints in different subgraphs Gi , i ∈ {۱,…, p}. Thus, E can be thought of as a cut that splits G into p nonempty subgraphs. Further, we call a cut with this property a p-cut. Assuming that all edges of G have a unit weight and taking into account the relation between E and exceptional elements, it is possible to reformulate the CF problem in terms of graphs as follows: given an undirected weighted graph find a p-cut of the minimum weight. Let us abbreviate this problem as MINpCUT, in literature it is also known as “min k-cut” (we prefer to denote the number of subgraphs by p as letter k is handy as an index).