Two-person cooperative games on minimizing the makespan

This paper considers the problem of two-person cooperative games on minimizing the makespan. A special case of this problem is proved NP-hard, and a dynamic programming algorithm is presented for the general case, which runs in pseudo-polynomial time and indicates that this problem is binary NP-hard. This paper also adopts List Scheduling (LS) and Longest Processing Time (LPT) algorithms for classical parallel machines scheduling problem to cooperative game problem and develops the performance ratios of the algorithms.