О задаче составления расписания работы операторов центра обработки вызовов

О задаче составления расписания работы операторов центра обработки вызовов

Еремеев А. В., Сахно М. А.
Дискретный анализ и исследование операций, 30, 2, 48-66 (2023)
Скачать статью

УДК 519.85 
DOI: 10.33048/daio.2023.30.735

Аннотация:

Работа посвящена решению задачи составления расписаний работы персонала центра обработки вызовов. Сформулирована модель целочисленного линейного программирования, доказана труднорешаемость задачи, предложен генетический алгоритм, учитывающий специфику задачи, а также проведено экспериментальное сравнение оптимальных решений, полученных с помощью пакета CPLEX, с решениями, найденными генетическим алгоритмом. Вычислительный эксперимент показал практически приемлемую точность решений, полученных генетическим алгоритмом, и его применимость к задачам большой размерности. 
Табл. 1, библиогр. 18.

Литература:
  1. Gans N., Koole G., Mandelbaum A. Telephone call centers: Tutorial, review, and research prospects // Manuf. Serv. Oper. Manag. 2003. V. 5, No. 2. P. 79–141.
     
  2. Avramidis A. N., Deslauriers A., L’Ecuyer. P. Modeling daily arrivals to a telephone call center // Manag. Sci. 2004. V. 50. P. 896–908.
     
  3. Brown L., Gans N., Mandelbaum A., Sakov A., Shen H., Zeltyn S., Zhao L. Statistical analysis of a telephone call center: A queueing-science perspective // J. Am. Stat. Assoc. 2010. V. 100. P. 36–50.
     
  4. Mehrotra V. Ringing up big business // ORMS Today. 1997. V. 24. P. 18–24.
     
  5. Cezik M., L’Ecuyer P. Staffing multi-skill call centers via linear programming and simulation // Manag. Sci. 2008. V. 54. P. 310–323.
     
  6.  Avramidis A. N., Chan W., L’Ecuyer P. Staffing multi-skill call centers via search methods and a performance approximation // IIE Trans. 2009. V. 41, No. 6. P. 483–497.
     
  7. Pot A., Bhulai S., Koole G. A simple staffing method for multi-skill call centers // Manuf. Serv. Oper. Manag. 2008. V. 10, No. 3. P. 421–428.
     
  8. Zaozerskaya L. A. A heuristic for a special case of the generalized assignment problem with additional conditions // J. Phys. Conf. Ser. 2021. V. 1791, No. 1, ID 012092. 6 p.
     
  9. Bhulai S., Koole G., Pot A. Simple methods for shift scheduling in multiskill call centers // Manuf. Serv. Oper. Manag. 2008. V. 10, No. 3. P. 411–420.
     
  10. Avramidis A. N., Chan W., Gendreau M., L’Ecuyer P., Pisacane O. Optimizing daily agent scheduling in a multi-skill call center // Eur. J. Oper. Res. 2010. V. 200. P. 822–832.
     
  11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 c.
     
  12.  Holland J. Adaptation in natural and artificial systems. Ann Arbor: Univ. Michigan Press, 1975. 183 p.
     
  13. Baker J. E. Adaptive selection methods for genetic algorithms // Proc. Int. Conf. Genetic Algorithms and Their Applications (Pittsburgh, PA, USA, July 24–26, 1985). Pittsburgh, PA: Carnegie-Mellon Univ., 1985. P. 101–111. 
     
  14. Lehre P. K. Fitness-levels for non-elitist populations // Proc. 13th Annu. Conf. Genetic and Evolutionary Computation (Dublin, Ireland, July 12–16, 2011). New York: ACM, 2011. P. 2075–2082.
     
  15. Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // Eur. J. Oper. Res. 2009. V. 195. P. 770–779.
     
  16. Hampson S., Kibler D. Large plateaus and plateau search in Boolean Satisfiability problems: When to give up searching and start again // Cliques, Coloring and Satisfiability. Proc. 2nd DIMACS Implementation Challenge, Workshop (Piscataway, USA, Oct. 11–13, 1993). Providence: AMS, 1996. P. 437–456.
     
  17. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems // J. Heuristics. 1998. V. 4, No. 2. P. 107–122.
     
  18. Тюнин Н. Н., Еремеев А. В. Алгоритм дифференциальной эволюции для оптимизации направленности фазированных антенных решёток // Мат. структуры и моделирование. 2022. № 3. С. 57–68.

Исследование выполнено за счёт гранта Российского научного фонда (проект № 21–41–09017).

