Рубрика «bin packing»

в 10:22, , рубрики: bin packing, vm placement optimization, виртуализация, высокая производительность, Облачные вычисления, Серверная оптимизация

Какое-то время назад один мой коллега рассказал, что место в ДЦ кончается, сервера ставить больше некуда, а нагрузка растет и непонятно, что делать, и наверно придется все имеющиеся сервера поменять на более мощные.

Я в это время занимался задачей составления оптимальных расписаний, и подумал — а что, если применить оптимизационные алгоритмы для повышения утилизации серверов в ДЦ? Отсюда и родился проект, про который я хочу написать.

Для продвинутых сразу скажу, что в этой статье речь пойдет про bin packing, а остальным, кто хочет узнать, как с помощью относительно несложных расчетов сэкономить до 30% серверных ресурсов, добро пожаловать под кат.
Читать полностью »

в 5:03, , рубрики: bin packing, c++, qt, микроконтроллеры, Песочница, Программинг микроконтроллеров, протокол, Сетевые технологии, метки: , , , ,

Дробление непрерывного потока данных на структурные единицы

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

Такие задачи возникают, к примеру, при передаче телеметрии и для управления удаленным оборудованием. С одной стороны обычно стоит простейший микроконтроллер, с другой стороны стоит компьютер. Связь между ними может осуществляться по старому, доброму RS232. Хотя бывает и сложнее, например, выход микроконтроллера UART преобразуется в 802.11b, затем идет распространение радиосигнала до радиомачты и в сервер приходит Ethernet.

Если интересен мой велосипед на эту тему, добро пожаловать под кат.
Читать полностью »

в 21:10, , рубрики: 2DSP, bin packing, Алгоритмы, двумерная упаковка, задача о рюкзаке, метки: , , ,

Про двумерную упаковку: online алгоритмыЭто продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

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

в 14:55, , рубрики: 2DSP, bin packing, Алгоритмы, двумерная упаковка, задача о рюкзаке, метки: , , ,

Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

Читать полностью »

в 15:07, , рубрики: bin packing, EvoJ, генетические алгоритмы, генетический алгоритм, метки: , , ,

Доброго времени суток, коллеги.
Этой статьей я продолжаю цикл посвященный EvoJ — Java фреймворку для решения задач генетическим алгоритмом.
В своей предыдущей заметке я познакомил читателей Хабра с основными принципами работы с EvoJ.

Сегодня мы рассмотрим, как при помощи EvoJ можно решить задачу упаковки в контейнеры.

Постановка задачи

Если в двух словах, то задача упаковки в контейнеры ставится следущим образом: имеется набор контейнеров определенного объема, и набор предметов, которые в эти контейнеры требуется уложить (вЧитать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js