بخشی از مقاله
چکیده:
در این مقاله، پس از بررسی دو مدل مساله زمانبندی تک ماشینی فازی، این دو مساله زمانبندی فازی را به مساله معادل تخصیص فازی تبدیل میکنیم. در این دو مساله زمانهای پردازش مشاغل و نیز زمانهای تحویل، اعداد فازی مثلثی در نظر گرفته شدهاند. از طرفی مساله زمانبندی فازی مذکور با مدل تخصیص فازی هم ارز است که میتوان آن را به عنوان یک مساله بهینهسازی فازی با روشهای موجود حل کرد. در این مقاله، مدل تخصیص مذکور به روش استفاده از تابع رتبهبندی حل میشود. برای روشن شدن روش پیشنهادی یک مساله زمانبندی با 10 شغل حل می گردد.
کلمات کلیدی:مساله تخصیص فازی؛ مساله زمانبندی فازی؛ تابع رتبهبندی.
-1 مقدمه
زمانبندی به فرآیندی تصمیم گیری در کارخانجات و صنایع مختلف اتلاق میشود که هدف آن تخصیص منابع و فعالیتها در بازههای زمانی معین با هدف بهینهسازی اهداف از پیش تعیین شده است .[1] منابع و فعالیتها در یک سازمان میتوانند به شکلهای مختلف ظاهر شوند. به عنوان مثال ماشینها در یک کارگاه، باندهای پرواز هواپیما در یک فرودگاه، کارکنان یک موسسه، واحدهای پردازش در یک محیط محاسباتی و... همه مثالهایی از منابع هستند. برای برنامه ریزی و زمانبندی مشاغل در حالات مختلف، تعیین زمان دقیق پردازش کاری دشوار است. همچنین تعیین زمانهای موعد تحویل نیز در واقعیت ممکن است نادقیق و غیر قطعی باشند. یکی از رویکردهایی که میتوان برای مدلسازی عدم قطعیت در مساله زمانبندی در نظر گرفت، نظریه مجموعه های فازی است.
در [3] نویسندگان مقاله زمانهای پردازش و نیز موعد تحویل را اعداد فازی در نظر گرفته و از نظریه امکان و توابع عضویت برای مدلسازی عدم قطعیت استفاده کردند. در [2] مساله زمانبندی تک ماشینی با دسته های موازی از مشاغل در نظر گرفته شد که زمانهای تحویل و نیز روابط پیشنیازی به صورت فازی بودند. در این مقاله، دو مدل زمانبندی تک ماشین با زمانهای پردازش و تحویل فازی معرفی و با تبدیل آنها به مدل تخصیص فازی روشی برای حل پیشنهاد میگردد.در ادامه این بخش، برخی از پیشنیازهای لازم از نظریه مجموعههای فازی معرفی میگردد.تعریف.1 یک عدد فازی مثلثی توسط سه تای نشان داده شده که تابع عضویت آن به صورت زیر است:
-2 بررسی مدل تک ماشینه با هدف کمینهسازی مجموع وزندار زمانهای تاخیر دو مدل مورد بحث در این مقاله، مساله زمانبندی تک ماشینه با زمان پردازش برابر - یک - با هدف کمینهسازی مجموع وزندار زمانهای تاخیر ورود مشاغل - یعنی مسالهو نیز مساله زمانبندی تک ماشینه با زمان پردازش برابر - یک - با هدف کمینهسازی حداکثر تاخیر - یعنی مساله است. اکنون مدل اول یعنی ∑ را با فرض اینکه تعداد مشاغل باشد در نظر بگیرید. در این مدل فرض بر این است که زمانهای موعد - - عدد فازی مثلثی باشد. اگر زمان تکمیل شغل ام برابر باشد طبق تعریف زمان تاخیر داریم:
و بنابراین زمان تاخیر ورود عبارتست از که در آن ماکزیموم عدد فازی را میتوان به کمک تابع رتبه بندی تعریف 3 حساب کرد. اکنون اگر شغل ام به عنوان امین کار واردماشین شود قرار میدهیم و در غیر اینصورت . واضح است که اگر شغل ام به عنوان امین کار وارد ماشین شود، لذا در اینصورت مساله زمانبندی فوق را میتوان به صورت مساله تخصیص زیر مدلبندی نمود:
مساله - 4 - یک مساله تخصیص فازی با ضرایب تابع هدف فازی است که میتوان آن را به کمک روشی که در ادامه مورد بحث قرار میگیرد، حل کرد. در مساله تخصیص - 4 - ، قید اول تضمین می کند که هر شغل تنها یکبار روی ماشین، مورد پردازش قرار بگیرد. قید دوم نیز متضمن این است که در هر لحظه نیز تنها یک شغل در حال پردازش روی ماشین باشد.
-3 بررسی مدل تک ماشینه با هدف کمینهسازی حداکثر تاخیر
در این بخش مساله را در حالتی بررسی میکنیم که زمانهای پردازش و نیز زمانهای موعد اعداد فازی مثلثی هستند. بنابراین از آنجا که:
فرض کنید همانند بخش 2، اگر شغل ام به عنوان امین کار وارد ماشین شود قرار میدهیم و در غیر اینصورت. واضح است که اگر شغل ام به عنوان امین کار وارد ماشین شود،، لذا در اینصورت مساله زمانبندی فوق را میتوان به صورت مساله تخصیص زیر مدلبندی نمود:
مساله - 7 - یک مساله تخصیص فازی با ضرایب تابع هدف فازی است که میتوان آن را به کمک روشی که در ادامه مورد بحث قرار میگیرد، حل کرد. در مساله تخصیص - 7 - ، قید اول تضمین می کند که هر شغل تنها یکبار روی ماشین، مورد پردازش قرار بگیرد. قید دوم نیز متضمن این است که در هر لحظه نیز تنها یک شغل در حال پردازش روی ماشین باشد.
-4 روش پیشنهادی برای حل مدل تخصیص فازی
هر یک از دو مساله - - 4 یا - 7 - یک مساله بهینهسازی فازی با ضرایب تابع هدف فازی اند که میتوان برای حل آنها از روشهای موجود برای حل مسایل بهینهسازی فازی استفاده کرد. در این مقاله از تابع رتبه بندی پیشنهادی در تعریف 4 استفاده شده است. برای این منظور، ابتدا به کمک تابع رتبه بندی معرفی شده در تعریف 4، ضرایب تابع هدف که اعداد فازی مثلثی هستند، را به اعداد قطعی تبدیل میکنیم، سپس الگوریتم مجارستانی را برای مساله مذکور بکار میبریم.
-5 مثال عددی
مساله زمانبندی ده شغل بر یک ماشین با زمانهای موعد داده شده در جدول1 زیر را در نظر بگیرید. فرض بر این است که زمان پردازش تمام مشاغل ̃ است که همانند اعداد جدول1 اعدادی فازی مثلثی اند. همچنین فرض میکنیم
