یک تکنیک تقسیم و حل برای مسئله جریان کارگاهی جایگشتی

چکیده مقاله

زمان بندی جریان کارگاهی جایگشتی، مسئله ای مهم با انواع مختلف و طیف گسترده ای از کاربردها در صنعت و مهندسی است به دلیل NP Complete بودن مسئله، روش های ابتکاری و فراابتکاری مختلفی برای یافتن جواب های تقریبی بهینه ارائه و به کار گرفته شده اند که هدف آنها کمینه کردن حداکثر زمان تکمیل همه کارها است از این میان، روش ابتکاری نوز انسکور هام NEH یکی از مشهورترین تکنیک هاست که جواب های کارآمدی ارائه می دهد و به طور گسترده توسط سایر روش ها برای داشتن یک جواب اولیه خوب مورد استفاده قرار می گیرد پیچیدگی زمانی روش NEH در مرتبه O n² m است که در آن n تعداد کارها و m تعداد ماشین ها می باشد اگرچه این پیچیدگی زمانی، استفاده از روش را برای مسائل با اندازه متوسط ممکن می سازد، اما کاربرد آن را برای تعداد زیاد کارها و ماشین ها محدود می کند از طرفی روش NEH در اکثر روش های مبتنی بر هوش مصنوعی برای ایجاد یک مجموعه اولیه از تخمین های خوب استفاده می شود در این مقاله، یک روش ابتکاری جدید برای مسئله با پیچیدگی زمانی O n m log n پیشنهاد می کنیم روش پیشنهادی ما از یک رویکرد تقسیم و حل Divide and Conquer برای یافتن جواب های مناسب برای نسخه های کوچک مسئله استفاده کرده و آن ها را ادغام می کند تا موارد بزرگ تر را حل کند این رویکرد را می توان به راحتی روی یک ماشین موازی با K هسته پیاده سازی کرد و زمان اجرا را به O n m log n /K کاهش داد آزمایش های ما نشان می دهد که روش پیشنهادی در مقایسه با نتایج روش NEH و نیز روش های سریع موجود نتایج با کیفیت بالایی ارائه می دهد

کلیدواژه‌ها

نویسندگان

محمدصادق محققی

استادیار گروه علوم کامپیوتر / دانشکده علوم ریاضی، دانشگاه ولیعصر رفسنجان، رفسنجان

علی ابولی نسب

دانشجو ارشد علوم کامپیوتر / دانشکده علوم ریاضی، دانشگاه ولیعصر رفسنجان، رفسنجان

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

ارائه‌شده در

مجموعه مقالات سومین کنفرانس ملی تحول دیجیتال و سیستم های هوشمند28 بهمن 1404 · لارستان