تحلیل ریاضی دامنه مسئله زمانبندی گرافهای جهتدار به عنوان یک مسئله NP-Hard و ارائه الگوریتمی برای نمونه گیری با توزیع یکنواخت

سال انتشار: 1381
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,942

فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ACCSI08_032

تاریخ نمایه سازی: 18 بهمن 1386

چکیده مقاله:

مسئله زمانبندی برنامههای موازی با ساختار گراف جهتدار روی سیستمهای چندپردازنده، یکی از مسایل پیچیده محاسباتی است . در این مسئله یک برنامه موازی با یک گراف جهتدار بیان میشود و هدف اختصاص مناسب پردازندهها به گرههای گراف است به طوریکه زمان اجرای کل گرهها کمینه شود . یکی از مشکلات مسایل پیچیده محاسباتی، عدم دسترسی به اطلاعات و شکل دامنهای است که تابع هدف مورد نظر قرار است در آن بهینه شود . این مسئله سبب میشود، در استفاده از الگوریتمهای جستجو مانند الکوریتم ژنتیک که در آن لازم است جمعیت اولیه دارای توزیعی یکنواخت روی کل دامنه باشد، مشکلاتی بوجود آید، به این ترتیب که با روشهای موجود جمعیت اولیه در گوشهای از دامنه متمرکر شده و امکان و احتمال جستجوی همه فضای دامنه را به میزان بسیار زیادی کاهش میدهد . در این تحقیق دامنه مسئله زمانبندی گرافهای جهتدار به صورت ریاضی تحلیل شده و بر اساس آن الگوریتمی دقیق برای انتخاب جمعیت اولیه با توزیع یکنواخت بدست داده میشود . الگوریتم بدست آمده میتواند در همه مسایلی که ورودی آنها به نوعی گرافها هستند مفید باشد .

نویسندگان

حسین میارنعیمی

دانشکده برق - دانشگاه علم و صنعت ایران

مجید نادری

دانشکده برق - دانشگاه علم و صنعت ایران

عادل رحمانی

دانشکده کامپیوتر - دانشگاه علم و صنعت ایران

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • J. K Lenstra, M. Veldhorst and B. Veltman. The complexity ...
  • J. A. Hoogveen, J.K. Lenstra and B. Veltman. Three, four, ...
  • T.G. Lewis and H. EI-Rewini, Introduction to parallel computing, Prentice-Hall, ...
  • A. Munier and J.-C. Konig. A heuristic for a scheduling ...
  • N. Alon, Y. Azar, G.J. Woeginger, and T. Yadid. Approximati ...
  • F.E. Sandnes and G.M. Megson. Improved Static Multiproces sor Scheduling ...
  • H. H. Ali, R. Vemulapalli. A new approach for task ...
  • Eric W. Parsons. Using knowledge of job characteristics in mu ...
  • R Graham. Bounds on Multiproces sing Timing Analysis. SIAM J.Computers, ...
  • A.Gerasoulis and T. Yang. A comparison of clustring heuristics for ...
  • Y.-K. Kwok and I. Ahmad, Dynamic critical-path scheduling: An effectrive ...
  • 2] H.EI-Rewini and T.G. Lewis, Scheduling Parallel Programs onto Arbitrary ...
  • T. Yang and A. Gerasoulis, DSC: Scheduling parallel Tasks _ ...
  • A. M. S. Zalzala, P. J. Fleming. Genetic algorithms in ...
  • Albert Y. Zomaya, Chris Ward, Ben Macey. Genetic Scheduling for ...
  • F.Glover, Tabu search, ORSA Journal on computing, 1990, 4-32. ...
  • P. Rebreyend and F. E. Sandnes. Static mul tiprocessor task ...
  • نمایش کامل مراجع