Approximation schemes for the min-max starting time problem

Leah Epstein, Tamir Tassa

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

We consider the off-line scheduling problem of minimizing the maximal starting time. The input to this problem is a sequence of n jobs and m identical machines. The goal is to assign the jobs to the machines so that the first time at which all jobs have already started running is minimized, under the restriction that the processing of the jobs on any given machine must respect their original order. Our main result is a polynomial time approximation scheme (PTAS) for this problem in the case where m is considered as part of the input. As the input to this problem is a sequence of jobs, rather than a set of jobs where the order is insignificant, we present techniques that are designed to handle order constraints imposed by the sequence. Those techniques are combined with common techniques of assignment problems in order to yield a PTAS for this problem. We also show that when m is a constant, the problem admits a fully polynomial time approximation scheme. Finally, we show that the makespan problem in the linear hierarchical model may be reduced to the min-max starting time problem, thus concluding that the former problem also admits a PTAS.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)657-674
عدد الصفحات18
دوريةActa Informatica
مستوى الصوت40
رقم الإصدار9
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - سبتمبر 2004

بصمة

أدرس بدقة موضوعات البحث “Approximation schemes for the min-max starting time problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا