- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- On the Control of Fork-Join Networks
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
On the Control of Fork-Join Networks Ward, Amy
Description
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.
Item Metadata
| Title |
On the Control of Fork-Join Networks
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2015-06-02T11:03
|
| Description |
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.
|
| Extent |
48 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: University of Southern California
|
| Series | |
| Date Available |
2016-01-04
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivs 2.5 Canada
|
| DOI |
10.14288/1.0221662
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivs 2.5 Canada