حل مسائل پیچیده با فضای جستجوی بزرگ، همواره یکی از چالش های محققان برای رسیدن به پاسخ های بهینه بوده و هست. اما از آنجایی که به دست آوردن راه حل بهینه با استفاده از روش های دقیق و غیرهوشمند، بسیار مشکل است، اغلب رویکردها در سال های اخیر بر روی روش های تقریبی و فراابتکاری معطوف شده است. در این مقاله، روش جدیدی در ترکیب الگوریتم های فراابتکاری برای حل مسئله زمان بندی کار کارگاهی انعطاف‌پذیر در شرایط چندهدفی ارائه شده است. این مسئله که نوع تعمیم یافته مسئله کلاسیک زمان بندی کار کارگاهی است، جزء مسائل NP-hard محسوب می شود. معمولاً در خصوص استفاده از روش های جستجوی محلی، دغدغه اصلی برای رسیدن به بهینه سراسری، انتخاب نقاط شروع مناسب است. لذا در این مقاله الگوریتم ژنتیک توسعه یافته ای با تکیه بر پارامتر جدید همسایگی ارائه شده است که خروجی آن شناسایی چند خوشه در اطراف نواحی برازنده تر است. بهترین راه حل هر خوشه، نماینده مناسبی برای نقطه شروع در روش های جستجوی محلی به شمار می آید. بهینه سراسری نیز از مقایسه نتایج این جستجوهای محلی به دست می آید. نتایج محاسباتی بر روی نمونه مسائل معروف نشان می دهد که راه حل های بهینه سریع تر و مطمئن تر از سایر روش ها به دست آمده است.