به‌کارگیری الگوریتم شاخه و حد با حدودِ پایین قوی برای حل مسئلۀ حداقل‌کردن زمان انجام کل کارها روی ماشین پردازندۀ انباشته

مقدمه

امروزه مسائل زمان‌بندی در اکثر محیط­های اقتصادی به‌صورت مزیت رقابتی مطرح و شناخته شده است. طی سه‌دهۀ اخیر به مسائل زمان‌بندی که در آنها انباشته‌سازی کارها مطرح است توجه زیادی شده است، به‌‌نحوی‌‌که امروزه زمان‌بندی انباشته‌ها در سیستم تولید یکی از سیاست‌های معمول در بسیاری از صنایع است. علت این انگیزش در افزایش سرعت تولید و کاهش هزینه­های مرتبط با آن ازطریق سیاست تولید انباشته‌ای به‌جای تولید منفرد کارها است. ماشین‌های پردازش انباشته^[i] در سیستم‌های تولید انباشته‌ای قابلیت پردازش دسته‌ای از کارها را درقالب یک انباشته به‌طور هم‌زمان دارند. منظور از یک‌ انباشته، گروهی از کارهاست که به‌طور هم‌زمان زیر عملیات ماشین قرار می‌گیرند؛ بنابراین ظرفیت ماشین تعیین‌کنندۀ اندازۀ انباشته است. خانوادۀ مسائل زمان‌بندی ماشین­های پردازندۀ انباشته با کارهای با اندازۀ غیریکسان در دسته مسائل NP-hard قرار می­گیرد (اوزوی^[ii]، 1994).

در ادبیات زمان‌بندی تولید انباشته‌ای، مثال‌های متعددی از ایستگاه‌های تولیدی ذکر شده‌اند که در آن از ماشین‌های پردازش انباشته‌ استفاده می‌شود؛ برای نمونه عملیات فر درون‌سوز در تولید بوردهای مدار چاپی، داخل فرهایی انجام می‌شود که می‌توانند چندین گروه از بوردها را در خود و زیر عملیات حرارتی قرار دهند (لی و همکاران، 1999). در اینجا فرها نقش ماشین‌های پردازش انباشته را بازی می‌کنند. مثالی دیگر، فرآیند حکاکی هدایت الکتریکی^[iii] در بوردهای مدار چاپی است. طی این فرآیند و طی عملیات فوتولیتوگرافی^[iv] از تانک‌هایی (ماشین‌های پردازش انباشته) استفاده می‌شود که حاوی مواد شیمیایی برای از بین بردن لایۀ فلزی روی بورد هستند که با مادۀ محافظت‌کننده پوشانده نشده است (احمدی و همکاران، 1992). همچنین می‌توان به روترهای کنترل عددی^[v] استفاده‌شده در برش ورق‌های فلزی و یا مدارهای چاپی اشاره کرد. طی فرآیند برش ورق‌ها، با چرخش صفحه‌گردنده یک انباشته از قطعات فلزی هم‌خانواده تولید می‌شود. در اینجا روتر برنده با یک ماشین پردازش انباشته مدل می‌شود (احمدی و همکاران، 1992). همچنین می‌توان به کاربرد مدل‌های زمان‌بندی پردازش انباشته در سایر صنایع ازجمله صنایع ریخته‌گری (ماتیراجان و سیواکومار^[vi]، 2006) ، صنایع تولید مبلمان و اثاثیۀ خانه‌ (یعقوبیان و همکاران^[vii]، 1999) ، صنایع تولید آهن و فولاد (اولامارا^[viii]، 2007) و غیره اشاره کرد.

اگرچه کاربردهای مدل‌های زمان‌بندی ماشین‌های پردازش انباشته در طیف وسیعی از صنایع تولیدی یافت می‌شوند، حجم عظیمی از پژوهش‌های انجام‌شده فقط به کاربرد این مدل‌ها در صنایع تولید نیمه‌هادی‌ها مربوط می‌شوند. تعداد زیادی از ماشین‌آلات استفاده‌شده در صنایع تولید نیمه‌هادی‌ها در زمرۀ ماشین‌های پردازش انباشته هستند که قابلیت انجام عملیات هم‌زمان را بر کارهای درون‌انباشته دارند. بعضی از این ماشین‌آلات عبارتند از cleaning، diffusion، oxidation وburn-in operation. عملیات انجام‌‌شده با فرهای درون‌سوز (burn-in operation) قابل مدل­سازی درقالب ماشین(های) پردازش انباشته‌ است. فقط ممکن است ظرفیت فر، بزرگ‌تر از اندازۀ یک کار باشد؛ بنابراین تعداد بوردهایی که می‌توانند داخل فر قرار بگیرند تعیین‌کنندۀ ظرفیت فر است. اندازۀ یک کار نیز با تعداد بوردهای لازم تعریف می‌شود. ازآنجاکه چیپ‌های IC برای مدتی طولانی بیش از آنچه که برای آنها در نظر گرفته شده است در داخل فر زیر عملیات حرارتی قرار می‌گیرند، قرارگیری چیپ‌های مربوط به سفارشات مختلف داخل فر امکان‌پذیر است. این در حالی است که خارج‌کردن آنها از فر پیش از مدت زمان لازم برای پخت امکان­پذیر نیست. گروهی از بوردهایی که هم‌زمان داخل فر قرار می‌گیرند یک انباشته را تشکیل می‌دهند. زمان لازم برای انجام عملیات حرارتی روی انباشته برابر زمان لازم برای انجام عملیات روی کاری است که در بین سایر کارهای درونِ انباشته زمان بیشتری را برای انجام عملیات حرارتی می‌طلبد. با شروع عملیات روی یک انباشته، هیچ کاری نمی‌تواند به انباشته اضافه و یا از آن خارج شود. همچنین ازآنجاکه دمای فر همواره ثابت است، نیاز به هیچ‌گونه آماده­سازی حرارتی نیست (لی و همکاران، 1999). اغلب در فرآیند تولید نیمه‌هادی‌ها، ایستگاه‌هایی که این ماشین‌ها در آنها فعالیت می‌کنند ایستگاه گلوگاه تولید هستند. این امر بدین خاطر است که این تجهیزات بسیار گران است؛ بنابراین میزان بهره‌گیری از آنها زیاد است. به‌علاوه عملیات تولید در این ماشین‌ها طولانی است و بدون انقطاع انجام می‌شود و این موجب انتظار طولانی سایر قطعات می‌‌شود؛ بنابراین هرگونه بهبود در زمان‌بندی و کاهش زمان سیکل نتایج مثبتی را از دیدگاه اقتصاد تولید دارد (ماتیراجان و سیواکومار^[ix]، 2006). با‌توجه‌به اینکه تلاش‌های انجام‌شده در این زمینه به ارائۀ روش‌های حل محدود است و در رابطه با ارزیابی عملکرد واقعی این روش‌ها تلاش زیادی انجام نشده است، در این مقاله ضعف موجود درزمینۀ ارزیابی عملکرد الگوریتم‌های ارائه‌شده برای مسئلۀ زمان‌بندی ماشین‌های پردازش انباشته با وجود کارهای با اندازۀ غیریکسان‌ جبران می‌شود.

