رویکرد شبیه‌سازی در حل مسأله زمان‏بندی ماشین‏ های موازی پردازشگر دسته ‏ای با زمان‏ های احتمالی

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، ایران

2 استادیار گروه مهندسی صنایع، دانشگاه شاهد، تهران، ایران، ایران

3 کارشناس ارشد مهندسی صنایع، اداره کل بنادر و دریانوردی استان هرمزگان، بندرعباس، ایران

چکیده

در این مقاله، مسأله‏ زمان‏بندی ماشین‏های موازی پردازشگر دسته‏ای با هدف حداقل کردن حداکثر زمان تکمیل کارها بررسی می‌شود. نوآوری این پژوهش، به کارگیری زمان های پردازش و در دسترس بودن کارها به صورت احتمالی است. در تحقیقات پیشین اثبات شده است که مسأله‏ مورد بررسی دارای پیچیدگی سخت است. بنابراین، از روش‏های ابتکاری برای حل مسأله استفاده می‏شود. مسأله مورد مطالعه، دو مرحله تصمیم‌گیری دارد. در مرحله اول ابتدا کارها به دسته‌هایی طبقه‌بندی می‌شوند و در مرحله بعد، دسته‌های به دست آمده به ماشین‌های موازی تخصیص می‌یابند. در این مقاله، از دو روش ابتکاری برای ایجاد دسته‏ها و از سه روش ابتکاری برای ترتیب دهی توالی دسته‏ها استفاده خواهد شد. به علت احتمالی بودن زمان‏های پردازش و در دسترس بودن کارها، با استفاده از رویکرد شبیه‏سازی، 10000 نمونه مسأله به صورت تصادفی تولید می‌شود. 6 حالت ترکیبی روش‏های ابتکاری با حل نمونه مسائل به دست آمده از شبیه‏سازی مقایسه می‌شوند. نتایج به دست آمده نشان می‏دهد که ترکیب روش‌های ابتکاری MBF در فاز اول و روش ERT-LPT در فاز دوم از کارایی بهتری در رسیدن به جواب‌های مناسب برخوردار است.

کلیدواژه‌ها


عنوان مقاله [English]

Development of Simulation on parallel Batch Scheduling Problem With Stochastic Times

نویسندگان [English]

  • Iman Rastgar 1
  • Rashed Sahraeian 2
  • Farshid Samaei 3
1 PhD Student Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran
2 Assistant Professor, Industrial Engineering, Shahed Universit, Tehran, Iran
3 M.Sc. of Industrial Engineering, PMO, Bandar Abbas, Iran
چکیده [English]

In this paper, the problem of batch scheduling in parallel machines environment with the objective of minimizing make span (Cmax) is addressed. The main contribution of this research is the stochastic nature of the processing times of jobs and release times for better depiction of the real world. It has been proved that the problem is NP-hard. Therefore, we apply heuristic approaches to solve this problem. The provided problem includes two stages of decision making. In the first stage, the jobs are classified into batches and in the next stage; these batches should be assigned to parallel machines. Two and three heuristic methods are used for producing batches and sequencing batches, respectively. 10,000 test problems are randomly generated due to stochastic nature of processing times and release dates. Using the results of simulating test problems, six combinations of heuristic methods are compared. The results show that applying MBF heuristic method in the first stage and ERT-LPT method in the second stage provide better and efficient solutions.

کلیدواژه‌ها [English]

  • Scheduling
  • Parallel machine
  • Batch processing
  • Heuristics
  • Simulation

1- مقدمه

زمان‏بندی شامل برنامه­ریزی و اولویت­دهی فعالیت‌هایی است که لازم است به ترتیب عملیات انجام شوند. به بیان دیگر، زمان‏بندی ابزاری است که استفاده از منابع در دسترس را بهینه می‌کند. در مسائل زمان‏بندی، با تخصیص مناسب مجموعه‌ای از کارها به مجموعه­ای از ماشین­ها و تعیین اولویت‏دهی و زمان‏های فعالیت­ها، بهره­وری از منابع مانند اپراتورها و ماشین­ها حداکثر می‌گردد
(Pinedo, 2012). در بیشتر سیستم­های زمان‏بندی سعی می‏شود، کل هزینه‏ها کاهش یابد. هزینه­های تولید از مهمترین هزینه­هایی است که با کاهش زمان کل تولید یعنی بیشترین زمان تکمیل کارها در یک سیستم زمان‏بندی به دست می­آید.

در مسائل زمان‏بندی، نسل جدیدی از پردازش کارها به صورت پردازش همزمان دسته­ای در محیط‏های صنعتی ایجاد شده است که موجب کاهش زمان‏های آماده­سازی، هزینه­های حمل و نقل و زمان عملیات پردازش کارها می‏شود. در این نوع پردازش کارها با توجه به محدودیتی که برای اندازه هر دسته وجود دارد، تعداد محدودی کار تا جایی که از ظرفیت دسته تجاوز نکند در دسته قرار می‏گیرند و روی ماشین پردازشگر دسته­ای پردازش می­شوند.

مسأله مورد پژوهش در این مقاله، زمان‏بندی و توالی کارها در یک محیط تک ایستگاهی با m ماشین موازی مشابه است. کارها در قالب دسته­هایی تقسیم‏بندی می­شوند و هر دسته به طور مستقیم روی یکی از ماشین­ها پردازش می‏شود و از ایستگاه خارج می‏شود. محدودیت­های اصلی این مسأله، زمان در دسترس بودن کارها و محدود بودن ظرفیت تعداد کارها در هر دسته است.

