Scheduling to minimize the weighted sum of completion times

Scheduling was considered in order to minimize the weighted sum of completion times. To minimize the weighted sum of completion times is NP-hard for the parallel machines. Based on the analysis of the problem, a polynomial optimal algorithm was given according to the special case of uniform machines problem where all jobs have equal processing time. The open shop problem to minimize the weighted sum of completion time is NP-hard in strong sense. The relationship between no wait Open Shop scheduling problem and parallel machines scheduling problem is established. According to the relationship, a polynomial optimal algorithm for no wait Open Shop scheduling problem where all operations have equal processing time, is presented. The complexity of the algorithm is O(nlog(n) + mn).