An exact model for cell formation in group technology

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.

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  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).

چکیده

علیرغم سابقه طولانی مسأله تشکیل سلول (CF) و در دسترس بودن دهها روش، تعداد اندکی از آنها به صراحت هدف تشکیل سلول را بهینه می کنند. این رویکردهای ضعیف معمولا منجر به ساختارهای سخت گیرانه می شود که می تواند برای موارد عملی تنها به صورت صوری مورد استفاده قرار گیرد. در مقابل، ما نشان می دهیم که CF می تواند به روش صریح از طریق حداقل مشکل چندگانه و با بهینه سازی در عمل (برای نمونه های متوسط اندازه گیری) مدل شده است. ما چندین محدودیت دنیای واقعی را در نظر می گیریم که می تواند در فرمول بندی های پیشنهادی گنجانده شود و نتایج تجربی را با داده های تولید واقعی ارائه دهد.

مقدمه

تشکیل سلول (CF) یک گام کلیدی در پیاده سازی تکنولوژی گروه است – یک پارادایم مهندسی صنعتی توسط Mitrofanov (1966) و Burbidge (1961) و پیشنهاد می کند که قطعات مشابه باید به روش مشابه پردازش شوند. در تنظیمات عمومی، مشکل (بدون محدودیت) CF به شرح زیر می باشد: با توجه به مجموعه های محدودی از ماشین آلات و قطعات که باید در یک دوره زمانی خاص پردازش شوند، هدف این است که ماشین آلات را به سلول های تولید (به همین ترتیب نام مشکل) و قطعات به خانواده های محصول دسته بندی کنند، به طوری که هر خانواده محصول به طور عمده درون یک پردازش می شود سلول. به همین ترتیب، این هدف را می توان به عنوان به حداقل رساندن آنچه که معمولا به عنوان مقدار جنبش بین سلول – جریان قطعات سفر بین سلول ها، اصلاح می شود. این مقدار را می توان از طریق تعداد قطعات، حجم کل آنها یا توده های آنها، بسته به انگیزه خاصی برای CF بیان کرد. به عنوان مثال، اگر سلول ها به صورت فضایی توزیع شوند، ممکن است مهم تر شود که هزینه های حمل و نقل را کاهش دهد که به حجم یا حجم بستگی دارد، نه بر تعداد قطعات. در طول دهه ها، این مسئله توجه زیادی را به خود جلب کرده و موجب ایجاد صدها مقاله و ده ها روش است که از انواع ابزارهای مختلف از روش های تکراری بصری استفاده می کند (مانند McCormick و همکاران 1972؛ King 1980؛ Wei and Kern 1989). الگوریتم های تکاملی (به عنوان مثال Adil و Rajamani 2000؛ Filho and Tiberti 2006) و برنامه ریزی عدد صحیح مخلوط (به عنوان مثال، چن و هراگو 1999؛ Bhatnagar و Saddikuti 2010)؛ شبکه های عصبی (به عنوان مثال، Kaparthi و Suresh 1992؛ یانگ و یانگ 2008)؛ الگوریتم های تکاملی. یک مرور کلی در Selim و همکارانش یافت می شود. (1998).

Year: 2012

Publisher : SPRINGER

By :  Dmitry Krushinsky · Boris Goldengorin

File Information: English Language/ 16 Page / size: 509 MB

Download

سال : 1391

ناشر : SPRINGER

کاری از : دیمیتری کروشینسکی · بوریس گلدنژورن

اطلاعات فایل : زبان انگلیسی / 16 صفحه / حجم : MB 509

لینک دانلود