از مزایای چیدمان موازی ماشین­ها در یک ایستگاه کاری این است که احتمال توقف در برنامه­ریزی تولید کاهش می‏یابد. به بیان دیگر، در شرایطی که از یک ماشین در ایستگاه کاری استفاده شود، خرابی این ماشین موجب توقف خط تولید خواهد شد. در حالی که اگر در این ایستگاه از چند ماشین به طور موازی استفاده شود، برنامه تولید متوقف نخواهد شد و احتمال رسیدن به ظرفیت تولید افزایش خواهد یافت (Uzsoy, 1995). با توجه به اهمیت موضوع، ایستگاه‏های کاری با ماشین‏های موازی در صنایع مدرن رایج شده است و مورد توجه بیشتر محققان قرار گرفته است (Mönch, Fowler, Dauzère-Pérès, Mason, & Rose, 2011).

یکی از موارد مهمی که صنعتگران در بیشتر ایستگاه‏های کاری با آن مواجه هستند، زمان غیر قطعی کارها است که مستقیم یا غیر مستقیم بر روی زمان تکمیل محصول تأثیر دارد. در اکثر مطالعات انجام شده بر روی مسائل زمان‏بندی، زمآنها به طور قطعی و معین (در ابتدای دوره زمان‏بندی) فرض شده است، در حالی که در دنیای واقعی این زمان‏ها ممکن است به طور تصادفی تغییر یابند. در نتیجه، در نظر گرفتن زمآنها به صورت احتمالی، مطالعات پیشین را به واقعیت نزدیکتر خواهد کرد. در این مقاله، زمان ها پردازش و زمان‏های در دسترس به صورت متغیرهای تصادفی با تابع توزیع یکنواخت محاسبه می­شوند. ساختار این مقاله به صورت زیر است. در بخش 2 پژوهش­های حوزه مسائل زمان‏بندی در محیط ماشین­های موازی با فرض پردازش دسته­ای مرور می­شود. در بخش 3 مسأله تعریف و مفروضات مسأله مورد مطالعه بررسی می‌شوند. در بخش 4 روش­های ابتکاری برای حل مسأله شرح داده می­شوند. رویکرد خاص شبیه­سازی توسعه داده شده در بخش 5 ارائه می‏شود. مقایسه کارایی عملکرد روش­های ابتکاری با استفاده از رویکرد شبیه سازی در بخش 6 شرح داده خواهد شد و نتیجه گیری و پیشنهادهای تحقیقات آتی نیز در بخش 7 ارائه می­شود.

 

2- مرور ادبیات

محیط ماشین­های موازی از محیط­های مهم در مسائل زمانبندی است که در پژوهش­های زمانبندی ماشین‏های پردازشگر تکی بسیار مورد توجه بوده است و از اهمیت زیادی برخوردار است. اما در زمینه­ی محیط ماشین­های موازی با ماشین­های پردازشگر دسته­ای، به ندرت پژوهش صورت گرفته است. در این محیط ماشین­های پردازش دسته­ای به صورت موازی چیدمان می­گردند و کارها در قالب دسته­ها به صورت همزمان پردازش می­شوند.

(Chandru, Lee, & Uzsoy, 1993) یک روش ابتکاری نسبت حریصانه (GR[1]) و یک روش ابتکاری کوتاه‏ترین زمان پردازش دسته پر (FBSPT[2]) برای مسأله ماشین­های پردازشگر دسته­ای تک ماشین و موازی یکسان ارائه دادند به طوری که زمان تکمیل کل را حداقل کند. آنها پیشنهاد دادند که الگوریتم GR از الگوریتم FBSPT در شاخص‏های کیفیت جواب و توزیع­های زمان پردازش در مسائل مختلف بهتر عمل می­کند و یک حد عملکردی بدترین حالت را برای یکی از آنها به کار بردند.

(Chang, Damodaran*, & Melouk, 2004) یک الگوریتم فراابتکاری شبیه سازی تبرید (SA) را برای مسأله زمان‏بندی ماشین­های موازی پردازشگر دسته‌ای ارائه نمودند و نتایج آن را با نتایج حاصل از حل کننده CPLEXمقایسه نمودند که نتیجه این شد که الگوریتم فراابتکاری کارآیی بهتری در شاخص­های زمان‏های محاسبات و کیفیت حل برای مسائل با ابعاد بزرگ در تعداد ماشین­های موازی و کارهای تشکیل دهنده خواهد داشت. (Koh*, Koo, Ha, & Lee, 2004) مسأله زمان‏بندی ماشین‏های پردازشگر دسته­ای موازی را بررسی کردند که (1) اندازه کارها از هم متفاوت بودند، (2) هر کار متعلق به یک خانواده بود و (3) خانواده همه کارها دارای زمان پردازش یکسانی بودند. در این پژوهش، زمان پردازش برای یک دسته از کارها، تنها به خانواده کارها در دسته بستگی دارد و به تعداد کارهای دسته یا اندازه ظرفیت دسته، وابسته نیست. سه معیار عملکردی در این مقاله در نظر گرفته شده است: مجموع زمان تکمیل، زمان تکمیل وزن‏دهی شده کل، زمان تکمیل آخرین کار روی آخرین ماشین. به علت پیچیدگی سخت مسأله مورد بررسی، روش­های ابتکاری برای هر نوع از معیارهای عملکردی پیشنهاد و یک الگوریتم فراابتکاری ژنتیک بر پایه تکنیک به کار رفته در مقاله (C.-S. Wang & Uzsoy, 2002) توسعه داده شده است. عملکرد روش­های ابتکاری پیشنهادی و الگوریتم ژنتیک نیز با هم مقایسه گردید.

