The full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period, even for Texas A&M users with NetID.
On Fork-Join Queues and Maximum Ratio Cliques
MetadataShow full item record
This dissertation consists of two parts. The ﬁrst part delves into the problem of response time estimation in fork-join queueing networks. These systems have been seen in literature for more than thirty years. The estimation of the mean response time in these systems has been found to be notoriously hard for most forms of these queueing systems. In this work, simple expressions for the mean response time are proposed as conjectures. Extensive experiments demonstrate the remarkable accuracy of these conjectures. Algorithms for the estimation of response time using these conjectures are proposed. For many of the networks studied in this dissertation, no approximations are known in literature for estimation of their response time. Therefore, the contribution of this dissertation in this direction marks signiﬁcant progress in the analysis of fork-join queues. The second part of this dissertation introduces a fractional version of the classical maximum weight clique problem, the maximum ratio clique problem, which is to ﬁnd a maximal clique that has the largest ratio of beneﬁt and cost weights associated with the cliques vertices. This problem is formulated to model networks in which the vertices have a beneﬁt as well as a cost associated with them. The maximum ratio clique problem ﬁnds applications in a wide range of areas including social networks, stock market graphs and wind farm location. NP-completeness of the decision version of the problem is established, and three solution methods are proposed. The results of numerical experiments with standard graph instances, as well as with real-life instances arising in ﬁnance and energy systems, are reported.
Fractional Combinatorial Optimization
Social Network Analysis
Sethuraman, Samyukta (2015). On Fork-Join Queues and Maximum Ratio Cliques. Doctoral dissertation, Texas A & M University. Available electronically from