ساختار ادامۀ مقاله بدین شرح است که درادامۀ پژوهش حاضر، مروری بر پیشینۀ پژوهش ارائه می‌شود. سپس تعریف مسئله و مفروضات بیان و بعد از آن حدود بالا و پایین تشریح می‌شود. بخش بعدی به رویکرد حل مسئله اختصاص داده می‌شود. درپایان نیز بحث و نتایج حاصل از محاسبات تشریح و نتیجه‌گیری ارائه می‌شود.

مروری بر پیشینۀ پژوهش

نخستین تلاش­های انجام‌شده در زمان‌بندی ماشین‌های پردازندۀ انباشته به ایکورا و جیمپل^[x] (1986) نسبت داده می‌شود. همچنین نخستین افرادی که زمان‌بندی ماشین‌های پردازش‌گر انباشته را با فرض وجود کارهای با اندازه نامساوی^[xi] بررسی کردند، دابسون و نامبیادوم^[xii](2001) بودند. اوزوی (1994) مسئلۀ حداقل‌کردن C_max و SC_i روی یک ماشین پردازش‌گر انباشته را بررسی و محل کاربرد آن را در صنایع تولید نیمه‌هادی معرفی کرد. وی برای مسئلۀ حداقل‌کردن C_max نشان داده است که این مسئله با فرض یکسان‌بودن کلیۀ زمان‌های پردازش معادل مسئلۀ شناخته‌شدۀ بسته‌بندی اشیاء در ظروف و مسئله‌ای NP-hard است. سپس برمبنای الگوریتم first-fit که برای مسئلۀ بسته‌بندی اشیاء در ظروف ابداع شده است، 4 الگوریتم برای مسئلۀ حداقل‌کردن C_max ارائه کرده است. مبنای عمل کلیۀ این الگوریتم‌ها ابتدا مرتب‌سازی کارها براساس ترتیب‌های مختلف و سپس استفاده از الگوریتم first-fit برای انباشته‌سازی کارها است. کارایی این الگوریتم‌ها ازطریق محاسبات کامپیوتری بررسی و معلوم شده است. یکی از این الگوریتم‌ها که برمبنای مرتب‌سازی کارها براساس LPT^[xiii] عمل می‌کند، دارای عملکرد بهتری نسبت به سایرین است. دربارۀ مسئلۀ حداقل‌کردن SC_i نیز نشان داده شده است که این مسئله NP-hard است و الگوریتم شاخه و حدی برای به دست آوردن جواب بهینه در مسائل کوچک ارائه شده است. وی همچنین 2 الگوریتم ابتکاری برای این مسئله توسعه داده است.

دوپونت و جولای^[xiv] (1998) برای مسئلۀ حداقل‌کردن C_max دو الگوریتم ابتکاری ارائه کرده‌اند که یکی از آنها برمبنای اصلاح الگوریتم‌های ارائه‌شده به‌وسیلۀ اوزوی(1994) در استفاده از الگوریتم best-fit به‌جای first-fit است و دیگری برمبنای تعیین اقلام یک انباشته با استفاده از حل مسئلۀ کوله‌پشتی است. نتایج محاسباتی نشان داده‌اند هر دو الگوریتم عملکرد بهتری نسبت به الگوریتم‌های قبلی دارند. آنها همچنین برای مسئلۀ حداقل‌کردن SC_i تعدادی الگوریتم ابتکاری ارائه کرده‌اند و ازطریق محاسبات کامپیوتری نشان داده‌اند عملکرد این الگوریتم‌ها در مقایسه با الگوریتم‌های ارائه‌شده به‌وسیلۀ اوزوی (1994) بهتر است. ژانگ و همکاران^[xv] (2001) عملکرد الگوریتم‌های ارائه‌شدۀ اوزوی (1994) را برای مسئلۀ حداقل‌کردن  در بدترین حالت تحلیل و یک الگوریتم تقریب جدید ارائه کرده‌اند. حسین‌زاده کاشان و همکاران ) 2009) فرضیات مسئلۀ معرفی‌شده در مرجع ژانگ و همکاران (2001) را تعمیم و یک الگوریتم ابتکاری با نسبت عملکرد معلوم ارائه داده‌اند. آنها همچنین یک الگوریتم تقریب برای حالتی ارائه داده‌اند که اندازه و زمان پردازش کارها موافق یکدیگر هستند.

دوپونت و فیلپو^[xvi](2002) مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با کارهایی با اندازۀ غیریکسان را مطالعه کرده‌اند و برای این مسئله یک الگوریتم شاخه و حد ارائه داده‌اند. همچنین رفیعی پارسا و همکارانش^[xvii](2010) برای این مسئله حد پایین مناسبی ارائه‌ و با استفاده از روش تولید ستون و روش شاخه و کران، الگوریتم شاخه و قیمت را برای رسیدن به جواب بهینه پیشنهاد کرده­اند. این الگوریتم قابلیت رقابت با روش شاخه و کرانِ دوپونت و فیلپو(2002) را دارد. مالاپرت و همکارانش^[xviii] (2012) با استفاده از برنامه­ریزی محدودیت­ها همین مسئله را با تابع هدف  بررسی کرده‌اند. کاشان و کریمی (2010) نیز در مقالۀ خود این مسئله را بررسی کرده‌اند و دو روش جدید تولید حد پایین ( ) روی مقدار بهینۀ تابع هدف به‌‌نام‌های  و  ارائه داده‌اند‌. آنها ثابت کرده‌‌اند این روش نسبت به حد پایین  که به‌وسیلۀ اوزوی(1994) ارائه شده است عملکرد بهتری دارد. همچنین در این مرجع ثابت شده است عملکرد  حداقل به‌خوبی عملکرد  است. لی و ژانگ (2018) مسئلۀ حداقل‌کردن زمان انجام کارها را در یک ماشین پردازش دسته‌ای مطالعه کرده‌اند. برخلاف مسائل زمان‌بندی ماشینِ پردازشِ دسته‌ای کلاسیک که در آن ظرفیت یک ماشین به‌صورت مسئلۀ کوله‌پشتی یک‌بعدی مدل‌سازی می‌شود، در این مطالعه ظرفیت ماشین و اندازۀ کارها با مستطیل دوبعدی نشان داده شده است. یک انباشته از کارها زمانی شدنی است که کارها بتوانند بدون هم‌پوشانی با یکدیگر در ماشین قرار بگیرند. کارها دارای اندازۀ متفاوت هستند و با طول، عرض و زمان پردازش نشان داده می‌شوند. هدف، تعیین تعداد انباشته‌ها برای تخصیص کارها به انباشته‌ها به‌نحوی‌ است که زمان انجام کل کارها حداقل شود. مسئلۀ مطالعه‌شده در این مقاله، ترکیبی از مسئلۀ بسته‌بندی اقلام در ظروف به‌صورت دوبعدی (2D-BPP) و مسئلۀ زمان‌بندی ماشین پردازندۀ انباشته (BPM) است. آنها برای حل این مسئله مدل برنامه‌ریزی عدد صحیح مختلط و چند روش ابتکاری ارائه داده‌اند. مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با دو تابع هدف هم‌زمان "حداقل‌کردن زمان تکمیل تمام کارها" و "حداقل‌کردن هزینۀ انرژی کل" به‌وسیلۀ وانگ و همکاران^[xx] (2016) بررسی و این مسئله به‌صورت یک مسئلۀ برنامه‌ریزی عدد صحیح مدل شده است. سپس روش دقیق  محدودیت^[xxi] برای به دست آوردن نقاط پارتوی دقیق و دو روش ابتکاری برمبنای ایدۀ تجزیه برای به دست آوردن نقاط پارتوی تقریبی در مسائل با اندازه‌های بزرگ توسعه یافته است.