(Xu & Bean, 2007) یک مدل برنامه­ریزی عدد صحیح برای حداقل کردن زمان تکمیل کل و یک الگوریتم ژنتیکی که شیوه نمایش جواب آن بر پایه مقادیر تصادفی است برای ماشین­های پردازشگر موازی غیریکسان ارائه کردند. (Malve & Uzsoy, 2007) مسأله حداقل کردن حداکثر تاخیر کارها روی ماشین­های پردازشگر دسته­ای موازی که کارها به صورت پویا به ایستگاه کار می‏رسند را بررسی کردند. آنها بر مبنای روش ابتکاری زودترین زمان تحویل، یک روش ابتکاری پیشنهاد کرده و بر مبنای این روش ابتکاری، دو روش ابتکاری در محیط ماشین­های موازی توسعه دادند. سپس بر مبنای این دو روش ابتکاری دو الگوریتم ژنتیک پیشنهاد کردند که هر دو عملکرد بسیار خوبی را نشان دادند، با این تفاوت که الگوریتم دوم 50% زمان بیشتر صرف می‏کند.

(Shao et al., 2008) یک رویکرد حل بر پایه شبکه­های عصبی با فرض زمان‏های در دسترس صفر در نظر گرفتند. آنها نتایج خود را با روش‏های ابتکاری BFLPT[3] و FFLPT[4] مقایسه نمودند. (Chung, Tai, & Pearn, 2009) یک مدل ریاضیاتی و 3 روش ابتکاری برای حداقل کردن زمان تکمیل کل تحت زمان در دسترس غیر صفر ارائه دادند. در کار بعدی همین گروه رویکردی ترکیبی ارائه شد که در آن دسته­ها ابتدا تشکیل و سپس زمان‏بندی انجام می‏شد. برای تشکیل دسته­ها از روش ابتکاری تأخیری که لی و همکارانش در سال 1999 برای مسأله تک ماشین ارائه شده بود استفاده کردند و برای زمان‏بندی دسته­ها روی ماشین­های موازی دو زمان‏بندی غیر تأخیری به وسیله دو قاعده زمان‏بندی ساده ارائه نمودند.

(Kashan, Karimi, & Jenabi, 2008) با هدف حداقل کردن حداکثر زمان تکمیل کارها روی ماشین­های پردازشگر دسته­ای موازی، پزوهش دیگری را بررسی کردند. آنها ابتدا یک حد پایین برای حداکثر زمان تکمیل بهینه ارائه کردند. سپس روش ابتکاری  پیشنهاد کرده که دسته‌ها طبق این قاعده از کارهای موجود تشکیل می‌شوند. ایده اصلی در این روش بر این اساس است ­که کارها با زمان پردازش بالاتر در دسته­های یکسان اجرا گردند. که یک طرح شدنی دسته­ها را از طریق حداقل کردن به طور همزمان ظرفیت باقیمانده دسته می­سازد:

1) همه کارها به L دسته به صورت تصادفی تخصیص داده می‌شود (بدون در نظر گرفتن محدودیت ظرفیت).

(1)

 

2) اگر طرح تقسیم دسته­ها شدنی باشد روش متوقف می‌شود در غیر این صورت به گام سوم می‌رود.

3) یک دسته با ظرفیت تجاوز شده انتخاب و بزرگترین زمان پردازش دسته کار با بزرگترین زمان پردازش در آن انتخاب می‌شود.

4) اگر کار انتخاب شده در هر دسته موجود (این دسته­ها را به عنوان مجموعه K فرض شود) نبود یک دسته جدید ایجاد می­شود و به آن کار انتخاب شده را تخصیص می­دهیم سپس ظرفیت دسته­های ایجاد شده بررسی می‌شود تا اگر مجموع حداقل دو دسته کمتر مساوی S شود آنها با هم ترکیب شوند تا زمانی که یک طرح شدنی دسته­سازی به وجود بیاید.

5) اگر در میان دسته­های در K تعدادی دسته وجود دارد که زمان پردازش دسته­، طولانی­تر از زمان پردازش کار انتخاب شده باشد، کار انتخاب شده در یکی از دسته­های r با کمترین ظرفیت باقیمانده قرار می‌گیرد، در غیر این صورت کار انتخابی دریک batch شدنی در k، با بیشترین زمان پردازش قرار می‌گیرد (r زیرمجموعه  kاست).

بر مبنای این روش ابتکاری، یک الگوریتم ژنتیک ترکیبی توسعه دادند. الگوریتم پیشنهادی با یک الگوریتم شبیه­سازی تبرید موجود در پژوهش­های پیشین مقایسه شد که عملکرد بهتری در مقایسه با آن داشت.

(Damodaran, Hirani, & Velez-Gallego, 2009) یک الگوریتم ژنتیک برای حداقل کردن زمان تکمیل ماشین­های پردازش دسته­ای موازی ارائه کردند. آنها نتایج خود را با رویکرد فراابتکاری شبیه­سازی تبرید پیشنهاد شده در مقاله (Chang et al., 2004) و الگوریتم ژنتیک بر پایه کدگذاری عدد تصادفی (RKGA[5]) (Xu & Bean, 2007) و حل کننده CPLEX مقایسه نمودند. الگوریتم ژنتیک ارائه شده داموداران در پیدا کردن جواب‏های خوب بسیار موثرتر بود. (H.-M. Wang & Chou, 2010) یک مدل برنامه ریزی عدد صحیح ترکیبی برای کمینه کردن حداکثر زمان تکمیل کارها روی ماشین­های پردازشگر دسته­ای موازی ارائه کردند که زمان آماده بودن برای کارها در نظر گرفته شده است. سپس برای حل مدل، یک الگوریتم شبیه سازی تبرید و یک الگوریتم ژنتیک پیشنهاد کردند. همچنین، در این پژوهش یک الگوریتم برنامه­ریزی پویای چند مرحله‏ای، کارها را برای هر ماشین دسته‏بندی می­کند.

