نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 دانشجوی دکتری مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، ایران
2 استادیار گروه مهندسی صنایع، دانشگاه شاهد، تهران، ایران، ایران
3 کارشناس ارشد مهندسی صنایع، اداره کل بنادر و دریانوردی استان هرمزگان، بندرعباس، ایران
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [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]
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 واحد کار در قالب یک دسته است. بنابراین، کارها باید قبل از پردازش روی ماشینها، در دستههای قرار بگیرند، به طوری که مجموع اندازه کارهای داخل دسته از ظرفیت ماشین کمتر یا مساوی باشند. سپس دستهها در صورت بیکار بودن ماشین به هر کدام از آنها تخصیص مییابند. هر دسته بعد از پردازش ایستگاه را ترک میکند و جای خود را به دسته بعدی میدهد. در این مسأله، اندازه هر کار با توجه به تعداد سفارشی از محصول است که مشتری تقاضا میکند. زمان پردازش دسته، حداکثر زمان پردازش از میان زمانهای پردازش کارهای داخل دسته است و زمان آماده به پردازش هر دسته برابر با حداکثر زمان دردسترس از میان زمانهای دردسترس کارهای دسته است.
مسأله مورد مطالعه شامل دو مرحله است. در مرحله اول با توجه به کارهای موجود، دستهها تشکیل میشود. هر دسته با توجه به این که مستقیمأ روی ماشین پردازش میشود، دارای ظرفیت برابر با اندازه ظرفیت ماشین است. پس، استفاده از روشهای ابتکاری در ساخت دستهها، تأثیر بالایی در کیفیت حل نهایی دارد. در مرحله دوم، دستههای ساخته شده ابتدا به ماشینهای موازی موجود تخصیص مییابد سپس روی هر ماشین دستهها به ترتیب و قاعدهای مرتب میشود تا تابع هدف مورد نظر که در این مقاله حداکثر زمان تکمیل است، بهینه گردد.
در ادامه برای شرح بهتر مسأله، مثالی ساده ارائه میشود که در آن 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- روشهای تشکیل دسته
هدف از تشکیل دستهها این است که با توجه به ظرفیت مشخص دستهها تا حد امکان تعداد دستهها حداقل و منابع موجود به حداکثر بهرهوری برسند.
(Velez Gallego, 2009) این روش را برای مسأله زمانبندی ماشینهای پردازشگر دستهای موازی در شرایطی که زمان دردسترس (rj) غیرصفر است ارائه کرد. قدمهای این روش به صورت زیر است:
1) ابتدا کارها به ترتیب غیر کاهشی زمان دردسترس مرتب میشوند (اگر زمان دردسترس چند کار برابر باشد، از قاعده LPT[8] برای اولویت دادن استفاده میشود).
2) نخستین کار در لیست به اولین دسته تخصیص یابد.
3) کار بعدی در لیست به شرطی به این دسته اضافه شود که مطابق رابطه 2، شرط تجاوز نکردن از ظرفیت دسته رعایت گردد. یعنی اندازه کار کاندید برای ورود به دسته، از مقدار باقیمانده ظرفیت دسته باید کوچکتر یا مساوی باشد. در غیر این صورت دسته جدید تشکیل میشود و کار کاندید، به آن تخصیص مییابد.
k کارهای تعلق یافته به دسته و B اندازه ظرفیت دسته است.
4) برای بقیه کارها در لیست، قدم 3 اجرا میَگردد تا همهی کارها به دستهها تخصیص یابند.
این روش را (Velez Gallego, 2009) برای مسأله زمانبندی ماشینهای پردازشگر دستهای موازی ارائه کرده است. قدمهای این روش به صورت زیر است:
1) کارها را به ترتیب غیر کاهشی زمان دردسترس مرتب میشود (اگر زمان دردسترس چند کار برابر باشد، از قاعده LPT برای اولویت دادن استفاده میشود).
2) نخستین کار در لیست به اولین دسته تخصیص مییابد.
3) کار کاندید j که در لیست بالاتر است روی دستهای که بیشترین محتویات را دارد یعنی دستهای که حجم باقیمانده ظرفیت آن برای تخصیص کار، کمترین است به شرط عدم تجاوز از ظرفیت دسته جایگذاری میشود.
4) برای بقیه کارها در لیست هم به ترتیب، قدم 3 اجرا میشود تا همهی کارها به دستهها تخصیص یابند.
پس از این که دستهها تشکیل شد، مسأله به مسأله ماشین موازی پردازش تکی کاهش مییابد که با توجه به پیچیدگی سخت مسأله، از روشهای ابتکاری یا فراابتکاری برای حل آن میتوان استفاده کرد.
سه روشی که ولز در سال 2009 ارائه کرد به اختصار شرح داده میشود.
دستهها به ترتیب زودترین زمان در دسترس دستهها مرتب میشوند. سپس به هر دسته، آن ماشینی که آزاد است تخصیص مییابد.
دستهها به ترتیب غیرکاهشی زمان در دسترس هر دسته منظم میشوند. تا زمانی که حداقل زمان دردسترس ماشینها بزرگتر یا مساوی حداکثر زمان دردسترس دستهها باشد، دستهها مطابق قاعده LPT به نخستین ماشین در دسترس تخصیص مییابند. از این زمان به بعد، دستهها به نخستین ماشین طبق قاعده LPT تخصیص مییابد.
برای هر دسته، مقدار 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
[9] Modified fit decressing
[10] Scheduling Rules
[11] Earliest ready time
[12] Longest earliest complation time
[13] ComplEtion time
)