Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Scheduling with Rejection to Minimize the Makespan
verfasst von : Yuzhong Zhang, Jianfeng Ren, Chengfei Wang
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider the scheduling with rejection. The objective functions are to minimize the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem 1|
rej
|
C
max
/
TCP
is NP-hard, which implying that
P
m
|
rej
|
C
max
/
TCP
, 1 |
rej
,
r
j
|
C
max
/
TCP
, 1 |
rej
,
on
−
line
|
C
max
/
TCP
are all NP-hard. Secondly, for problem
P
m
|
rej
|
C
max
/
TCP
, we design a pseudopolynomial time dynamic programming algorithm that solves it exactly and an
FPTAS
(full polynomial time approximation scheme) when
m
is a constant. We also design a pseudopolynomial time dynamic programming algorithm and an
FPTAS
for the case of non-identical job arrival problem 1 |
rej
,
r
j
|
C
max
/
TCP
. In the end, we consider the on-line problem 1 |
rej
,
on
−
line
|
C
max
/
TCP
and prove that there doesn’t exist any on-line algorithm with a constant competitive ratio for it, even if the jobs only have two different release times.