(Damodaran, Vélez-Gallego, & Maya, 2011) یک روش جستجوی تطبیقی تصادفی حریصانه برای کمینه کردن حداکثر زمان تکمیل کارها روی ماشین‏های پردازشگر دسته­ای که به طور موازی قرار گرفته‏اند، با فرض زمان آماده ­بودن برای کارها ارائه کردند. در این مسأله، زمان آماده بودن دسته برابر با طولانی­ترین زمان آماده بودن کارهای داخل دسته است. روش ابتکاری پیشنهادی‏شان عملکرد بهتری در مقایسه با یک حد پایین و چند روش ابتکاری موجود در پژوهش­های پیشین داشت. در ادامه، (Damodaran & Velez-Gallego, 2010) روش ابتکاری دیگری برای کمینه کردن حداکثر زمان تکمیل کارها روی ماشین‏های پردازشگر دسته­ای موازی ارائه کردند. روش ابتکاری پیشنهادی با استفاده از تعدادی مسأله نمونه با چند روش ابتکاری پیشنهادی در پژوهش‏های پیشین از جمله همان روش ابتکاری تحقیق قبلی‏شان مقایسه شد که عملکرد بهتری در مقایسه با آنها داشت. (Chiang, Cheng, & Fu, 2010) یک الگوریتم ممتیک (MA[6]) برای مسأله زمان‏بندی ماشین­های پردازشگر دسته­ای موازی با ویژگی­های ابعاد اندازه‏های کاری واحد و یکسان و خانواده­های کار ناسازگار و ورود کارها به صورت پویا ایجاد کردند. همچنین، یک طرح کدگذاری جدید برای جستجوی همزمان تشکیل دسته­های بهینه و زمان‏بندی بهینه روی ماشین آلات در روش MA پیاده­سازی کردند. با مقایسه آن با الگوریتم اولیه MA به این نتیجه رسیدند که در شاخص­های کیفیت حل و اثر بخشی محاسباتی مزیت بالاتری دارد.

(Chang et al., 2004) مدل ریاضی برای مسأله مورد مطالعه، در حالتی که محدودیت زمان در دسترس در نظر گرفته نشده، معرفی کردند. در ادامه (Chung et al., 2009) مدل ریاضی با در نظرگیری محدودیت زمان در دسترس ارائه دادند که (Velez Gallego, 2009) با تغییر مدل ریاضی آنرا با در نظرگیری جایگاه دسته­ها روی هر ماشین ارائه دادند.

با توجه به بررسی پژوهش­های مرتبط در زمینه ماشین­های موازی پردازشگر دسته­ای، پژوهشی که در آن، زمان‏های پردازش و دردسترس به طور احتمالی در مسأله در نظر گرفته شوند، بررسی نشده‏اند که مقاله حاضر در ادامه تحقیق (Chung et al., 2009)، به توسعه رویکرد شبیه سازی در حالت شرایط احتمالی برای پارامترهای مسأله می­پردازد  و از 6 روش حل ابتکاری به منظور حل مسأله مورد مطالعه استفاده می‌شود.

 

3- تعریف مسأله

در ابتدای دوره زمان‏بندی n کار  با مشخصات زمان پردازش Pj، زمان دردسترس jr و اندازه­ی کار Sj وجود دارند. این کارها با توجه به زمان دردسترس بودنشان وارد ایستگاه کاری  می‏شوند که درآن ایستگاه m ماشین مشابه به طور موازی قرار دارد. منظور از ماشین‏های یکسان موازی این است که همه ماشین‏ها دارای ظرفیت یکسان پردازش هستند و با سرعت برابر، دسته­ها را پردازش می­کنند. هر ماشین دارای حداکثر ظرفیت پردازش همزمان B واحد کار در قالب یک دسته است. بنابراین، کارها باید قبل از پردازش روی ماشین­ها، در دسته­های  قرار بگیرند، به طوری که مجموع اندازه کارهای داخل دسته از ظرفیت ماشین کمتر یا مساوی باشند. سپس دسته­ها در صورت بیکار بودن ماشین به هر کدام از آنها تخصیص می‏یابند. هر دسته بعد از پردازش ایستگاه را ترک می­کند و جای خود را به دسته بعدی می­دهد. در این مسأله، اندازه هر کار با توجه به تعداد سفارشی از محصول است که مشتری تقاضا می­کند. زمان پردازش دسته، حداکثر زمان پردازش از میان زما‏‏ن‏های پردازش کارهای داخل دسته است و زمان آماده به پردازش هر دسته برابر با حداکثر زمان دردسترس از میان زمان‏های دردسترس کارهای دسته است.

مسأله مورد مطالعه شامل دو مرحله است. در مرحله اول با توجه به کارهای موجود، دسته­ها تشکیل می‌شود. هر دسته با توجه به این که مستقیمأ روی ماشین پردازش می­شود، دارای ظرفیت برابر با اندازه ظرفیت ماشین است. پس، استفاده از روش‏های ابتکاری در ساخت دسته­ها، تأثیر بالایی در کیفیت حل نهایی دارد. در مرحله دوم، دسته­های ساخته شده ابتدا به ماشین­های موازی موجود تخصیص می­یابد سپس روی هر ماشین دسته­ها به ترتیب و قاعده­ای مرتب می­شود تا تابع هدف مورد نظر که در این مقاله حداکثر زمان تکمیل است، بهینه گردد.

 

3-1- ویژگی­های مسأله مورد نظر

  • هر کار دارای اندازه (s)، زمان پردازش (p) و زمان دردسترس بودن (r) دلخواه است و همه مقادیر احتمالی هستند.
  • تعداد ماشین­ها حداقل 2 و حداکثر m است.
  • ظرفیت هر دسته طوری فرض می‌شود که مجموع اندازه کارهای تشکیل­دهنده آن از B بیشتر نگردد.
  • فرض می­شود هیچ کاری وجود ندارد که اندازه آن به تنهایی از ظرفیت دسته بزرگتر باشد.
  • زمانی که پردازش دسته شروع شود، کارها نمی‏توانند از دسته حذف یا اضافه شوند.
  • ماشین­ها دارای ظرفیت پردازش B و یکسان هستند.
  • همه­ی ماشین­ها، پردازشگر دسته­ای هستند.
  • تقدم و تأخر مجاز نیست.
  • خرابی ماشین مجاز نیست.

