Optimal preemptive scheduling for general target functions

Leah Epstein, Tamir Tassa

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرفصلمراجعة النظراء

ملخص

We study the problem of optimal preemptive scheduling with respect to a general target function. Given n jobs with associated weights and m ≤ n uniformly related machines, one aims at scheduling the jobs to the machines, allowing preemptions but forbidding parallelization, so that a given target function of the loads on each machine is minimized. This problem was studied in the past in the case of the makespan. Gonzalez and Sahni [7] and later Shachnai, Tamir and Woeginger [12] devised a polynomial algorithm that outputs an optimal schedule for which the number of preemptions is at most 2(m -1). We extend their ideas for general symmetric, convex and monotone target functions. This general approach enables us to distill the underlying principles on which the optimal makespan algorithm is based. More specifically, the general approach enables us to identify between the optimal scheduling problem and a corresponding problem of mathematical programming. This, in turn, allows us to devise a single algorithm that is suitable for a wide array of target functions, where the only difference between one target function and another is manifested through the corresponding mathematical programming problem.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفMathematical Foundations of Computer Science 2004 (MFCS 2004)
المحررونJirí Fiala, Jan Kratochvíl, Vá clav Koubek
مكان النشرBerlin, Heidelberg
ناشرSpringer
الصفحات562-573
عدد الصفحات12
رقم المعيار الدولي للكتب (الإلكتروني)9783540286295
رقم المعيار الدولي للكتب (المطبوع)9783540228233
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2004

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت3153
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

ملاحظة ببليوغرافية

Funding Information:
∗Corresponding author. E-mail addresses: lea@math.haifa.ac.il (L. Epstein), tamirta@openu.ac.il (T. Tassa). 1Research supported by Israel Science Foundation (Grant no. 250/01).

بصمة

أدرس بدقة موضوعات البحث “Optimal preemptive scheduling for general target functions'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا