Partial flexibility in routeing and scheduling.

*(English)*Zbl 1273.90049Summary: We consider partial customer flexibility in service systems under two different designs. In the first design, flexible customers have their own queue and each server has its own queue of dedicated customers. Under this model, the problem is a scheduling problem and we show under various settings that the dedicated customers first (DCF) policy is optimal. In the second design, flexible customers are not queued separately and must be routed to one of the server’s dedicated queues upon arrival. We extend earlier results about the ‘join the smallest work (JSW)’ policy to systems with dedicated as well as flexible arrivals. We compare these models to a routeing model in which only the queue length is available in terms of both efficiency and fairness and argue that the overall best approach for call centers is JSW routeing. We also discuss how this can be implemented in call centers even when work is unknown.

##### MSC:

90B22 | Queues and service in operations research |

60K25 | Queueing theory (aspects of probability theory) |

PDF
BibTeX
XML
Cite

\textit{O. T. Akgun} et al., Adv. Appl. Probab. 45, No. 3, 673--691 (2013; Zbl 1273.90049)

**OpenURL**

##### References:

[1] | Aalto, S., Ayesta, U. and Righter, R. (2009). On the Gittins index in the M/G/1 queue. Queueing Systems 63 , 437-458. · Zbl 1209.90100 |

[2] | Ahn, H.-S., Duenyas, I. and Zhang, R. Q. (2004). Optimal control of a flexible server. Adv. Appl. Prob. 36 , 139-170. · Zbl 1072.93029 |

[3] | Akgun, O. T., Righter, R. and Wolff, R. (2011). Multiple-server system with flexible arrivals. Adv. Appl. Prob. 43 , 985-1004. · Zbl 1229.90041 |

[4] | Aksin, Z., Armony, M. and Mehrotra, V. (2007). The modern call-center: A multi-disciplinary perspective on operations management research. Prod. Operat. Manag. 16 , 665-688. |

[5] | Bambos, N. and Michailidis, G. (2002). On parallel queueing with random server connectivity and routing constraints. Prob. Eng. Inf. Sci. 16 , 185-203. · Zbl 1014.90021 |

[6] | Bell, S. L. and Williams, R. J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. Ann. Appl. Prob. 11 , 608-649. · Zbl 1015.60080 |

[7] | Daley, D. J. (1987). Certain optimality properties of the first-come first-served discipline for \(G/G/s\) queues. Stoch. Process. Appl. 25 , 301-308. · Zbl 0642.60077 |

[8] | Down, D. G. and Lewis, M. E. (2010). The \(N\)-network model with upgrades. Prob. Eng. Inf. Sci. 24 , 171-200. · Zbl 1189.90048 |

[9] | Ephremides, A., Varaiya, P. and Walrand, J. (1980). A simple dynamic routing problem. IEEE Trans. Automatic Control 25 , 690-693. · Zbl 0451.90060 |

[10] | Foley, R. D. and McDonald, D. R. (2001). Join the shortest queue: stability and exact asymptotics. Ann. Appl. Prob. 11 , 569-607. · Zbl 1016.60078 |

[11] | Foss, S. G. (1980). Approximation of multichannel queueing systems. Siberian Math. J. 21 , 851-857. · Zbl 0461.60097 |

[12] | Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: Tutorial, review and research prospects. Manufact. Service Operat. Manag. 5 , 79-141. |

[13] | Garnett, O. and Mandelbaum, A. (2000). An introduction to skills-based routing and its operational complexities. Teaching note, Technion, Haifa, Israel. |

[14] | Gurumurthi, S. and Benjaafar, S. (2004). Modeling and analysis of flexible queuing systems. Naval Res. Logistics 51 , 755-782. · Zbl 1054.90017 |

[15] | Harchol-Balter, M., Crovella, M. E. and Murta, C. D. (1999). On choosing a task assignment policy for a distributed server system. J. Paral. Distr. Comput. 59 , 204-228. |

[16] | Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. Ann. Appl. Prob. 8 , 822-848. · Zbl 0938.60094 |

[17] | Harrison, J. M. and López, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33 , 339-368. · Zbl 0997.60108 |

[18] | Hordijk, A. and Koole, G. (1990). On the optimality of the generalized shortest queue policy. Prob. Eng. Inf. Sci. 4 , 477-487. · Zbl 1134.90340 |

