On the complexity of two machine job-shop scheduling with regular objective functions

For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Σfi and max fi, where fi are nondecreasing functions of the finish times of job i, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functions LÅmax, ΣwiUi, and ΣwiTi. The authors generalize these results by showing that the problem with any regular criterion can be solved in polynomial time