The scheduling of n tasks with m operations on two processors

[摘要] The job shop problem is one scheduling problem for which no efficient algorithm exists. That is, no algorithm is known in which the number of computational steps grow algebraically as the problem enlarges. This paper presents a discussion of the problem of scheduling N tasks on two processors when each task consists of three operations. The operations of each task must be performed in order and among the processors. We analyze this problem through four sub-problems. Johnson's scheduling algorithm is generalized to solve two of these sub-problems, and functional equation algorithms are used to solve the remaining two problems. Except for one case, the algorithms are efficient. The exceptional case has been labelled the "core" problem and the difficulties are described.

[学科分类] 计算机科学（综合）