زمانبندی کار ها با پردازش زمان برابر در ماشین های موازی با ظرفیت های غیر یکسان برای کمینه سازی طول عمر آنها

ما در این مقاله، مشکل زمانبندی مجموعه ای از کارها با پردازش زمان برابر، و با اندازه کار دلخواه در مجموعه ای از ماشین ها با ظرفیت های متفاوترا مورد بررسی قرار داده ایم. یک کار میتواند تنها به یک ماشینی که از ظرفیت آن کار کمتر نیست، اختصاص بیابد. هدف ما در این مقاله، کمینهساختن طول زمانبندی میباشد. ما نشان می دهیم که هی الگوی تخمین چند جمله ای با بدترین نسبت کمتر از 2 وجود ندارد، مگر آنکهما همچنین ما یک الگو تخمین چندجمله ای با نسبت قدر مطلق پایین برابر 5 را نشان خواهیم داد. علاوه بر آن ما یک الگو تخمین با نسبتمجانب پایین کوچکتر از 3/2 را معرفی می کنیم و در نهایت یک مثال محاسباتی را حل خواهیم کرد و چگونگی تخمین بسیار خوب را با استفاده از این الگوریتم را در آن مثال خواهیم گفت.

کلیدواژه ها:

دسته ماشین های موازی ، طول ساخت ، Np-hard ، الگوریتم تخمین ، نسبت مجانب پایین ، بدترین نسبت قطعی