Process pipeline scheduling

Two processes, p and q, may be scheduled in pipeline when q may start when p starts, and q may process data items from p, one-by-one, without waiting for p to write the complete set of data items. This paper explores how process pipeline scheduling may become a viable strategy for executing workflows. The paper first details a workflow model that captures the characteristics of the application programs that pipeline scheduling requires. It proceeds by showing that the process pipeline scheduling problem is NP-Complete. Then, it describes a specific algorithm that pipelines as many processes as possible, within the bounds of the storage space available, based on a greedy process scheduling heuristics that has acceptable performance. Finally, the paper presents a detailed example that illustrates how the algorithm schedules processes.