Parallel Machine Scheduling Problem With Machine Delivery Times

Parallel machine scheduling problem is an extension of the single machine scheduling problem and the foundation of some more complicate problems.This paper considers the parallel machine scheduling problem with delivery times. The problem is NP-hard, so we want to find approximate algorithms to solve the problem. We investigate three approximate algorithms of the problem: the first one is the Dual-Threshold algorithm, and we give the bound of the algorithm when the number of the machines is 3 and we prove that the bound is tight; the second one is the LPT algorithm, and we give the bound of the algorithm which is not necessarily tight; for a more complicate problem we give an approximate algorithm based on the preprocessing algorithm. All of the three algorithms above are polynomial, so they can be easily realized.