2010 | OriginalPaper | Chapter
Bounded Parallel-Batch Scheduling on Unrelated Parallel Machines
Authors : Cuixia Miao, Yuzhong Zhang, Chengfei Wang
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.