Two Scheduling Models: p-Batch Scheduling and
Rescheduling I
Jinjiang Yuan
Department of Mathematics, Zheng Zhou University, Henan 450052,
P.R. China
yuanjj@zzu.edu.cn
Abstract Full Text PDF
In the p-batch scheduling, we have a single machine which can
process several jobs simultaneously as a batch, and the processing time of
the batch is equal to the longest processing time of the jobs assigned to it.
The existing complexity results and open problems will be reviewed. Specially,
the NP-hardness proof of the problem 1|p-batch, 
will be
reported in detail, in which we use the NP-complete vertex cover problem
of graphs for the reduction.
