الگوریتم بهینه تعیین توالی عملیات در مسئله یک ماشین بازود کرد و دیرکرد

نویسنده

چکیده

مسئلۀ تعیین توالی مجموعه ای از کارها با معیار کمینه سازی بیشینه های زودکرد و دیرکرد در یک ماشین مورد بررسی قرار گرفته است. این معیار می تواند منطبق بر سیستمهای تولیدی مختلفی از جمله JIT باشد. این معیار در حالتهای خاص بررسی شده و جواب بهینۀ آنها با ترتیبهای ساده ارائه شده است. برای حالت کلی شرایط همسایگی موثری توسعه داده شده و مجموعۀ غالب، برای جواب بهینه مشخص شده است. همچنین روش شاخه و کرانه برای این معیار به کار گرفته شده است. ارائۀ حدود بالا و پایین قوی موجب شده که در روش شاخه و کرانه، بسیاری از مسائل در مدت زمانهای کوتاه به جواب بهینه برسند. 720 مسئله در اندازه های کوچک، متوسط و بزرگ به صورت تصادفی تولید شده است. محدودۀ این مسائل از 5 کار تا 100 کار بوده و کارایی الگوریتم پیشنهادی در آنها نشان داده شده است.

عنوان مقاله [English]

An Optimum Algorithm for Single Machine with Early/Tardy Cost

نویسنده [English]

  • M. Amin-Nayeri and G. Moslehi
چکیده [English]

The problem of determining the sequence of a set of jobs with the objective function of minimizing the maximum earliness and tardiness in one machine is studied. Production systems like JIT are one of the many applications of the problem. This problem is studied in special cases and their optimal solutions are introduced with simple orders. In general, some effective conditions for neighboring jobs have been developed and the dominant set for the optimal solution is determined. Branch and Bound (BB) method is also used for this problem. The strong upper and lower limits are introduced in BB, resulting in optimal solutions to a lot of problems in short time periods. To show the effectiveness of the suggested solution methods, as many as 720 problems in different sizes, with 5 to 100 jobs, have been randomly generated and solved.

تحت نظارت وف ایرانی