در ادامه برای شرح بهتر مسأله، مثالی ساده ارائه می‌شود که در آن 5 کار با مقادیر قطعی پارامترهای زمان دردسترس، زمان پردازش و اندازه برای هر کار فرض می‌شود. در این مدل، منظور از ابعاد یا اندازه کار (Sj) مقدار سفارشی است از طرف مشتری که برای کار j-ام تقاضا می‌شود.

مثال: در جدول 1 اطلاعات مربوط به 5 کار برای زمان‌بندی روی 2 ماشین‌ موازی پردازشگر دسته‌ای ارائه شده است. شکل1 نمایش گرافیکی از داده‌های جدول1 نشان می‌دهد. هر مستطیل یک کار را نشان می‌دهد. طول مستطیل تشبیهی از زمان پردازش هر کار و ارتفاع مستطیل تشبیهی از اندازه کار است. محور افقی بیان‌کننده زمان دردسترس کارها است. ظرفیت اندازه‌ای هر دسته 7 واحد است. نمودار گانت زمانبندی شدنی در شکل2 نشان داده شده است. در این مثال دو دسته تشکیل می‌شود و مقدار Cmax برابر با 19 واحد زمانی است. اجزای هر دسته در شکل2 نشان داده شده است.

 

جدول 1- داده‌های مربوط به 5 کار در نمونه مسأله

کارها

1

2

3

4

5

زمان پردازش (Pj)

7

6

10

7

5

زمان دردسترس (rj)

5

2

8

4

9

اندازه کار (sj)

2

3

1

3

3

 

 


شکل 1-نمایش مسأله

 

 

 

 


شکل 2- نمودار گانت یک زمانبندی شدنی برای مسأله با 5 نمونه کار

 

4- روش­های حل

به طور کلی به منظور حل مسائل و به دست آوردن جواب‏های مناسب، از 3 رویکرد اصلی شامل روش‏های دقیق، روش­های ابتکاری و روش‏های فراابتکاری استفاده می­شود. روش­های دقیق مانند شاخه و کران و برنامه ریزی پویا اغلب در نرم افزارهای بهینه­سازی تعبیه شده­اند. این روش­ها با پیچیده­تر شدن مدل، کارایی خود را در پیدا کردن نقطه بهینه در زمان مناسب از دست می­دهند. رویکرد دوم روش­های ابتکاری است که در طی50 سال اخیر برای حل مسائل پیچیده کاربرد داشته است. این روش­ها در مسائل پیچیده جواب نزدیک به بهینه را در زمان مناسبی به دست می­آورند.

روش­های ابتکاری عبارتند از معیارها، روش‏ها یا اصولی که مطابق با ساختار هر مسأله ایجاد می‏شوند. خاصیت روش­های ابتکاری خوب در این است که ابزار ساده‌ای برای تشخیص خط‌مشی‌های بهتر ارائه دهند. با وجود این، تشخیص خط‌ مشی‌های اثربخش را تضمین نمی‌کنند، ولی اغلب به صورت شرط کافی این تضمین را فراهم ‌می‌کنند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق هستند. روش­های ابتکاری با استفاده از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند و جواب­هایی که در زمانی مناسب ارائه می‌کنند، نقشی اثربخش در حل چنین مسائلی دارند (عالم تبریز و همکاران، 1387).

با توجه به پیچیدگی مدل مورد مطالعه در این مقاله، از روش­های ابتکاری در دو بخش تشکیل دسته و ترتیب­دهی دسته­ها روی ماشین­ها استفاده شده است. ترکیب­های مختلف از روش­های ابتکاری در دو بخش اشاره شده، تاثیر بسیاری در جواب­های به دست آمده دارند. در این قسمت دو روش ابتکاری برای تشکیل دسته و 3 روش ابتکاری برای ترتیب دهی دسته ها به طور خلاصه شرح داده می‏شود.

 

4-1- روش­های تشکیل دسته­

هدف از تشکیل دسته­ها این است که با توجه به ظرفیت مشخص دسته­ها تا حد امکان تعداد دسته­ها حداقل و منابع موجود به حداکثر بهره‏وری برسند.

 

4-1-1- روش­ ابتکاری نخستین تناسب طراحی[7] شده MFF))

(Velez Gallego, 2009) این روش را برای مسأله زمان‏بندی ماشین­های پردازشگر دسته­ای موازی در شرایطی که زمان دردسترس (rj) غیرصفر است ارائه کرد. قدم‏های این روش به صورت زیر است:

1)  ابتدا کارها به ترتیب غیر کاهشی زمان دردسترس مرتب می‌شوند (اگر زمان دردسترس چند کار برابر باشد، از قاعده LPT[8] برای اولویت دادن استفاده می‌شود).

2)  نخستین کار در لیست به اولین دسته تخصیص یابد.

3)  کار بعدی در لیست به شرطی به این دسته اضافه شود که مطابق رابطه 2، شرط تجاوز نکردن از ظرفیت دسته رعایت گردد. یعنی اندازه کار کاندید برای ورود به دسته، از مقدار باقیمانده ظرفیت دسته باید کوچکتر یا مساوی باشد. در غیر این صورت دسته جدید تشکیل می‏شود و کار کاندید، به آن تخصیص می­یابد.

 

k کارهای تعلق یافته به دسته و B اندازه ظرفیت دسته است.

4)  برای بقیه کارها در لیست، قدم 3 اجرا می‌َگردد تا همه­ی کارها به دسته­ها تخصیص یابند.

 

4-1-2- روش­ ابتکاری بهترین تناسب طراحی شده[9](MFD)

