نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 گروه مطالعات علم و فناوری، دانشگاه فرماندهی و ستاد آجا، تهران، ایران
2 گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه کردستان، سنندج، ایران
چکیده
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Purpose: This paper aims to propose a flow shop scheduling problem for equipment overhaul. This problem consists of three stages, the separation of the components of an equipment is done in the first stage. Repairs and overhaul operations are carried out on the separated parts of the first stage in the second stage. Finally, the overhauled parts of the previous stage are mounted on each other in the third stage. In the third stage, operations are performed in parallel workshops. The objective function of the problem is the maximum time to complete jobs, and the sequence of processing jobs should be done in such a way that the value of the objective function is minimized.
Design/methodology/approach: To solve the problem, a mixed integer programming model has been proposed for small size, which determines the processing sequence of jobs based on the position of each job. A genetic algorithm has been used to solve the problem in large dimensions. By increasing the size of the problem and in different sizes, the results have been examined and analyzed, which shows the efficiency of the model and the proposed algorithm.
Findings: To check the accuracy of the model's performance and also the effect of the presence of parallel machines in the third stage, an example was presented in this paper. Accordingly, while the accuracy of the model's performance was checked, the effect of the presence of more machines was determined in the third stage. As the number of machines increased in the third stage, the value of the objective function did not deteriorate. The performance of GAMS in solving the problem in a small size was investigated. Considering that solving the problem for large dimensions is not possible in a reasonable time and the problem is NP-hard, then solving the problem in large dimensions was done using a genetic algorithm. Therefore, solving the problem on a large dimension has been done using the genetic algorithm. According to the obtained results, the efficiency of the genetic algorithm was shown. Due to its low average value, it indicated the convergence of the genetic algorithm.
Research limitations/implications: Considering that there are not many published papers in the field of equipment overhaul, it is difficult to access related models and papers. Therefore, in this paper, the model and solution method have been written with many reviews. Also, to check and reduce costs, the number of third-stage machines has been determined using sensitivity analysis.
Practical implications: The problem of equipment overhaul is used in many fields in reality. For example, the operations related to the maintenance, repair and overhaul of the aircraft engine have been investigated. Since the planning of maintenance and maintenance operations is difficult, the focus of research has been on improving maintenance operations by finding suitable scheduling for job shop operations in maintenance operations. They emphasized that scheduling can improve maintenance operations and presented a simulation model.
Social implications: The purpose of creating a space to start an activity is to reduce costs, earn money and achieve profit. To examine the cost-effectiveness of the equipment overhaul issue, we can refer to the number of third-stage machines. According to the amount of equipment to perform an overhaul on them, the number of third-stage machines can be determined. Therefore, extra machines can be removed to reduce the cost. On the other hand, if the related equipment to the customers is different, to reduce the storage costs or increase customer satisfaction, different goals should be considered. Here, the objective function of maximum completion time is considered for this purpose. If the equipment must be available at a certain time, goals such as the total time to complete the job can be considered. In line with the application of the social implications in the investigated problem in this paper and considering that the investment costs, as well as the ability to respond to the applicants' requests, are related to the number of third-stage machines, the value of the objective function is analyzed based on the number of third-stage machines and analysis has been done.
Originality/value: In this paper, a three-stage flow shop scheduling problem in the overhaul industry was studied. Accordingly, a new mathematical model based on the job processing position was proposed, which dealt with the exact solution of the problem in small dimensions. According to the type of problem in the overhaul environment, the combined flow shop problem for equipment overhaul was investigated. Also, the use of parallel machines in the third stage of the equipment overhaul problem is one of the new issues under investigation.
کلیدواژه‌ها [English]
1-مقدمه
تجهیزات و داراییهای فیزیکی سازمان در طول چرخۀ عمرشان، دچار استهلاک می‌شوند و این امر سازمان‌ها را در دوره‌های زمانی متناوب، در برابر تصمیم‌گیری برای از رده خارج کردن یا بازسازی تجهیزات قرار می‌دهد. در بسیاری از موارد، بازسازی و اورهال تجهیزات صنعتی در صورتی که به‌درستی اجرا شود، میتواند در مسیر خلق بیشترین ارزش از داراییهای فیزیکی، به سازمان کمک کند.
بنا به یک تعریف عمومی، اورهال عبارت است از احیای همه‌جانبه و کامل یک دارایی برای رساندن آن به شرایط پذیرفتنی، ازطریق بازسازی و یا تعویض قطعات و زیرمجموعه‌های آن (لنهان[i]، 2011). درواقع هدف از اجرای اورهال، بازیابی عملکرد بهینۀ تجهیز، در عین تضمین قابلیت اطمینان آن است. فرآیند اورهال تجهیزات عموماً شامل مراحل زیر میشود (چانگ و عبداله[ii]، 2014):
کلمۀ اورهال معمولاً برای تجهیزات مکانیکی به کار می‌رود و فرآیند آن عموماً در میانۀ عمر مفید تجهیز پیادهسازی میشود. گاهی به‌جای کلمۀ اورهال، از عبارت تعمیرات عمده[iii] استفاده میشود. برای اورهال برخی تجهیزات، لازم است که آنها را از محل استقرار خارج و به محل مناسب برای اجرای فرآیند بازسازی منتقل کرد، اگرچه بسیاری از تجهیزات را نیز باید در محل استقرارشان اورهال کرد. در فرآیند اورهال تجهیزات، گاهی به بازسازی[iv] برخی قطعات و تجهیزات زیرمجموعه نیاز است. برای قطعاتی که امکان بازسازی‌شان وجود ندارد، باید برای تعویض[v] آنها اقدام کرد.
عملیات اورهال میتواند به‌صورت اضطراری، در پی یک شکست غیرمنتظره، در قالب یک برنامۀ از پیش تعیین شده و در زمان خارج از بهره‌برداری‌بودن تجهیز شود. به‌طور کلی، اجرای فرآیند تعمیرات اساسی دو نوع هزینه را به سازمان تحمیل می‌کند: یکی هزینه‌های مستقیم اجرای فرآیند اورهال و دیگری هزینه‌های مرتبط با از دسترس خارج بودن تجهیز در زمان تعمیرات اساسی. برنامه‌ریزی صحیح و بر مبنای وضعیت سلامت تجهیز در طی چرخۀ عمر آن، میتواند زمان‌بندی اجرای عملیات تعمیر اساسی را بهگونهای تنظیم کند که هر دو نوع هزینه به حداقل برسد.
بهمنظور افزایش سرعت و دقت در اورهال و تعمیرات تجهیزات در این طرح تحقیقاتی، مسئلۀ زمان‌بندی و تخصیص اورهال تجهیزات در یک جریان کارگاهی[vi] چندمرحله‌ای در نظر گرفته شده است. با هدف بهبود انجام فرآیند اورهال و به اقتضای زمان و وضع موجود، می‌توان بهمنظور کاهش هزینه‌های نیروی انسانی و زمان، از توابع هدفی همچون بیشینۀ زمان تکمیل عملیات استفاده کرد. مسئله در حالت کلی این‌گونه تعریف میشود که تعمیرات و اورهال تجهیزات به چه صورتی زمان‌بندی میشود. در صورتی که اورهال تجهیزات به‌موقع و به‌درستی زمان‌بندی شود، میتواند در مسیر ایجاد بیشترین ارزش از داراییهای فیزیکی به مجموعه کمک کند؛ بنابراین در این تحقیق به‌دنبال زمان‌بندی درست و به‌موقع اورهال و تعمیرات تجهیزات هستیم، به‌طوری‌که حداکثر بهرهوری در فرآیند مدنظر حاصل و درنهایت به آمادگی سیستمهای مربوطه منجر شود.
در قرن حاضر سازمان‌ها با محیطی بسیار ناپایدار و پویا در حال فعالیت‌اند و همواره با خطرات و تهدیدهایی روبه‌رو می‌شوند که در صورت پاسخ‌ندادن به‌موقع و سریع، بدون تردید با چالشهای بسیار مهمی مواجهه خواهند شد. با توجه به اینکه مدت‌زمان استفاده از تجهیزات نظامی، بیشتر از وسایل تجاری است و تغییرات در آن معمولاً در زمان بیشتری اتفاق میافتد، یکی از این عوامل کلیدی در به‌کارگیری تجهیزات، بحث اورهال و بهینه‌کردن است که در سال‌های اخیر، بیشتر مدیران، سازمان‌ها و فرماندهان به آن توجه کرده‌اند و با توجه به این شرایط، زمان‌بندی اورهال، تعمیرات وسایل و تجهیزات، میتواند نقش بسزایی در حوضۀ صنایع دفاعی و نظامی داشته باشد. هر موقع که هرکدام از وسایل و تجهیزات به تعمیرات اساسی و بهینه‌سازی نیاز دارد، به مراکز اورهال و بهینه‌سازی ارسال و به همان نسبت، از آمادگی و توان رزمی آن واحد کم میشود و با این وصف، هرگونه سرعت و چابکی به تقویت مجدد توان و آمادگی آن واحد کمک می‌کند (بهرامی و همکاران،[vii] 1396).
میزان آمادگی میتواند معیاری برای تخصیص بودجه، خرید تجهیزات، اقلام پشتیبانی و همچنین انجام اقدامات نظامی در زمان صلح یا جنگ باشد. آمادگی تجهیزات یکی از مؤلفههای اساسی در آمادگی عملیاتی سازمان‌ها و هدف اصلی سیستم نگهداری، تعمیرات (نت) و فلسفۀ وجودی آن در فرآیند پشتیبانی آنهاست (رمضانی و همکاران،[viii] 1390).
در این مقاله ما یک مسئلۀ زمان‌بندی جریان کارگاهی را بهمنظور کاهش هزینه و زمان اورهال تجهیزات ارائه دادهایم که این مسئله در جلوگیری از تعمیرات اضافی، تشخیص و پیشگویی معایب، قبل از خرابی و کاهش ضایعات کاربرد دارد (خدابخشیان و همکاران،[ix] 1387). یکی از مهم‌ترین عوامل دفاعی هر کشور، تجهیزات نظامی آن است. ازجمله ضرورت‌های ارائهشده در این تحقیق، آماده نگه داشتن تجهیزات و در اختیار داشتن حداکثر توان مقابله با نیروهای غیرخودی در زمان نیاز است. اهمیت این مسئله مربوط به زمانی است که حفاظت از کشور و جان افراد در میان باشد و کاربرد آن در مواقع صلح، برای حفظ امنیت و در مواقع جنگ، بهمنظور تسریع در آمادهسازی تجهیزات است.
در راستای افزایش توان دفاعی، آمادهسازی و در دسترس بودن تجهیزات نظامی برای استفاده در مواقع اضطراری تعمیرات و اورهال تجهیزات انجام میشود. در صورت روبه‌روشدن با تهدیدات احتمالی، امکان به‌کارگیری تجهیزات در زمان نیاز، وجود خواهد داشت. همچنین زمان‌بندی انجام اورهال و بهینه‌سازی مناسب، دقیق، با قابلیت اطمینان بالا و با کیفیت، میتواند باعث افزایش اعتماد کارکنان و سازمان به سیستم تعمیرات و اورهال داخلی و درنتیجه افزایش روحیه و اعتمادبه‌نفس پرسنل فنی شود که این خود باعث نوعی وابستگی‌نداشتن به عوامل خارجی میشود. همچنین زمان‌بندی انجام تعمیرات، اورهال و بهینه‌سازی باکیفیت و قابلیت اعتماد بالا، باعث جلوگیری از دوباره‌کاری و عودت مجدد تجهیزات و ادوات بازسازی‌شده به مراکز میشود و میتواند در کاهش هزینه و وقت پرسنل سازمان مؤثر باشد.
با توجه به موارد مطرح‌شده، هدف از ارائۀ این مقاله، برنامه‌ریزی منظم برای اورهال تجهیزات بهمنظور جلوگیری از ایجاد وقفه در فعالیت‌هایی است که یک سازمان انجام می‌دهد؛ بهنحوی که کمترین مشکل برای به‌کارگیری تجهیزات وجود داشته باشد. حال برای انجام تعمیرات، به‌روزرسانی و اورهال تجهیزات، از یک سیستم منظم استفاده و طی یک فرآیند مشخص، عملیات اورهال انجام میشود. برنامه‌ریزی و زمان‌بندی این سیستم، از جهت تسریع در انجام فرآیند اورهال بسیار حائز اهمیت است. در این مقاله یک مسئلۀ زمان‌بندی جریان کارگاهی سه مرحله‌ای، برای اورهال تجهیزات ارائه شده است؛ به‌طوری که در مراحل اول و دوم یک ماشین و در مرحلۀ سوم، ماشین‌های موازی وجود دارند. نوآوریهای مسئله شامل موارد زیر است: در نظر گرفتن جریان کارگاهی سه مرحله‌ای برای اورهال تجهیزات، ارائۀ مدل برنامه‌ریزی عدد صحیح آمیختۀ جدید، در نظر گرفتن ماشین‌های موازی یکسان در مرحلۀ سوم مسئلۀ جریان کارگاهی، در نظر گرفتن سیستم جریان کارگاهی بهمنظور اورهال تجهیزات و به‌کارگیری الگوریتم ژنتیک بهمنظور حل مسئله در ابعاد بزرگ.
۲- پیشینۀ پژوهش و مبانی نظری
رمنی و استادچر[x] (2014) عملیات مربوط به نگهداری، تعمیر و اورهال[xi] موتور هواپیما را بررسی کردند. با توجه به اینکه برنامه‌ریزی و عملیات تعمیر و نگهداری دشوار است، تمرکز تحقیق بر بهبود عملیات نگهداری، ازطریق یافتن زمان‌بندی[xii] مناسب برای عملیات کار کارگاهی[xiii]، در عملیات نگهداری و تعمیرات بوده است. آنها تأکید کردند که زمان‌بندی میتواند عملیات نگهداری را بهبود دهد، یک مدل شبیهسازی را ارائه و فرآیند نگهداری و تعمیرات را به 3 مرحلۀ مجزا تقسیم کردند که شامل عملیات دمونتاژ، انجام تعمیرات و مونتاژ است.
چانگ و عبداله (2014) یک مدل مدیریت عملیات را ارائه کردند که مفهوم توسعۀ پایدار را در فرآیند نگهداری و مدیریت در نگهداری، تعمیرات و اورهال یک کارخانه به کار میگیرد. نگهداری، تعمیرات و اورهال هواپیما برای عملیات هوایی بسیار مهم است. آنها چهار بررسی برای نگهداری و تعمیرات در نظر گرفتند که بررسی C و D به زمان بیشتر و هزینۀ بالاتری نسبت‌به بررسی‌های A و B نیاز دارد. بهمنظور افزایش رضایت مشتریان، بخش MRO شرکت باید بر تحویل، کیفیت، هزینه و انعطافپذیری تمرکز کند.
هوانگ و همکاران[xiv] (2016) براساس مدل‌های چند اعتباری، یک بهینه‌سازی شبیهسازی را برای مسئلۀ زمان‌بندی نگهداری، تعمیر و اورهال به وجود آوردند و نیز یک مدل شبیهسازی را با درجۀ اعتبار بالا ارائه دادند که احتمالی و زمان‌بر است؛ سپس فرآیند را به سه بخش تقسیم کردند: کارگاه دمونتاژ، تعمیرات و مونتاژ. کارگاه تعمیرات شامل یک یا چند ماشین چندکاره با یک یا چند ماشین یکسان است.
مایتو و همکاران[xv] (2016) یک تحقیق را با هدف بهبود زمان‌بندی ماشین‌ها ارائه کردند؛ به‌طوری که مقدار بیشینۀ زمان تکمیل کارها در زمان‌بندی کار کارگاهی، با استفاده از الگوریتم ژنتیک[xvi] کمینه میشود. همچنین برنامه‌ریزی جدیدی را برای انجام تعمیرات ماژول بخش سرد موتور انجام دادند.
حسنی[xvii] (1396) مسئلۀ زمان‌بندی مونتاژ را در جریان کارگاهی انعطاف‌پذیر دو مرحله‌ای، با خط اختصاصی تولیدکنندۀ محصولات متنوع چنددورهای در نظر گرفت. تابع هدف، مسئلۀ بیشینۀ زمان تکمیل کارها و میانگین وزنی کل زمان‌های تأخیر است. مرحلۀ اول شامل ماشین‌های اختصاصی در گام اول و یک ماشین در گام دوم و مرحلۀ دوم شامل دو گام تولید اختصاصی است. آنها یک مدل ریاضی و همچنین یک روش فراابتکاری مبتنی بر نقاط قوت پارتو و جست‌وجوی وسیع همسایگی انعطاف‌پذیر را ارائه کردند.
لیو و همکاران[xviii] (2017) یک مسئلۀ زمان‌بندی را در کلاس سیستمهای نگهداری، تعمیرات و اورهال ارائه کردند. آنها با در نظر گرفتن همۀ مشخصههای کلیدی از قبیل دمونتاژ، بازیابی غیرقطعی مواد، مسیریابی احتمالی و زمان‌های پردازش احتمالی، یک مسئلۀ زمان‌بندی را به‌عنوان یک مسئلۀ شبیهسازی فرموله کردند و برای حل مسئله، دو الگوریتم ترکیبی را ارائه دادند. مسئله برای یک مجموعه از کارها، عبارت است از: تعیین توالی کارها بهمنظور دمونتاژ در کارگاه دمونتاژ، تعیین توالی اجزا برای تعمیر در کارگاه تعمیرات و تعیین توالی کارها برای انجام عملیات مونتاژ در مرحلۀ مونتاژ؛ به‌طوری که مجموع وزنی زمان‌های تأخیر کمینه شود.
بزرگ‌نژاد و همکاران[xix] (1397)، مسئلۀ یکپارچۀ زمان‌بندی کارها و نیروی انسانی را در محیط جریان کارگاهی ارائه دادند که در آن تعدادی نیروی انسانی با مهارت‌های مختلف، کارهای متفاوتی را با سرعت‌های مختلف انجام می‌دهند. تابع هدف مسئله، تعیین زمان‌بندی کارها در مراحل مختلف و تخصیص نیروی انسانی به این مراحل است؛ بهگونهای که بیشنۀ زمان تکمیل کارها حداقل شود. آنها همچنین یک مدل ریاضی خطی عدد صحیح مختلط و یک الگوریتم فراابتکاری را از ترکیب الگوریتم بهینه‌سازی ازدحام ذرات و شبیهسازی تبرید ارائه کردند.
حسام و همکاران[xx] (1398) مسئلۀ زمان‌بندی کارها و فعالیت‌های نگهداری و تعمیرات را در یک سیستم تولیدی با ماشین‌های موازی غیر یکسان در نظر گرفتند، با فرض زمان‌های پردازش کنترل‌شدنی، یک مدل برنامه‌ریزی ریاضی چندهدفه را برای کمینه‌کردن مجموع هزینه‌های توسعه، فشردهسازی زمان‌های پردازش، نگهداری و تعمیرات، حداکثر زمان تکمیل، دیرکردها و زودکردها ارائه کردند، برای حل مدل چندهدفۀ پیشنهادی، از رویکرد کلاسیک برنامه‌ریزی آرمانی چند انتخابی و برای حل نمونۀ مسائل در ابعاد متوسط و بزرگ، از ژنتیک مرتبسازیشدۀ غیرغالب[xxi] استفاده کردند.
ترن و همکاران[xxii] (2019) الگوریتم هوش ازدحامی و بهینه‌سازی کلونی مورچگان[xxiii] را بهمنظور حل مسئلۀ زمان‌بندی فرآیندهای MRO، با دو تابع هدف بیشینۀ زمان تکمیل و مجموع زمان‌های تأخیر همۀ کارها ارائه دادند و سه مرحله برای فرآیند MRO در نظر گرفتند: همۀ اجزا در مرحلۀ اول، بازرسی می‌شوند، در مرحلۀ دوم زمان‌بندی عملیات تعمیرات است و درنهایت در مرحلۀ سوم، عملیات آزادسازی انجام میشود.
لی و همکاران[xxiv] (2020) یک روش بهینه‌سازی زمان‌بندی را برای نگهداری و تعمیرات منابع خدماتی در محصولات پیچیده ارائه کردند که این موضوع سبب بهبود رضایت مشتریان، بالابردن ارزش محصول و افزایش مزیت رقابتی میشود. آنها ابتدا مسئلۀ زمان‌بندی را در منابع خدماتی تحلیل کردند، سپس یک مدل ریاضی را برای مسئلۀ زمان‌بندی مربوطه ارائه دادند که شامل سه تابع هدف کمینه‌کردن زمان انتظار مشتریان، کاهش منابع مازاد و ماکزیمم‌کردن شاخص هزینۀ عملکرد منابع است. درنهایت هریک از سه تابع هدف براساس روش‌های ژنتیک بهبودیافته، روش بهینه‌سازی ضریب وزنی ترکیبی و روش NSGA-II تحلیل شده‌اند.
رحمان و همکاران[xxv] (2020) معتقدند که فرآیند MRO یک عمل بهمنظور کنترل، شناسایی و اطمینان از عمر یک تجهیز دفاعی است. اندونزی باید مفهوم MRO را در صنایع دفاعی در نظر داشته باشد. مسئلۀ مربوطه عبارت است از: چگونگی تعیین وزندهی و توسعۀ برنامه‌ریزی استراتژیک، برای نگهداری و تعمیرات اساسی کشتی‌های جنگی بهمنظور پشتیبانی از آمادگی عملیات دریایی. هدف از تحقیق ارائهشده، ایجاد یک برنامه‌ریزی استراتژیک در توسعۀ MRO کشتی‌های جنگی، در پشتیبانی از آمادگی عملیات دریایی است.
گا و همکاران[xxvi] (2022) با توجه به نبود تطابق بین انواع و تعداد واحدهای تعمیرات و فعالیت‌های پشتیبانی در زمان جنگ، همراه با زمان‌بندی فعالیت‌های نگهداری تجهیزات، مسئلۀ زمان‌بندی جریان کارگاهی انعطاف‌پذیر را در نظر گرفتند و مدل زمان‌بندی فعالیت‌های نگهداری تجهیزات را براساس گروه تعمیرات همراهیکننده ارائه کردند. بر پایۀ توانایی محدود و زمان تیم تعمیرات، مدل ارائهشده زمان‌بندی فعالیت‌های تیم تعمیرات را با هدف کمینه‌کردن زمان صرفشده برای تعمیرات در نظر گرفت.
بهمنظور بررسی و مقایسۀ پیشینۀ موضوع، خلاصۀ مقالات مطرح‌شده در جدول ۱ نشان داده شده است. در این مقالات: ۱ مقالۀ ماشین‌های موازی، 1 مقالۀ جریان کارگاهی، ۱ مقالۀ کار کارگاهی، 4 مقالۀ کار کارگاهی دو مرحله‌ای، 1 مقالۀ جریان کارگاهی دو مرحله‌ای، ۱ مقالۀ جریان کارگاهی انعطاف‌پذیر و 2 مقالۀ جریان کارگاهی سه مرحله‌ای را ارائه دادند.
جدول 1- خلاصۀ پیشینۀ مسئله
Table 1- Summary of problem literature
|
ردیف |
نویسنده |
مسئله |
|
1 |
رمنی و استادچر (2014) |
کار کارگاهی دو مرحله‌ای |
|
2 |
چانگ و عبداله (2014) |
جریان کارگاهی سه مرحله‌ای |
|
3 |
هوانگ و همکاران (2016) |
کار کارگاهی دو مرحله‌ای |
|
4 |
مایتو و همکاران (2016) |
کار کارگاهی دو مرحله‌ای |
|
5 |
حسنی (1396) |
جریان کارگاهی دو مرحله‌ای |
|
6 |
لیو و همکاران (2017) |
کار کارگاهی دو مرحله‌ای |
|
7 |
بزرگ‌نژاد و همکاران (1397) |
جریان کارگاهی |
|
8 |
حسام و همکاران (1398) |
ماشین‌های موازی |
|
9 |
ترن و همکاران (2019) |
کار کارگاهی |
|
10 |
رحمان و همکاران (2020) |
جریان کارگاهی سه مرحله‌ای |
|
11 |
گا و همکاران (2022) |
کار کارگاهی انعطاف‌پذیر |
با توجه به پیشینۀ بررسی‌شده، در این تحقیق یک مسئلۀ زمان‌بندی جربان کارگاهی ترکیبی بهمنظور نگهداری، تعمیرات و اورهال تجهیزات در ارتش ارائه خواهد شد. در این مسئله، تجهیزات مدنظر برای زمان‌بندی تعمیرات و اورهال در یک جریان کارگاهی چندمرحله‌ای قرار میگیرند که مرحلۀ اول آن دمونتاژ تجهیزات، مرحلۀ دوم تعمیرات و اورهال و مرحلۀ سوم مونتاژ است،. مرحلۀ سوم، ماشین‌های موازی در نظر گرفته شده است که با توجه به دانش ما از مسئله، تاکنون برای مسئلۀ اورهال تجهیزات بررسی نشده است. در صنعت اورهال تجهیزات، مدل ارائهشده در این مقاله تاکنون بررسی نشده است. لیو (2017)، پیچیدهترین حالت را ارائه کرده و در مرحلۀ دوم کار کارگاهی در نظر گرفته شده است؛ در صورتی که در مسئلۀ ما و در مرحلۀ سوم، ماشین‌های موازی در نظر گرفته شده است؛ بنابراین اهم نوآوری مسئلۀ مدنظر، به شرح ذیل است:
1- ارائۀ یک مدل ریاضی جدید بر مبنای موقعیت پردازش کارها؛
2- به‌کارگیری مسئلۀ جریان کارگاهی ترکیبی برای اورهال تجهیزات؛
۳- به‌کارگیری ماشین‌های موازی در مرحلۀ سوم مسئلۀ اورهال تجهیزات.
۳- روش‌شناسی پژوهش
مسئلۀ بررسی‌شده در این مقاله، یک مسئلۀ جریان کارگاهی سه مرحله‌ای بهمنظور تعمیرات و اورهال تجهیزات است. در این مسئله تعداد n تجهیز برای انجام عملیات اورهال، در یک جریان کارگاهی سه مرحله‌ای پردازش میشود که در مرحلۀ سوم آن تعداد m ایستگاه وجود دارد. اگر تجهیزات به‌عنوان کار و هر مرحله نیز همانند یک ماشین در نظر گرفته شود، مسئلۀ مورد بررسی، یک مسئلۀ جریان کارگاهی سه مرحله‌ای است که در مراحل اول و دوم، یک ماشین و در مرحلۀ سوم، ماشین‌های موازی یکسان وجود دارد. توابع هدف مختلف، معانی متفاوتی در مسائل زمان‌بندی دارند. در این مقاله تابع هدف، بیشینۀ زمان تکمیل کارها در نظر گرفته شده است. این تابع هدف برای حالتی کاربرد دارد که تجهیزاتی بهمنظور اورهال برنامه‌ریزی می‌شوند که به‌صورت دستهای، به مراکز مختلف مربوط‌ا‌ند. در این حالت برای کاهش زمان تکمیل کل کارها، بیشترین زمان تکمیل، کمینه میشود و تجهیزات اورهال‌شدۀ مربوط به یک مرکز، به‌طور هم‌زمان، در زمان کمتری تحویل می‌شوند.
۳-1- فرضیات مدل
مدل مسئله با در نظر گرفتن مفروضات زیر، ارائه شده است:
۳-2- نمادگذاری
با توجه به توضیحات ذکرشده، مدل ریاضی مسئله به شرح زیر است:
اندیسها
|
s |
اندیس پوزیشن کارها {1, 2, ... , n} |
|
i ، j ، r |
اندیس کارها {1, 2, ... , n} |
|
l |
اندیس ماشین‌ها در مرحلۀ سوم {1, 2, ... , m} |
پارامترها
|
n |
تعداد کارها |
|
|
تعداد ماشین‌های مرحلۀ سوم |
|
|
زمان پردازش کار j در مرحلۀ اول |
|
|
زمان پردازش کار j در مرحلۀ دوم |
|
|
زمان پردازش کار j در مرحلۀ سوم |
|
A |
یک عدد بسیار بزرگ |
متغیرهای تصمیم
|
|
اگر کار i در پوزیشن s در مرحلۀ دمونتاژ پردازش شود، برابر 1 و در غیر این صورت برابر صفر است. |
|
|
اگر کار i در پوزیشن s بر ماشین در مرحلۀ مونتاژ پردازش شود، برابر 1 و در غیر این صورت برابر صفر است. |
|
|
زمان تکمیل کار در پوزیشن s در مرحلۀ اول |
|
|
زمان تکمیل کار در پوزیشن s در مرحلۀ دوم |
|
|
زمان تکمیل کار در پوزیشن s بر ماشین در مرحلۀ سوم |
۳-3- مدل ریاضی
با توجه به تعریف اندیسها، پارامترها و متغیرهای تصمیم، معادلات مدل ریاضی به شرح زیر تعریف می‌شوند:
|
Minimize |
|
(1) |
|
|
|
|
(2) |
|
|
|
|
(3) |
|
|
|
|
(4) |
|
|
|
|
(5) |
|
|
|
|
(6) |
|
|
|
|
(7) |
|
|
|
|
(8) |
|
|
|
|
(9) |
|
|
|
|
(10) |
|
|
|
|
(11) |
|
|
|
|
(12) |
|
|
|
|
(13) |
|
|
|
|
(14) |
|
|
|
|
(15) |
|
|
, |
|
(16) |
|
|
|
|
(17) |
|
رابطۀ 1 تابع هدف مسئله را نشان می‌دهد که کمینه‌کردن بیشینۀ زمان تکمیل کارهاست. محدودیت 2 نشان می‌دهد هر کار فقط به یک پوزیشن در مراحل اول و دوم تخصیص می‌یابد. محدودیت 3 مشخص می‌کند که به هر پوزیشن در مراحل اول و دوم، حتماً یک کار تخصیص می‌یابد. محدودیت 4 تعیین می‌کند که در مراحل اول و دوم، یک پوزیشن زمانی تکمیل میشود که پوزیشن قبلی آن، توسط یک کار اشغال شده باشد. محدودیت 5 مشخص می‌کند که در مرحلۀ سوم، هر کار را فقط یک ماشین پردازش می‌کند و امکان توقف در پردازش و جابه‌جایی بین ماشین‌ها وجود ندارد. محدودیت 6 نشان می‌دهد به هر پوزیشن هر ماشین، حداکثر یک کار تخصیص می‌یابد. محدودیت 7 مشخص می‌کند در مرحلۀ سوم، یک پوزیشن زمانی تکمیل میشود که پوزیشن قبلی آن، توسط یک کار اشغال شده باشد. محدودیت 8 نیز زمان تکمیل کارها را در مرحلۀ اول مشخص می‌کند. محدودیت 9 زمان تکمیل کاری را معین می‌کند که در اولین پوزیشن مرحلۀ اول قرار دارد. محدودیت 10 زمان تکمیل کار را در پوزیش اول و در مرحلۀ دوم مشخص می‌کند. محدودیت‌های 11 و 12، 13 و 14، زمان تکمیل کارها را در مرحلۀ دوم معین میکنند. محدودیت 15 نشان می‌دهد بیشینۀ زمان تکمیل کار باید از زمان تکمیل هریک از کارها بیشتر باشد. محدودیت 16 متغیرهای باینری و محدودیت 17، محدودۀ متغیرهای پیوسته را تعیین می‌کند.
۴- روش حل
بهمنظور حل مسئله در این بخش، از دو روش استفاده شده است: ۱- حل دقیق مسئله به‌وسیلۀ الگوریتم شاخه و کران در ابعاد کوچک، با استفاده از نرم‌افزار گمز و ۲- حل مسئله در ابعاد بزرگ با استفاده از الگوریتم ژنتیک.
4-1- حل دقیق مسئله
حل مسئله در ابعاد کوچک با استفاده از مدل امکان‌پذیر است. در این مقاله، نتایج حل مدل به‌صورت دقیق و با استفاده از حلکنندۀ سیپلکس در نرم‌افزار گمز بررسی شده است. مدل ارائهشده بر مبنای پوزیشن و به این صورت است که پوزیشن کارها بر ماشین‌ها در هر مرحله مشخص میشود. جانسون[xxvii] (1954) اثبات کرد که مسئلۀ جریان کارگاهی سه مرحله‌ای، در صورتی که تابع هدف بیشینۀ زمان تکمیل کارها باشد ( )، یکسان در نظر گرفتن توالی کارها در همۀ مراحل نیز، شامل جواب بهینه میشود و به تغییر توالی کارها در هریک از مراحل، برای رسیدن به جواب بهینه نیازی نیست؛ بنابراین اگر تعداد ماشین‌ها در هریک از مراحل برابر 1 باشد، در نظر گرفتن یک متغیر برای مدل کافی است؛ مثلاً برای مراحل اول و دوم فقط یک متغیر در نظر گرفته شده است.
بهمنظور کاهش تعداد متغیرهای مسئله و همچنین کاهش زمان حل، توالی پردازش کارها در مرحلۀ دوم یکسان در نظر گرفته شده است. برای بررسی عملکرد مدل، شرط توقف اجرا ۳600 ثانیه است و در صورتی که مدل قبل از این زمان به جواب بهینه برسد، اجرا متوقف میشود؛ در غیر این صورت، جواب به دست آمده تا این زمان (3600 ثانیه)، بهترین جواب مدل در نظر گرفته میشود.
4-2- الگوریتم ژنتیک
چن[xxviii] (1995) برای مسئلۀ جریان کارگاهی دو مرحله‌ای با ماشین‌های موازی در یک مرحله و تابع هدف بیشینۀ زمان تکمیل کارها، نشان داد مسئله با زمان چندجمله‌ای NP-سخت[xxix] است. با توجه به اینکه مسئلۀ بررسی‌شده در این مقاله، جریان کارگاهی سه مرحله‌ای با ماشین‌های موازی در مرحلۀ سوم و پیچیدهتر از مسئلۀ ارائهشده توسط چن (1995) است، بنابراین NP-سخت است. حل مسائل NP-سخت در ابعاد بزرگ، با توجه به محدودیت زمانی و ظرفیت پردازنده به‌صورت دقیق امکان‌پذیر نیست؛ بنابراین بهمنظور دستیابی به جواب‌های بهینه یا نزدیک به بهینه، از روش فراابتکاری استفاده شده است. در این مقاله از الگوریتم ژنتیک برای حل مسئله، با استفاده از نرم‌افزار جاوا استفاده شده است.
الگوریتم ژنتیک یکی از شناخته‌شده‌ترین الگوریتم‌های فراابتکاری است که اولین بار هلند[xxx] (۱۹75) آن را ارائه کرد. این الگوریتم بر مبنای جمعیت[xxxi] و الهام‌گرفته از طبیعت است. در جواب هر مسئله، یک کروموزوم شناخته میشود و از ترکیب ژن‌ها به وجود می‌آید. ازطریق ایجاد تغییرات، در هر کروموزوم یک جواب جدید ایجاد میشود. الگوریتم ژنتیک شامل عملگرهای جهش و تقاطع بهمنظور ایجاد جمعیت جدید است.
الگوریتم ارائهشده شامل چند قسمت است که عبارت‌اند از: 1- ارائۀ نمایش جواب بهمنظور کدنویسی مسئله؛ 2- رمزگشایی مسئله از نحوۀ نمایش در مرحلۀ سوم 3- ایجاد جمعیت اولیه به میزان ؛ 4- انتخاب تصادفی جواب‌ها از جمعیت موجود، بهمنظور انجام عملیات تقاطع با احتمال ؛ 5- انتخاب تصادفی جواب‌ها برای انجام عملیات جهش با احتمال در این مقاله، یک الگوریتم ژنتیک ارائه شده است. در ادامه، مراحل الگوریتم تا تولید جواب جدید شرح داده شده است.
4-۲-1- نمایش جواب
هر کروموزوم در الگوریتم ژنتیک با استفاده از یک نحوۀ نمایش در کدنویسی مشخص میشود. با فرض اینکه تعداد ۶ کار وجود داشته باشد، نمایش جواب در الگوریتم ژنتیک ارائهشده در این مقاله، مطابق شکل 1 و براساس توالی پردازش کارهاست. در این نمایش، جواب توالی پردازش کارها در مرحلۀ اول مشخص میشود. در مرحلۀ سوم با توجه با اینکه ماشین‌های موازی وجود دارند، توالی پردازش بر هر ماشین با استفاده از رمزگشایی مشخص میشود.
|
۴ |
۳ |
۵ |
۲ |
۱ |
۶ |
شکل 1- نمایش جواب
Fig. 1- Solution representation
4-۲-2- رمزگشایی
پس از تعیین توالی کارها در مراحل اول و دوم، با توجه به اینکه مرحلۀ سوم شامل ماشین‌های موازی است، توالی پردازش کارها متفاوت خواهد بود. به این منظور، بعد از اتمام پردازش یک کار در مرحلۀ دوم، در مرحلۀ سوم کار بر ماشینی پردازش میشود که آزاد باشد و یا زودتر از ماشین‌های دیگر آزاد شود.
4-2-3- جمعیت اولیه
بهمنظور اجرای الگوریتم ژنتیک، باید یک جمعیت اولیه از جواب‌ها به‌اندازۀ ، ایجاد و با اعمال تغییرات در هر جواب، جمعیت جدید تولید شود. با توجه به نمایش جواب ارائهشده در بخش قبل، جمعیت اولیه به‌صورت تصادفی تولید و پس از انجام تغییرات لازم، در هر تکرار به‌روزرسانی میشود.
۴-2-۴- عملگر تقاطع
بهمنظور ایجاد جمعیت جدید و بهبود جواب‌ها، عملگر تقاطع در الگوریتم ژنتیک، بر دو جواب اعمال میشود که به‌صورت تصادفی انتخاب شده‌اند. برای انجام تقاطع، در این بخش از عملگر تقاطع دو نقطهای استفاده شده است. در این عملگر، دو نقطه به‌صورت تصادفی بر والدین انتخاب میشود. اعداد بین این دو نقطه از والد اول به فرزند دوم و از والد دوم به فرزند اول منتقل میشود. برای پرکردن بقیۀ پوزیشن‌ها در فرزند اول، از والد اول استفاده میکنیم.
در صورتی که عدد انتخاب‌شده بین دو نقطه نباشد، جایگاه پر میشود و اگر وجود داشته باشد، عدد بعدی انتخاب میشود. یک مثال از این نوع تقاطع در شکل 2 نشان داده شده است. عملگر تقاطع در الگوریتم ارائهشده با احتمال ، بر یک جواب انجام میشود.
|
|
|
|||||
|
والد 1 |
۵ |
۱ |
۳ |
۲ |
۶ |
۴ |
|
|
|
|||||
|
والد 2 |
۳ |
۲ |
۴ |
۱ |
۵ |
۶ |
|
فرزند 1 |
|
|
|
۱ |
۵ |
|
|
|
|
|
|
|
|
|
|
فرزند 2 |
|
|
|
۲ |
۶ |
|
|
فرزند 1 |
۳ |
2 |
۶ |
۱ |
۵ |
۴ |
|
|
|
|
|
|
||
|
فرزند 2 |
۳ |
4 |
1 |
۲ |
۶ |
5 |
|
|
|
|
|
شکل 2- عملیات تقاطع
Fig. 2- Crossover operation
4-2-5- عملگر جهش
بهمنظور ایجاد تغییرات جزئی در هر جواب، الگوریتم ژنتیک از عملگر جهش استفاده می‌کند. این عملگر در الگوریتم ژنتیک، با اعمال تغییرات در هر جواب، باعث تولید جواب جدید میشود. اگر جواب جدید نسبت‌به جواب قبلی بهتر باشد، جایگزین آن میشود و در غیر این صورت، جواب قبلی بدون تغییر باقی می‌ماند. نویسندگان، حالت‌های گوناگونی را برای انجام جهش مختلف ارائه کرده‌اند. در این مقاله از جهش تعویض[xxxii] برای جهش استفاده شده و در شکل 3 نشان داده شده است.
در این نوع جهش، دو ژن به‌صورت تصادفی انتخاب و با یکدیگر جابه‌جا می‌شوند؛ برای مثال مطابق شکل 3، ژن‌های موجود در سلول‌های ۱ و ۴ به‌صورت تصادفی انتخاب و با یکدیگر جابه‌جا شده‌اند؛ درنتیجه یک جواب جدید به دست آمده است. عملگر جهش در الگوریتم ارائهشده، با احتمال بر یک جواب انجام میشود.
|
والد |
۴ |
۳ |
۵ |
۲ |
۱ |
۶ |
|
فرزند |
۲ |
۳ |
۵ |
۴ |
۱ |
۶ |
شکل 3- عملیات جهش
Fig. 3- Mutation operation
4-2-6- به‌روزرسانی جواب‌ها
پس از انجام عملیات تقاطع و جهش، مقدار تابع هدف محاسبه میشود. اگر جواب‌های به دست آمده بهتر از جواب فعلی باشد، جواب جدید جایگزین جواب فعلی میشود و در غیر این صورت، جواب بدون تغییر باقی می‌ماند.
4-2-7- شرط توقف
بهمنظور توقف اجرای الگوریتم، از محدودیت زمانی 600 ثانیه استفاده شده است.
شبه کد الگوریتم GA به کار گرفته شده، مطابق شکل ۴ است.
|
1- تعیین مقادیر اولیۀ پارامترهای مسئله ، و |
|
2- ایجاد جمعیت اولیه به‌اندازۀ |
|
3- انجام عملیات تقاطع |
|
3-1- انتخاب والد اول با احتمال ؛ |
|
3-2- انتخاب والد دوم با احتمال ؛ |
|
3-3- انجام عملیات تقاطع بر دو والد. |
|
۴- انجام عملیات جهش |
|
4-1- انتخاب والد با احتمال ؛ |
|
4-2- انجام عملیات جهش؛ |
|
۵- تولید جمعیت جدید؛ |
|
۶- بررسی شرط توقف؛ |
|
6-1- در صورتی که شرط توقف بر قرار باشد، به گام ۷ و در غیر این صورت به گام 3 بروید؛ |
|
۷- پایان. |
شکل ۴- شبه کد الگوریتم GA
Fig. 4- Pseudo code of GA algorithm
5- یافتهها
در این بخش نتایج محاسبات ارائه و مدل مدنظر، در نرم‌افزار گمز[xxxiii] اجرا شده است. همچنین محاسبات برای سایز بزرگ و با استفاده از الگوریتم ژنتیک انجام شده است. با توجه به آزمایش‌های انجام‌شده، مقادیر مناسب پارامترهای الگوریتم برابر ، و این در نظر گرفته شده است.
مقادیر مختلف پارامترها برای ایجاد نمونه‌های مختلف، در جدول ۲ نشان داده شده است.
جدول ۲- مقادیر مختلف پارامترها بهمنظور ایجاد سایزهای مختلف مسئله
Table 2- Different values of parameters in order to create different problem sizes
|
محدودۀ مقادیر پارامترها |
|
پارامتر |
|
سایز بزرگ |
سایز کوچک |
|
|
{۴۰,۳۵,۳۰,۲۵,۲۰} |
{4.5.6.7.9.11.13.15} |
n |
|
{1.2.3.4.5} |
{1.2.3.4} |
m |
|
U (1.100) |
pf |
|
|
U (1.100) |
ps |
|
|
U (1.100) |
pt |
|
در بخش ۳ و در قسمت مفروضات مدل، فرض آخر توالی پردازش کارها در مراحل اول و دوم، یکسان در نظر گرفته شده است که با توجه به مقالۀ جانسون (1954) (ارائهشده در بخش ۴)، این فرض مشکلی در رسیدن به جواب بهینه ایجاد نمیکند. به همین منظور دو متغیر را به‌سبب تعیین توالی پردازش کارها در نظر گرفتهایم. یک متغیر برای تعیین توالی کارها در مراحل اول و دوم و یک متغیر برای تعیین توالی کارها بر ماشین‌های موازی در مرحلۀ سوم مشخص شده است.
5-1- مثال عددی
بهمنظور بررسی صحت عملکرد مدل و همچنین تأثیر وجود ماشین‌های موازی در مرحلۀ سوم، یک مثال با تعداد ۶ کار، 1 و 2 ماشین در مرحلۀ سوم در نظر گرفته شده است. زمان‌های پردازش کارها مطابق جدول ۳ است.
جدول ۳- زمان‌های پردازش کارها
Table 3- Job processing times
|
کار |
مرحله 1 |
مرحله 2 |
مرحله 3 |
|
۱ |
۹۳ |
۶۳ |
۸۶ |
|
۲ |
۹۳ |
۷۰ |
۳۱ |
|
۳ |
۲۱ |
۲۹ |
۸۳ |
|
۴ |
۴۵ |
۳۹ |
۷۴ |
|
۵ |
۱۰ |
۲۴ |
۴۰ |
|
۶ |
۸۸ |
۲۷ |
۷۰ |
اگر تعداد ماشین‌ها در مرحلۀ سوم برابر 1 باشد، مقدار تابع هدف برابر 447 به دست می‌آید و در صورتی که تعداد ماشین‌ها در مرحلۀ سوم، برابر 2 باشد، مقدار تابع هدف برابر 437 است که مقدار آن به میزان ۱۰ واحد بهبود می‌یابد. در حالت اول، یعنی زمانی که تعداد ماشین‌ها در مرحلۀ سوم برابر 1 باشد، توالی پردازش کارها مطابق شکل 5 است.
شکل 5- توالی پردازش کارها در حالت تک‌ماشینی
Fig. 5- job processing sequence in single machine mode
با توجه به اینکه در مدل ارائهشده، دو متغیر برای تعیین توالی کارها در مراحل اول، دوم و سوم در نظر گرفته شده است، برای مرحلۀ سوم توالی کارها متفاوت است. توالی، مطابق شکل 6 مشخص شده است که در این حالت نیز، مقدار تابع هدف برابر 447 است؛ بنابراین ثابت در نظر گرفتن توالی پردازش کارها در سه مرحله با تابع هدف بیشینۀ زمان تکمیل کارها، تفاوتی در مقدار بهینۀ تابع هدف ندارد.
شکل 6- توالی پردازش کارها در مرحلۀ سوم حالت تک‌ماشینی
Fig. 6- Job processing sequence in the third stage of single machine mod
زمان‌های تکمیل کارها در سه مرحله برای تمامی کارها و براساس توالی به دست آمده، در جدول 4 نشان داده شده است. زمان تکمیل مرحلۀ سوم به‌عنوان زمان تکمیل هر کار در نظر گرفته میشود. بیشترین مقدار مربوط به کار 6 است که مقدار زمان تکمیل آن برابر 447 است و به‌صورت پررنگ نشان داده شده است.
جدول 4- زمان‌های تکمیل کارها برای 3 مرحله
Table 4- Job completion times for 3 stages
|
شمارۀ کار |
زمان‌های تکمیل |
||
|
مرحلۀ 1 |
مرحلۀ 2 |
مرحلۀ 3 |
|
|
۳ |
۲۱ |
۵۰ |
۱۳۳ |
|
۴ |
۶۶ |
۱۰۵ |
۲۰۷ |
|
۵ |
۷۶ |
۱۲۹ |
۲۴۷ |
|
۱ |
۱۶۹ |
۲۳۲ |
۳۳۳ |
|
۲ |
۲۶۲ |
۳۳۲ |
۳۶۴ |
|
۶ |
۳۵۰ |
۳۷۷ |
۴۴۷ |
چنانچه تعداد ماشین‌ها در مرحلۀ سوم برابر با 2 باشد، توالی به دست آمده برای کارها در مراحل اول و دوم، مطابق شکل 7 است.
شکل 7- توالی پردازش کارها در مراحل اول و دوم، با وجود 2 ماشین در مرحلۀ سوم
Fig. 7- The sequence of processing jobs in the first and second stages with the presence of 2 machines in the third stage
زمان‌های تکمیل کارها در مراحل اول و دوم در جدول 5 نشان داده شده است.
جدول 5- زمان‌های تکمیل کارها در مراحل 1 و 2
Table 5- The completion times of the jobs in stages 1 and 2
|
شمارۀ کار |
زمان‌های تکمیل |
|
|
مرحله 1 |
مرحله 2 |
|
|
۳ |
۲۱ |
۵۰ |
|
۴ |
۶۶ |
۱۰۵ |
|
۱ |
۱۵۹ |
۲۲۲ |
|
۲ |
۲۵۲ |
۳۲۲ |
|
۶ |
۳۴۰ |
۳۶۷ |
|
۵ |
۳۵۰ |
۳۹۱ |
توالی پردازش کارها بر هریک از ماشین‌های مرحلۀ سوم در شکل 8 مشخص شده است.
|
|
ماشین 1 |
|
ماشین 2 |
شکل 8- توالی پردازش کارها بر هریک از ماشین‌ها در مرحلۀ سوم
Fig. 8- The sequence of processing jobs on each of the machines in the third stage
زمان‌های تکمیل کارها در مرحلۀ ۳ در جدول ۶ نشان داده شده است. براساس این جدول، بیشینۀ زمان تکمیل کارها مربوط به کار 6، با مقدار تابع هدف 4۳7 است.
جدول ۶- زمان تکمیل کارها در مرحلۀ سوم
Table 6- The job completion time in the third stage
|
شمارۀ ماشین |
شمارۀ کار |
زمان تکمیل |
|
ماشین 1 |
۴ |
۱۷۹ |
|
۲ |
۳۵۳ |
|
|
۶ |
۴۳۷ |
|
|
ماشین 2 |
۱ |
۳۰۸ |
|
۳ |
۳۹۱ |
|
|
۵ |
۴۳۱ |
با توجه به مثال ارائهشده، علاوه بر صحت عملکرد مدل، تأثیر وجود ماشین‌های بیشتر در مرحلۀ سوم نیز مشخص شد. با افزایش تعداد ماشین‌ها در مرحلۀ سوم، مقدار تابع هدف بدتر نمیشود.
5-2- مقایسۀ نتایج سایز کوچک
بهمنظور بررسی و مقایسۀ نتایج گمز و الگوریتم ژنتیک، برای تعداد ۲۶ مسئله در سایزهای مختلف، مدل در نرم‌افزار گمز و همچنین الگوریتم ژنتیک اجرا شد که نتایج آن در جدول ۷ نشان داده شده است. حل‌ِ در نرم‌افزار گمز با محدودیت زمانی ۳۶۰۰ ثانیه و برای الگوریتم ژنتیک، n ثانیه در نظر گرفته شده است. هر نمونه از الگوریتم ژنتیک نیز، 5 بار اجرا شده است. برای مقایسۀ نتایج حل دقیق و الگوریتم ژنتیک، از شاخص میزان انحراف از بهترین[xxxiv] جواب، براساس رابطۀ 18 استفاده شده است.
|
(18) |
|
در رابطۀ (18)، میزان انحراف از بهترین جواب، جواب الگوریتم و بهترین جواب به دست آمده از 5 بار اجرا و جواب گمز است. در جدول ۷، ستون CD[xxxv] میزان انحراف جواب گمز از بهترین جواب مدل و الگوریتم ژنتیک و ستون «تابع هدف»، مقدار تابع هدف به دست آمده توسط گمز را نشان می‌دهد. ستون «زمان» حل گمز، «Min» مقدار کمینۀ انحراف از بهترین جواب، «Avr» میانگین انحراف از بهترین جواب، «Max» مقدار بیشینۀ انحراف از بهترین جواب و ستون «تابع هدف»، مقدار تابع هدف و ستون «زمان» نیز، زمان اجرای الگوریتم ژنتیک را نشان می‌دهد.
جدول ۷- مقایسۀ نتایج الگوریتم ژنتیک و حل دقیق برای سایز بزرگ مسئله
Table 7- Comparison of genetic algorithm results and exact solution for large size problem
|
نمونه |
|
|
گمز |
ژنتیک |
||||||
|
CD |
تابع هدف |
زمان (ثانیه) |
Min |
Avr |
Max |
تابع هدف |
زمان (ثانیه) |
|||
|
۱ |
4 |
2 |
0.000 |
353 |
1.8 |
0.000 |
0.000 |
0.000 |
353 |
4 |
|
۲ |
5 |
2 |
0.000 |
363 |
2.9 |
0.000 |
0.000 |
0.000 |
363 |
5 |
|
۳ |
5 |
3 |
0.000 |
363 |
4.3 |
0.000 |
0.000 |
0.000 |
363 |
5 |
|
۴ |
6 |
1 |
0.000 |
447 |
3.3 |
0.000 |
0.000 |
0.000 |
447 |
6 |
|
۵ |
6 |
2 |
0.000 |
437 |
16.9 |
0.000 |
0.000 |
0.000 |
437 |
6 |
|
۶ |
6 |
3 |
0.000 |
437 |
28 |
0.000 |
0.000 |
0.000 |
437 |
6 |
|
۷ |
7 |
1 |
0.000 |
450 |
4 |
0.000 |
0.000 |
0.000 |
450 |
7 |
|
۸ |
7 |
2 |
0.000 |
440 |
63 |
0.000 |
0.000 |
0.000 |
440 |
7 |
|
۹ |
7 |
3 |
0.000 |
440 |
760 |
0.000 |
0.000 |
0.000 |
440 |
7 |
|
۱۰ |
7 |
4 |
0.000 |
440 |
1393 |
0.000 |
0.000 |
0.000 |
440 |
7 |
|
۱۱ |
9 |
1 |
0.000 |
5۳9 |
657 |
0.000 |
0.074 |
0.117 |
5۳9 |
9 |
|
۱۲ |
9 |
2 |
0.000 |
525 |
728 |
0.000 |
0.000 |
0.000 |
525 |
9 |
|
۱۳ |
9 |
3 |
0.000 |
525 |
3600 |
0.000 |
0.000 |
0.000 |
525 |
9 |
|
۱۴ |
9 |
4 |
0.000 |
525 |
3600 |
0.000 |
0.000 |
0.000 |
525 |
9 |
|
۱۵ |
11 |
1 |
0.316 (OM) |
578 |
1211 |
0.000 |
0.047 |
0.099 |
439 |
11 |
|
۱۶ |
11 |
2 |
0.000 |
562 |
3600 |
0.014 |
0.045 |
0.095 |
570 |
11 |
|
۱۷ |
11 |
3 |
0.000 |
562 |
3600 |
0.000 |
0.018 |
0.089 |
562 |
11 |
|
۱۸ |
11 |
4 |
0.000 |
562 |
3600 |
0.002 |
0.027 |
0.046 |
563 |
11 |
|
۱۹ |
13 |
1 |
0.304 (OM) |
745 |
559 |
0.000 |
0.027 |
0.059 |
571 |
13 |
|
۲۰ |
13 |
2 |
0.000 |
727 |
3600 |
0.006 |
0.020 |
0.032 |
731 |
13 |
|
۲۱ |
13 |
3 |
0.008 |
727 |
3600 |
0.000 |
0.032 |
0.060 |
727 |
13 |
|
۲۲ |
13 |
4 |
0.005 |
727 |
3600 |
0.000 |
0.030 |
0.076 |
727 |
13 |
|
۲۳ |
15 |
1 |
0.417 (OM) |
792 |
782 |
0.000 |
0.061 |
0.089 |
559 |
15 |
|
۲۴ |
15 |
2 |
0.150 |
771 |
3600 |
0.000 |
0.032 |
0.125 |
771 |
15 |
|
۲۵ |
15 |
3 |
0.265 (OM) |
771 |
1936 |
0.000 |
0.059 |
0.125 |
609 |
15 |
|
۲۶ |
15 |
4 |
0.065 |
771 |
3600 |
0.000 |
0.058 |
0.109 |
771 |
15 |
|
میانگین |
0.059 |
- |
1698.1 |
0.001 |
0.020 |
0.043 |
- |
9.7 |
||
دربارۀ نتایج گمز، همان‌طور که در جدول ۷ مشاهده میشود، با افزایش سایز، مسئلۀ دسترسی به جواب بهینه کمتر شده است، محدودیت زمانی (3۶00 ثانیه) باعث توقف اجرا شده و بهترین جواب به دست آمده تا این زمان، ثبت شده است. این موضوع نشان‌دهندۀ پیچیدگی بالای مسئلۀ ارائهشده در این مقاله است و NP-سخت مسئله، اثبات میشود. جواب‌های بهینه در جدول ۷، به‌صورت پررنگ نشان داده شده است و در صورتی که گمز، خطای حافظه[xxxvi] داشته باشد، با نشان OM در داخل پرانتز مشخص شده است. از تعداد 2۶ سایز، مدل در تعداد ۴ سایز با خطای حافظه روبه‌رو شده است (که با علامت OM نشان داده شده‌اند). تعداد 12 نمونه گمز، به جواب بهینه رسیده و درنهایت در تعداد 10 نمونه، محدودیت زمانی باعث توقف اجرا شده است.
بهمنظور بررسی عملکرد گمز در حل دقیق مسئله، نمودار زمان حل مسئله برای 14 سایز اول مطابق شکل 9 رسم شده است. با توجه به اینکه برای سایزهای بزرگ‌تر، گمز در 3600 ثانیه متوقف شده و یا خطای حافظه رخ داده است، نمودار برای 14 سایز اول رسم شده است.
شکل 9- نمودار مقایسۀ زمان حل سیپلکس در سایزهای مختلف مسئله
Fig. 9- Comparison of time to solve cplex in different problem sizes
همان‌طور که از شکل 9 مشخص است، با افزایش سایز، مسئلۀ زمان حل به‌صورت نمایی افزایش می‌یابد؛ بنابراین حل مسئله برای ابعاد بزرگ در زمان معقول امکان‌پذیر نیست و مسئلۀ NP-سخت است. پس حل مسئله در ابعاد بزرگ، با استفاده از الگوریتم ژنتیک انجام شده است.
با توجه به نتایج به دست آمده در 12 نمونۀ اول، حل دقیق به جواب بهینه رسیده و در 11 نمونه، الگوریتم ژنتیک در هر 5 بار اجرا، به جواب برابر با گمز رسیده است که اعتبار نتایج را نشان می‌دهد. در مقایسه با نتایج الگوریتم ژنتیک، میانگین زمان حل برای 26 نمونه و برای حل دقیق، برابر 1698.1 و برای الگوریتم ژنتیک برابر 9.7 است؛ این نشان‌دهندۀ کارایی الگوریتم ژنتیک است. در جدول ۷، ستون CD که به میانگین میزان انحراف نتایج مدل از بهترین جواب مربوط میشود، برابر 0.059 است؛ در صورتی که برای الگوریتم ژنتیک در ستون Avr، برابر 0.02 است، برای الگوریتم ژنتیک کمتر و نشان‌دهندۀ اثربخشی الگوریتم است.
5-3- مقایسۀ نتایج سایز بزرگ
پس از مشخص‌شدن عملکرد الگوریتم در سایز کوچک، مسئله در 30 نمونه و در سایز بزرگ، با استفاده از الگوریتم ژنتیک حل شده است. هر نمونه 5 بار اجرا شده و میزان انحراف از بهترین جواب، با استفاده از رابطۀ (18) محاسبه شده است.
جدول ۸- جدول ارزیابی نتایج الگوریتم ژنتیک برای سایز بزرگ مسئله
Table 8- Evaluation table of genetic algorithm results for large problem size
|
نمونه |
n |
m |
میزان انحراف |
||
|
Min |
Avr |
Max |
|||
|
۱ |
۲۰ |
۱ |
0.000 |
0.015 |
0.0۳4 |
|
۲ |
۲۰ |
۲ |
0.000 |
0.01۳ |
0.028 |
|
۳ |
۲۰ |
۳ |
0.000 |
0.014 |
0.027 |
|
۴ |
۲۰ |
۴ |
0.000 |
0.024 |
0.0۳5 |
|
۵ |
۲۰ |
۵ |
0.000 |
0.050 |
0.128 |
|
۶ |
۲۵ |
۱ |
0.000 |
0.011 |
0.044 |
|
۷ |
۲۵ |
۲ |
0.000 |
0.027 |
0.044 |
|
۸ |
۲۵ |
۳ |
0.000 |
0.025 |
0.0۶7 |
|
۹ |
۲۵ |
۴ |
0.000 |
0.01۳ |
0.0۳1 |
|
۱۰ |
۲۵ |
۵ |
0.000 |
0.0۳۳ |
0.086 |
|
۱۱ |
۳۰ |
۱ |
0.000 |
0.016 |
0.024 |
|
۱۲ |
۳۰ |
۲ |
0.000 |
0.025 |
0.057 |
|
۱۳ |
۳۰ |
۳ |
0.000 |
0.01۳ |
0.026 |
|
۱۴ |
۳۰ |
۴ |
0.000 |
0.012 |
0.0۳7 |
|
۱۵ |
۳۰ |
۵ |
0.000 |
0.0۳8 |
0.078 |
|
۱۶ |
۳۵ |
۱ |
0.000 |
0.024 |
0.050 |
|
۱۷ |
۳۵ |
۲ |
0.000 |
0.017 |
0.0۳4 |
|
۱۸ |
۳۵ |
۳ |
0.000 |
0.027 |
0.055 |
|
۱۹ |
۳۵ |
۴ |
0.000 |
0.008 |
0.021 |
|
۲۰ |
۳۵ |
۵ |
0.000 |
0.022 |
0.048 |
|
۲۱ |
۴۰ |
۱ |
0.000 |
0.014 |
0.028 |
|
۲۲ |
۴۰ |
۲ |
0.000 |
0.012 |
0.0۳4 |
|
۲۳ |
۴۰ |
۳ |
0.000 |
0.010 |
0.024 |
|
۲۴ |
۴۰ |
۴ |
0.000 |
0.021 |
0.058 |
|
۲۵ |
۴۰ |
۵ |
0.000 |
0.007 |
0.01۳ |
|
۲۶ |
۴۵ |
۱ |
0.000 |
0.017 |
0.027 |
|
۲۷ |
۴۵ |
۲ |
0.000 |
0.006 |
0.015 |
|
۲۸ |
۴۵ |
۳ |
0.000 |
0.016 |
0.026 |
|
۲۹ |
۴۵ |
۴ |
0.000 |
0.025 |
0.047 |
|
۳۰ |
۴۵ |
۵ |
0.000 |
0.0۳8 |
0.055 |
|
میانگین |
0.000 |
0.020 |
0.043 |
||
در جدول ۸ مقادیر مینیمم، میانگین و ماکزیمم انحراف از بهترین جواب برای هر نمونه نشان داده شده است. مقدار میانگین انحراف، 30 نمونه برابر 0.02 و با توجه به پایین‌بودن آن، نشان‌دهندۀ همگرایی الگوریتم ژنتیک است.
همان‌طور که قبلاً هم اشاره شد، مسئلۀ بررسی‌شده در این مقاله، موضوع جریان کارگاهی سه مرحله‌ای با ماشین‌های موازی در مرحلۀ سوم، برای اورهال تجهیزات است. دیدگاه مدیریت بهمنظور ایجاد یک فضا برای شروع یک فعالیت، کاهش هزینه، کسب درآمد و دستیابی به سود است. برای بررسی بینش مدیریتی دربارۀ مسئلۀ اورهال تجهیزات، به تعداد ماشین‌های مرحلۀ سوم اشاره میشود. با توجه به حجم تجهیزات برای انجام اورهال بر آنها، تعداد ماشین‌های مرحلۀ سوم تعیین میشود؛ به‌طوری که می‌توان ماشین‌های اضافه را بهمنظور کاهش هزینه حذف کرد و یا در حالت دیگر، اگر تجهیزات مربوط به مشتریان متفاوت باشند، برای کاهش هزینه‌های انبارش و یا افزایش رضایت مشتریان، اهداف متفاوت در نظر گرفته شود. در اینجا تابع هدف بیشینۀ زمان تکمیل کارها نیز به همین منظور مدنظر قرار گرفته شده است. چنانچه تجهیزات باید در یک زمان خاص در دسترس باشند، می‌توان اهدافی نظیر مجموع زمان تکمیل کارها را در نظر گرفت.
۶- بحث
به منظور بررسی تأثیر مقادیر مختلف پارامترها در مقدار تابع هدف، مقدار تابع هدف به‌ازای مقادیر مختلف یک پارامتر، با ثابت در نظر گرفتن مقادیر پارامترهای دیگر محاسبه شده است. برای سایزهای مختلف، به‌ویژه سایزهای بزرگ، با افزایش تعداد ماشین‌های مرحلۀ سوم، مقدار تابع هدف بهبود می‌یابد. در این حالت برای کاهش هزینه‌های جاری و هزینه‌های سرمایهگذاری اولیه، مناسبترین تعداد ماشین، با توجه به اهداف تعیین‌شده توسط مدیریت مشخص میشود. با استفاده از تحلیل نتایج، مناسبترین تعداد ماشین انتخاب میشود؛ برای مثال، برای تعداد 9 کار مطابق شکل 10، اگر تعداد ماشین‌های مرحلۀ سوم برابر با 1 باشد، مقدار تابع هدف 539 است و برای 2 ماشین، مقدار تابع هدف بهبود می‌یابد و برابر 525 میشود. چنانچه تعداد ماشین‌ها برابر با 3 یا 4 باشد، مقدار تابع هدف ثابت می‌ماند و بهبودی ایجاد نمیشود؛ بنابراین بهمنظور کاهش هزینه می‌توان تعداد ماشین‌ها را برابر با 2 در نظر گرفت.
شکل 10- نمودار تأثیر مقادیر مختلف تابع هدف به‌ازای تعداد 9 کار
Fig. 10- The effect of different values of the objective function for the number of 9 jobs
همچنین برای تعداد 17 کار، مقادیر مختلف تابع هدف در مدت‌زمان اجرای 3600 ثانیه در شکل 11 نشان داده شده است. همان‌طور که در شکل مشخص است، با افزایش تعداد ماشین‌ها در مرحلۀ سوم، مقدار تابع هدف تا تعداد 3 ماشین بهبود می‌یابد، ولی در مقادیر 3 و 4 ثابت می‌ماند؛ به این معنی که می‌توان برای مدیریت هزینه، تعداد 3 ماشین را برای مرحله سوم در نظر گرفت.
شکل 11- نمودار تأثیر مقادیر مختلف تابع هدف به ازای تعداد 17 کار
Fig. 11- The effect of different values of the objective function for the number of 17 jobs
برای بررسی تأثیر مقادیر مختلف کارها بر مقدار تابع هدف، برای تعداد 2 ماشین در مرحلۀ سوم، مقدار تابع هدف برای تعداد 5، ۶، 7 و 9 کار، به ترتیب برابر ۳۶۳، ۴۳۷، 440 و 525 شده است که نمودار آن مطابق شکل 12 است.
شکل 12- نمودار تأثیر مقادیر مختلف تابع هدف به‌ازای تعداد مقادیر مختلف کارها و 2 ماشین در مرحلۀ سوم
Fig. 12. The impact of different values of the objective function for the number of different values of joba and 2 machines in the third stage
7- نتیجهگیری
در این مقاله یک مسئلۀ زمان‌بندی و تخصیص جریان کارگاهی برای اورهال تجهیزات در نظر گرفته شده است. در قسمت زمان‌بندی، توالی پردازش کارها در ماشین‌ها مشخص و در قسمت تخصیص، عملیات تخصیص کارها به ماشین‌ها انجام میشود. هدف انجام عملیات زمان‌بندی و تخصیص کارها به صورتی است که بیشینۀ زمان تکمیل کارها کمینه شود. یک مدل ریاضی برای این مسئله ارائه شد که براساس پوزیشن کارها و به این صورت است که هر کار به یک پوزیشن تخصیص می‌یابد و براساس پوزیشن مربوطه، پردازش میشود. بهمنظور ارزیابی صحت عملکرد مدل ارائهشده، مثال‌های عددی ارائه شد. مدل مربوطه در نرم‌افزار گمز اجرا و نتایج آن بررسی، تجزیه و تحلیل شد. با توجه به NP-سخت‌بودن مسئله، حل آن برای مسائل با سایز بزرگ‌تر در زمان معقول (کمتر از ۳۶۰۰ ثانیه) امکان‌پذیر نیست؛ بنابراین الگوریتم ژنتیک، حل مسئله در ابعاد بزرگ را انجام داده است. در راستای به‌کارگیری بینش مدیریتی در مسئلۀ مورد بررسی در این مقاله و با توجه به اینکه هزینه‌های سرمایهگذاری و همچنین توان پاسخگویی به درخواست‌های متقاضیان با تعداد ماشین‌های مرحلۀ سوم مرتبط است، مقدار تابع هدف براساس تعداد ماشین‌های مرحلۀ سوم، تجزیه و تحلیل شده است. تأثیر مقادیر مختلف تعداد ماشین‌ها برای دو نمونه بررسی و تعداد بهینۀ ماشین‌ها بهمنظور دستیابی به بهترین مقدار تابع هدف مشخص شد. با توجه به مسئلۀ ارائهشده، پیشنهادهایی برای تکمیل موضوع و یا در نظر گرفتن شرایط متفاوت به شرح زیر ارائه میشود: در نظر گرفتن ماشین‌های موازی در هریک از مراحل، به‌کارگیری توابع هدف دیگر با توجه به شرایط مختلف و استفاده از الگوریتم‌های تقریبی دیگر بهمنظور حل مسئله در ابعاد بزرگ‌تر.
[i] Lenahan
[ii] Chang & Abdullah
[iii] Major Maintenance
[iv] Rebuild
[v] Swap Out
[vi] Flow shop
[vii] Bahrami et al.
[viii] Ramezani et al.
[ix] Khodabakhshian et al.
[x] Reményi & Staudacher
[xi] MRO (maintenance, repair and overhaul)
[xii] scheduling
[xiii] Job shop
[xiv] Huang et al.
[xv] Maytoet al.
[xvi] Genetic Algorithm (GA)
[xvii] Hassani
[xviii] Liu et al.
[xix] Bozorgnejad et al.
[xx] Hessam et al.
[xxi] Nondominated Sorting Genetic Algorithm II (NSGA-II)
[xxii] Tran et al.
[xxiii] Ant Colony Optimization (ACO)
[xxiv] Li et al.
[xxv] Rahman et al.
[xxvi] Guo (2022)
[xxvii] Johnson
[xxviii] Chen
[xxix] Non-deterministic Polynomial-time hard (NP-hard)
[xxx] Holland
[xxxi] population based
[xxxii] Swap mutation
[xxxiii] GAMS
[xxxiv] Deviation
[xxxv] Cplex Deviation
[xxxvi] Out of Memmory
)