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 条

[11]

Brucker P., Knust S., Complexity results for scheduling problems

[12]

Garey M.R., Johnson D.R., Simons B.B., Tarjan R.E., Scheduling unit-time tasks with arbitrary release times and deadlines, SIAM J. Comput., 10, pp. 256-269, (1981)

[13]

Simons B., Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines, SIAM J. Comput., 12, pp. 294-299, (1983)

[14]

Lenstra J.K., Rinnooy Kan A.H.G., Brucker P., Complexity of machine scheduling problems, Ann. Discrete Math., 1, pp. 343-362, (1977)

[15]

Dessouky M.I., Lageweg B.J., Lenstra J.K., van de Velde S.L., Scheduling identical jobs on uniform parallel machines, Stat. Neerl., 44, pp. 115-123, (1990)

[16]

Baptiste P., Scheduling equal-length jobs on identical parallel machines, Discrete Appl. Math., 103, pp. 21-32, (2000)

[17]

Baptiste P., Durr C.

[18]

Labetoulle J., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Preemptive scheduling of uniform machines subject to release dates, Progress in Combinatorial Optimization, pp. 245-261, (1984)

[19]

Leung J.Y.-T., Young G.H., Preemptive scheduling to minimize mean weighted flow time, Inform. Process. Lett., 34, pp. 47-50, (1990)

← 1 2 →