بخشی از مقاله
چکیده
با گسترش روز افزون رقابت در صنایع مختلف تولیدي، بهبود عملکرد تولید کنندگان بیش از پیش مورد توجه قرار گرفته است. در کارخانجات تولیدي که تولید محصولات متنوع به صورت سفارشی انجام می گیرد، چگونگی تولید محصولات مختلف به گونه اي که منجر به عملکرد بهینه شود، شامل پیچیدگی هاي بسیاري می باشد. هدف این تحقیق کلاس بندي سفارشات تولید به منظور کاهش زمان هاي راه اندازي است. بدین منظور از روش K-Means که یکی از روش هاي خوشه بندي می باشد براي دسته بندي محصولات مشابه استفاده شده است . در انتها یک مطالعه موردي در کارخانجات حدید صنعت قائم، براي مساله ي خوشه بندي سفارشات پیشنهاد و پیاده سازي شد که نتایج آن، عملکرد بهتر برنامه ریزي سفارشات را در مقایسه با نتایج قبل از اجراي تحقیق حاضر نشان می دهد . همچنین در این مطالعه موردي سه نمونه واقعی در اندازه هاي کوچک - 25 نوع سفارش - ، متوسط - 250 نوع سفارش - و بزرگ - 500 نوع سفارش - توسط رویکرد پیشنهادي مورد بررسی قرار گرفت؛ نمونه هاي بررسی شده به ترتیب در خوشه هاي 3، 5 و 8 تایی دسته بندي شدند؛ با مطالعه ي خوشه هاي ساخته شده مشخص شد که رویکرد پیشنهادي قادر به دسته بندي سفارشات در دسته هاي مشابه به منظور کاهش زمان هاي راه اندازي دستگاه ها می باشد.
کلمات کلیدي: داده کاوي؛ کارخانجات تولیدي؛ الگوریتم خوشه بندي؛ روش شلسسهوK
1.مقدمه
با توجه به این که تنوع محصولات تولیدي کارخانجات روز به روز در حال افزایش می باشد، افزایش تنوع محصولات موجب پیچیده تر شدن برنامه ریزي تولید می شود. در صورت عدم برنامه ریزي اصولی، این مهم می تواند منجر به افزایش زمان راه اندازي دستگاه ها، زمان بی کاري دستگاه ها و اپراتور ها و ضایعات تولیدي شود؛ لازم به ذکر است که افزایش زمان هاي راه اندازي دستگاه ها و بی کاري آنها موجب افزایش هزینه ها در سیستم تولید می شود.در این تحقیق سعی بر این است که فرآیند تولید در کارخانجاتی مورد بررسی قرارگیرد که محصولات متنوع را به صورت سفارشی تولید می کنند؛ بنابراین به دلیل تولید محصولات متنوع، کاهش زمان راه اندازي دستگاه ها به یکی از پیچیده ترین مسایل موجود در چنین محیط هایی تبدیل شده است.
در تحقیق پیش رو یک مطالعه موردي در کارخانجات حدید صنعت قائم بررسی می شود که انواع پایه هاي روشنایی و دکل هاي انتقال نیرو را تولید می کند؛ به دلیل تنوع سفارشات و تنوع دستگاه هاي خطوط تولید، فرآیند تولید محصولات نیازمند گروه بندي است تا زمان هاي راه اندازي دستگاه هاي تولید کاهش یابد. در حال حاضر، ترتیب تولید سفارشات در این مجموعه معمولا به صورت FIFO - تولید محصولات به ترتیب دریافت سفارش - می باشد؛ بنابراین، تنوع محصولات در این مجموعه می تواند موجب افزایش بی رویه زمان راه اندازي دستگاه ها و زمان بیکاري دستگاه و اپراتور ها شود .
از طرف دیگر، تنظیم مجدد دستگاه ها به دلیل تغییر محصول تولیدي در خط تولید، احتمال تولید قطعه معیوب و یا قطعه بی کیفیت را به دلیل ایجاد نوسان در روغن هیدرولیک دستگاه ها افزایش می دهد. این مشکل موجب آسیب رسیدن به قالب دستگاه بر اثر جابجایی نیز می شود. بنابراین تهیه برنامه ریزي تولید دقیق و کامل در چنین مراکزي - مراکزي با سیستم تولید کارگاهی - بسیار ضروري به نظر می رسد.[2] لازم به ذکر است که مرحله ي خمکاري در تولید محصولات کارخانجات ذکر شده از مهم ترین مراحل به شمار می آید؛ به گونه اي که تغییر محصول در خط تولید نیازمند تغییر در تنظیمات اولیه دستگاه ها - تغییر در زاویه خم، طول، عرض، ضخامت، کیفیت مورد نظر و جنس - می باشد.
به عنوان مثال، دستگاه پرس بریک - دستگاه خم کن - موجود در این کارخانه، متشکل از 4 جک هیدرولیک است که هر جفت جک قادر به وارد ساختن 600 تن نیرو می باشد . دستگاه مورد ذکر از 6 نقطه در طول 16 متر تنظیم می شود؛ این دستگاه قادر به تولید انواع مختلف محصولات بوده که براي تولید هر کدام از محصولات مختلف نیاز مند تنظیمات اولیه متفاوت می باشد؛ با توجه به پیچیدگی فرآیند تولید اشاره شده، در صورتی که بتوان سفارشات مختلف را بر روي یک خط تولید بر اساس معیار هاي شباهت براي تنظیمات اولیه دستگاه ها خوشه بندي نمود، می توان هر کلاس از سفارشات را به یک مجموعه از تنظیمات نسبت داد و براي آن برنامه ریزي کرد. در این صورت انجام عملیات سفارشات به صورت کلاس بندي شده صورت می گیرد و در نتیجه زمان راه اندازي دستگاه ها کاهش چشمگیري می یابد؛ بدین منظور با استفاده از الگوریتم خوشه بندي سعی شده است تا محصولات مختلف در کلاس بندي هاي مشابه گروه بندي شوند. از مزایاي دیگر روش ذکر شده این است که بدون داشتن هیچ گونه اطلاعات از قبل می توان سفارشات را صرفا بر اساس معیار هاي شباهت دسته بندي نمود.
2.مرور ادبیات
در این قسمت تاریخچه ي تحقیقات انجام شده در زمینه هاي مختلف علم داده کاوي مورد بررسی قرار گرفته است . با توجه به افزایش سرعت انبارش داده ها و نیاز مبرم به کشف دانش از میان حجم انبوه اطلاعات، محققان زیادي در این زمینه تحقیقات گسترده اي انجام داده اند.با رشد فناوري اطلاعات و روش هاي تولید و جمع آوري داده ها، پایگاه داده هاي مربوط به داده هاي تبادلات تجاري، کشاورزي، اینترنت، جزییات مکالمات تلفنی، داده هاي پزشکی سریع تر از هرروز جمع آوري و انبارش می شوند. لذا در اواخر دهه ي 80 میلادي بشر به فکر دستیابی به اطلاعات نهفته در این پایگاه هاي داده هاي حجیم افتاد.
داده کاوي فرآیندي است که در آغاز دهه 90 مطرح شد و با نگرشی نو به مساله استخراج اطلاعات از پایگاه داده ها پرداخته است. از سال 1995 داده کاوي به صورت جدي وارد مباحث آماري شده و در سال 1996 براي اولین مرتبه در مجله کشف دانش و معرفت از پایگاه داده ها منتشر شد. محققانی نظیر Brachman و Anand کلیه مراحل واقع گرایانه و رو به جلو کشف دانش از پایگاه داده ها - KDD - را براي اولین بار کشف کرده اند.[17]آقاي Su-Yeon و همکاران در سال 2006 با در نظر گرفتن اهمیت شناخت مشتري در جهت ایجاد ارتباط بلند مدت، کسب وفاداري و سودآوري بیشتر مشتري، ارزش هر مشتري را تعیین نمودند؛ سپس با در نظر گرفتن ارزش مشتریان، آن ها را بخش بندي نموده و استراتژي هاي مناسب را براي هر بخش تعیین نموده اند .[8]
آقایان Tsai و Chiu در سال 2004 به بسط متدلوژي جدید براي بخش بندي بازار بر مبناي متغیرهاي خاص از جمله اقلام خریداري شده و میزان درآمد مرتبط با آن ها با در نظر گرفتن تراکنش هاي قبلی مشتریان پرداخته و بازار را بخش بندي نموده اند.[9] در سال2004، آقایان Shina و Sohnb در حوزه بخش بندي بازار با وجود دو نوع هزینه هاي عملیاتی از روش هاي خوشه بندي Fuzzy، K-Means و Som براي بخش بندي مشتریان استفاده کرده اند.[20] آقایان Singhi و Liu, در سال 2006 به بررسی مساله انتخاب زیر مجموعه اي از داده ها براي طبقه بندي داده هاي بسیار پیچیده پرداخته اند. آنها عوامل تاثیر گذار بر انتخاب زیر مجموعه ها و اثرات مثبت و منفی انتخاب زیر مجموعه را از طریق آزمایش هاي فراوان مورد بررسی قرار داده اند.[5]
آقایان Choi و Moon در سال 2007 یک مدل گسسته سازي فازي ژنتیک را با انتخاب زیر مجموعه اي از داده ها براي مسایل دسته بندي اطلاعات ادغام کرده اند. آنها از الگوریتم ژنتیک به منظور کاهش استفاده از معیار هاي ناکارآمد در کنار بهینه کردن دسته بندي اطلاعات استفاده کرده اند. [3]در سال 2013، آقاي Al-Hassan و همکاران با مطالعه دیتا ست هاي بزرگ، راهکار هاي کارآمدي براي بکارگیري ابزار هاي داده کاوي ارایه کرده اند؛ آنها همچنین مشکلات موجود در بکارگیري ابزار هاي مربوط به داده کاوي را مورد بررسی قرار داده اند.[11] در سال هاي گذشته تحقیق هاي گسترده اي در زمینه گسترش روش K-Means به منظور بکارگیري این روش خوشه بندي در چند دیتا ست به صورت موازي صورت گرفته است.
آقایان Yi و Zhang در سال 2013 روش K-Means را براي داده هاي تقسیم شده به صورت عمودي مورد مطالعه قرار دادند. مدل ایجاد شده توسط آنها قادر به دسته بندي چندین دیتا ست به صورت همزمان در حالی که اطلاعات موجود در هر دیتا ست محرمانه باقی بماند، می باشد.[12] بسیاري از روش هاي خوشه بندي قادر به تشخیص دقیق تعداد دسته ها نیستند؛ از این رو آقایان Rahman و Islam در سال 2014 الگوریتم ژنتیک نوآورانه اي را بر پایه ي روش هاي خوشه بندي طراحی کردند که قادر به تشخیص دقیق تعداد دسته ها می باشد. علاوه بر اینها، الگوریتم ژنتیک آنها قادر به شناسایی ژن هاي مناسب براي جمعیت اولیه می باشد.[7]
آقاي Velmurugan در سال 2014 به بررسی دو روش Fuzzy C-Means و K-Means که زیر مجموعه هایی از الگوریتم خوشه بندي می باشند، در حیطه مخابرات پرداخته است. آنها این دو روش را بر اساس زمان محاسباتی شان با یکدیگر مقایسه کرده اند.[4] عدم تمرکز اطلاعات - گسترده بودن اطلاعات - یکی از بزرگ ترین مشکلات موجود در روش هاي خوشه بندي می باشد. آقایان Naldi و Campello در سال 2014 با ارایه یک روش ابتکاري روش K-Means را به گونه اي طراحی کردند که قادر به خوشه بندي دیتا ست هاي گسترده نیز باشد. آنها براي مشکل اشاره شده دو الگوریتم ابتکاري ارایه کرده اند؛ دو روش مورد بحث در تحقیق آنها از نظر تئوري و از نظر تجربی با یکدیگر مقایسه شده اند.[13]
همانطور که اشاره شد، داده کاوي عملکرد قابل توجهی در مقابل دیتا ست هاي گسترده از خود نشان نمی دهد. اما آقاي Hamrouni و همکاران در سال 2015 مدلی از داده کاوي را بر اساس شبکه داده ارایه کردند که مشکل اشاره شده را برطرف می کند. نتایج بدست آمده از تحقیق آنها، روش ابتکاري ارایه شده را کارآمد نشان می دادند.[10] آقاي Durduran در سال 2015 به بررسی کاربرد روش K-Means در رابطه با تحلیل نقشه پوشش زمین با وضوح بالا پرداخته است. وي یک مدل ابتکاري را با ادغام روش هاي K-Means و گرایش مرکزي ارایه کرده است. راهکار ارایه شده توسط آقاي Durduran از دقت بسیار بالایی برخوردار می باشد.[14]
3.متدلوژي پیشنهادي
غالبا الگوریتم هاي مختلف داده کاوي به سه دسته ي کاوش قوانین انجمنی ، طبقه بندي و تخمین و خوشه بندي تقسیم می شوند.[1, 15, 16] با توجه به این که در مساله ي پیش رو به دنبال دسته بندي داده ها بر اساس شباهت می باشیم و همچنین با توجه به این که خصوصیات مرتبط با هر کلاس از قبل مشخص نمی باشد، از الگوریتم خوشه بندي که هدف اصلی اش دسته بندي محصولات بر اساس تشابه یا عدم تشابه داده ها می باشد، جهت گروه بندي سفارشات استفاده شده است. الگوریتم خوشه بندي قادر به دسته بندي داده ها به روش هاي مختلفی می باشد که در ادامه تشریح خواهیم کرد.
روش هاي مرتبط با الگوریتم خوشه بندي به پنج دسته ي خوشه بندي مبتنی بر افزار ، خوشه بندي سلسله مراتبی ، خوشه بندي مبتنی بر تراکم داده ها ، خوشه بندي مبتنی بر شبکه هاي گرید و خوشه بندي مبتنی بر مدل تقسیم می شود. با توجه به این که معیار هاي شباهت در مساله ي مورد بررسی مشخص است - زاویه خم، طول، عرض، ضخامت، کیفیت مورد نظر و جنس - ، خوشه بندي مبتنی بر افراز از بهترین روش هاي خوشه بندي براي مساله ي حال حاضر به حساب می آید.از این رو در ادامه زیر مجموعه هاي روش خوشه بندي مبتنی بر افراز را به تفصیل شرح داده و مناسب ترین آنها را براي پیشبرد مساله ي مورد نظر انتخاب می کنیم. از معروف ترین روش هاي خوشه بندي مبتنی بر افزار می توان به روش هایی نظیر K-Means، K-Medidos و Fuzzy C-Means اشاره کرد.
در روش K-Means که یکی از پرکاربرد ترین روش هاي الگوریتم خوشه بندي مبتنی بر افراز می باشد، حرف لاتین K نشان دهنده هدف این الگوریتم براي پیدا کردن تعداد ثابتی از خوشه ها براساس نزدیکی نقاط داده ها به هم می باشد. مراحل اجراي الگوریتم K-Means به شرح زیر می باشد:
-1 انتخاب K داده به عنوان مرکز خوشه
-2 تعیین فواصل بقیه داده ها با مرکز خوشه ها
-3 قرار دادن داده هاي نزدیک مرکز هر خوشه در آن خوشه
-4 محاسبه میانگین هر خوشه به عنوان مرکز جدید خوشه
-5 تکرار مرحله دوم تا چهارم تا رسیدن با عدم تغییر در خوشه ها
تابع هدف روش ذکر شده براي محاسبه فاصله بین داده ها که مبین شباهت آنها می باشد به صورت زیر است:
علامت €€ مبین فاصله ي بین نقاط بوده و نشان دهنده ي مرکز خوشه ي j ام می باشد.روش K-Medidos از لحاظ عملکرد شباهت بسیاري به الگوریتم K-Means دارد، با این تفاوت که روش K-Medidos به جاي استفاده از میانگین خوشه ها، از نمونه هاي موجود در خوشه ها به عنوان مرکز ثقل خوشه ي مربوطه استفاده می کند. از این رو، روش K-Medidos از مرکزي ترین داده ي موجود در هر خوشه به عنوان نماینده آن خوشه استفاده می کند.بر اساس مطالب مطرح شده، کاملا مشخص است که روش K-Medidos در خوشه بندي داده ها بر اساس شباهت از حساسیت کم تري نسبت به روش K-Means برخوردار می باشد؛ با توجه به این که هدف اصلی مساله پیش رو دسته بندي محصولات مشابه در خوشه هاي یکسان می باشد، استفاده از الگوریتم K-Means براي مساله پیش رو منطقی تر به نظر می رسد.
الگوریتم Fuzzy C-Means که بر اساس منطق خانواده فازي به خوشه بندي داده ها می پردازد براي اولین بار در سال 1984 توسط آقاي Bezdek معرفی شده است.[19] بر خلاف روش K-Means که داده هاي به صورت قطعی به خوشه ها تخصیص می یابند، در روش Fuzzy C-Means داده ها بااستفاده از تعریف درجه عضویت می توانند به خوشه هاي مختلف تخصیص بیابند. این روش به دنبال دسته بندي مجموعه اي از n المان در مجموعه اي از k خوشه بر اساس بردار شاخص هاي تعریف شده می باشد. الگوریتم مورد بحث به دنبال حداقل سازي اهداف زیر می باشد:
