Проблема аренды лыж в нескольких магазинах

Проблема аренды лыж (SR) – это дилемма, с которой сталкивается потребитель, который не знает, сколько дней он будет кататься на лыжах, и вынужден выбирать между покупкой и арендой лыж: как только он купит лыжи, он будет наслаждаться оставшимися днями без арендной платы, но перед этим она должна оплатить ежедневную стоимость аренды. Есть много публикаций изучения оптимальной онлайн-стратегии потребителя. Таким образом, стратегия, которая дает самое низкое конкурентное отношение без какой-либо информации о будущем (как это стандартно в литературе, конкурентное отношение определяется как отношение между стоимостью, полученной в результате стратегии потребителя, и стоимостью, полученной из неправильная стратегия пророка, который предвидит, сколько дней продлится поездка, и соответственно разработает оптимальную стратегию). Проблема проката лыж (например, Домбай прокат) и ее варианты составляют важную часть онлайн-литературы по разработке алгоритмов как с теоретической, так и с прикладной точек зрения [9, 12, 16, 17, 18, 22].

В этой статье мы рассмотрим проблему аренды лыж в нескольких магазинах (MSR), когда потребитель сталкивается с несколькими магазинами, предлагающими разные цены аренды и покупки. Она должна выбрать один магазин сразу после прибытия на лыжную площадку и с тех пор должна арендовать или купить лыжи в этом конкретном магазине. Другими словами, после того, как она выбрала магазин, единственная переменная решения – это когда покупать лыжи. Помимо базовой настройки, мы также предлагаем три важных расширения MSR, как показано ниже:

• MSR со стоимостью переключения (MSR-S): потребителю разрешено переключаться из одного магазина в другой, и каждое переключение стоит ему постоянную сумму денег.
• MSR с вступительным взносом (MSR-E): каждый магазин требует некоторого вступительного взноса, и покупатель не может сменить магазин.
• MSR с платой за вход и переключением (MSR-ES): потребитель может переключаться из одного магазина в другой, и он оплачивает вступительный взнос, пока он входит в любой магазин.

Во всех вышеперечисленных настройках цель потребителя – минимизировать конкурентное соотношение. В MSR и MSR-E она должна рассмотреть два вопроса в самом начале: (1) где она должна взять напрокат или купить лыжи (место), и (2) когда она должна купить лыжи (время)? В то время как MSR-S и MSR-ES позволяют потребителю переключаться между магазинами и, таким образом, более детализированы, чем предыдущие два, в том смысле, что она может решить, где взять напрокат или купить лыжи в любое время. Например, это один из ее вариантов: арендовать в магазине 1 в первый день, перейти в магазин 2 со второго дня и, наконец, перейти в магазин 3, а затем купить лыжи.

Проблема аренды лыж в нескольких магазинах, естественно, расширяет проблему аренды лыж и допускает неоднородность в выборе покупателя, что является желательной особенностью, которая делает проблему аренды лыж более общей основой моделирования для онлайн-алгоритма. Ниже мы представляем несколько реальных сценариев, которые могут быть смоделированы с проблемой аренды лыж в нескольких магазинах.

1. Планирование в распределенных вычислениях: файл реплицируется и хранится на разных компьютерах в кластере. Некоторому узлу, выполняющему некоторую вычислительную работу, нужны данные в файле во время выполнения. Узел может либо запросить соответствующий блок данных файла с некоторой выбранной машины, когда это необходимо, что вызывает некоторую задержку, либо он может просто попросить эту машину заранее передать весь файл целиком, жертвуя более длинной задержкой в ​​начале. – без дальнейших ожиданий. При выборе реплицирующего компьютера узел планирования должен учитывать текущую пропускную способность, задержку чтения и т.д. В этом приложении каждый реплицирующий компьютер рассматривается как магазин, и аренда соответствует запросу на блок данных по требованию. во время покупки означает получить весь файл заранее.

2. Управление затратами в облаке IaaS: Несколько поставщиков облаков IaaS, таких как Amazon EC2 [1], ElasticHosts [4] и Microsoft Windows Azure [6], предлагают разные варианты цен, которые можно разделить на два уровня обязательств: пользователи платят за экземпляры сервера по требованию по почасовой ставке или единовременный авансовый платеж для размещения каждого экземпляра в течение некоторого периода времени (например, ежемесячно или ежегодно), в течение которого пользователи либо используют экземпляры бесплатно [4], либо получают скидку на аренду экземпляра [1].

Рассмотрим пример из Таблицы 1. В таблице 1 перечислены варианты ценообразования для экземпляров с идентичными конфигурациями, предлагаемыми Amazon EC2 и ElasticHosts. Каждый вариант ценообразования можно рассматривать как магазин в рамках проблемы аренды лыж в нескольких магазинах, где в контракте на 1 (3) год (ы) в Amazon EC2 вступительный взнос является авансовым платежом, а почасовая цена – ценой аренды.

