A Preemptive Scheduling Problem with Different Interrupted Time Cost on Identical Parallel Machines

A new preemptive scheduling problem P|ptmn(δ\-i)|C\-{max} is proposed in this paper, in which a preemption penalty δ\-i is introduced if a task is interrupted and resumed later. This problem has numerous applications in task scheduling, distributed computing, and network communication. Firstly, P|ptmn(δ\-i)|C\-{max} is proved to be an NP-hard optimization problem. Then an LPT algorithm is presented. LPT is relatively succinct and easy to implement. However, the approximation ratio of LPT is unsatisfied. In order to improve the approximation ratio, a new LPT-based algorithm is designed. In this LPT-based algorithm, the technique of LPT is applied to not only the execution time p\-i but also the interrupt time δ\-i, therefore avoiding the worst case of LPT algorithm. In the key part of the LPT-base algorithm, the averaging technique is employed to enhance the parallelism.