Openshop scheduling with machine dependent processing times

This paper examines the openshop problem with machine dependent processing times. Two objectives are considered; minimizing the maximal completion (makespan), and minimizing the mean flow time. For this problem with the makespan criteria and the number of jobs greater or equal to the number of machines the paper presents an O(mn) optimal algorithm and proves that the same problem with the number of jobs less than the number of machines but greater or equal three is NP-hard. It also presents an O(n) optimal algorithm for this problem with mean flow time criteria but two machines only, and for a special case with m machines describes an optimal O(mn) algorithm. The three machine openshop problem with machine dependent processing times and mean flow time criteria remains open.