Abstract: | We consider the time-optimal scheduling problemn/m/J
of n jobs with fixed routes on m machines. The problem3/m/J/
with identical routes and the problem3/5/J/
are shown to be NP-hard. Similar results are obtained for the problem of minimizing the mean processing time of three jobs on m machines.Translated from Kibernetika, No. 5, pp. 50–54, September–October, 1990. |