Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Some Problems in Queueing Systems with Resequencing

    Thumbnail
    View/Open
    MS_87-9.pdf (3.895Mb)
    No. of downloads: 328

    Date
    1987
    Author
    Varma, S.
    Advisor
    Makoski, A.
    Metadata
    Show full item record
    Abstract
    The aim of this thesis is to solve some problems associated with queueing systems with resequencing of customers. Resequencing is associated with the presence of some disordering system which operates on an input arrival stream of customers and delays each customer by a random amount, so that they may leave the system in a different order than the one in which they entered it. However, if the constraint that the customers should leave the system in the same order in which they entered it, is imposed, then a customer may have to undergo an additional delay, which is known as resequencing delay. Such situations typically arise due to packet switching in a computer communication network, in an interconnection network of a multi-processor architecture and concurrency control schemes of distributed data bases among other places. The presence of resequencing makes the analysis of the queueing system intractable in most cases, and very few analytical results are known about these systems. Two general representation results for resequencing systems are the principal tools used in the thesis. The first representation gives the delay in a general resequencing system, in a recursive sample path form. It is used to investigate multistage resequencing systems and also to deduce some interesting structural properties of multiple server resequencing systems. It is shown that hop- by-hop resequencing leads to greater delay compared to end-to-end resequencing in N stage infinite server systems in the sense of strong stochastic ordering. The effect of varying the number of servers on the resequencing delay in a finite server system is investigated for both single stage as well as two stage disordering systems, and also several useful structural properties which can be used to develop bounds for intractable resequencing systems, are identified. The second represenation provides a Markovian state space description for the two server resequencing system with exponential interarrival and service times. The state occupation probabilities are calculated for the M/M/2/B queue with resequencing using this representation. The optimal policy for assigned cutomers to the two servers in the case when they have different service rates, to minimize the total delay (including the resequencing delay), is investigated using dynamic programming arguments. The optimal policy is shown to be of the threshold type in the number of customers in the main queue buffer and independent of the number of customers in the resequencing buffer.
    URI
    http://hdl.handle.net/1903/4731
    Collections
    • Institute for Systems Research Technical Reports

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility