The Problem Of Makespan Of Total Completion Time With Restrictions And Design Of Its Algorithms

In this thesis, we study the problem of the makespan of total completion time with restrictions, which is a generalization of the parallel machine scheduling. In our new problem, each job can only be processed on some specified machines; During the process, a job starts to be processed, it can not be interrupted until the job is completely executed. The objective is to find an allocation scheme to minimize the makespan of total completion time. Using the priority of the shortest total completion time and the shortest makespan, we design two heuristic algorithms, called as STC first algorithm and SMS first algorithm, whose time complexity are O((n2+mn) log n) and O(n(logn+m)), respectively, where m and n denote the number of machines and jobs, respectively.