Job shop scheduling with two jobs and nonregular objective functions

摘要

We consider the job shop scheduling problem with two jobs. We consider a broad class of non-regular, quasi - convex functions of the completion time of the two jobs. We show that the optimal solution, for this class of objective functions, can be computer in O(r log r+log H) time, where r is the number of operation pairs using the same machine, and H is the maximum operation processing time.