ترجمه فارسی عنوان مقاله

رویکرد شی گرا برای مساله ی زمان بندی انعطاف پذیر و چند هدفه ی کار کارگاهی

عنوان انگلیسی

An object-oriented approach for multi-objective flexible job-shop scheduling problem

کد مقاله	سال انتشار	تعداد صفحات مقاله انگلیسی
43090	2016	14 صفحه PDF

منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Expert Systems with Applications, Volume 45, 1 March 2016, Pages 71–84

فهرست مطالب ترجمه فارسی

چکیده

کلیدواژه ها

1. مقدمه

شکل 1. تعریف کلاس کار و دستگاه (اقتباس از پیندو، 2012).

2. تعریف مساله

3. نمایش راه حل FJSP

3.1. نمایش راه حل FJSP پیشین

جدول 1. مساله 4 × 5.

شکل 2. نمایش راه حل در مقالات (بر گرفته از ژانگ و همکاران، 2009).

شکل 3. ارتباط بین دستگاه و عملیات.

شکل 4. ارتباط بین دستگاه و عملیات.

شکل 5. ساختار داده تحت ارتباطات چند-به-چند.

3.2. نمایش راه حل شیء گرای FJSP

شکل 6. دیاگرام کلاس UML رویکرد پیشنهاد شده.

3.2.1. دیاگرام کلاس FJSP

3.2.2. دیاگرام تعامل

شکل 7. دیاگرام تعامل نمونه.

3.2.3. طراحی OO و اثرش بر سیستم های کنترل تولید

شکل 8. طراحی OO و سیستم اطلاعات تولید پیشنهادی.

4. الگوریتم بازپخت شبیه سازی شده برای FJSP شی گرا

4.1. حرکت همسایگی

شکل 9. درج پیش رو و پس رو.

شکل 10. مقدار دهی اولیه FJSP.

شکل 11. زمان بندی برای مجموعه مساله 4 × 5.

جدول 2. مساله 8 × 8.

4.2. تابع برازش

شکل 12. زمان بندی برای مجموعه مساله 8 × 8.

جدول 3. مساله 10 × 10.

شکل 13. زمان بندی برای مجموعه مساله 10 × 10.

شکل 14. زمان بندی برای مجموعه مساله 15 × 10.

4.3. زمان بندی خنک سازی

جدول 4. مساله 15 × 10.

4.4. مقداردهی اولیه

جدول 5. مقایسه عملکردهای الگوریتم برای مجموعه مساله 8 × 8.

جدول 6. مقایسه ی عملکردهای الگوریتم برای مجموعه مساله 10 × 10.

جدول 7. مقایسه عملکردهای الگوریتم برای جموعه مسائل 15 × 10.

جدول 8. تحلیل آماری و مقایسه زمان CPU رویکرد پیشنهاد شده.

5. نتایج آزمایش

6. نتیجه گیری

ترجمه کلمات کلیدی

کنترل و تولید شی گرا - طراحی شی گرا - برنامه ریزی انعطاف پذیر کارگاهی چندهدفه - الگوریتم بازپخت شبیه سازی شده

کلمات کلیدی انگلیسی

Object-oriented manufacturing control; Object-oriented design; Multi-objective flexible job-shop scheduling; Simulated annealing algorithm

ترجمه چکیده

