توسعه روش آزادسازی لاگرانژین برای حل مسأله زمانبندی در محیط جریان کارگاهی انعطاف پذیر

Abstract

مسأله زمانبندی در محیط جریان کارگاهی انعطاف­پذیر شامل تعیین توالی در یک مسأله جریان کارگاهی می­باشد که در هر مرحله حداقل یک یا چند ماشین موازی غیرمشابه وجود دارد. تابع هدف مسأله کمینه­سازی حداکثر زمان تکمیل کارها می­باشد. برای حل این مسأله از روش آزادسازی لاگرانژین استفاده‌شده است. برای حل زیرمسأله­های تولیدشده با استفاده از روش آزادسازی لاگرانژین نیز از دو رویکرد ساده­سازی زیرمسأله­ها و توسعه قوانین چیرگی استفاده‌شده است. نتایج نشان می­دهد که هر دو روش می­توانند به جواب­های نزدیک به بهینه در زمان­های نسبتاً معقول دست پیدا کنند ولی تفاوت معناداری با یکدیگر ندارند. همچنین روش ساده­سازی زیرمسأله‌ها در مدت زمان کوتاه­تری می­تواند به جواب­های مورد نظر دست یابند.