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

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

Developing a Lagrangian Relaxation Method for Flexible Flowshop Scheduling Problem

Flexible flow shop scheduling problem (FFS) with unrelated parallel machines contains sequencing in flow shop where, at any stage, there exists one or more unrelated parallel machines. The objective consists of minimizing the maximum completion time. A new Lagrangian relaxation (LR) method is developed to solve the candidate problem. To solve the subproblems in LR, we use two approaches such as, simplicity of subproblems and dominance rules. The results show that the both approaches can achieve the nearoptimal solution in reasonable time but there is no significant difference between them. On the other side, simplicity of subproblems can achieve the solution in reasonable time.