حل مسائل زمان‌بندی ماشین‌های پردازندۀ انباشته با فرض وجود کارهای با اندازۀ نامساوی با استفاده از الگوریتم‌های فراابتکاری توجه پژوهشگران زیادی را به‌خود جلب کرده است. ملوکو همکارانش^[xxii](2004) برای مسئلۀ حداقل‌کردن  روی یک ماشین پردازندۀ انباشته با فرض اینکه که زمان پردازش و اندازۀ کارهای مختلف متفاوت است، الگوریتم شبیه­سازی تبرید را استفاده کرده‌اند. نونگ و همکارانش)^[xxiii]2012) همین مسئله را در دو حالتِ مختلف برای اندازۀ کارها بررسی کرده­اند. در حالت نخست اندازۀ کارها یکسان در نظر گرفته و یک الگوریتم تقریب با پیچیدگی زمانی چندجمله­ای ارائه شده است. در حالت دوم نیز اندازۀ کارها متفاوت فرض و یک الگوریتم تقریب پیشنهاد شده است. حسین‌زاده کاشان و همکاران^[xxiv] (2006) نیز این مسئله را بررسی کرده‌اند و برای آن یک الگوریتم ژنتیک برمبنای نمایش کروموزومی براساس کلیدهای تصادفی و یک الگوریتم ژنتیک ترکیبی براساس نمایش کروموزومی ابداعی پیشنهاد کرده­‌اند. نتایج مقایسات آنها نشان می­دهد الگوریتم ژنتیک ترکیبی عملکرد بهتری را نسبت به شبیه­سازی تبریدِ ارائه‌شده به‌وسیلۀ ملوکو همکارانش(2004) دارد. چانگ و سون (2018) مسئلۀ یک ماشین پردازندۀ انباشته با فرض وجود کارها با زمان آزادسازی و اندازه‌های متفاوت را برای حداقل‌کردن زمان انجام کل کارها در نظر گرفته‌اند و یک الگوریتم سیستم ایمنی مصنوعی مبتنی‌بر ایمونوگلوبولین (IAIS) برای حل این مسئله ارائه داده‌اند. الگوریتم مدنظر دو مشخصۀ اصلی دارد؛ نخست اینکه فضای جستجو به فرایند نوسازی جسمی محدود شده است تا زمان محاسبات کاهش یابد و دیگر اینکه ترکیبی از چندین روش جستجوی محلی استفاده شده است تا در هر بار اجرا همسایگی تغییر کند و از بهینگی محلی جلوگیری شود. نتایج محاسبات آنها نشان داده است روش ارائه‌شده عملکرد خوبی دارد.

مسئلۀ حداقل‌کردن هم‌زمان  و  به‌وسیلۀ کاشان و همکاران^[xxv] (2010) مطالعه شده است. برای این مسئله مؤلفین یک الگوریتم ژنتیک دوهدفه ترکیبی ارائه کرده‌اند. نتایج محاسبات آنها نشان می‌دهد این الگوریتم قابلیت یافتن جواب‌های نزدیک به جواب‌های بهینۀ پارتو را دارد. کاشان و کریمی (2008) نیز چارچوبی برمبنای بهینه‌سازی کلونی مورچگان در دو نسخۀ متفاوت ارائه داده‌اند. زو و همکاران^[xxvi] (2012) مسئلۀ حداقل‌کردن  را با فرض وجود زمان‌های ورود پویا برای کارها با اندازۀ غیریکسان روی یک ماشین پردازندۀ انباشته در نظر گرفته‌اند و یک مدل برنامه‌ریزی عدد صحیح مختلط و یک حد پایین معتبر برای این مسئله پیشنهاد داده‌اند. چون این مسئله است، آ‌نها برای حل یک الگوریتم ابتکاری و یک الگوریتم بهینه­سازی کلونی مورچگان برمبنای فرض‌های ارائه‌شده پیشنهاد دادند. نتایج کار نشان می­دهد الگوریتم کلونی مورچگان پیشنهادشده به‌وسیلۀ آنها جواب­های بهتری را در زمان قابل قبولی در مقایسه با دو روش ابتکاری ژنتیک و سیمپلکس تولید می‌کند؛ مخصوصاً زمانی­که اندازۀ کار­ها بزرگ است. لی و همکاران^[xxvii] (2013) الگوریتمی برای مسئله­ای با یک ماشین پردازش انباشته­ با کارهایی ارائه کرده‌اند که دارای موعد تحویلِ مشخص، هستند. در این مسئله، محدودیت­های فازی برای برقراری روابط پیش­نیازی و پس­نیازی اعمال شده ­است. تابع هدف نیز به‌صورت حداقل‌کردن زمان تکمیل تمام کارها تعریف شده ­است. چاندرو و همکاران^[xxviii] (1993) در مقالۀ خود یک روش شاخه و حد برای حداقل‌کردن زمان انجام کل کارها روی یک ماشین ارائه کردند. آنها همچنین برای مسئلۀ ماشین‌های موازی چند روش ابتکاری معرفی کردند. لی و همکارانش^[xxix] (2013) چند روش ابتکاری برای مسئلۀ حداقل‌کردن  روی تعدادی ماشین متفاوت به‌صورت موازی در‌حالت متفاوت‌بودن اندازۀ کارها ارائه کرده­اند.

