کمینهکردن مجموع وزن دار تعدادواحدهای کاری دارای دیرکرد درزمان بندی کارها برروی پردازنده های موازی با تاخیر ارتباطی

دراین مقاله مساله زمان بندی Pm/prec,cjk/Yw مورد بررسی قرارگرفته است که درآن تعدادی کار با روابط پیش نیازی مشخص برروی m پردازنده موازی مشابه پردازش م یشود روابط پیش نیازی مابین فعالیت ها نشان دهنده تبادل اطلاعات است تبادل اطلاعات بین دوکاری اتفاق می افتد که بطور مستقیم وابسته بوده و این تبادلمتناظر با یک زمان تاخیرارتباطی است اگر این دو کار برروی یک پردازش پردازش نشوند دراین مقاله مساله ای که درآن زمان تاخیر ارتباطی مستقل از پردازشگرها بوده و فقط وابسته به کارها می باشد را معرفی می کنیم همچنین فرض می کنیم که برای هرکار یک زمان تحویل از پیش تعیین شده داده شده است و هدف ما یافتن زمان بندی است که دارای کمترین مجموع وزن دار تعدادواحدهای کاری دارای دیرکرد باشد.