Dynamic visit-order rules for batch-service polling

被引:24
作者
Van Der Wal, J
Yechiali, U
机构
[1] Tech Univ Eindhoven, NL-5600 MB Eindhoven, Netherlands
[2] Tel Aviv Univ, Dept Stat & OR, IL-69978 Tel Aviv, Israel
关键词
D O I
10.1017/S0269964803173044
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
We explore visit-order policies in nonsymmetric polling systems with switch-in and switch-out times, where service is in batches of unlimited size. We concentrate on so-called "Hamiltonian tour" policies in which, in order to give a fair treatment to the various users, the server attends every nonempty queue exactly once during each round of visits (cycle). The server dynamically generates a new visit schedule at the start of each round, depending on the current state of the system (number of jobs in each queue) and on the various nonhomogeneous system parameters. We consider three service regimes, globally gated, (locally) gated, and exhaustive, and study three different performance measures: (1) minimizing the expected weighted sum of all sojourn times of jobs within a cycle; (2) minimizing the expected length of the next cycle, and (3) maximizing the expected weighted throughput in a cycle. For each combination of performance measure and service regime, we derive characteristics of the optimal Hamiltonian tour. Some of the resulting optimal policies are shown to be elegant index-type rules. Others are the solutions of deterministic NP-hard problems. Special cases are reduced to assignment problems with specific cost matrices. The index-type rules can further be used to construct fixed-order, cyclic-type polling tables in cases where dynamic control is not applicable.
引用
收藏
页码:351 / 367
页数:17
相关论文
共 22 条
[1]  
Ahuja RK, 1993, NETWORK FLOWS THEORY
[2]   Polling in a closed network [J].
Altman, Eitan ;
Yechiali, Uri .
Probability in the Engineering and Informational Sciences, 1994, 8 (03) :327-343
[3]   ON THE OPTIMALITY OF CYCLIC TRANSMISSION IN TELETEXT SYSTEMS [J].
AMMAR, MH ;
WONG, JW .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1987, 35 (01) :68-73
[4]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[5]  
[Anonymous], ACM COMPUTING SURVEY
[6]  
Armony R, 1999, STOCH MODELS, V15, P395
[7]  
BOXMA O, 1991, ANN OPER RES, V36, P187
[8]  
BOXMA OJ, 1991, NORTH HOLL STUD TELE, V15, P173
[9]   DYNAMIC PRIORITY RULES FOR CYCLIC-TYPE QUEUES [J].
BROWNE, S ;
YECHIALI, U .
ADVANCES IN APPLIED PROBABILITY, 1989, 21 (02) :432-450
[10]   Closed polling models with failing nodes [J].
Dror, H ;
Yechiali, U .
QUEUEING SYSTEMS, 2000, 35 (1-4) :55-81