این روش را (Velez Gallego, 2009) برای مسأله زمان‏بندی ماشین­های پردازشگر دسته­ای موازی ارائه کرده است. قدم‏های این روش به صورت زیر است:

1)  کارها را به ترتیب غیر کاهشی زمان دردسترس مرتب می‌شود (اگر زمان دردسترس چند کار برابر باشد، از قاعده LPT برای اولویت دادن استفاده می‌شود).

2) نخستین کار در لیست به اولین دسته تخصیص می‌یابد.

3) کار کاندید j که در لیست بالاتر است روی دسته‏ای که بیشترین محتویات را دارد یعنی دسته­ای که حجم باقیمانده ظرفیت آن برای تخصیص کار، کمترین است به شرط عدم تجاوز از ظرفیت دسته جایگذاری می‌شود.

4) برای بقیه کارها در لیست هم به ترتیب، قدم 3 اجرا می‌شود تا همه­ی کارها به دسته­ها تخصیص یابند.

4-2- روش­های ترتیب دسته­ ها[10]

پس از این که دسته‏ها تشکیل شد، مسأله به مسأله ماشین موازی پردازش تکی کاهش می­یابد که با توجه به پیچیدگی سخت مسأله، از روش­های ابتکاری یا فراابتکاری برای حل آن می­توان استفاده کرد.

سه روشی که ولز در سال 2009 ارائه کرد به اختصار شرح داده می­شود.

 

4-2-1- روش­ ابتکاری زودترین زمان دردسترس بودن[11]ERT))

دسته­ها به ترتیب زودترین زمان در دسترس دسته‏ها مرتب می­شوند. سپس به هر دسته،  آن ماشینی که آزاد است تخصیص می‌یابد.

 

4-2-2- روش­ ابتکاری زودترین زمان دردسترس بودن-طولانی­ترین زمان پردازش (ERT-LPT)

دسته­ها به ترتیب غیرکاهشی زمان در دسترس هر دسته منظم می­شوند. تا زمانی که حداقل زمان دردسترس ماشین­ها بزرگتر یا مساوی حداکثر زمان دردسترس دسته­ها باشد، دسته­ها مطابق قاعده LPT به نخستین ماشین در دسترس تخصیص می‌یابند. از این زمان به بعد، دسته­ها به نخستین ماشین طبق قاعده LPT تخصیص می­یابد.

 

4-2-3- روش­ ابتکاری طولانی­ترین زودترین زمان تکمیل [12](LECT)

برای هر دسته، مقدار Cb[13] بر اساس رابطه Cb=Rb+Pbمحاسبه می‌شود. در این رابطه Pb معرف زمان پردازش هر دسته و Rb معرف زمان در دسترس هر دسته است. پس از محاسبه Cb، دسته‏ها، مطابق ترتیب غیر افزایشی Cb مرتب می‏شوند و هر دسته به نخستین ماشین دردسترس تخصیص می­یابد.

جدول2 فاکتور تعیین کننده در روش­های ابتکاری، به همراه کد اختصاصی هر روش را نشان می­دهد. در ادامه از ترکیب کدهای اختصاصی به منظور نام گذاری روش­های ترکیبی استفاده می­شود. برای مثال روش B1S2 به این معناست که از روش دسته­بندی MBF و توالی ERT-LPT استفاده شده است.

4-3- به کارگیری زمان احتمالی در روش­های ابتکاری

با توجه به احتمالی بودن پارامترها، از میانگین تابع توزیع آنها در محاسبات مورد نیاز در انواع روش­های ابتکاری­ استفاده می­شود. این رویه یکی از معمول‏ترین و ساده­ترین راه­کارها برای استفاده روش­های قطعی در مسائل احتمالی هستند، که مبتنی بر اطلاعات و داده­های پیشین ثبت شده است.
به جای استفاده از روش میانگین ساده می­توان از تکنیک­های دیگری همچون روش پیش­بینی نمو هموار تعدیل شده یا دیگر روش­های پیش­بینی یا داده­کاوی استفاده کرد.

در دو روش ابتکاری تشکیل دسته، زمان دردسترس و اندازه کارها مشخص شده سپس دسته‏بندی صورت می­گیرد. ولی به هنگام استفاده از قاعده LPT از میانگین زمان پردازش استفاده می­شود. در سه روش ابتکاری اکثر محاسبات بر پایه زمان پردازش صورت می­گیرد، در نتیجه از میانگین زمان پردازش در محاسبات استفاده می­شود.

 

جدول2- روش­های ابتکاری

نام روش ابتکاری

فاکتور تعیین کننده

کد اختصاصی

ERT

rj

S1

ERT-LPT

rj - Pj

S2

LECT

Pj

S3

MBF

rj

B1

MFF

Pj

B2

 

5- شبیه­سازی

با پیدایش کامپیوتر در دهه 50 و 60 میلادی، پژوهشگران شروع به استفاده از زبان‏های برنامه‏نویسی معمول مانند FORTRAN برای شبیه‏سازی سیستم­های پیچیده کردند. این رویه بسیار قابل انعطاف اما پر زحمت و مستعد خطا بود (Kelton, Sadowski, & Sturrock, 2004).

مدل­های‌ شبیه‌­سازی‌ از لحاظ‌ منطقی‌ معمولاً پیچیده‌ هستند و دارای‌ فعل‌ و انفعال­های‌ متقابل بسیاری‌ در بین‌ عناصر سیستم هستند.‌ بیشتر این‌ فعل‌ و انفعال­ها در حین‌ برنامه‌ به‌ طور پویا تغییر می‌کنند. این وضعیت‌ موجب‌ شده است‌ که‌ پژوهشگران، زبان‏های‌ برنامه‏نویسی‌ مخصوص شبیه­سازی مانند GPSS را ایجاد و توسعه‌ دهند.