کنترل سیستم های تولیدی انعطاف پذیر بسیار پیچیده است و تولید سیستم های کنترل کننده برای این حوزه مساله دشوار است. مساله زمان بندی انعطاف پذیر کار کارگاهی (FJSP) یکی از موارد این حوزه است. این مساله ای است که مشخصه های مساله زمان بندی کار کارگاهی (JSP) را به ارث می برد. FJSP زیر-مساله ی مسیریابی اضافی ای را افزون بر JSP دارد. در زیر-مساله مسیریابی، هر عملیات به یک دستگاه از بین مجموعه ای از دستگاه های فعال تخصیص می یابد. در زیر-مساله برنامه ریزی، توالی عملیات های تخصیص یافته در هنگام بهینه سازی تابع (های) هدف به دست می آید. در این مقاله، رویکرد شی گرا (OO) برای FJSP چند هدفه همراه با الگوریتم بهینه سازی بازپخت شبیه سازی شده ارائه می شود. رویکردهای راه حل در مقالات عموما از طرح کدگذاری دو رشته ای برای بیان این مساله استفاده می کنند. با این حال، متدولوژی تحلیل، طراحی و برنامه نویسی OO به ارائه ی موثر این مساله در طرح کدگذاری کمک می کند، که به ادغام عملی راه حل مساله با سیستم های کنترل تولید که در آن ها اغلب از پارادایم OO استفاده می شود منجر می شود. طراحی FJSP به روش OO از طریق استفاده از دیاگرام کلاس UML حاصل می آید، و این طراحی کدگذاری مساله را به یک ساختار داده ی واحد تقلیل می دهد که در آن شی عملیات FJSP می تواند داده های خود در مورد دستگاه های جایگزین را در ساختار داده ی خودش به صورت سلسله مراتبی حفظ کند. ارتباطات چند-به-چند بین عملیات ها و دستگاه ها از طریق درج یک کلاس جدید بین آنها به دو ارتباط یک-به-چند تبدیل می شوند. کمینه کردن سه تابع هدف زیر در این مقاله در نظر گرفته می شود: حداکثر زمان تکمیل، بار کاری دستگاه دارای بیشترین بار و بار کاری کل همه دستگاه ها. چند مجموعه معیار به منظور نشان دادن اثربخشی رویکرد پیشنهاد شده اجرا می شوند. ثابت می شود که استفاده از رویکرد OO برای FJSP چند هدفه نه تنها به ساخت سیستم های کنترل تولید موثر، بلکه به دستیابی به راه حل های موثر نیز منجر می شود.

ترجمه مقدمه

