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

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