Let J{1, 2, , n} be a set of jobs. Each job j can be processed on one of the m identical machines in one unit time, and has ready and due times. It is shown that the problem of finding an optimal schedule minimizing the sum of costs associated with jobs j, which are monotone functions of completion time of j, can be reduced to the assignment problem with 0(n) vertices; hence it can be solved in 0(n3) steps. As important special cases, this cost includes the weighted number of late jobs, the weighted tardiness, and the weighted flow-time. In addition, it is shown that the problem has an 0(n log n) algorithm if the objective is to minimize the (unweighted) number of late jobs. This problem is critical for having an efficient algorithm in the sense that generalizing it in various directions easily results in NP-complete problems. As an example, it is shown that it becomes NP-complete if precedence constraints are imposed.