کوه و همکارانش^[xxx] (2005) برای مسئلۀ پردازش دسته­ای با خانواده­های ناسازگار کارها و اندازۀ متفاوت کارها و سه تابع هدفِ "حداقل‌کردن زمان تکمیل تمام کارها"، "حداقل‌کردن مجموع زمان تکمیل کارها" و "حداقل‌کردن مجموع وزنی زمان تکمیل کارها" مدلی ریاضی ارائه کرده­اند. همچنین برای حل مسائل با اندازۀ واقعی تعدادی روش ابتکاری و یک الگوریتم ژنتیک ترکیبی پیشنهاد کرده­اند. لی ^[xxxi](2012) نیز مسئلۀ حداقل‌کردن  را روی چند ماشین موازی درحالت متفاوت‌بودن اندازۀ کارها در نظر گرفته و برای آن یک الگوریتم تقریب ارائه کرده ­است. در مقالۀ جیا و همکاران^[xxxii] (2017) مسئلۀ زمان‌بندی کارهای با اندازۀ غیریکسان و زمان رسیدن پویا روی مجموعه‌ای از ماشین‌های موازی با ظرفیت متفاوت با هدف حداقل‌کردن  در نظر گرفته شده است. در این مقاله ابتدا مدلی ریاضی برای مسئله ارائه و حد پایینی برای آن معرفی شده است، سپس دو روش فراابتکاری برمبنای الگوریتم کلونی مورچگان برای حل مسئله ارائه شده است. داموداران و همکاران^[xxxiii] (2012) نیز این مسئله را مطالعه کرده‌اند و یک الگوریتم بهینه‌سازی ازدحام ذرات (PSO) را برای حل آن ارائه داده‌اند. در مقالۀ جیا و همکاران^[xxxiv] (2015) نیز همین مسئله، مطالعه و برای حل آن یک روش ابتکاری برمبنای الگوریتم First-Fit-Decreasing (FFD) و یک روش ابتکاری برمبنای الگوریتم Max-Min Ant System (MMAS) ارائه شده است. نتایج این مقاله نشان می‌دهد این دو روش‌ عملکرد بهتری را نسبت به روش ابتکاری معرفی‌شده به‌وسیلۀ داموداران و همکاران (2012) برای این مسئله دارند. از طرف دیگر MMAS عملکرد بهتری در مقایسه با FFD دارد. ژو و همکاران(2018) مسئلۀ حداقل‌کردن  را روی ماشین‌های موازی نامرتبط با فرض وجود کارهای با اندازۀ غیریکسان و زمان‌های آزادسازی دلخواه بررسی کرده‌اند و برای حل این مسئله دو حد پایین و یک الگوریتم ژنتیک برمبنای کدگزاری کلید تصافی ارائه داده‌اند. عملکرد الگوریتم پیشنهادی با یک حل‌کنندۀ تجاری (ILOG CPLEX)و دو روش فراابتکاری موجود در ادبیات (الگوریتم حریصانه و الگوریتم بهینه‌سازی ازدحام ذرات) مقایسه شده و آزمایش‌ها محاسباتی نشان داده است الگوریتم پیشنهادی در مقایسه با روش‌های دیگر راه‌حل‌های بهتری را تولید می‌کند. آنها همچنین کیفیت حدود پایین پیشنهادی را ارزیابی کرده‌اند و نشان داده‌اند که از حدود پایین موجود، عملکرد بهتری دارد. ارویو و همکاران^[xxxv] (2017) مسئلۀ زمان‌بندی مجموعه‌ای از کارهای با اندازۀ متفاوت و زمان آماده‌سازی غیر‌صفر را روی مجموعه‌ای از ماشین‌های موازی غیرمرتبط برای حداقل‌کردن  در نظر گرفته‌اند و برمبنای الگوریتم‌های FF^[xxxvi] و BF^[xxxvii]، چند روش ابتکاری برای مسئله توسعه داده‌اند. در این مرجع یک مدل برنامه‌ریزی عدد صحیح مختلط و یک حد پایین برای ارزیابی کیفیت ابتکاری‌ها ارائه شده است.

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

تعریف مسئله و مفروضات

مسئله‌ای که در این پژوهش درحال بررسی است، مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهای با اندازۀ غیریکسان است. مفروضات مسئله به‌شرح زیر است:

1- تعداد n کار برای زمان‌بندی روی یک ماشین پردازش انباشته وجود دارد که همگی در لحظۀ صفر در سیستم در دسترس هستند. کلیۀ کارها با یکدیگر سازگار وتنها متعلق به یک خانواده هستند (زمان‌بندی بدون خانواده‌های کارها).

2- با شروع عملیات ماشین روی یک انباشته، توقف عملیات امکان‌پذیر نیست و پیش از اتمام عملیات ماشین، هیچ‌کاری نمی‌تواند به انباشته اضافه و یا از آن خارج شود.

3- مقادیر زمان‌های پردازش و اندازۀ کارها از قبل مشخص و قطعی هستند.

4- زمان شروع و زمان ختم عملیات تمامی کارهایی که متعلق به یک انباشته هستند با یکدیگر یکسان است. زمان پردازش انباشته نیز برابر زمان پردازش کاری است که بین سایر کارهای متعلق به انباشته زمان پردازش لازم برای آن طولانی‌تر است.

5- حداکثر ظرفیت ماشین برای انجام عملیات هم‌زمان روی کارها برابر Bاست؛ به عبارت دیگر مجموع ابعاد کارهای متعلق به یک انباشته نباید از مقدار B متجاوز شود. همچنین فرض می‌شود کلیۀ کارها دارای اندازه‌ای کوچک‌تر یا مساوی با ظرفیت ماشین است.

6- خرابی ماشین(ها) مجاز نیست.

ماشین‌های پردازش انباشته در مقایسه با سایر عملیات تولید و تست دارای زمان انجام عملیات طولانی‌تری هستند و ایستگاه گلوگاه تولید به‌شمار می‌روند؛ بنابراین میزان بهره‌برداری زیاد از ماشین(ها) در این عملیات باعث افزایش توان عملیاتی کل سیستم می‌شود. ازآنجا‌که میزان بهره‌برداری بیشتر به‌معنی کاهش زمان انجام عملیات کلیۀ کارها (یا به‌طور معادل مقدار C_max) با ماشین‌ها است، معیار عملکرد، حداقل‌کردن C_max است.

اندیس‌ها و نمادها

j : نشانگر کار jام، j=1,2,…,n (n تعداد کل کارها برای زمان‌بندی).

: زمان پردازش کار jام.

