Maximum weight matching with hysteresis in overloaded queues with setups

Carri W. Chan (), Mor Armony () and Nicholas Bambos ()
Additional contact information
Carri W. Chan: Columbia Business School
Mor Armony: New York University
Nicholas Bambos: Stanford University

Queueing Systems: Theory and Applications, 2016, vol. 82, issue 3, No 3, 315-351

Abstract: Abstract We consider a system of parallel queues where arriving service tasks are buffered, according to type. Available service resources are dynamically configured and allocated to the queues to process the tasks. At each point in time, a scheduler chooses a service configuration across the queues, in response to queue backlogs. Switching from one service configuration to another incurs a setup time, during which idling occurs and service bandwidth is lost. Such setup times are inherent in manufacturing and computer systems. Frequent switchings can significantly compromise the service capacity of such systems. A maximum weight matching (MWM) scheduler, which is known to maximize throughput in the absence of setups, can easily become unstable with setups, even under low load. To remedy this problem, we propose a new MWM-H scheduler which utilizes a controller introduced hysteresis and achieves maximum throughput even with setups, without requiring knowledge of arrival rates and average traffic loads. During prolonged traffic bursts, the queues may become overloaded and the issue becomes how to reasonably distribute the growing backlog under MWM-H. It is shown that by appropriately selecting the MWM-H parameters, one can control the backlog among the individual queues in order to achieve a desired balance.

Keywords: Hysteresis; Maximum weight matching; Setup times; 60K25; 90B22 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-015-9468-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:82:y:2016:i:3:d:10.1007_s11134-015-9468-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-015-9468-4

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().