مسائل زمان بندی نقش بسیار مهمی را در سیستم های صنعتی بسیاری ایفا می کنند. این مسائل توجه پژوهشگران بسیاری را جلب می کنند (بایکاسوقلو و همکاران، 2004، بروکر و شلی، 1990، دای و همکاران، 2013، گری و همکاران، 1976، لیو و همکاران، 2014، لو و همکاران، 2014، وانگ و لیو، 2014، شیا و وو، 2005، ژینگونگ و یونگ، 2015 و ژائو و همکاران، 2014). اکثر مسائل زمان بندی مسائل بهینه سازی ترکیبی پیچیده هستند و حل کردن آن ها بسیار دشوار است (شیا و وو، 2005 و زیبالوس، 2010). یکی از مسائل زمان بندی پیچیده JSP است. در کار کارگاهی، هر کار می تواند مسیر پردازش متفاوتی را از درون سیستم داشته باشد، و از این رو مساله زمان بندی بسیار پیچیده می شود (فهمی، بالاکریشنان، و المکاوی، 2011). کار کارگاهی شاخه ای از زمان بندی تولید است. این مساله یک مساله ی NP-سخت معروف است (گری و همکاران، 1976). FJSP مساله ای است که مشخصه های JSP را به ارث می برد. FJSP به دلیل اهمیتش در صنعت توجه پژوهشگران بسیاری را جلب کرده است. FJSP زیر-مساله مسیریابی اضافی را افزون بر JSP دارد. در زیر-مساله مسیریابی، هر عملیات به یک دستگاه از بین مجموعه ای از دستگاه های توانمند تخصیص داده می شود. در زیر-مساله زمان بندی، توالی عملیات های تخصیص یافته در هنگام بهینه سازی تابع (های) هدف به دست می آید. بنابراین، FJSP دو مشکل را ایجاد می دهد؛ تخصیص عملیات و یافتن زمان بندی بهینه ی عملیات (شیا و وو، 2005). اگر چه الگوریتم جواب بهینه برای JSP کلاسیکی هنوز توسعه نیافته است، روندی در جامعه ی محققان برای مدل سازی و حل نسخه بسیار پیچیده تر JSP وجود دارد. نیاز به مدل سازی و حل FJSP عمدتا به دلیل این واقعیت که ابزارهای دستگاهی مدرن مقدار قابل توجهی قابلیت های همپوشان دارند پدید آمده است (بایکاسوقلو و همکاران، 2004). تعداد مطالعات برای FJSP بیشتر از تعداد مطالعات برای JSP به نظر می رسد. بروکر و شلی (1990) در میان اولین کسانی بودند که به FJSP پرداختند. آنها یک الگوریتم چند جمله ای را برای حل FJSP با دو کار توسعه دادند. برندیمارته (1993) از یک الگوریتم سلسله مراتبی برای FJSP بر اساس فرا ابتکاری جستجوی ممنوعه استفاده کردند. داوزره-پرز و پائولی (1997) نسخه ی تعمیم یافته ای از مدل گراف تقاطعی را توسعه دادند که قادر به لحاظ کردن این واقعیت است که عملیات ها باید به دستگاه ها برای FJSP تخصیص یابند. ماسترولیلی و گامبردلا (2002) دو تابع همسایگی را همراه با رویه ی جستجوی ممنوعه برای FJSP معرفی کردند. همچنین زمانی که بیش از یک تابع هدف وجود دارد FJSP مجددا جستجو می شود. بایکاسوقلو و همکاران (2004) رویکرد مدل سازی و راه حل فرا ابتکاری مبتنی بر زبان شناسی را برای FJSP چند هدفه پیشنهاد کردند. شیا و وو (2005) رویکرد بهینه سازی ترکیبی موثر را برای FJSP چند هدفه پیشنهاد کردند. ژانگ، شائو، لی، و گائو (2009) الگوریتم بهینه سازی ازدحام ذرات ترکیبی موثر را برای FJSP چند هدفه پیشنهاد کردند. وانگ ژو، خو، و لیو (2012) الگوریتم کلونی زنبور مصنوعی مبتنی بر پارتو را برای حل موثر FJSP چند هدفه پیشنهاد کردند. لی، پان، و زی (2012) الگوریتم جهش قورباغه ی آمیخته ی ترکیبی را برای راه حل این مساله پیشنهاد کردند. پور و قاسمی شبانکاره (2013) الگوریتم های ژنتیکی ترکیبی و بازپخت شبیه سازی شده (SA) را برای FJSP چند هدفه پیشنهاد کردند. وانگ، وانگ و لیو (2013) الگوریتم توزیع مبتنی بر پارتوی موثر را برای این مساله پیشنهاد کردند. در سیستم های تولیدی واقعی، تحلیل مساله زمان بندی و توسعه الگوریتم ها و رویه ها تنها بخشی از کار است. این رویه باید در سیستمی جاسازی شود که تصمیم گیرنده را قادر به استفاده ی واقعی از آن می کند. این سیستم باید در سیستم اطلاعات سازمان ادغام شود، که می تواند کاری دشوار باشد (پیندو، 2012) ادغام مدل طراحی با اطلاعات فرآیند و زمان بندی به صورت آنی به منظور افزایش کیفیت محصول، کاهش هزینه، و کوتاه کردن چرخه تولید محصول لازم است (سورماز، آروموگام، هاری هارا، پاتل، و نیروکوندا، 2010). طراحان سیستم به جهت گیری الگوریتم ها و رویه های زمان بندی توسعه یافته نسبت به سیستم اطلاعات تولید واقعی شان نیاز دارند، زیرا سیستم زمان بندی پیوندهای بسیاری با سیستم های مختلف دیگر در سازمان دارد. گاهی اوقات تطبیق الگوریتم زمان بندی با سیستم اطلاعات تولید، نسبت به توسعه ی الگوریتم یا رویه، بسیار بیشتر طول می کشد. ادغام سیستم های زمان بندی با سیستم اطلاعات جاری برای برنامه نویسان کامپیوتر کار بی اهمیتی نیست. طراحی سیستم های نرم افزاری فعالیت بسیار پیچیده ای است، زیرا به شدت تحت تاثیر کیفیت مورد نیاز در محصولات نهایی قرار دارد (وازکوئز، آندرس دیاز پیس، و کامپو، 2014). تحلیل، طراحی و برنامه نویسی OO تا الان به مدت 30 سال در دست توسعه بوده است، با این حال در دهه ی گذشته بود که متدولوژی های رشد و توسعه ی سریعی را با استفاده از پیشرفت های توانایی سرعت و پردازش در توسعه ی نرم افزارهای بسیار پیچیده دریافت کرد (مورنو رینا و همکاران، 2012). برنامه نویسی OO روشی است که به شدت ساخت یافته است. این روش شامل ماژولار بودن و نظم منطقی ساختارهای نرم افزاری است (شیزین و منگوانگ، 2000). فناوری های OO پرکاربردترین فناوری برنامه نویسی کامپیوتری در فناوری های اطلاعاتی کنترلی تولیدی امروزی هستند (فرناندز د کانته و همکاران، 2013، کوان، 2011، لیائو و هو، 2011 و لین و همکاران، 2003). بنابراین محققان در حوزه ی زمان بندی دستگاه باید تناسب راه حل شان با فناوری های اطلاعاتی مدرن را در نظر بگیرند. استفاده از فناوری اطلاعات (IT) یک ممکن کننده ی قابل توجه فرصت هاست (نگای، پنگ، الکساندر، و مون، 2014). سیستم های مدیریت پایگاه داده ی (DBMS) امروزی که در سیستم های کنترل تولید استفاده می شوند عموما بر اساس اصول برنامه نویسی OO ساخته می شوند. آنها از زبان پرس و جوی ساخت یافته (SQL) در هنگام ضبط و بازیابی داده ها استفاده می کنند. Oracle، MySql، Sybase، و MS SQL Server نمونه هایی از DBMS ها هستند که معمولا در سیستم های کنترل تولید استفاده می شوند. DBMS ها در ارتباط با الگوریتم های زمان بندی استفاده می شوند. بنابراین رابطه ی بسیار نزدیکی در میان برنامه نویسی OO، زمان بندی دستگاه و DBMS وجود دارد. داده های مرتبط با کار و دستگاه را می توان بر اساس متدولوژی برنامه نویسی OO پردازش و در یک DBMS ثبت کرد. این داده ها را می توان در اشیاء کپسوله کرد و می توانند برای اهداف زمان بندی و ثبت / بازیابی داده ها استفاده شوند. شکل 1 برخی ویژگی ها و رفتارهای اساسی کار معمولی و کلاس دستگاه را در یک سیستم اطلاعات تولید نشان می دهد. داده های ایستای مربوط به یک کار را می توان در یک شی کار نگاه داشت. به عنوان مثال فهرست عملیات، وزن مرتبط، زمان جابجایی مواد، هزینه حمل و نقل، و موعد، برخی داده های ایستای مربوط به شی یک کار خاص هستند. برخی از رفتارهای اساسی برای یک کار می توانند ساخت، کپی، حذف و نمایش باشند. داده های ایستای مربوط به دستگاه نیز می توانند در شی دستگاه کپسوله شوند؛ فهرست قابلیت ها، سرعت، زمان نگهداری زمان بندی شده و غیره. از سوی دیگر برخی داده های ایستای مربوط به هر دوی کارها و دستگاه ها وجود دارند. به عنوان مثال، زمان راه اندازی وابسته به توالی می تواند به عنوان داده های ایستای مربوط به هر دوی دستگاه ها و کارها در نظر گرفته شود. این انواع داده ها به عنوان ایستا طبقه بندی می شوند، زیرا به زمان بندی تولید شده بستگی ندارند. در FJSP، عملیات های کارها دستگاه های جایگزینی را برای پردازش شدن دارند. داده های مربوط به دستگاه جایگزین به داده های هر دوی عملیات های دستگاه و کار وابسته هستند. بنابراین FJSP شامل یک ارتباط اضافی دستگاه-کار است. تحقیقات ارائه شده در مقالات عموما این ارتباط را به دو زیر مساله تقسیم بندی می کنند. زیر-مساله اول تخصیص عملیات ها به یک دستگاه از بین چند دستگاه در دسترس است. زیر-مساله دوم توالی بندی تمام عملیات ها بر روی هر دستگاه است (شائو، لیو، لیو، و ژانگ، 2013). اگرچه متدولوژی برنامه نویسی OO و مساله FJSP برای محققان جدید نیستند، اما طراحی FJSP توسط پارادایم OO برای هر دوی کارورزان علم و توسعه دهندگان الگوریتم جدید به نظر می رسد. به نظر می رسد که شکافی بین توسعه دهندگان نرم افزار سیستم های کنترل تولید و توسعه دهندگان الگوریتم نظریه زمان بندی وجود دارد، که قبلا گفتیم پر کردن این شکاف کار دشواری است (پیندو، 2012). این تحقیق قرار است که این شکاف را پر کند و پلی بین توسعه دهندگان نرم افزار و توسعه دهندگان الگوریتم باشد. در این مقاله، ارتباط بین دستگاه و عملیات ها با تعریف یک کلاس جدید بازنمایی می شود. با انجام این کار، نمایش راه حل دو فازی FJSP چند هدفه می تواند به راه حلی تبدیل شود که به ساختار راه حل هوشمند و موثر منجر می شود. ارائه ی موجودیت های سیستم و ارتباطات شان بر روی اشیاء نرم افزار قرار است که پیچیدگی سیستم را بدون از دست دادن کیفیت راه حل کاهش دهد. الگوریتم SA برای رویکرد OO پیشنهاد شده استفاده می شود. ساختار ادامه این مقاله به شرح زیر است: بخش 2 تعريف مساله برای FJSP چند هدفه را ارائه می دهد. بخش 3 طراحی OO برای FJSP را ارائه می دهد. بخش 4 اعمال الگوریتم SA به رویکرد پیشنهاد شده را ارائه می دهد. بخش 5 چند مساله تست و راه حل های شان را در رویکرد پیشنهاد شده ارائه می دهد و بخش 6 این مقاله را خلاصه می کند.