: زمان پردازش کار jام.

B: حداکثر ظرفیت ماشین.

مجموعه‌ها.

S: مجموعۀ اندازۀ کارها.

P: مجموعۀ زمان پردازش کارها.

: مجموعه کارهایی که اندازۀ آنها بزرگ‌تر از uو کوچک‌تر یا مساوی با v است.

: مجموعه کارهایی که اندازۀ آنها بزرگ‌تر یا مساوی با uو کوچک‌تر یا مساوی با v است.

حدود بالا و پایین

در این بخش روش‌های تولید حد پایین و بالای موجود برای مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهایی با اندازۀ غیریکسان بررسی می‌شود و در بخش بعد در بدنۀ روش شاخه و حد به ‌کار گرفته می‌شود.

حدود بالا

در این پژوهش از دو الگوریتم FFLPT^[xxxviii] (اوزوی، 1994) وBFLPT^[xxxix] (دوپونت و جولای، 1998) برای تولید حدود بالا استفاده شده است و کمترین مقدار از بین این دو در مراحل حل مسئله برای حد بالا لحاظ شده است.

حدود پایین

ازجمله مهم‌ترین کاربردهای حدود پایین، استفاده از آنها در بدنۀ الگوریتم‌های دقیق مانند روش شاخه و حد است. در این مقاله تلاش شده است از حدود پایین ، (اوزوی، 1994)، و ، (کاشان و کریمی، 2012) برای تولید حد پایین در الگوریتم شاخه و کران استفاده و نتایج مقایسه شود. درادامه الگوریتم‌های مذکور تشریح می‌شود.

الگوریتم

روش کار در این الگوریتم به‌صورت زیر خلاصه شده است:

گام1. ابتدا کلیۀ کارها را به‌ترتیب نزولیِ زمان پردازش­شان مرتب کنید.

گام2. با شروع از ابتدای لیست، نخستین کار را در تنها انباشته­ای قرار دهید که به­طور کامل پر نشده است (ظرفیت استفاده‌نشدۀ آن از B یعنی ظرفیت انباشته کمتر است). اگر همۀ انباشته­ها به حد بالای ظرفیت خود رسیده باشند یک انباشتۀ جدید تشکیل دهید و اگر فضای لازم برای قراردادن کار در انباشتۀ مذکور وجود ندارد، قسمتی از کار را که ظرفیت خالی انباشته را به‌طور کامل اشغال می­سازد درون انباشته قرار دهید. سپس یک انباشتۀ جدید تشکیل و باقیماندۀ کار خرد‌شده را در آن قرار دهید.

گام3. این فرآیند را تا زمانی تکرار کنید که هیچ‌کاری در لیست باقی نمانده باشد. بدین ترتیب تعداد انباشته­های حاصل برابر  است.

مبنای الگوریتم اشاره‌شده در بالا براساس آزادسازی است. بدین ترتیب که در آن فرض مجازنبودن شکست کارها به اجزا، آزاد شده است. هنگامی‌که اندازۀ کارها نسبت به ظرفیت ماشین کوچک است، عملکرد متوسط  خوب تلقی می‌شود؛ درواقع ثابت شده است هرچقدر اندازۀ کارها نسبت به ظرفیت ماشین کوچک‌تر شود عملکرد  در بدترین حالت بهتر می‌شود. براساس تجربه نیز ثابت شده است برای بسیاری از مسائلی که در آنها اندازۀ کارها نسبت به ظرفیت ماشین کوچک است، مقدار حد پایین تولیدشده به‌وسیلۀ  با مقدار  برابر است؛ اما عملکرد  زمانی تقلیل می‌یابد که اندازۀ کارها به نسبت بزرگ باشد. کاشان و کریمی )2012) از این نقطه ضعف برای تولید حدود پایین جدید استفاده و حد پایین  و  را معرفی کرده‌اند.

الگوریتم

برای دست­یابی به یک حد پایین روی مقدار  به‌ازاءِ مقادیر مختلف ε (ε ≤ B/2) تنها اجازه داده می‌شود کارهایی شکست‌پذیر باشد که اندازۀ آنها در دامنۀ [ε, B- ε] باشد. فرض کنید  دلالت بر مجموعه کارهایی داشته باشد که اندازۀ آنها بزرگ‌تر از uو کوچک‌تر یا مساوی با v است. به‌طور مشابه تعریف می‌شود . روش زیر با عنوان NLB یک حد پایین معتبر را روی مقدار  به دست می­دهد.

گام1. به‌ازاءِ ، یک حد پایین را روی مقدار  به‌صورت زیر محاسبه کنید.

که در آن  مقدار حد پایین به‌دست‌آمده به‌وسیلۀ  براساس مجموعه کارهایی است که اندیس آنها متعلق به مجموعۀ  است.

گام2. با تکرار گام 1 به‌ازاءِ تمامی مقادیرε، بزرگ‌ترین مقدار به‌دست‌آمده برای  یک حد پایین روی مقدار  است؛ یعنی:

این الگوریتم یک حد پایین معتبر روی مقدار  به دست می­دهد. همچنین ثابت شده است مقدار حد پایینِ حاصل از الگوریتم  بیشتر از حد پایین تولید‌شده به‌وسیلۀ الگوریتم  است؛ اما درادامه حد  معرفی می‌شود که عملکرد آن از هر دو الگوریتم  و  بهتر است؛ بنابراین پس از معرفی این حد از آن برای حد پایین در روش شاخه و کران استفاده می­شود.

الگوریتم  

 ازآنجا‌که دو کاری که اندازۀ آنها در بازۀ  قرار می‌گیرد نباید در یک انباشته باشند، هنگامی‌که ، ممکن است مقدار حد  قوی‌تر شود؛ ازاین‌رو حد  به‌صورت زیر تعریف می­شود.

که در آن

الگوریتم  

با استفاده از ایدۀ تفکیک کارها درقالب سه مجموعه، حد پایین LB3 به‌صورت زیر ارائه شده است.

که در آن،  مقدار بهینۀ C_maxدر زیرمسئله‌ای از مسئلۀ اصلی است که فقط کارهای با اندازۀ بزرگ‌تر از  در نظر گرفته شده‌ است.

طبق تعریف، مجموعه کارهایی که اندیس آنها در مجموعۀ S(B/3,B)قرار دارد درقالب سه زیرمجموعه تفکیک می‌شود؛ نخستین زیرمجموعه به‌صورت ، دومین زیرمجموعه به‌صورت  و سومین زیرمجموعه به‌صورت  است. همچنین مجموعۀ x به‌این‌صورت تعریف می‌شود؛  که در آن  مجموعه‌ای از زیرمجموعۀ دوم است و می­تواند با یکی از کارهای مجموعۀ سوم گروه­بندی شوند. بدین ترتیب باتوجه‌به ترکیب‌بندی کارها به‌صورت بالا می‌توان  را به‌صورت رابطۀ زیر ارائه کرد.

