Efficient Implementation Of Johnson's Scheduling Algorithm
IIE Transactions (Institute of Industrial Engineers)
Most of the real world scheduling problems are difficult to solve and are named in the scheduling literature as NP-hard. One of the approaches for solving large scale scheduling problems is to decompose them into subproblems which can hopefully be solved by constructive scheduling algorithms. An efficient implementation of Johnson's algorithm for n job two machine scheduling problem has been developed. Computational complexity of the proposed scheduling algorithm is O (nlogn).
Published Article/Book Citation
IIE Transactions (Institute of Industrial Engineers), 18:2 (1986) pp.215-216.