مدل مورد بررسی در این مقاله، بسیار پیچیده است و چارچوب آن منطبق با زبان‏های برنامه­نویسی معمول شبیه­سازی و یا برنامه­های سطح بالای شبیه‏سازی مثل Arena نیست. بنابراین، در این مقاله رویه شبیه‏سازی با استفاده از زبان برنامه‏نویسی MATLAB انجام شده است.

رویه شبیه­سازی ارائه شده بر اساس تکنیک شبیه‏سازی گسسته-پیشامد که یکی از پر کاربردترین رویه­های شبیه­سازی است طراحی شده است. در این تکنیک حوادث یا عملیات سیستم به صورت توالی از عملیات نمایش داده می­شود. هر رخداد در یک لحظه به تغییر در حالت سیستم منجر می­شود (Stewart, 2004).

روش‏های زیادی برای انجام شبیه­سازی رویداد گسسته مانند روش­های مبتنی بر رویداد، مبتنی بر فعالیت و فرآیند سه فازی ارائه شده است (Pidd, 1998). رویه شبیه­سازی ارائه شده در این مقاله، مبتنی بر فعالیت است که نهادهای مدل، مطابق با تعریف (Kelton et al., 2004) کارها هستند و ماشین­ها منابع سیستم هستند. نمودار فعالیت مدل شبیه­سازی شده در شکل3 نمایش داده شده است.

 

 

 

شکل3-. نمودار فعالیت

 

­­

شکل4- فرآیند شبیه­سازی

 

برای شبیه­سازی یک رویه دو فازی طراحی شده است که در فاز اول کارها به طور تصادفی تولید و مطابق دو روش ابتکاری دسته­بندی می­شوند. در فاز دوم دسته­ها روی ماشین­های موازی پردازش می‏شوند. شکل4 مدل پایه از رویه دو فازی فرآیند شبیه­سازی را نمایش می­دهد.

6- نتایج محاسباتی

زمان پردازش و زمان در دسترس بودن کارها بر اساس توزیع یکنواخت محاسبه شده­اند، زیرا واریانس بالای توزیع یکنواخت متضمن این است که نتایج شبیه­سازی برای مقایسه روش­های ابتکاری تحت شرایط کاملاً یکسان اجرا شود (Weng, Lu, & Ren, 2001).

شش نوع نمونه مسأله بر اساس رویه پیشنهادی ولِز (2009) تعریف شده است. مشخصات مسائل در جدول 3 آورده شده است. طبق هر نوع نمونه مسأله، 100 مسأله تولید و روش‏های ابتکاری دسته­بندی و توالی روی آنها اعمال شده است. سپس برای هر مورد 10000 بار عملیات شبیه­سازی انجام شده است. تعداد تکرار یا اجرای شبیه‏سازی بر اساس به دست آوردن فاصله اطمینان خوب طبق رویه (Banks & Carson) محاسبه شده است. ابتدا، تعداد تکرار برای بزرگ­ترین مسأله محاسبه و سپس به منظور یکسان سازی رویه، برای مسائل کوچک نیز اعمال شده است.

در جدول3 مشخصات نمونه مسائل تصادفی تولید شده آمده است. جدول4 میانگین عملکرد نسبی هر یک از روش­های ترکیبی را نمایش می­دهد. عملکرد نسبی روش k با رابطه زیر محاسبه می­شود:

 

که Ck حداکثر زمان تکمیل روش k و Cmin حداقلِ حداکثر زمان تکمیل بین تمام شش روش ترکیبی است. هر چه روش ابتکاری ترکیبی عملکرد بهتری داشته باشد، عدد به دست آمده به یک نزدیکتر خواهد شد.

شکل5 عملکرد نسبی هر یک از روش­های ترکیبی را به صورت نمودار سهام نمایش می­دهد. هر خانه، تعداد ماشین و تعداد کار مشخص شده در سطر و ستون را نمایش می‏دهد. در این نمودار، هر خانه حاوی 6 خط به نمایندگی از روش ابتکاری ترکیبی است. بالا و پایین هر خط، بیشترین و کمترین مقدار معیار است و میانگین معیار روی خط مشخص شده است.

در هر نمودار سهام، هر خانه حاوی 6 خط به نمایندگی از روش ابتکاری ترکیبی است. بالا و پایین هر خط، بیشترین و کمترین مقدار معیار است و میانگین معیار روی خط مشخص شده است.

 

جدول 3- انواع نمونه مسأله تصادفی

مسأله

تعداد ماشین

تعداد کار

1

3

50

2

3

100

3

3

200

4

5

50

5

5

100

6

5

200

 

برای بررسی رفتار مدل، آنالیز حساسیت روی نمونه مسأله چهارم انجام شده است. شکل 6 حساسیت میزان احتمالی بودن زمان فرآیند عملیات را نمایش می­دهد. همانگونه که از شکل مشخص است، روش دوم ابتکاری توالی بهترین عملکرد را دارد و روش ابتکاری دسته­بندی نوع اول کارایی اندک بهتری از روش ابتکاری دسته­بندی دوم دارد.

 

 


 

شکل 5- نمودار سهام عملکرد نسبی روش­های ابتکاری ترکیبی

 

 

 

.7- نتیجه گیری

در این مقاله، مسأله زمان‏بندی ماشین­های پردازشگر دسته­ای موازی با پارامترهای احتمالی و با هدف حداقل کردن حداکثر زمان تکمیل، بررسی شده است. به منظور تعیین کاراترین روش حل ابتکاری در مسأله فوق، 5 روش ابتکاری در دو فاز از ساختار مسأله شامل فازهای تشکیل دسته از کارهای موجود و تعیین توالی دسته­ها روی هر ماشین تشریح گردید. سپس با رویکرد شبیه‏سازی، کاراترین ترکیب روش‏های ابتکاری در دو فاز مشخص شده است. نتیجه محاسبات نشان از این دارد که روش MBF در فاز اول و روش ERT-LPT در فاز دوم، کارایی بالاتری در به دست آوردن جواب­های مناسب در نمونه مسائل ایجاد شده دارند.

