On the Control of Fork-Join Networks

Networks in which the processing of jobs occurs both sequentially and in parallel are prevalent in many application domains, such as computer systems, healthcare, manufacturing, and project manage- ment. The parallel processing of jobs gives rise to synchronization constraints that can be a main reason for job delay, which results in holding costs. In comparison with feedforward queueing networks that have only sequential processing of jobs, the approximation and control of networks that have synchronization constraints is less understood. One well-known modeling framework in which synchronization constraints are prominent is the fork-join processing network. Our objective is to find scheduling rules for fork-join processing networks that minimize holding costs. To do this, we focus on a prototypical network with two job classes (a and b), two fork operations, one shared server, and two join operations. The fork operations are first, followed by the simultaneous processing of type a (b) jobs by a dedicated server and a shared server, and, finally the join operations. We solve the scheduling problem for the shared server (that is, which type of job to prioritize each time the server becomes available) when that server is in heavy traffic. We show that a cμ-type static priority policy is asymptotically optimal when the shared server is in some sense slow at processing the more expensive type a jobs. Otherwise, an asymptotically optimal control is a state-dependent slow departure pacing control in which the shared server slows its processing of type a jobs to match the departure process of those jobs from the dedicated type-a server. Finally, by considering a broader class of fork-join networks, we see that the departure pacing idea is to some extent robust.Non UBCUnreviewedAuthor affiliation: University of Southern CaliforniaFacult