Maximizing throughput in queueing networks with limited flexibility
Φόρτωση...
Ημερομηνία
Συγγραφείς
Down, D. G.
Karakostas, G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Latin 2006: Theoretical Informatics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We study a queueing network where customers go through several stages of processing, with the class of a customer used to indicate the stage of processing. The customers are serviced by a set of flexible servers, i.e., a server may be capable of serving more than one class of customer and the sets of classes that the servers are capable of serving may overlap. We would like to choose an assignment of servers that achieves the maximal capacity of the given queueing network, where the maximal capacity is lambda* if the network can be stabilized for all arrival rates lambda < lambda* and cannot possibly be stabilized for all lambda > lambda*. We examine the situation where there is a restriction on the number of servers that are able to serve a class, and reduce the maximal capacity objective to a maximum throughput allocation problem of independent interest: the TOTAL DISCRETE CAPACITY CONSTRAINED PROBLEM (TDCCP). We prove that solving TDCCP is in general NP-complete, but we also give exact or approximation algorithms for several important special cases.
Περιγραφή
Λέξεις-κλειδιά
queueing networks, scheduling, approximation algorithms, source unsplittable flow, flexible servers, policies, systems, lines
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000236886100038
http://download.springer.com/static/pdf/121/chp%253A10.1007%252F11682462_38.pdf?auth66=1390991913_15ff2eb9e374df7171d0312db37bd919&ext=.pdf
http://download.springer.com/static/pdf/121/chp%253A10.1007%252F11682462_38.pdf?auth66=1390991913_15ff2eb9e374df7171d0312db37bd919&ext=.pdf
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών