حد پایین

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