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

زمان بندی جریان کارگاهی جایگشتی، مسئله ای مهم با انواع مختلف و طیف گسترده ای از کاربردها در صنعت و مهندسی است. به دلیل complete-npبودن مسئله زمان‌بندی جریان کارگاهی با جایگشت یکی از مسائل مهم با نسخه‌های گوناگون و دامنه وسیعی از کاربردها در صنعت و مهندسی است. به دلیل np-کامل بودن این مسئله، روش‌های ابتکاری متعددی برای دستیابی به جواب‌های تقریباً بهینه با هدف کمینه‌سازی بیشینه زمان تکمیل همه کارها پیشنهاد و به‌کار گرفته شده‌اند. در میان این روش‌ها، ابتکار nawaz–enscore–ham (neh) یکی از شناخته‌شده‌ترین و موثرترین تکنیک‌ها محسوب می‌شود که راه‌حل‌های کارآمدی ارائه می‌دهد و به‌طور گسترده در سایر روش‌ها به‌عنوان یک جواب اولیه مناسب مورد استفاده قرار می‌گیرد. پیچیدگی زمانی روش neh برابر با o(n2⋅m) است که در آن n تعداد کارها و m تعداد ماشین‌ها را نشان می‌دهد. اگرچه این پیچیدگی زمانی، امکان به‌کارگیری این روش را برای مسائل با اندازه متوسط فراهم می‌کند، اما کاربرد آن را برای مسائل بزرگ با تعداد زیاد کارها و ماشین‌ها محدود می‌سازد. در این مقاله، یک روش ابتکاری جدید برای این مسئله ارائه می‌شود که دارای پیچیدگی زمانی o(n⋅m⋅log(n)) است. روش پیشنهادی از یک رویکرد تقسیم و حل بهره می‌گیرد؛ بدین صورت که ابتدا جواب‌های مناسبی برای نسخه‌های کوچک‌تر مسئله به‌دست می‌آورد و سپس با ترکیب آن‌ها، مسائل بزرگ‌تر را حل می‌کند. این رویکرد به‌سادگی قابل پیاده‌سازی روی ماشین‌های موازی با k هسته پردازشی است و می‌تواند زمان اجرا را به o(n⋅m⋅log(n)/k) کاهش دهد. نتایج آزمایش‌ها نشان می‌دهد که روش پیشنهادی، در مقایسه با روش neh، جواب‌هایی با کیفیت بالا ارائه می‌دهد.