A New nlogn Algorithm for Single Machine Scheduling Problem Which Minimize Maximum Completion cost

In this paper, we propose a new nlog n algorithm for single machine scheduling problem which minimize maximum completion cost. In this problem, there are precedence constraints among jobs that we represent these constraints by graph. The proposed algorithm uses topological ordering for labeling the graph and we utilize same labeling for scheduling the jobs. This algorithm runs in o (nlog n) time when precedence constraints be sparse.

Keywords:

topological ordering , scheduling problem , single machine , precedence constraints