در ادامه تحقیق انجام شده و در تحقیقات آتی به منظور واقعی­تر شدن مسأله می­توان مفروضات جدیدی در مدل در نظر گرفت که شامل بررسی سایر مقیاس­های عملکردی مانند متوسط زمان‏های تکمیل کارها یا حداکثر زمان جریان تولید، توسعه مدل در حالت چند ایستگاهی به صورت جریان کارگاهی و اضافه کردن فرض­های خرابی ماشین­ها، زمان آماده سازی وابسته به توالی، سیستم­های حمل و نقل و آماده سازی گروهی هستند.

 

 

 

جدول 4-نتایج محاسباتی

روش ابتکاری ترکیبی

نمونه مسأله

B1S1

B1S2

B1S3

B2S1

B2S2

B2S3

n×M

0/921939

0/997729

0/982274

0/996384

0/981295

0/921424

3×50

953402/0

994299/0

991819/0

988011/0

985731/0

947466/0

3×100

983182/0

997/0

996818/0

990006/0

990006/0

97649/0

3×200

930587/0

998132/0

971828/0

998687/0

972222/0

931117/0

5×50

934468/0

998597/0

973643/0

998887/0

973528/0

933985/0

5×100

973256/0

996077/0

995399/0

990918/0

990251/0

968125/0

5×200

949472/0

996972/0

985297/0

993846/0

982172/0

946435/0

میانگین

 


 


شکل6- تحلیل حساسیت برای زمان فرآیند عملیات



[1] -Greedy ratio

[2] -Full batch short processing time

[3] -Best fit long processing time

[4] -First fit long processing time

[5] -Random key genetic algorithm

[6] -Memetic algorithm

[7] Modified First fit

8-  Long processing time

[9] Modified fit decressing

[10] Scheduling Rules

[11] Earliest ready time

[12] Longest earliest complation time

[13] ComplEtion time

عالم تبریز.الف، زندیه. م، محمدرحیمی.ع. ر، 1389. الگوریتم­های فراابتکاری در بهینه­سازی ترکیبی. شابک: 4-217-388-978-964. نشر اشراقی.

Banks, J, & Carson, JS. II, Nelson, BL, and Nicol, DM (2005). Discrete-event system simulation.

Chandru, Vijaya, Lee, C-Y, & Uzsoy, Reha. (1993). Minimizing total completion time on batch processing machines. THE INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 31(9), 2097-2121.

Chang, P-Y, Damodaran*, P, & Melouk, S. (2004). Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42(19), 4211-4220.

Chiang, Tsung-Che, Cheng, Hsueh-Chien, & Fu, Li-Chen. (2010). A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival. Computers & Operations Research, 37(12), 2257-2269.

Chung, SH, Tai, YT, & Pearn, WL. (2009). Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research, 47(18), 5109-5128.

Damodaran, Purushothaman, Hirani, Neal S, & Velez-Gallego, Mario C. (2009). Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms. European Journal of Industrial Engineering, 3(2), 187-206.

Damodaran, Purushothaman, & Velez-Gallego, Mario C. (2010). Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times. The International Journal of Advanced Manufacturing Technology, 49(9-12), 1119-1128.

Damodaran, Purushothaman, Vélez-Gallego, Mario C, & Maya, Jairo. (2011). A GRASP approach for makespan minimization on parallel batch processing machines. Journal of Intelligent Manufacturing, 22(5), 767-777.

Kashan, Ali Husseinzadeh, Karimi, Behrooz, & Jenabi, Masoud. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098.

Kelton, WD, Sadowski, RP, & Sturrock, DT. (2004). Simulation with Arena, 3rd: McGraw-Hill Higher Education, Massachusetts, USA.

Koh*, Shie-Gheun, Koo, Pyung-Hoi, Ha, Jae-Won, & Lee, Woon-Seek. (2004). Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. International Journal of Production Research, 42(19), 4091-4107.

Malve, Sujay, & Uzsoy, Reha. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34(10), 3016-3028.

Mönch, Lars, Fowler, John W, Dauzère-Pérès, Stéphane, Mason, Scott J, & Rose, Oliver. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14(6), 583-599.

Pidd, Michael. (1998). Computer simulation in management science.

Pinedo, Michael L. (2012). Scheduling: theory, algorithms, and systems: Springer Science & Business Media.

Shao, Hao, Chen, Hua-Ping, Huang, George Q, Xu, Rui, Cheng, Ba-yi, Wang, Shuan-shi, & Liu, Bo-wen. (2008). Minimizing makespan for parallel batch processing machines with non-identical job sizes using neural nets approach. Paper presented at the Industrial Electronics and Applications, 2008. ICIEA 2008. 3rd IEEE Conference on.

Stewart, Robinson. (2004). Simulation–The practice of model development and use. Hoboken, NJ: John Wiley & Sons.

Uzsoy, Reha. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685-2708.

Velez Gallego, Mario Cesar. (2009). Algorithms for scheduling parallel batch processing machines with non-identical job ready times.

Wang, Cheng-Shuo, & Uzsoy, Reha. (2002). A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers & Operations Research, 29(12), 1621-1640.

Wang, Hui-Mei, & Chou, Fuh-Der. (2010). Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37(2), 1510-1521.

Weng, Michael X, Lu, John, & Ren, Haiying. (2001). Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International journal of production economics, 70(3), 215-226.

Xu, Shubin, & Bean, James C. (2007). A genetic algorithm for scheduling parallel non-identical batch processing machines. Paper presented at the Computational Intelligence in Scheduling, 2007. SCIS'07. IEEE Symposium on.