Preemptive scheduling of equal-length jobs in polynomial time

被引：0

作者：

Mertzios G.B. ^{[1
]}

Unger W. ^{[1
]}

机构：

[1] Department of Computer Science, RWTH Aachen University, 52074 Aachen

来源：

Mathematics in Computer Science | 2010年 / 3卷 / 1期

关键词：

Equal-length jobs; Machine scheduling; Parameterized algorithm; Polynomial algorithm; Preemptive scheduling;

D O I：

10.1007/s11786-009-0003-z

中图分类号：

学科分类号：

摘要：

We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times of the jobs. We propose for this problem the first parameterized algorithm on the number k of different weights. The runtime of the proposed algorithm is and hence, the problem is polynomially solvable for any fixed number k of different weights. © 2009 Birkhäuser Verlag Basel/Switzerland.

引用

页码：73 / 84

页数：11

共 19 条

[1]

Herrbach L.A., Leung J.Y.-T., Preemptive scheduling of equal length jobs on two machines to minimize mean flow time, Oper. Res., 38, pp. 487-494, (1990)

[2]

Baptiste P., Brucker P., Chrobak M., Durr C., Kravchenko S.A., Sourd F., The complexity of mean flow time scheduling problems with release times, J. Sched., 10, 2, pp. 139-146, (2007)

[3]

Garey M.R., Johnson D.S., Computers and Intractability, a Guide to the Theory of NP-Completeness, (1979)

[4]

Lawler E.L., A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Ann. Discrete Math., 26, 1-4, pp. 125-133, (1990)

[5]

Baptiste P., Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine when processing times are equal, J. Sched., 2, pp. 245-252, (1999)

[6]

Baptiste P., Chrobak M., Durr C., Jawor W., Vakhania N., Preemptive scheduling of equal-length jobs to maximize weighted throughput, Oper. Res. Lett., 32, 3, pp. 258-264, (2004)

[7]

Tian Z., Ng C.T., Cheng T.C.E., An O(n<sup>2</sup>) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness, SIAM J. Comput., 9, 4, pp. 343-364, (2006)

[8]

Baker K.R., Introduction to Sequencing and Scheduling, (1974)

[9]

Baptiste P., An o(n<sup>4</sup>) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Oper. Res. Lett., 24, pp. 175-180, (1999)

[10]

Brucker P., Scheduling Algorithms, (2007)

← 1 2 →