Еремеев Антон Валентинович
  1. Институт математики им. С. Л. Соболева, Омский филиал, 
    ул. Певцова, 13, 644099 Омск, Россия

E-mail: eremeev@ofim.oscsbras.ru

Сахно Максим Алексеевич
  1. Институт математики им. С. Л. Соболева, Омский филиал, 
    ул. Певцова, 13, 644099 Омск, Россия

E-mail: maxim.sakhno@gmail.com

Статья поступила 29 апреля 2022 г. 
После доработки — 25 января 2023 г. 
Принята к публикации 13 февраля 2023 г.

Abstract:

The paper is devoted to solving the problem of scheduling the work of the call center staff. A model of integer linear programming is formulated, the problem is shown to be NP-hard, and a genetic algorithm is proposed that takes into account the specifics of the problem. An experimental comparison of optimal solutions obtained using the CPLEX package with solutions found by the genetic algorithm is carried out. The computational experiment showed the practically acceptable accuracy of the solutions obtained by the genetic algorithm and its applicability to large-dimensional problems. 
Tab. 1, bibliogr. 18.

References:
  1. N. Gans, G. Koole, and A. Mandelbaum, Telephone call centers: Tutorial, review, and research prospects, Manuf. Serv. Oper. Manag. 5 (2), 79–141 (2003).
     
  2. A. N. Avramidis, A. Deslauriers, and P. L’Ecuyer, Modeling daily arrivals to a telephone call center, Manag. Sci. 50, 896–908 (2004).
     
  3. L. Brown, N. Gans, A. Mandelbaum, A. Sakov, H. Shen, S. Zeltyn, and L. Zhao, Statistical analysis of a telephone call center: A queueing-science perspective, J. Am. Stat. Assoc. 100, 36–50 (2010).
     
  4. V. Mehrotra, Ringing up big business, ORMS Today 24, 18–24 (1997).
     
  5. M. Cezik and P. L’Ecuyer, Staffing multi-skill call centers via linear programming and simulation, Manag. Sci. 54, 310–323 (2008).
     
  6. A. N. Avramidis, W. Chan, and P. L’Ecuyer, Staffing multi-skill call centers via search methods and a performance approximation, IIE Trans. 41 (6), 483–497 (2009).
     
  7. A. Pot, S. Bhulai, and G. Koole, A simple staffing method for multi-skill call centers, Manuf. Serv. Oper. Manag. 10 (3), 421–428 (2008).
     
  8. L. A. Zaozerskaya, A heuristic for a special case of the generalized assignment problem with additional conditions, J. Phys. Conf. Ser. 1791 (1), ID 012092, 6 p. (2021).
     
  9. S. Bhulai, G. Koole, and A. Pot, Simple methods for shift scheduling in multi-skill call centers, Manuf. Serv. Oper. Manag. 10 (3), 411–420 (2008).
     
  10. A. N. Avramidis, W. Chan, M. Gendreau, P. L’Ecuyer, and O. Pisacane, Optimizing daily agent scheduling in a multi-skill call center, Eur. J. Oper. Res. 200, 822–832 (2010).
     
  11. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  12. J. Holland, Adaptation in Natural and Artificial Systems (Univ. Michigan Press, Ann Arbor, 1975).
     
  13. J. E. Baker, Adaptive selection methods for genetic algorithms, in Proc. Int. Conf. Genetic Algorithms and Their Applications, Pittsburgh, PA, USA, July 24–26, 1985 (Carnegie-Mellon Univ., Pittsburgh, PA, 1985), pp. 101–111. 
     
  14. P. K. Lehre, Fitness-levels for non-elitist populations, in Proc. 13th Annu. Conf. Genetic and Evolutionary Computation, Dublin, Ireland, July 12–16, 2011 (ACM, New York, 2011), pp. 2075–2082.
     
  15. P. Borisovsky, A. Dolgui, and A. Eremeev, Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder, Eur. J. Oper. Res. 195, 770–779 (2009).
     
  16. S. Hampson and D. Kibler, Large plateaus and plateau search in Boolean Satisfiability problems: When to give up searching and start again, in Cliques, Coloring and Satisfiability (Proc. 2nd DIMACS Implementation Challenge, Workshop, Piscataway, USA, Oct. 11–13, 1993) (AMS, Providence, 1996), pp. 437–456.
     
  17. E. Balas and W. Niehaus, Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems, J. Heuristics 4 (2), 107–122 (1998).
     
  18. N. N. Tyunin and A. V. Eremeev, Differential evolution for directivity optimization of short-wave phased antenna arrays, Mat. Strukt. Model., No. 3, 57–68 (2022) [Russian].