Optimum scheduling in pipeline processing

The authors comment on usefulness of applying scheduling algorithms and propose two applicable algorithms in multi-stage pipeline processing systems. The models taken up are intrinsically nonpolynomial and theoretically intractable. However, not only utilizing given data of processing times but also referring to their stochastic parameters, experiments show that Johnson´s algorithm for the flow-shop problem can work effectively within some limitation and new algorithms can extend its applicability. An initial model compares the minimum makespan in the optimum order with a makespan in random order, with given task processing timers drawn from statistical distributions. In a second model, two algorithms are examined for success probability