تحلیل ریاضی دامنه مسئله زمانبندی گرافهای جهتدار به عنوان یک مسئله NP-Hard و ارائه الگوریتمی برای نمونه گیری با توزیع یکنواخت
- سال انتشار: 1381
- محل انتشار: هشتمین کنفرانس سالانه انجمن کامپیوتر ایران
- کد COI اختصاصی: ACCSI08_032
- زبان مقاله: فارسی
- تعداد مشاهده: 2068
نویسندگان
دانشکده برق - دانشگاه علم و صنعت ایران
دانشکده برق - دانشگاه علم و صنعت ایران
دانشکده کامپیوتر - دانشگاه علم و صنعت ایران
چکیده
مسئله زمانبندی برنامههای موازی با ساختار گراف جهتدار روی سیستمهای چندپردازنده، یکی از مسایل پیچیده محاسباتی است . در این مسئله یک برنامه موازی با یک گراف جهتدار بیان میشود و هدف اختصاص مناسب پردازندهها به گرههای گراف است به طوریکه زمان اجرای کل گرهها کمینه شود . یکی از مشکلات مسایل پیچیده محاسباتی، عدم دسترسی به اطلاعات و شکل دامنهای است که تابع هدف مورد نظر قرار است در آن بهینه شود . این مسئله سبب میشود، در استفاده از الگوریتمهای جستجو مانند الکوریتم ژنتیک که در آن لازم است جمعیت اولیه دارای توزیعی یکنواخت روی کل دامنه باشد، مشکلاتی بوجود آید، به این ترتیب که با روشهای موجود جمعیت اولیه در گوشهای از دامنه متمرکر شده و امکان و احتمال جستجوی همه فضای دامنه را به میزان بسیار زیادی کاهش میدهد . در این تحقیق دامنه مسئله زمانبندی گرافهای جهتدار به صورت ریاضی تحلیل شده و بر اساس آن الگوریتمی دقیق برای انتخاب جمعیت اولیه با توزیع یکنواخت بدست داده میشود . الگوریتم بدست آمده میتواند در همه مسایلی که ورودی آنها به نوعی گرافها هستند مفید باشد .کلیدواژه ها
زمانبندی، گرافهای جهتدار، توزیع یکنواختمقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.