Таблица 1. Варианты ценообразования для «одного и того же» экземпляра в Amazon EC2 (c1.medium) и ElasticHosts.

3. Решения о покупке: Компания, предлагающая услугу спутниковой или спутниковой карт высокого разрешения, выбирает между Astrium [2] и DigitalGlobe [3]. Он может либо подписаться на изображения от одной компании, либо занимать исключительно службу, «покупая» один спутник, как это сделал Google [19]. Аналогичные приложения включают человека, покупающего SIM-карту у разных телекоммуникационных компаний.

Выводы

В этой статье рассмотрели проблему аренды лыж в нескольких магазинах (MSR) и ее расширения (MSR-S, MSR-E и MSR-ES), в которых есть несколько магазинов, и потребитель хочет минимизировать конкурентную борьбу. соотношение.

Для каждой проблемы доказано, что в оптимальной смешанной стратегии потребителя она назначает положительную вероятность покупки только одному магазину в любое время. Заказ в магазине тесно связан с соотношением между покупной ценой и арендной ценой, даже с учетом вступительного взноса. Далее, в основной задаче (MSR) выводится линейный алгоритм времени для вычисления оптимальной стратегии потребителя. Для MSR-S доказано, что в соответствии с оптимальной смешанной стратегией потребитель переключается в другой магазин только во время покупки. В задачах MSR-E и MSR-ES показано, что оптимальная стратегия может быть решена, если известны точки останова. Подобно основной задаче (MSR), мы предполагаем, что квазивогнутое свойство также справедливо для этих двух вариантов. Кроме того, показано, что существует итерационный алгоритм, использующий метод градиентного приличия, который может сходиться к цифрам в каждом виртуальном магазине, может быть больше 1. К счастью, оптимальное решение.

Использованные источники

[1] Amazon EC2, aws.amazon.com/ec2/.

[2]   Astrium, astrium-geo.com/.

[3]  Digitalglobe, digitalglobe.com/.

[4]   Elastichosts, elastichosts.com/.

[5] The multi-shop ski rental problem, sites. google.com/site/multishopskirental/MSRtech.pdf.

[6]   Microsoft  Windows  Azure, gogrid.com/. [7] C. Bodenstein, M. Hedwig, and D. Neumann. Strategic decision support for smart-leasing infrastructure-as-a-service.  2011.

[8] M. de Berg, M. van Kreveld, M. Overmars, Schwarzkopf, and M. Overmars. Computational geometry: algorithms and applications. 2000. New York, New York.

[9]  R. Fleischer. On the bahncard problem. Theoretical Computer Science, 268(1):161–174, 2001.

[10] B. Guenter, N. Jain, and C. Williams. Managing cost, performance, and reliability tradeoffs for energy-aware server provisioning. In INFOCOM, 2011 Proceedings IEEE, pages 1332–1340. IEEE, 2011.

[11]  Y.-J. Hong, J. Xue, and M. Thottethodi. Dynamic server provisioning to minimize cost in an iaas cloud. In Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, pages 147–148. ACM, 2011.

[13] A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542–571, 1994.

[14] A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3(1-4):79–119, 1988.

[15]  A. Khanafer, M. Kodialam, and K. P. Puttaswamy. The constrained ski-rental problem and its application to online cloud cost optimization. In Proc. IEEE INFOCOM, 2013.

[16] M. Lin, A. Wierman, L. L. Andrew, and E. Thereska. Dynamic right-sizing for power-proportional data centers. In INFOCOM, 2011 Proceedings IEEE, pages 1098–1106. IEEE, 2011.

[17] Z. Lotker, B. Patt-Shamir, D. Rawitz, S. Albers, and P. Weil. Rent, lease or buy: Randomized algorithms for multislope ski rental. In 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), volume 1, pages 503–514. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2008.

[18] T. Lu and M. Chen. Simple and effective dynamic provisioning for power-proportional data centers. In Information Sciences and Systems (CISS), 2012 46th Annual Conference on, pages 1–6. IEEE, 2012.

[19] S. Shankland. Google to buy GeoEye satellite imagery, news.cnet.com/8301-1023_3-10028842-93.html. [20] R. Singh, U. Sharma, E. Cecchet, and P. Shenoy. Autonomic mix-aware provisioning for non-stationary data center workloads. In Proceedings of the 7th international conference on Autonomic computing, pages 21–30. ACM, 2010.

[21] C. Wang, B. Urgaonkar, Q. Wang, G. Kesidis, and A. Sivasubramaniam. Data center cost optimization via workload modulation under real-world electricity pricing. arXiv preprint arXiv:1308.0585, 2013.

[22] W. Wang, B. Li, and B. Liang. To reserve or not to reserve: Optimal online multi-instance acquisition in iaas clouds. arXiv preprint arXiv:1305.5608, 2013.

The Multi-shop Ski Rental Problem
Lingqing Ai