بنابراین با محاسبۀ مقدار  می‌توان به مقدار  رسید. درنهایت  به‌صورت رابطۀ زیر نمایش داده می‌شود.

که مقدار  ازطریق تبدیل مسئلۀ زمان‌بندی مربوطه به یکی از مسائل شناخته‌شده در نظریۀ گراف (مسئلۀ حداکثر تطابق وزنی) به دست می‌آید. لازم به ذکر است در محاسبۀ الگوریتم  باید یک مسئلۀ حداکثر تطابق وزنی حل شود که در پژوهش‌ قبل از جعبۀ بهینه‌سازی موجود در نرم‌افزار متلب استفاده شده است و مبتنی‌بر روش شاخه و حد عمل می­کند؛ اما در این پژوهش از الگوریتم ادموند (گابو^[xl] ،1976) برای حل این مسئله استفاده شده است. این الگوریتم قادر است در زمان چندجمله­ای مسئلۀ مدنظر را حل کند؛ بنابراین در زمان حل الگوریتم بهبود حاصل شده است.

روش شاخه و حد

در این بخش برای محاسبۀ حداقل  در مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با اندازۀ کارهای غیریکسان، الگوریتم شاخه و کرانی به کار گرفته شده است که برمبنای روش دوپونت و فیلیپو (2002) است. برای شاخه‌زدن در الگوریتم شاخه و کران، در هر مرحله باید دو تصمیم گرفته شود؛ نخست کار انتخابی باید به انباشتۀ جاری اضافه شود یا در انباشتۀ جدید قرار بگیرد و دوم اینکه مشخص شود کدام کار باید به انباشته اضافه شود. همچنین دو روش برای اضافه‌کردن یک کار جدید به جواب جزئی (p) وجود دارد که عبارتند از:

1- نوع یک: در این نوع، کار جدید در یک انباشتۀ جدید قرار می‌گیرد.

2- نوع دو: در این نوع، کار جدید به انباشتۀ موجود در P اضافه می‌شود، به‌طوری‌که انباشته ظرفیت پذیرش کار جدید را داشته باشد.

در سطح نخست از درخت شاخه و کران، در هر جواب جزئی P، دقیقاً یک کار در یک انباشته قرار می‌گیرد. زمانی‌که یک گره برای شاخه‌زدن انتخاب می‌شود، فهرستی از کارهای موجود که هنوز زمان‌بندی نشده‌اند برای اضافه‌شدن به P در نظر گرفته می‌شود. یک مثال از نحوۀ شاخه‌زدن یک مسئله با تعداد 3n= کار با اندازۀ یک و 3B= در شکل 1 آورده شده است. سطح نخست از درخت تنها شامل گره‌های نوع یک است که درواقع هر کار در انباشتۀ مربوط به خود قرار می‌گیرد. در سطح بعدی درخت، گره‌های نوع یک و نوع دو تولید هستند. کارهایی که با هم در یک پرانتز قرار دارند نشان‌دهندۀ کارهایی است که در یک انباشته با هم پردازش می‌شوند. باتوجه‌به اینکه ترتیب قرارگرفتن کارها در انباشته‌ها اهمیتی ندارد و کارهای موجود در یک انباشته به‌صورت هم‌زمان پردازش می‌شوند و زمان شروع و پایان یکسانی دارند، تعداد زیادی از جواب های جزئی ایجاد‌شده تکراری هستند؛ برای مثال دو جواب جزئی ((23)(1)) و ((32)(1)) یکی هستند. برای افزایش کارایی الگوریتم از سه نکتۀ اشاره‌شده درادامه استفاده شود تا از این تکرارها در الگوریتم شاخه و کران اجتناب کرد (دوپونت و فیلیپو، 2002):

الف) ابتدا کارها را براساس زمان پردازششان از بیشتر به کمتر(به‌صورت نزولی) مرتب کنید.

ب) برای شاخه‌زدن، درصورتی‌که گره فرزند از نوع دوم باشد باید زمان پردازش کار جدیدی که قرار است به انباشته اضافه شود از زمان پردازش مابقی کارهایِ موجود در انباشته کمتر یا مساوی باشد.

ج) در نظر نگرفتن جواب‌های جزئی‌ که انباشته‌هایی با کارهای یکسان دارند؛ برای مثال دو جواب جزئی ((1) (32)) و ((32)(1)) یکی هستند و می‌توان یکی از آنها را در نظر نگرفت.

شکل 1- نحوۀ شاخه‌زدن در درخت شاخه و کران

در روش شاخه و کران برای رسیدن به جواب بهینه به حدود بالا و پایین احتیاج است. هرچه مقدار این حدود بالا و پایین به یکدیگر نزدیک­تر باشد، این روش سریع‌تر به جواب می­رسد و تعداد گره­های کمتری بررسی می­شود. در اینجا برای محاسبۀ مقدار اولیه از هر دو روش ابتکاری FFLPT و BFLPT استفاده شده است و کمترین مقدار از بین آنها برای یک حد بالا در مسئله استفاده می­شود. برای توصیف این الگوریتم، اگر مجموعه کارهای زمان‌بندی‌نشده مجموعۀ j نامیده شود، برای به ­دست آوردن یک حد پایین روی مجموعۀ j می­توان از الگوریتم تولید حدود پایین ذکر‌شده در بخش قبل استفاده کرد. مقدار حد پایین روی مجموعۀ j، BInf(j) نامیده می‌شود (اگر j مجموعۀ کل کارها باشد، این حد پایین با Cmin نشان داده می­شود). فرض کنید Valbest مقدار بهترین جواب شناخته‌شده و Valsol جواب جزئی مسئلۀ زمان‌بندی روی انباشتۀ نخست تا انباشتۀ فعلی باشد، دراین‌صورت اگر ، می­توان این گره را قطع کرد؛ چون جواب بهتری تولید نمی‌کند؛ درغیراین‌صورت با استفاده از یک الگوریتم حریصانه جوابی شدنی روی مجموعۀ j تولید کنید و آن را valgreedy نام‌گذاری کنید (در اینجا از FFlPT استفاده شده است). درصورتی‌که  باشد، درواقع یک بهترین جواب جدید به دست آمده است. همچنین اگر  جواب بهینه روی j به ­دست آمده باشد، می‌توان عملیات را در این گره به پایان رساند. در حالت کلی در دو حالت الگوریتم به پایان می­رسد؛ نخست اینکه جواب بهینه برای مسئله پیدا شود و یا زمان در نظر گرفته شده برای حل مسئله به پایان برسد. در روش حاضر برای تولید حد پایین از الگوریتم‌های  و  و  استفاده و نتایج آنها با هم مقایسه شده است. تجربه ثابت کرده است این الگوریتم‌ها بسیار سریع هستند و جواب‌های نزدیک به بهینه را تولید می‌کنند. درادامه برای بررسی کیفیت جواب‌های حاصل‌شده، درصورت استفاده از حدود پایین  و  و  و انجام مقایسات، یک برنامۀ کامپیوتری در نرم‌افزار متلب نوشته و آزمایش‌ها روی یک رایانه با RAM 4 Gb و CPU 40/2 GHz انجام شده است.

