سال انتشار: ۱۳۹۱

محل انتشار: نهمین کنفرانس بین المللی مهندسی صنایع

تعداد صفحات: ۹

نویسنده(ها):

عباسعلی جعفری ندوشن – کارشناسی ارشد مهندسی صنایع، دانشگاه صنعتی اصفهان
قاسم مصلحی – عضو هیئت علمی دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان

چکیده:

در این مقاله مسأل هی زمان بندی تک ماشین با فرض زوال خطی-تکه ای ۱ با هدف کمینهسازی تعداد کارهای دیرکرددار وزنی بررسی شده است که در آن مدت زمان پردازش هر کار بر اساس یک تابع خطی -تکه ای به زمان شروع آن کار وابسته است و تمام کارها نرخ زوال ۲ مجزایی دارند. در ابتدا پیچیدگی مسأله بررسی و ثابت شده است که این مسألهNP-hard است. بنابراین برای حلمسأله فوق یک رویکرد شاخه و کران با در نظر گرفتن اصول غلبه و حدود پایین ارائه شده است. نتایج محاسباتی برای ۱۹۰۰ مسأله نشان می دهد که رویه شاخ هو کران قادر به حل مسائل با ابعاد ۲۸ فعالیت می باشد و در بعضی از گروه ها مسائل با ابعاد بزرگ تر نیزحل شد هاند. به طور کلی الگوریتم شاخ هو کران۹۶/۹%از نمونهها را به صورت بهینه حل می کند، که این امر کارآیی بالای رویه ارایه شده را نشان می دهد