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

در این مقاله مسئله زمان بندی ماشین پردازنده انباشته با فرض وجود کارهایی با اندازه غیریکسان و با هدف حداقل کردن زمان انجام کل کارها (Cmax) بررسی شده است. هدف این مقاله، حل مسئله مدنظر با بهره گیری از حدود پایین قوی و با استفاده از الگوریتم شاخه و کران حد، یکی از روش های حل دقیق، است. در این الگوریتم از دو روش جدید به نام های  و  برای تولید حد پایین استفاده و نتایج با حد پایین موجود در ادبیات به نام  مقایسه شده است. برای ارزیابی عملکرد روش ارائه شده، دسته ای از نمونه مسائل به صورت تصادفی تولید و روش شاخه و حد با حدود پایین متفاوت روی این مسائل آزمایش شده است. نتایج محاسبات نشان می دهد در الگوریتم شاخه و کران وقتی اندازه کارها نسبت به ظرفیت ماشین بزرگ باشد، حد پایین  بهترین عملکرد را دارد و زمانی که اندازه کارها نسبت به ظرفیت ماشین کوچک باشد (حداکثر به اندازه G نصف ظرفیت ماشین)، الگوریتم با حد پایین  عملکرد بهتری دارد. همچنین زمانی که اندازه کارها متوسط باشد،  بهترین عملکرد را دارد.