واژگان کلیدی: تولید سلولی، تشکیل سلول، چیدمان سلولی، زمانبندی گروهی، الگوریتم ژنتیک فهرست مطالب فصل اولکلیات تحقیق1-1- مقدمه. 21-2- بیان مساله. 31-3- هدف انجام تحقیق. 51-4- ضرورت انجام تحقیق. 51-5- ساختار تحقیق. 6 فصل دوممرور ادبیات2-1- مقدمه. 82-2- تکنولوژی گروهی. 92-2-1- کاربرد کدگذاري در تکنولوژي گروهي102-2-2- نتايج انعطافپذيري112-3- توليد سلولي. 162-3-1- مزايا و معايب توليد سلولي.. 242-4- زمانبندي. 342-4-1- مدلهاي زمانبندي.. 392-5- مروری بر مسائل تولید سلولی با رویکردهای تشکیل سلول، چیدمان سلول و زمانبندی گروهی. 43 فصل سومروش تحقیق3-1- مقدمه. 533-2- مفروضات. 543-3- نمادهای مدل. 553-3-1- اندیسها.. 553-3-2- پارامترهای ورودی.. 563-3-3- پارامترهای خروجی.. 563-3-4- متغیرهای تصمیمگیری.. 573-4- مدل ریاضی. 574-4- تشریح مدل. 573-2- روش حل با استفاده از الگوریتم ژنتیک. 613-2-1- آشنایی با الگوریتم ژنتیک.. 613-2-1-1- مقدمه.. 613-2-1-2- زمينه هاي بيولوژيکي.. 633-2-1-3- فضايجستجو.. 643-2-1-4- مسائل NP. 653-2-1-5- مفاهيماوليهدرالگوريتمژنتيك.. 673-2-1-5-1- اصولپايه.. 673-2-1-5-2- شمايكليالگوريتمژنتيك.. 673-2-1-5-3- کد کردن.. 693-2-1-5-4- روش هاي کدينگ.. 703-2-1-5-5- کروموزوم.. 733-2-1-5-6- جمعيت.. 733-2-1-5-7- مقدار برازندگي.. 743-2-1-5-8- عملگر تقاطع.. 753-2-1-5-9- عملگر جهش.. 773-2-1-5-10- روش هاي انتخاب.. 773-2-1-6- ارائه الگوریتم پیشنهادی. 803-2-1-7- نمایش کروموزوم.. 803-2-1-8- ایجاد جمعیت اولیه.. 823-2-1-9- تابع برازندگی.. 823-2-1-10- انتخاب.. 833-2-1-11- تقاطع.. 833-2-1-12- جهش.. 863-2-1-13- معیار توقف.. 86 فصل چهارممحاسبات و تحلیل نتایج4-1- مقدمه. 884-2- اعتبارسنجی و ارائه مثال عددی. 884-3- نتایج محاسباتی و تحلیل آنها. 93 فصل پنجمنتیجهگیری و پیشنهادات5-1- نتیجهگیری. 1005-2- پیشنهادات برای تحقیقات آتی. 100پیوستکد الگوریتم ژنتیک در نرم افزار متلب.. 103منابع و مراجع. 109 فهرست جداول جدول 2‑1. مزایای CM بعد از دو ماه عملیات [31].. 28جدول 2‑2. منفعتهای گزارش شده از تولید سلولی در [15].. 30جدول 2‑3. بهبودهای عملکرد گزارش شده در [13].. 31جدول 2‑4. خلاصهای از مرور ادبیات.. 49جدول 3‑1. نمایش جواب مساله توسط کروموزوم.. 80جدول 3‑2. مثالی از تقاطع مورد استفاده.. 85جدول 4‑1. اطلاعات اولیه مثال.. 90جدول 4‑2. مقایسه زمانی بین حل با لینگو و حل با الگوریتم GA 94 فهرست شکلها شکل 2‑1. محيط توليدي توليد کارگاهي [9].. 18شکل 2‑2. خط توليدي خط جريان [9].. 19شکل 2‑3. سیستم تولید سلولی [9].. 22شکل 2‑4. چیدمان سلولی پایه الف) چیدمان خطی تک ردیفی ب) چیدمان خطی دو ردیفی.. 50شکل 3‑1. چیدمان سلولها و ماشینها.. 54شکل 3‑2. نمونه اي از فضاي جواب.. 65شکل 3‑3. کدينگ باينري.. 70شکل 3‑4. کدينگ جهشي.. 71شکل 3‑5. کدينگ ارزشي.. 71شکل 3‑6. کدينگ درختي.. 72شکل 3‑7. فضاي کدينگ وفضاي جواب.. 73شکل 3‑8. مثالي از عمل جابجايي تک نقطهاي.. 75شکل 3‑9. تقاطعي دو نقطه اي.. 76شکل 3‑10. عمل تقاطعي يکنواخت.. 76شکل 3‑11. چرخ رولت.. 78شکل 3‑12. انتخاب تورنامنت.. 79شکل 4‑1. نمایی از تشکیل سلول و چیدمان سلولی مثال حل شده 92شکل 4‑2. نمای گانت مثال حل شده.. 92 فصل اول کلیات تحقیق 1-1- مقدمهتکنولوژی گروهی[1] یک فلسفه تولیدی مبتنی بر سازماندهی و گروهبندی وظایف مشترک با هدف بهبود بهرهوری سیستم تولیدی است. تولید سلولی[2] یکی از مهمترین کاربردهای تکنولوژی گروهی است که سلولهای تولیدی را به طریقی تشکیل میدهد که هر خانواده قطعات[3] در یک سلول توسط یک گروه معین از ماشینهای مربوط به آن سلول (سلول ماشینی[4]) پردازش شوند. تولید سلولی یک استراتژی تولیدی نوآورانهای میباشد که در سیستمهای تولیدی مدرنی همچون سیستمهای تولید منعطف[5] و تولید بهنگام [6] بکار گرفته شده است. تولید سلولی با گروهبندی، تولید و مدیریت قطعات و ماشینهایی که مشخصههای مشابه و نزدیک به هم دارند، میتواند از تولید دستهای به سمت تولید انبوه حرکت کند و در عین حال درجه بالایی از انعطافپذیری را همچون تولید کارگاهی حفظ نماید. از میان مزایای متعددی که سیستم تولید سلولی به همراه دارد میتوان به مواردی چون سادهسازی جریان مواد، کاهش زمان راهاندازی، کاهش میزان موجودی در جریان، کاهش زمان تکمیل کار، کنترل بهتر و نرخ ضایعات کمتر اشاره نمود. تشکیل سلول[7] ، چیدمان سلول[8] و مدیریت سلول سه گام مهمی هستند که در طراحی موفق یک سیستم تولید سلولی باید در نظر گرفته شوند. تشکیل سلول شامل تعیین خانواده قطعات و سلولهای ماشینی با هدف کاهش زمان جابجایی بین سلولی قطعات میباشد. طراحی یک چیدمان سلولی که شامل دو بخش است: 1) تعیین چیدمان سلولها در سطح کارگاه[9] و 2) مشخص کردن چیدمان ماشینها در هر سلول[10]، که هر دو با هدف کاهش زمان جابجاییها صورت میگیرند و در نهایت مدیریت سلول به موضوعات برنامهریزی همچون زمانبندی سلولی[11] میپردازد. در زمانبندی سلولی، مساله زمانبندی خانواده قطعات و هر قطعه منحصربفرد مورد توجه قرار دارد. ارتباطات بین این سه تصمیمگیری نقش مهمی را در طراحی یک سیستم تولید سلولی بازی میکند.در اکثر مطالعات انجام شده در حوزه سیستمهای تولید سلولی، تنها برای حل یکی از سه موضوع ذکر شده (CF,CL,CS) تلاشهایی صورت گرفته است و برخی از تحقیقات به حل دو یا هر سه فاکتور به صورت متوالی و پی در پی پرداختهاند. این رویکردها راه حلهایی را ایجاد میکنند که احتمالا برای یکی از این سه مساله کارایی دارند در حالیکه برای سیستم کلی رضایتبخش نیستند. این رخداد به دلیل تاثیر این سه زیر مساله بر روی یکدیگر در هنگام طراحی سیستم تولید سلولی میباشد.تنها مدل یکپارچه ریاضی که در آن تشکیل سلول، چیدمان سلولی و زمانبندی به طور همزمان در نظر گرفته شده است توسط وو[12] [1] ارائه شد، اما در مدل و الگوریتم حل آنها چیدمان سلولی به روش صحیحی مشخص نمیشود و سلولها ممکن است با یکدیگر همپوشانی داشته باشند. در مدل آرکات[13][2] علاوه بر اینکه همه مفروضات و مزایای مدل قبلی حفظ شد، مشکل همپوشانی سلولها رفع گردید و موقعیت (مختصات) ماشینها به طور دقیق تعیین شد.از آنجاییکه در سیستم تولید سلولی فاکتور جابجایی بین سلولی به لحاظ زمان و هزینه از اهمیت بالایی برخوردار است [29] به واسطه آن موقعیت سلولها نسبت به هم و فاصله آنها از یکدیگر در هنگام تشکیل سلول مهم میباشد.در مدل پیشنهادی، ما بر آن هستیم که با طراحی مدل یکپارچه تشکیل سلول با چیدمان سلول و زمانبندی عملیاتها در سیستم تولید سلولی با هدف حداقل کردن زمان تکمیل کارها علاوه بر توجه به عدم همپوشانی سلولها و مشخص کردن موقعیت دقیق ماشینها، به تعیین چیدمان بهینه خود سلولها به طور مستقل در مدلسازی خود بپردازیم و نحوه قرارگیری بهینه سلولها را در کنار هم، مشخص نماییم. در این مدل چیدمان سلولها را به صورت خطی دو ردیفی در نظر گرفتهایم چراکه این چیدمان به دلیل انعطافپذیری که برای کار کردن با تجهیزات جابجایی مواد[14] [3] دارد و همچنین کاهش زمان جابجایی بین سلولی[15] به دلیل نزدیکی سلولها [4]، چیدمانی مناسب است. در نهایت برای حل مدل از الگوریتم ژنتیک استفاده نمودهایم.هدف این تحقیق، ارائه یک مدل یکپارچه است که به طور همزمان سلولهای تولیدی را تشکیل داده، چیدمان ماشینها و سلولها را تعیین کرده و عملیاتها را زمانبندی مینماید. تمامی این فرآیندها با هدف حداقل کردن زمان تکمیل کارها صورت میگیرند. برای حل این مساله از الگوریتم فراابتکاری ژنتیک استفاده شده است.
طراحی مدل یکپارچه تشکیل سلول با چیدمان سلول و زمانبندی عملیات ها با در نظر گرفتن چیدمان سلولی خطی دو ردیفی و حل آن با الگوریتم ژنتیکwword
واژگان کلیدی: تولید سلولی، تشکیل سلول، چیدمان سلولی، زمانبندی گروهی، الگوریتم ژنتیک فهرست مطالب فصل اولکلیات تحقیق1-1- مقدمه. 21-2- بیان مساله. 31-3- هدف انجام تحقیق. 51-4- ضرورت انجام تحقیق. 51-5- ساختار تحقیق. 6 فصل دوممرور ادبیات2-1- مقدمه. 82-2- تکنولوژی گروهی. 92-2-1- کاربرد کدگذاري در تکنولوژي گروهي102-2-2- نتايج انعطافپذيري112-3- توليد سلولي. 162-3-1- مزايا و معايب توليد سلولي.. 242-4- زمانبندي. 342-4-1- مدلهاي زمانبندي.. 392-5- مروری بر مسائل تولید سلولی با رویکردهای تشکیل سلول، چیدمان سلول و زمانبندی گروهی. 43 فصل سومروش تحقیق3-1- مقدمه. 533-2- مفروضات. 543-3- نمادهای مدل. 553-3-1- اندیسها.. 553-3-2- پارامترهای ورودی.. 563-3-3- پارامترهای خروجی.. 563-3-4- متغیرهای تصمیمگیری.. 573-4- مدل ریاضی. 574-4- تشریح مدل. 573-2- روش حل با استفاده از الگوریتم ژنتیک. 613-2-1- آشنایی با الگوریتم ژنتیک.. 613-2-1-1- مقدمه.. 613-2-1-2- زمينه هاي بيولوژيکي.. 633-2-1-3- فضايجستجو.. 643-2-1-4- مسائل NP. 653-2-1-5- مفاهيماوليهدرالگوريتمژنتيك.. 673-2-1-5-1- اصولپايه.. 673-2-1-5-2- شمايكليالگوريتمژنتيك.. 673-2-1-5-3- کد کردن.. 693-2-1-5-4- روش هاي کدينگ.. 703-2-1-5-5- کروموزوم.. 733-2-1-5-6- جمعيت.. 733-2-1-5-7- مقدار برازندگي.. 743-2-1-5-8- عملگر تقاطع.. 753-2-1-5-9- عملگر جهش.. 773-2-1-5-10- روش هاي انتخاب.. 773-2-1-6- ارائه الگوریتم پیشنهادی. 803-2-1-7- نمایش کروموزوم.. 803-2-1-8- ایجاد جمعیت اولیه.. 823-2-1-9- تابع برازندگی.. 823-2-1-10- انتخاب.. 833-2-1-11- تقاطع.. 833-2-1-12- جهش.. 863-2-1-13- معیار توقف.. 86 فصل چهارممحاسبات و تحلیل نتایج4-1- مقدمه. 884-2- اعتبارسنجی و ارائه مثال عددی. 884-3- نتایج محاسباتی و تحلیل آنها. 93 فصل پنجمنتیجهگیری و پیشنهادات5-1- نتیجهگیری. 1005-2- پیشنهادات برای تحقیقات آتی. 100پیوستکد الگوریتم ژنتیک در نرم افزار متلب.. 103منابع و مراجع. 109 فهرست جداول جدول 2‑1. مزایای CM بعد از دو ماه عملیات [31].. 28جدول 2‑2. منفعتهای گزارش شده از تولید سلولی در [15].. 30جدول 2‑3. بهبودهای عملکرد گزارش شده در [13].. 31جدول 2‑4. خلاصهای از مرور ادبیات.. 49جدول 3‑1. نمایش جواب مساله توسط کروموزوم.. 80جدول 3‑2. مثالی از تقاطع مورد استفاده.. 85جدول 4‑1. اطلاعات اولیه مثال.. 90جدول 4‑2. مقایسه زمانی بین حل با لینگو و حل با الگوریتم GA 94 فهرست شکلها شکل 2‑1. محيط توليدي توليد کارگاهي [9].. 18شکل 2‑2. خط توليدي خط جريان [9].. 19شکل 2‑3. سیستم تولید سلولی [9].. 22شکل 2‑4. چیدمان سلولی پایه الف) چیدمان خطی تک ردیفی ب) چیدمان خطی دو ردیفی.. 50شکل 3‑1. چیدمان سلولها و ماشینها.. 54شکل 3‑2. نمونه اي از فضاي جواب.. 65شکل 3‑3. کدينگ باينري.. 70شکل 3‑4. کدينگ جهشي.. 71شکل 3‑5. کدينگ ارزشي.. 71شکل 3‑6. کدينگ درختي.. 72شکل 3‑7. فضاي کدينگ وفضاي جواب.. 73شکل 3‑8. مثالي از عمل جابجايي تک نقطهاي.. 75شکل 3‑9. تقاطعي دو نقطه اي.. 76شکل 3‑10. عمل تقاطعي يکنواخت.. 76شکل 3‑11. چرخ رولت.. 78شکل 3‑12. انتخاب تورنامنت.. 79شکل 4‑1. نمایی از تشکیل سلول و چیدمان سلولی مثال حل شده 92شکل 4‑2. نمای گانت مثال حل شده.. 92 فصل اول کلیات تحقیق 1-1- مقدمهتکنولوژی گروهی[1] یک فلسفه تولیدی مبتنی بر سازماندهی و گروهبندی وظایف مشترک با هدف بهبود بهرهوری سیستم تولیدی است. تولید سلولی[2] یکی از مهمترین کاربردهای تکنولوژی گروهی است که سلولهای تولیدی را به طریقی تشکیل میدهد که هر خانواده قطعات[3] در یک سلول توسط یک گروه معین از ماشینهای مربوط به آن سلول (سلول ماشینی[4]) پردازش شوند. تولید سلولی یک استراتژی تولیدی نوآورانهای میباشد که در سیستمهای تولیدی مدرنی همچون سیستمهای تولید منعطف[5] و تولید بهنگام [6] بکار گرفته شده است. تولید سلولی با گروهبندی، تولید و مدیریت قطعات و ماشینهایی که مشخصههای مشابه و نزدیک به هم دارند، میتواند از تولید دستهای به سمت تولید انبوه حرکت کند و در عین حال درجه بالایی از انعطافپذیری را همچون تولید کارگاهی حفظ نماید. از میان مزایای متعددی که سیستم تولید سلولی به همراه دارد میتوان به مواردی چون سادهسازی جریان مواد، کاهش زمان راهاندازی، کاهش میزان موجودی در جریان، کاهش زمان تکمیل کار، کنترل بهتر و نرخ ضایعات کمتر اشاره نمود. تشکیل سلول[7] ، چیدمان سلول[8] و مدیریت سلول سه گام مهمی هستند که در طراحی موفق یک سیستم تولید سلولی باید در نظر گرفته شوند. تشکیل سلول شامل تعیین خانواده قطعات و سلولهای ماشینی با هدف کاهش زمان جابجایی بین سلولی قطعات میباشد. طراحی یک چیدمان سلولی که شامل دو بخش است: 1) تعیین چیدمان سلولها در سطح کارگاه[9] و 2) مشخص کردن چیدمان ماشینها در هر سلول[10]، که هر دو با هدف کاهش زمان جابجاییها صورت میگیرند و در نهایت مدیریت سلول به موضوعات برنامهریزی همچون زمانبندی سلولی[11] میپردازد. در زمانبندی سلولی، مساله زمانبندی خانواده قطعات و هر قطعه منحصربفرد مورد توجه قرار دارد. ارتباطات بین این سه تصمیمگیری نقش مهمی را در طراحی یک سیستم تولید سلولی بازی میکند.در اکثر مطالعات انجام شده در حوزه سیستمهای تولید سلولی، تنها برای حل یکی از سه موضوع ذکر شده (CF,CL,CS) تلاشهایی صورت گرفته است و برخی از تحقیقات به حل دو یا هر سه فاکتور به صورت متوالی و پی در پی پرداختهاند. این رویکردها راه حلهایی را ایجاد میکنند که احتمالا برای یکی از این سه مساله کارایی دارند در حالیکه برای سیستم کلی رضایتبخش نیستند. این رخداد به دلیل تاثیر این سه زیر مساله بر روی یکدیگر در هنگام طراحی سیستم تولید سلولی میباشد.تنها مدل یکپارچه ریاضی که در آن تشکیل سلول، چیدمان سلولی و زمانبندی به طور همزمان در نظر گرفته شده است توسط وو[12] [1] ارائه شد، اما در مدل و الگوریتم حل آنها چیدمان سلولی به روش صحیحی مشخص نمیشود و سلولها ممکن است با یکدیگر همپوشانی داشته باشند. در مدل آرکات[13][2] علاوه بر اینکه همه مفروضات و مزایای مدل قبلی حفظ شد، مشکل همپوشانی سلولها رفع گردید و موقعیت (مختصات) ماشینها به طور دقیق تعیین شد.از آنجاییکه در سیستم تولید سلولی فاکتور جابجایی بین سلولی به لحاظ زمان و هزینه از اهمیت بالایی برخوردار است [29] به واسطه آن موقعیت سلولها نسبت به هم و فاصله آنها از یکدیگر در هنگام تشکیل سلول مهم میباشد.در مدل پیشنهادی، ما بر آن هستیم که با طراحی مدل یکپارچه تشکیل سلول با چیدمان سلول و زمانبندی عملیاتها در سیستم تولید سلولی با هدف حداقل کردن زمان تکمیل کارها علاوه بر توجه به عدم همپوشانی سلولها و مشخص کردن موقعیت دقیق ماشینها، به تعیین چیدمان بهینه خود سلولها به طور مستقل در مدلسازی خود بپردازیم و نحوه قرارگیری بهینه سلولها را در کنار هم، مشخص نماییم. در این مدل چیدمان سلولها را به صورت خطی دو ردیفی در نظر گرفتهایم چراکه این چیدمان به دلیل انعطافپذیری که برای کار کردن با تجهیزات جابجایی مواد[14] [3] دارد و همچنین کاهش زمان جابجایی بین سلولی[15] به دلیل نزدیکی سلولها [4]، چیدمانی مناسب است. در نهایت برای حل مدل از الگوریتم ژنتیک استفاده نمودهایم.هدف این تحقیق، ارائه یک مدل یکپارچه است که به طور همزمان سلولهای تولیدی را تشکیل داده، چیدمان ماشینها و سلولها را تعیین کرده و عملیاتها را زمانبندی مینماید. تمامی این فرآیندها با هدف حداقل کردن زمان تکمیل کارها صورت میگیرند. برای حل این مساله از الگوریتم فراابتکاری ژنتیک استفاده شده است.