Two Scheduling Models: p-Batch Scheduling and Rescheduling II

Jinjiang Yuan
Department of Mathematics, Zheng Zhou University, Henan 450052, P.R. China
yuanjj@zzu.edu.cn

Abstract     Full Text   PDF

In the rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. The existing complexity results and open problems will be reviewed. Specially, a polynomial-time algorithm for the problem, will be reported in detail, where means that the maximum sequence disruption of the original jobs is limited to at most k.