[19] | Hytia, E., Aaalto, S., Penttinen, A. and Virtamo, J. (2012). On the value function of the \(M/G/1\) FIFO and LIFO queues. Submitted. |

[20] | Johri, P. K. (1989). Optimality of the shortest line discipline with state-dependent service times. Europ. J. Operat. Res. 41 , 157-161. · Zbl 0675.60084 |

[21] | Koole, G. (1992). On the optimality of FCFS for networks of multi-server queues. Tech. Rep. BS-R923, CWI, Amsterdam. |

[22] | Koole, G. (1992). Stochastic scheduling and dynamic programming. Doctoral Thesis, Leiden University. · Zbl 0851.90065 |

[23] | Koole, G., Sparaggis, P. D. and Towsley, D. (1999). Minimising response times and queue lengths in systems of parallel queues. J. Appl. Prob. 36 , 1185-1193. · Zbl 0985.60082 |

[24] | Liu, Z. and Righter, R. (1998). Optimal load balancing on distributed homogeneous unreliable processors. Operat. Res. 46 , 563-573. · Zbl 0987.90046 |

[25] | Liu, Z. and Towsley, D. (1994). Optimality of the round-robin routing policy. J. Appl. Prob. 31 , 466-475. · Zbl 0804.60080 |

[26] | Liu, Z., Nain, P. and Towsley, D. (1995). Sample path methods in the control of queues. Queueing Systems 21 , 293-335. · Zbl 0855.60094 |

[27] | Mandelbaum, A. and Stolyar, A. L. (2004). Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized \(c\mu\)-rule. Operat. Res. 52 , 836-855. · Zbl 1165.90402 |

[28] | Marshall, A. W. and Olkin, I. (1979). Inequalities: Theory of Majorization and Its Applications . Academic Press, New York. · Zbl 0437.26007 |

[29] | Menich, R. and Serfozo, R. F. (1991). Optimality of routing and servicing in dependent parallel processing stations. Queueing Systems 9 , 403-418. · Zbl 0748.90077 |

[30] | Movaghar, A. (2005). Optimal control of parallel queues with impatient customers. Performance Evaluation 60 , 327-343. |

[31] | Righter, R. and Shanthikumar, J. G. (1989). Scheduling multiclass single server queueing systems to stochastically maximize the number of successful departures. Prob. Eng. Inf. Sci. 3 , 323-333. · Zbl 1134.90413 |

[32] | Saghafian, S., Van Oyen, M. P. and Kolfal, B. (2010). The “W” network and the dynamic control of unreliable flexible servers. IIE Trans. 43 , 893-907. |

[33] | Shaked, M. and Shanthikumar, G. J. (1994). Stochastic Orders and Their Applications . Academic Press, Boston, MA. · Zbl 0806.62009 |

[34] | Sparaggis, P. D. and Towsley, D. (1994). Optimal routing and scheduling of customers with deadlines. Prob. Eng. Inf. Sci. 8 , 33-49. |

[35] | Sparaggis, P. D., Towsley, D. and Cassandras, C. G. (1993). Extremal properties of the shortest/longest nonfull queue policies in finite-capacity systems with state-dependent service rates. J. Appl. Prob. 30 , 223-236. · Zbl 0768.60090 |

[36] | Stoyan, D. (1976). A critical remark on a system approximation in queueing theory. Math. Operationsforsch. Statist. 7 , 953-956. · Zbl 0363.60089 |

[37] | Towsley, D., Sparaggis, P. D. and Cassandras, C. G. (1990). Stochastic ordering properties and optimal routing control for a class of finite capacity queueing systems. In Proc. 29th IEEE Conf. Decision and Control , pp. 658-663. |

[38] | Weber, R. R. (1978). On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15 , 406-413. · Zbl 0378.60095 |

[39] | Winston, W. (1977). Optimality of the shortest line discipline. J. Appl. Prob. 14 , 181-189. · Zbl 0357.60023 |

[40] | Wolff, R. W. (1977). An upper bound for multichannel queues. J. Appl. Prob. 14 , 884-888. · Zbl 0378.60097 |

[41] | Wolff, R. W. (1987). Upper bounds on work in system for multi-channel queues. J. Appl. Prob. 24 , 547-551. · Zbl 0625.60112 |

[42] | Wolff, R. W. (1989). Stochastic Modeling and Theory of Queues . Prentice Hall, Englewood Cliffs, NJ. · Zbl 0701.60083 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.