Article ID: | iaor2002224 |
Country: | Canada |
Volume: | 39 |
Issue: | 3 |
Start Page Number: | 227 |
End Page Number: | 244 |
Publication Date: | Aug 2001 |
Journal: | INFOR |
Authors: | Mirchandani Pitu B., Agnetis Alessandro, Pacciarelli Dario, Pacifici Andrea |
Keywords: | networks: scheduling |
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 computed 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.