2010 | OriginalPaper | Buchkapitel
Bounded Parallel-Batch Scheduling on Unrelated Parallel Machines
verfasst von : Cuixia Miao, Yuzhong Zhang, Chengfei Wang
Erschienen in: Algorithmic Aspects in Information and Management
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 bounded parallel-batch scheduling problem on unrelated parallel machines. Problems
R
m
|
B
|
F
are NP-hard for any objective function
F
. For this reason, we discuss the special case with
p
ij
=
p
i
for
i
= 1, 2, ⋯ ,
m
,
j
= 1, 2, ⋯ ,
n
. We give optimal algorithms for the general scheduling to minimize total weighted completion time, makespan and the number of tardy jobs. And we design pseudo-polynomial time algorithms for the case with rejection penalty to minimize the makespan and the total weighted completion time plus the total penalty of the rejected jobs, respectively.