بحث و نتایج محاسباتی

برای ارزیابی عملکرد حدود پایین ارائه‌شده و به دست آوردن جواب بهینه برای مسئلۀ مد‌نظر، دسته‌ای از نمونه مسائل به‌صورت تصادفی در نرم‌افزار متلب تولید شده است‌ و روش‌های ارائه‌شده در بخش قبل روی این داده‌ها آزمایش شده‌اند. ابتدا داده‌های استفاده‌شده بررسی و سپس نتایج محاسبات درقالب جداول و شکل‌ها در بخش بعد ارائه می‌شوند.

برای انجام آزمایش‌های محاسباتی، 6 مجموعه مسئله در نظر گرفته شده است. برای هر نمونه مسئله دو سطح از زمان پردازش و 5 سطح از اندازۀ کارها بررسی می‌شود. همچنین برای هر مجموعه، 10 نمونه مسئله به‌صورت تصادفی تولید شده است؛ درنتیجه تعداد مسائلی که در هر بخش آزمایش می‌شود برابر 600 است. این مسائل در جدول 1 به‌تفصیل آورده شده است.

جدول 1- دسته‌بندی مسائل

برای انجام آزمایش‌های محاسباتی، مجموعه مسائل مطرح‌شده در جدول 1) در نظر گرفته و مقادیر جواب بهینه برای آنها حساب شده‌ است. درادامه نتایج محاسبات درقالب جدول 2 تا 5 آورده می‌شوند.

جدول 2- شاخه و کران ,pj [1,10] B=10

جدول 3- روش شاخه و کران ,pj [1,10] B=5

جدول 4- روش شاخه و کران B=5, pj [1,5]

جدول 5- روش شاخه و کران pj [1,5],B=10

در این جداول  نشان‌دهندۀ اندازۀ کارها و #opt نمایانگر تعداد مسائلی است که جواب بهینۀ آنها در زمان کمتر از 1800 ثانیه به ‌دست آمده است. همچنینAvg. Nodes میانگین تعداد گره‌های بررسی‌شده برای رسیدن به جواب بهینه و Avg times میانگین زمان اجرای برنامه برای ده نمونه مسئله را نشان می‌دهد. Avg (LB1)و Avg ( ) وAvg.( )به‌ترتیب نشانگر میانگین حدود پایین ، ،  و Avg (UB) میانگین حد بالا برای ده نمونه مسئله هستند. لازم به ذکر است، Gap که میانگین شکاف بهینگی نامیده می‌شود، برای مسائلی محاسبه می‌شود که جواب بهینه در زمان 1800 ثانیه به دست نمی‌آید. میانگین شکاف بهینگی از رابطۀ زیر حاصل می‌شود:

