بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
برنامه ريزي زمانبندي خط توليد در صنعت نساجي با استفاده از روش الگوريتم ژنتيک فازي
چکيده :
در اين مقاله يک سيستم خبره فازي براي سيستم توليد صنعت نساجي با بکاربردن تجزيه تحليل خوشه بندي فازي ارايـه مـي شـود. سيسـتم پيشـنهادي اندازه ي شاخص زمان شناوري (flow time) براي سفارش هاي کاري جديد، هنگامي که اين سفارش ها تحت قواعد فعلي فرآيند مي شـوند، را پـيش گـويي مي کند. در روش مدلسازي سيستم فازي از الگوريتم هاي ژنتيک (GAs) که از ابزارهـاي بهينـه سـازي اسـت ، بـه منظـور تعيـين نـوع و مقـدار بهينـه ي پارامترهاي مورد نياز مدل استفاده شده است . روش پيشنهاد شده شامل دو فاز است . فاز نخست با آموزش بدون نظارت توسعه داده مي شود و شامل يـک طراحي مبنا به منظور شناسايي يک سيستم فازي نمونه است . در اين فاز از روش تجزيه تحليل استفاده مي شود. براي تعيين مقادير بهينه ي پارامترهـاي خوشه بندي ، يعني ، توان وزني (m) و تعداد خوشه ها (c)، الگوريتم هاي ژنتيک به کاربرده مي شود. در دومين فاز، فرآيند تطبيق به منظور تنظيم پارامترهـاي شناسايي شده در فاز مبنا، با توجه به آموزش بانظارت انجام مي شود. اين فاز با بکاربردن روند استدلال تقريبـي انجـام مـي شـود. پارامترهـاي اسـتدلال تقريبي نيز با بکاربردن الگوريتم ژنتيک بهينه مي گردند. در آخر روش پيشنهادي با بکاربردن آن در سيستم زمانبندي يک کارگاه نساجي و مقايسه آن بـا سيستم فازي از نوع سوگنو، که خوشه بندي کاهشي را درمرحله شناسايي ساختار بکارمي برد، اعتبارسنجي مي شود. نتايج نشان مي دهد که سيستم فـازي پيشنهاد شده رفتار سيستم هاي توليد پيچيده مانند صنايع نساجي را بهتر نشان مي دهد.
کلمات کليدي :
آموزش بانظارت و بدون نظارت ، تجزيه تحليل خوشه بندي فازي ، الگوريتم ژنتيک فازي ، صنعت نساجي ، زمانبندي فازي
١- مقدمه
سيستم هاي توليد صنايع نساجي شامل عمليات هاي چندمحصولي مانند توليد نـخ ، بافنـدگي ، رنگـرزي ، چـاپ ، تکميـل و توليـد لبـاس هسـتند. در ايـن سيستم ها، ترکيب توليد براساس انبار (make- to- stock) و توليد بر اسـاس سـفارش (make- to- order)، مسـئله زمانبنـدي را خيلـي سـخت مي نمايد. به عبارت ديگر، خصوصيات مخصوص ذکرشده در بالا موجب مي شود، کنترل توليد، برنامه ريزي توليد و زمانبندي کارگـاه هـاي نسـاجي امـري مشکل باشد [١]. المغربي و کارنوب [٢] (Almaghraby, Karnoub) مسئله برنامه ريزي توليد و زمانبندي در يک کارخانه نسـاجي را ماننـد مسـئله برنامه ريزي توليد و زمانبندي در يک کارگاه گردش کاري ترکيبي ١ (بعضي اوقات تحت عنوان کارگاه گردش کاري انعطاف پذير، يا فرآيند سـري / مـوازي نيز اشاره مي شود) مدل کرده اند. گوپتا [٣] نشان داده است ، مسائلي که کارگاه گردش کاري ترکيبي ناميده مـي شـوند NP- complete هسـتند. مسـئله زمانبندي يک کارگاه رنگرزي - چاپ - تکميل مي تواند به صورت يک مسئله زمانبندي کارگاه گردش کاري ترکيبي مدل شود و بنابراين جزو مسائل -NP complete است [٤]. بنابراين تجربه ي انسان نقش کليدي در حل اين نوع مسائل دشوار دارد.
هوش مصنوعي و سيستم هاي خبره ابزار مناسبي براي فائق شدن بر پيچيدگي بعضي مسائل زمانبندي مانند کارگاه هاي گردش کاري نسـاجي هسـتند. در اين صنعت ، متخصصين با بکاربردن قواعد تجربي مي توانند به بهينه نمودن کارگاه رنگرزي - چاپ - تکميل کمـک نماينـد. ايـن مـورد بـه ايـده ي روش زمانبندي که رفتار متخصصين را تقليد مي کند، منجر مي شود. مقاله ها تنوع وسيعي از تکنيک هاي بر اساس هوش را براي زمانبندي سيستم هاي توليدي پيشنهاد مي کنند. امروزه سيستم هاي منطق فازي (FLs)، شـبکه هـاي مصـنوعي (ANN)، الگـوريتم هـاي ژنتيـک (GAs)، هـوش مصـنوعي (AI) و سيستم هاي ترکيبي بسياري در زمانبندي پيشرفته استفاده مي شوند. از نقطه نظرکلي ، اين تکنيک هاي بر اساس هوش ، انعطاف پذيري زمانبندي در يـک کارگاه رنگرزي - چاپ - تکميل را افزايش مي دهند و مي توانند عملکرد کلي سيستم را بهبود دهند.
دراين مقاله هدف ، مدل کردن سيستم زمانبندي يک کارگاه رنگرزي - چاپ - تکميل و تجزيه تحليل اثـرات متقابـل فـازي متغيرهـايي کـه ايـن سيسـتم زمانبندي و اندازه ي کارآيي آن را تحت شرايط عملياتي فعلي تحت تاثير قرار مي دهند، با روش پيشنهادي است . روش پيشنهادي اندازه ي شـاخص زمـان شناوري (flow time) براي سفارش هاي کاري جديد را هنگامي که اين سفارش ها تحت قواعد فعلي فرآيند مي شوند را پيش گويي مـي کنـد. ترکسـن و فاضل زرندي [٥] (Turksen, Fazel Zarandi) ادعا نموده اند که به طور معمول ساختار واقعي قواعد عملياتي در زمانبندي به علت پيچيدگي اثـرات متقابل تعداد زيادي از متغيرها و روش هاي مختلفي که به وسيله ي زمانبند استفاده مي شوند، مخفي هستند. آن ها همچنين ادعا نموده اند کـه ايـن اثـرات متقابل به خوبي با روش هاي قطعي قابل توصيف نيستند و به طور معمول الگوهاي فازي و غيرخطي را به ميزان زياد نشان مـي دهنـد، کـه مـي تواننـد از طريق شناسايي ساختار سيستم فازي استخراج شوند. روش مدلسازي سيستم فازي پيشنهاد شده در اين تحقيق شامل دو فاز است . فاز نخست با آموزش بدون نظارت توسعه داده شده و شامل يک طراحي مبنا به منظور شناسايي موثر يک سيستم فازي نمونه براي سيستم هدف از مجموعه داده هاي ورودي - خروجي آموزشي است (شناسايي ساختار). در دومين فاز، فرآيند تطبيق به منظور پارامترهاي شناسايي شده در طراحي مبنا باتوجـه بـه آمـوزش بانظـارت براي يک مجموعه از داده هاي ورودي - خروجي آموزشي انجام مي شود. اين فاز با به کار بردن استدلال تقريبي انجام مي شود.
اين تحقيق روش سوگنو و ياسوکاوا [٦] (Sugeno- Yasukawa) را براي شناسايي ساختار به کار مي برد. بنابر روش آن ها، ابتدا داده هاي خروجـي از طريق روش خوشه بندي فازي ، خوشه بندي مي شوند. سپس خوشه هاي فازي خروجي بر روي فضاي ورودي به منظور انتخاب موثرترين متغيرهاي ورودي تصوير مي شوند. در اين مرحله قواعد اگر- آنگاه ساخته مي شوند. موثرترين الگوريتم هاي خوشه بندي فازي عبارتند از: (الف ) توان وزني (m) کـه ميـزان فازي بودن راتعيين مي کند و (ب ) تعداد خوشه ها (c). در اين مقاله الگوريتم ژنتيک به منظور تعيين مقادير بهينه اين پارامترها به کار بـرده مـي شـود. تـابع برازش بر مبناي انديس اعتبارسنجي اصلاح شده ي فوکوياما- سوگنو است که اندازه فاصله ماهالانبيس (Mahalanobis) در آن استفاده شده است . بايد توجه شود که در استدلال تقريبي ، چندين فاکتور بايد بهينه شوند: t- نرم ، s- نرم ، پارامترهاي مدل هاي زباني و پارامتر غيرفازي نمودن . در اين تحقيـق اين فاکتورها نيز با استفاده از الگوريتم ژنتيک بهينه مي شوند. تابع برازش در اين فاز ريشه ي ميانگين مربع خطا (RMSE١) است .
در اين تحقيق ، در بخش ٢ زمانبندي کارگاه رنگرزي - چاپ - تکميل ارائه مي شود. بخش ٣ روش پيشنهادي را توضيح مي دهد. در بخـش ٤ بکـارگيري روش پيشنهادي در کارگاه رنگرزي - چاپ - تکميل بحث مي شود. بخش ٥ مقايسه روش پيشنهادي با مدلسازي سيستم فازي از نوع سوگنو با الگـوريتم خوشه بندي کاهشي را ارائه مي دهد. در آخر، در بخش ٦ بحث و کارهاي آينده بيان مي شود.
٢- زمانبندي کارگاه رنگرزي - چاپ - تکميل
يک کارگاه رنگرزي - چاپ - تکميل به طور معمول همان گونه که در شکل ١ نشان داده شده شامل چهار ايستگاه کاري : تکميل اوليـه ، رنگـرزي ، چـاپ و تکميل نهايي است و در نهايت محصولات : پارچه سفيد تکميل شده ، پارچه رنگ شده و پارچه چاپ شده توليد مي شوند. با توجه به نوع پارچه ها و يـک يـا دوجرئي بودن نخ هايي که در پارچه استفاده شده است ، فرآيندهاي رنگرزي و تکميل مي توانند مراحل مختلفي را شامل شوند. در کارگاه رنگرزي - چـاپ - تکميل که تحقيق در آن جا انجام شده است ، مواد اصلي عبارتند از: تار و پود پنبه ، پلي استر- پنبه و پلي استر- ويسکوز. بـه عـلاوه عمليـات هـاي مختلفـي ممکن است با توجه به سفارش مشتري انجام شوند. خروجي تکميل اوليه ، ورودي به ايستگاه هاي کاري رنگرزي ، چاپ و تکميل نهايي اسـت . بنـابراين ، عدم وجود کارآيي در تکميل اوليه بر روي بازده ديگر عمليات هاي فيزيکي و شيميايي تاثير مي گذارد. عمليات هاي مختلف ممکن است يا بر روي فقـط يک ماشين انجام شوند، مانند شستشو، سفيدگري و غيره ، يا بر روي ماشين هاي موازي ، مانند تثبيت حرارتي و خشک کردن و فرآيند تکميل نهـايي ، کـه بر روي دو ماشين استنتر انجام مي شوند.
در اين جا اهداف اصلي سيستم زمانبندي عبارتند از:
١) ماکزيمم نمودن بهره وري سيستم
٢) حفظ کيفيت بالا
٣) ماکزيمم نمودن تحويل به موقع
٤) مي نيمم نمودن تفاوت شيد بين سفارش هاي رنگرزي متوالي که تحت عمليات استنتر قرار مي گيرند.
٥) مي نيمم نمودن زمان شناوري سفارش ها
٦) مي نيمم نمودن ديرکرد در زمان تحويل سفارش به مشتري
شکل ١: قسمت هاي اصلي يک کارگاه رنگزري - چاپ - تکميل
اين اهداف اغلب در تضاد هستند. براي مثال ، زمانبندي براي مي نيمم کردن زمان شناوري بعضي سفارش ها ممکن است به توالي از اين سفارش ها منجر شود که داراي شرايط عملياتي متفاوتي در استنتر هستند و اين نيازمند زمان آماده سازي بيشتري (به منظور مطابقت نمودن دماي هـر اتاقـک اسـتنتر بـا دماي دلخواه ) براي سفارش ها است . در نتيجه ، اضافه شدن زمان آماده سازي باعث تاخير در عمليات استنتر نمودن سفارش هاي بعـدي و افـزايش زمـان شناوري و تاخير در تحويل سفارش ها مي شود. به علاوه ، تغيير دما در هر يک از اتاقک هاي استنتر از يک سفارش به سفارش بعدي در زمانبندي ، با توجه به کيفيت محصول نهايي ، فاکتور مهمي است . اگر دماي اتاقک به دماي مورد نظر نرسد، تاثير منفي بر روي پارچه خواهـد داشـت کـه در نتيجـه باعـث پايين آمدن کيفيت و قيمت محصولات خواهدشد. همان تاثير منفي بايد براي قسمت هاي شستشو، سفيدگري و شستشوي مداوم که به طور معمول براي پارچه هاي چاپي و رنگي به کار گرفته مي شوند، مورد نظر قرارگيرد. عدم وجود شباهت بين سفارش ها، يعني پارچه هاي با اجـزاي متفـاوت و پارچـه هـاي چاپي با کلاس هاي رنگي متفاوت ، ممکن است باعث توقف ماشين در بين توالي ، تخليه ي ماشين و بارگيري آن با مواد شيميايي و همچنين مواد کمکي مورد احتياج جديد و تاخير ٣٠-٢٠ دقيقه در عمليات ها شود. اين موارد به طور معمول بهـره وري را کـاهش داده و باعـث بعضـي مشـکلات در تصـفيه ي پساب مي شود.
٣- مدلسازي سيستم فازي
در اين تحقيق مدلسازي سيستم فازي چند ورودي يک خروجي (MISO) به کار برده مي شود. ساختار MISO به صورت زير است :
که در آن امين قاعده فازي ، متغيرهاي ورودي و l متغيرهاي خروجي قاعـده فـازي هسـتند، Ail مجموعه فازي تعريف شده در مجموعه مرجع Xi محدوه فيزيکي xi، و isr فرم کوتاه شده "مربوط مي باشد به " و "شبيه مـي باشـد بـه " اسـت [٧].
به منظور سادگي ، فقط مورد MISO درنظرگرفته مي شود، زيرا يک سيسستم چند ورودي - چند خروجي همواره مي تواند به مجموعـه اي از سيسـتم هـاي MISO تجزيه شود. مدلسازي سيستم فازي پيشنهادي شامل دو فاز مجزا به صورت زير است :
٣-١- فاز نخست : طراحي مبنا (شناسايي ساختار)
اغلب روش هاي معمول شناسايي ساختار بر مبناي تکنيک هاي خوشه بندي فازي داده هاي ورودي - خروجي هستند. سوگنو و ياسوکاوا [٦] روشي جديـد براي سيستم هاي با مقياس بزرگ پيشنهاد کردند. در روش آن ها، داده هاي خروجي به منظور تعيين تعداد قواعد در سيستم MISO خوشه بندي مي شـوند.
سپس ، فضاي خروجي بر روي فضاي ورودي به منظور تعيين مهمترين ورودي ها تصوير مي شوند.
٣١٨
توليد قاعده از سه روال ١ اصلي تشکيل شده : (١) خوشه بندي ورودي و خروجي ، (٢) تعيين توابع عضويت ورودي و خروجي و (٣) ساده سازي قواعد
٣-١-١- خوشه بندي ورودي و خروجي
دو زيرروال در روال خوشه بندي ورودي - خروجي وجود دارد:
(الف ) تعيين تعداد بهينه ي خوشه ها (c)، ميزان فازي بودن (m) و تشکيل توابع عضويت خروجي
(ب ) انتخاب ورودي و تشکيل توابع عضويت متغيرهاي ورودي
(I) مراحل تعيين تعداد بهينه خوشه ها و توان وزني سيستم در شکل ٢ نشان داده مي شوند. همان گونه که در شـکل مشـاهده مـي شـود، الگـوريتم ژنتيک مقادير تصادفي از m و c به عنوان تکي هايي از جمعيت اوليه توليد مي کند. m و c توليدشده در الگوريتم خوشـه بنـدي فـازي c- Means (FCM) به منظور توليد ماتريس تقسيم بندي فازي اوليه ي استفاده مي شوند. الگوريتم حجم خوشه مي نيمم (MCV٢) الگوريتم FCM را به عنـوان اوليه بکار مي برد. بنابراين اين الگوريتم (١) ماتريس تقسيم بندي فازي اوليه توليد شده بوسيله FCM و (٢) m و c توليـد شـده بوسـيله GAs را استفاده نموده و ماتريس تقسيم بندي فازي بهينه و بردار مراکز خوشه ها را ايجاد مي کند. ايـن مـاتريس هـا بـه انـديس اعتبارسـنجي اصـلاح شـده فوکوياما- سوگنو (که در آن بردار ميانگين داده ها با بردار ميانگين تقسيم بندي فازي جايگزين مي شود) [٨] به عنوان مقدار برازش معرفي مي شوند.
GA عملگرهاي مخصوصش را براي تعيين مقادير بهينه ي m و c به کار مي برد.
الگوريتم خوشه بندي فازي حجم خوشه مي نيمم کريشناپورام و کيم [٩] (Krishnapuram, Kim) در مورد استفاده از معيار دترمينان (حجم ) براي خوشه بنـدي تحقيـق و بررسـي کردنـد.
آن ها الگوريتمي را که الگوريتم حجم خوشه مي نيمم (MCV) ناميده مي شود و مجموع حجم خوشه هاي تکي را مي نيمم مي نمايد، بدست آوردند.
آن ها ادعا کردند که الگوريتم پيشنهادي آن ها چندکاره تر و در کاربردهاي متنوع وسيع تري قابل استفاده است و شکل خوشه هـا تـاثير کمتـري در کارآيي آن دارد. آن ها الگوريتم MCV را با الگوريتم هاي مختلفـي ماننـد: گوستافسـون - کسـل [١٠] (Gustafson- Kessel) و K-means
به عنوان اوليه ساز به کار برده و نشان دادند که الگوريتم FCM داراي کارآيي بهتري است .
در MCV تابع هدف با جمع کردن ابرحجم هاي تکي هاي خوشه هاي فازي شده از رابطه زير بدست مي آيد:
که در آن B بردار مراکز خوشه ها، U ماتريس تقسيم بندي فازي ، X مجموعه داده ها، c تعداد خوشه ها و Cfi دترمينان ماتريس کوواريانس Cfi است که :
ماتريس کوواريانس فازي خوشه ي i ام است ، و در آن m ميزان فازي بودن و n تعداد داده ها مي باشد. بردار مراکز خوشه ها از رابطه ي زير بدست
فاصله ماهالانبيس بين xt و cs به صورت زير است :
فرض مي شـود ١ اسـت .Nt مجموعـه اي از انـديس هـاي خوشـه هـايي کـه فاصله شان از نقطه xt منفي است را مشخص مي نمايد وit نزديکترين خوشه به xt را مشخص مي نمايد. معادله جديـد بـراي c ,...,١ ust, s از رابطه ي زير بدست مي آيد:
انديس اعتبارسنجي خوشه اصلاح شده فوکوياما- سوگنو
سوگنو و ياسوکاوا معيار زير را به عنوان انديس اعتبارسنجي خوشه معرفي مي کنند:
که n تعداد داده ها، c تعداد خوشه ها، k xk امين داده ، x ميانگين داده ها، vi برداري است که مرکز خوشه i ام را تعريف مي کند، . هر نوع نـرم ، ik ذ درجه اي است که k امين داده به i امين خوشه تعلق دارد و m درجه فازي بودن است . در ايـن تحقيـق انـديس اصـلاح شـده فوکويامـا- سـوگنوي معرفي شده در [٨] و [١١] را به عنوان انديس اعتبارسنجي استفاده مي کنيم ، که در آن بردار ميـانگين داده هـا x بـا بـردار ميـانگين تقسـيم بنـدي فـازي به صورت زير جايگزين مي شود:
به علاوه تابع فاصله ماهالانبيس را به کار مي بريم :
(II) مقادير عضويت ورودي ها در دو زيرمرحله تعيين مي شوند:
(i) ابتدا، مقادير توابع عضويت خروجي به فضاي هر يک از متغيرهاي ورودي تصوير مي شود. تصوير کردن بـا روشـي کـه بوسـيله ي سوگنو و ياسوکاوا پيشنهاد شده است [٦] انجام مي شود.
(ii) سپس با توجه به روش پيشنهاد شده توسط فاضل زرندي (Fazel Zarandi)، [٨] همان گونه که در شکل ٣ مشاهده مـي شـود،
محدوده هايي که در آن تابع عضويت متغير ورودي مقدار ١ را اختيار مي کند مشخص کرده و داده ها را با مقدار m و c تعيين شده در مرحلـه قبل ، به روشي که در اين پژوهش استفاده شده و در زير توضيح داده مي شود، با استفاده از الگوريتم هاي ژنتيک کلاسه بندي ١ مي نماييم .
ابتدا فاصله اي را که تابع عضويت متغير ورودي مقدار ١ را مي گيرد، مشخص کرده (يعني ، ) VV١٢ سپس الگوريتم هـاي ژنتيـک جفتهـايي از مقادير تصادفي V١ و V٢ را بعنوان تکي هاي جمعيت اوليه توليد مي نمايد. مقادير اوليه بصورتي انتخاب مي شوند که در محدوده ( VV١٢) قـرار گيرند. اين مقادير به تابع هدف الگوريتم کلاسه بندي ، به عنوان تابع برازش الگوريتم هاي ژنتيک که به صورت رابطـه زيـر تعريـف مـي شـود، منتقل مي شود: (m و c بدست آمده از مرحله خوشه بندي متغير خروجي در رابطه زير استفاده مي شود)