دانلود رایگان 2 صفحه اول مقاله لاتین (PDF)

پیش نمایش مقاله

چکیده انگلیسی

Flexible manufacturing systems are very complex to control and it is difficult to generate controlling systems for this problem domain. Flexible job-shop scheduling problem (FJSP) is one of the instances in this domain. It is a problem which inherits the job-shop scheduling problem (JSP) characteristics. FJSP has additional routing sub-problem in addition to JSP. In routing sub-problem each operation is assigned to a machine out of a set of capable machines. In scheduling sub-problem the sequence of assigned operations is obtained while optimizing the objective function(s). In this paper an object-oriented (OO) approach is presented for multi-objective FJSP along with simulated annealing optimization algorithm. Solution approaches in the literature generally use two-string encoding scheme to represent this problem. However, OO analysis, design and programming methodology help to present this problem on a single encoding scheme effectively which result in a practical integration of the problem solution to manufacturing control systems where OO paradigm is frequently used. OO design of FJSP is achieved by using UML class diagram and this design reduces the problem encoding to a single data structure where operation object of FJSP could hold its data about alternative machines in its own data structure hierarchically. Many-to-many associations between operations and machines are transformed into two one-to-many associations by inserting a new class between them. Minimization of the following three objective functions are considered in this paper: maximum completion time, workload of the most loaded machine and total workload of all machines. Some benchmark sets are run in order to show the effectiveness of the proposed approach. It is proved that using OO approach for multi-objective FJSP contributes to not only building effective manufacturing control systems but also achieving effective solutions.