در جدول 2) ظرفیت انباشته برابر 10 و زمان پردازش کارها به‌طور تصادفی در بازۀ ]10-1[ در نظر گرفته شده است. همان‌طورکه مشاهده می‌‌شود زمانی‌که اندازۀ کارها بزرگ باشد، زمان اجرای الگوریتم شاخه و حد نیز افزایش می‌یابد. هنگامی‌که از حد پایین  در الگوریتم استفاده شود، افزایش زمان اجرا بیشتر است؛ زیرا ازآنجایی‌که حد پایین  نسبت به  و عمکرد ضعیف‌تری دارد، زمان اجرای الگوریتم نسبت به حالتی‌‌که از حد پایین  و استفاده شود به‌‌طور چشم‌گیری افزایش پیدا می‌کند. بیشترین زمان در نظر گرفته شده برای اجرای این الگوریتم 1800 ثانیه است که در این زمان یا الگوریتم جواب بهینه را پیدا می‌کند یا با بهترین جواب پیدا‌شده در این زمان متوقف می‌‌شود. باتوجه‌به نتایج جدول نتیجه می‌شود وقتی اندازۀ کارها در بازۀ ]10-1[ باشد و تعداد کارها 60 انتخاب شود، عملکرد  کاهش شدیدی می‌یابد و الگوریتم شاخه و کران زمان اجرای بیشتری می‌طلبد؛ درنتیجه در زمان تعیین‌شده این الگوریتم فقط قادر به حل بهینۀ نیمی از مسائل است. درصورتی‌که اگر از حدود پایین  و  در بدنۀ روش شاخه و کران استفاده شود، برای هر ده نمونه مسائل، جواب بهینه به دست می‌آید. هنگامی‌که تعداد کارها افزایش ‌یابد و برابر80 تا 100 انتخاب ‌شود الگوریتم شاخه و کران با حد پایین  قادر به یافتن جواب بهینۀ هیچ‌کدام از مسائل در زمان تعیین‌شده نیست. درحالی‌که اگر از حد پایین  و  استفاده شود بیش از نیمی از مسائل در زمان مدنظر به جواب بهینه می‌رسند. در‌این‌حالت از نظر زمان اجرا عملکرد  از بهتر است. البته برای مسائلی که در زمان تعیین‌شده به جواب بهینه نمی‌رسند مقدار  از رابطۀ (7) محاسبه می‌شود که این مقدار درصورت استفاده از کمتر می‌شود؛ یعنی در‌صورتی‌که از حد پایین  در روش شاخه و کران استفاده شود و الگوریتم در زمان تعیین‌شده به جواب بهینه نرسد جواب به‌دست‌آمده در زمان مذکور نزدیک‌تر از حالتی است که از حد پایین  استفاده شود؛ زیرا الگوریتم تولید حد پایین نسبت به دو الگوریتم دیگر حد پایین قوی‌تری تولید می‌کند.

اگر اندازۀ کارها در بازۀ ]8-4[ انتخاب شود، درحالتی‌که تعداد کارها کمتر یا مساوی 60 باشد، هر سه الگوریتم جواب بهینه را در زمان تعیین‌شده می‌یابند؛ با این تفاوت که روش شاخه و حدی که از حد پایین  استفاده می‌کند بهترین و  بدترین عملکرد را از نظر زمان اجرا دارند؛ اما هنگامی‌که تعداد کارها زیاد شود (بیشتر از 60 کار)  بهترین عملکرد را دارد. زمانی‌که اندازۀ کارها کوچک باشد (حداکثر به‌اندازۀ نصف ظرفیت ماشین باشد) الگوریتم شاخه و کران با حد پایین  بهترین عملکرد و بدترین عملکرد را از نظر زمان اجرا دارد. درواقع زمانی‌که ظرفیت انباشته زیاد و اندازۀ کارها کوچک باشد  عملکرد بهتری دارد و قادر به یافتن جواب بهینه در زمان کمتری نسبت به  و  است.

در جدول (3) Error! Reference source not found.ظرفیت انباشته کاهش یافته و برابر 5 در نظر گرفته شده است. زمان پردازش کارها نیز به‌‌طور تصادفی در بازۀ ]10-1[ در نظر گرفته شده است. وقتی اندازۀ کارها در بازۀ ]5-1[ است،  بهترین عملکرد را دارد و در زمان کمتری به جواب بهینه می‌رسد؛ اما هنگامی‌که اندازۀ کارها در بازۀ ]4-2[ قرار می‌گیرد روش شاخه و حد با هر سه حد معرفی‌شده، جواب بهینۀ مسائل را در زمان تعیین‌شده به‌ دست می‌آورد؛ چون اندازۀ کارها کاهش می‌یابد. اگرچه در‌این‌حالت نیز ابتدا  و سپس  بهترین عملکرد را دارد. در جداول (4) و (5) زمان پردازش کارها نسبت به جداول (2) و (3) کاهش یافته است و نتایج محاسبات نشان می‌دهد اگر زمان پردازش کارها کاهش یابد سرعت اجرای الگوریتم شاخه و حد افزایش می‌یابد.

برای نمایش بهتر، نتایج روش شاخه و حد درقالب شکل 1 تا شکل 3ارائه شده است. این شکل‌ها به‌ترتیب تعداد گره‌های بررسی‌شده، زمان و تعداد مسائل حل‌شدۀ بهینه را در‌صورت استفاده از حدود پایین  و  و  نشان می‌دهد.

شکل (1) میانگین تعداد گره‌های بررسی‌شده با الگوریتم شاخه و کران با حدود پایین مختلف را نشان می‌دهد. همان‌طورکه دیده می‌شود وقتی اندازۀ کارها کوچک‌تر یا مساوی نصف ظرفیت ماشین باشد میانگین تعداد گره‌های بررسی‌شده به‌وسیلۀ هر سه حد پایین برابر است و همۀ مسائل در زمان مشخص‌شده حل شده‌اند؛ اما زمانی‌که اندازۀ کارها نسبت به ظرفیت ماشین بزرگ می‌شود پیچیدگی مسئله افزایش می‌یابد و در درخت شاخه و حد میانگین تعداد گره‌های بررسی‌شده برای رسیدن به جواب بهینه زیاد می‌شود. در‌این‌حالت حد پایین  عملکرد ضیفی دارد و بهتر است از حدود پایین دیگر در بدنۀ شاخه و حد استفاده شود. دربارۀ استفاده از حد پایین  باید گفت که اگر‌چه کیفیت حدود پایینی که تولید می‌کند از دو الگوریتم دیگر بهتر است، زمان اجرای الگوریتم بیشتر است؛ چون در یکی از گام‌های الگوریتم باید مسئلۀ حداکثر تطابق وزنی حل شود. هرچند در این پژوهش از الگوریتم ادموند (که باعث بهبود زمان اجرای الگوریتم می‌شود) برای حل مسئله استفاده شده است، به ‌نظر می‌رسد اگر از زبان‌های برنامه‌نویسی با سرعت بیشتر مثل C استفاده شود سرعت اجرای الگوریتم افزایش می‌یابد و در مسائل با اندازۀ کارهای بزرگ کارایی بهتری نسبت به حدود پایین دیگر دارد. شکل 3 تعداد مسائل حل‌شدۀ بهینه را با استفاده از روش شاخه و حد در زمان تعیین‌شده نشان می‌دهد. در این شکل نیز عملکرد بهتر حدود  و  نبست به حد  در نمونه مسائل با کارهای با اندازۀ بزرگ به‌وضوح مشخص است.

شکل 1- نتایج تعداد گره‌های بررسی‌‌شده با استفاده از روش شاخه و حد

شکل 2- نتایج زمان حل مسائل با استفاده از روش شاخه و حد

شکل 3- نتایج تعداد مسائل حل‌شدۀ بهینه با استفاده از روش شاخه و حد

نتیجه‌گیری

در این مقاله روش شاخه و حد برای حل مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهای با اندازۀ غیریکسان ارائه شد. در این روش برای تولید حد بالا از دو روش ابتکاری FFLPT و BFLPT استفاده و کمترین مقدار از بین آنها برای یک حد بالا در مسئله به کار گرفته شد.هم‌چنین برای تولید حد پایین از سه الگوریتم  و  و  استفاده و نتایج آنها با هم مقایسه شد. در محاسبۀ الگوریتم  باید یک مسئلۀ حداکثر تطابق وزنی حل شود که در پژوهش قبل از جعبه بهینه‌سازی موجود در نرم‌افزار متلب استفاده شده است و مبتنی‌بر روش شاخه و حد عمل می­کند؛ اما در این پژوهش از الگوریتم ادموند برای حل این مسئله استفاده شد و قادر است در زمان چندجمله­ای مسئلۀ مدنظر را حل کند؛ بنابراین در زمان حل الگوریتم، بهبود حاصل شده است. نتایج محاسبات نشان داد که در الگوریتم شاخه و کرانِ استفاده‌شده، وقتی اندازۀ کارها نسبت به ظرفیت ماشین بزرگ باشد حد پایین  بهترین عملکرد را دارد؛ زیرا کیفیت حدود پایینی که تولید می‌کند از  و زمان اجرای آن نیز از الگوریتم  بهتر است؛ بنابراین تعداد مسائلی که جواب بهینۀ آنها در زمان تعیین‌شده به‌دست آمده است بیشتر از حالتی است که از دو حد پایین دیگر استفاده شود؛ اما وقتی اندازۀ کارها نسبت به ظرفیت ماشین کوچک باشد (حداکثر به‌اندازۀ نصف ظرفیت ماشین) الگوریتم شاخه و کران با حد پایین  بهترین عملکرد را دارد. همچنین وقتی اندازۀ کارها متوسط باشد  بهترین عملکرد را دارد؛ بنابراین طبق نتایج به‌دست‌آمده از این پژوهش، با‌توجه‌به اندازۀ کارها از حدود پایین مختلف استفاده می‌شود و نتایج روش شاخه و حد بهبود می‌یابد.

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