سیدغیاث الدین طاهری - گروه صنایع، واحد ساوه، دانشگاه آزاد اسلامی، ساوه، ایران
داود صدیقی زاده - گروه صنایع، واحد ساوه، دانشگاه آزاد اسلامی، ساوه، ایران

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

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