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(n³) 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.

This short paper treats some decision problems for Petri Nets and shows that the problems of the safeness, the reachability and the proper termination are NP-complete for Petri Nets in which each transition fires at most once.

Single axial mode oscillation in Integrated Twin-Guide AlGaAs laser fabricated by sputter-etching was observed by current injection pumping at room temperature, as predicted by theory.