Comments 38
Как соотносится
есть необходимость отбора товара по FIFO
с тем что остаются штучные остатки партий?
Если честно, не совсем понял вопроса, но постараюсь ответить. Штучные остатки во многих ячейках остаются потому что в 1 ячейке должна храниться только 1 партия (это требование из-за специфики продукции), а партий много, они каждый день приходят.

А по FIFO отбираем чтобы не оставалось старого залежавшегося товара на складе.

Если не ответил на вопрос, то поясните, что имели ввиду
Приходят то понятно что каждый день, но почему они не уходят по ФИФО?
Начало:
1 партия - 50 шт
2 партия - 50 шт
Забрали - 49 шт
Остаток:
1 партия - 1 шт
2 партия - 50 шт
Забрали - 50 шт
Остаток:
1 партия - 0 шт
2 партия - 1 шт

При списании по ФИФО, никаких штучных остатков не должно оставаться… А если у вас остаются, значит у вас нет ФИФО.
да, вы все верно написали, но это если не учитывать специфику складских операций. По факту ячейки с мелкими остатками товаров получаются из-за таких основных причин:

1. Каждый день: новая партия производства, так как новая дата. В результате получаем что небольшое количество штучных остатков помещаются в разные ячейки, хотя можно было поместить, например, в одну (сжать).

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

Учет по датам производства был требованием заказчика, так как до внедрения WMS системы у них была проблема с устареванием товара на складе.
По идее, если использовать постоянную «разницу дат», то всё равно ячейки будут заполняться неравномерно — где больше, где меньше. Может задачу немного переформулировать?
к этому термину «постоянная разница дат» мы с заказчиком приходили уже как-то :) Вы, наверное, имеете ввиду учет постоянной разницы дат при самОм помещении товаров в ячейки? То есть перед помещением товара в ячейку учитываем даты имеющиеся в ячейках, и кладем товар в ту ячейку, где партия отличается не более чем на заданную постоянную разницу дат. Верно я понял Вас?

Но тогда даже возникает потребность в сжатии, хотя конечно ситуацию улучшает (они так и делают сейчас). Могу в принципе показать на примере, но, думаю, вы его сами можете смоделировать :)
Нет, я имел в виду решать немного другую задачу: вместо «найти партии в фиксированном промежутке дат» >>> «заполнить ячейки как можно плотнее». Т.е. разница дат может быть не постоянной в 30 дней, но товары всё равно будут из ближайших партий.
Вообще интересно, как это происходит на практике у заказчика. Например, алгоритм нашел новое распределение. Надо переложить товары — но это же огромный объем работы для большого склада. Или эта процедура происходит не часто?
30 дней это максимальная разница дат между каждой парой партий в кластере. По факту разница может быть и 5 и 1 и даже 0 дней. А большей этой даты в 30 дней клиент не хочет товар объединять, так как краны это не пирожки конечно же, но тоже свой срок годности на складе имеют (может ржавчина появиться без спец покрытия и т.д.). Или вы другое имели ввиду?

процедура делается регламентно раз в неделю или по требованию, когда места критически мало становится.
Ясно, я думал можно объединять с бОльшим разбросом дат.
Интересно, как ваш алгоритм объединит их и разложит по двум ячейкам в такой ситуации?
Например, есть три Партии в трёх разных Ячейках — День 1 = 50; День 29=50; День 30=50. Ячейка вмещает 100. Все даты в одном промежутке 30 дней.
это хороший вопрос. Как раз здесь выходят на сцену алгоритмы комбинаторной оптимизации (скоро опубликуем в следующих статьях). Будет учитываться расстояние между ячейками. Оно в данном случае будет играть ключевую роль. Будем рады дельным комментам в следующих публикациях :)

Учёт шаровых кранов в разрезе дат изготовления — это похоже на создание себе трудностей с их последующим героическим преодолением. Более логичен учёт по сериям, например, с возрастанием номера серии раз в месяц.

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

Даже в том решение, которое вы предлагаете, возникнет потребность с сжатии (думаю, вы сами сможете это смоделировать).

на похожий вопрос ответил в комментарии
Компрессия склада нужна при любом алгоритме.
Пришла претензия на битые товары? И что? Это может быть как заводской брак, так и удар на складе, так и в машине перевозчика…
Ни разу на моей памяти ударенный(отгруженный товар) не компенсировали за счет склада; уверен что в 99.99% случаев битый товар просто списывается(разбирается по возможности).

Вот если «жахнули» на складе — тогда и вопросов нет, но там и историю отслеживать не нужно — все и так видно кто-где накосячил… камеры то стоят =)
отслеживание нужно по большей части для санкций к конкретным сотрудникам, чтобы впредь этого не делали и репутацию компании не портили. А кто именно, определяется по операциям. Получается набор моментов времени, а там уже смотрят камеры если нужно :)

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

да, решений по прослеживаемости действительно много. Для тотальной прослежки можно ввести уникальные идентификаторы на каждую единицу упаковки товара, но это влечет трудности с выполнением складских операций (за прозрачность нужно платить). Если без партий вообще (все в общий котел), то там очень долго и трудно концы искать потом.
Могу ошибаться, но предположу, что задача классифицирована неправильно.
По-моему, это занимательная «математическая» задача, но не более того.
Ведь если изобразить партии на временной оси (0, T), то, если там нет пропусков длиной более C, тогда минимальное число партий ВСЕГДА будет ] T / С [, то есть ближайшее сверху целое от деления размера интервала между первой и последней партией на «масштабный коэффициент» С.
Если промежутки есть, то к каждому разделенному промежутками «островку» применяется та же формула, определяющая число партий.
То есть минимальное число партий однозначно определяется простой формулой. Из нее же следует очевидный алгоритм разбиения на партии. Для реализации которого и 1С будет достаточно (даже запросом можно обойтись).
Некоторая вариативность просматривается в мелком движении границ партий, если до ближайшего сверху есть зазор ] T / С [ — T / С. Но на число партий это не повлияет.
А еще легче было бы вообще помечать партии не днем, а месяцем выпуска. В итоге бизнес-результат, думаю, был бы тем же.
А вот если бы декомпозиции на две задачи: «укрупнение партий» и «компрессия ячеек» не было, то задача в целом была бы поинтереснее.
то, если там нет пропусков длиной более C, тогда минимальное число партий ВСЕГДА будет ] T / С [

Наверное имелось ввиду: если разбить интервал от Тmin до Тmax, с длиной пропуска С — всегда получится точное количество новых партий (при округлении вверх). Разница формирования будет зависеть лишь от направлении сворачивания партий слева-справа.


Аналогично считаю что отметка партии месяцем — дала бы точно такой же бизнес-результат.

коммент интересный, спасибо, но вы немного не правы :) Поясню.
1. Если взять такую ситуацию, что промежутков больше C нет, то как вы выражаетесь "]T/С[" является верхней оценкой величины минимального числа партий. То есть больше быть не может, а вот меньше да ]T/С[ — 1. Например, вот рисунок. Здесь Т делится нацело на С.

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

В вашем 2-м решении в одном кластере оказались партии с датами более С

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

image
Как у вас 1,2 и 3 партии слились, если разница между 1 и 3 превышает С?
Аналогично 6,7,8....

так это 2 разные ситуации. Они никак не связаны. В первой ситуации, только на 4 группы можно, а во воторой на 3. Или я Вас не так понял?
  1. Алгоритм не от 0 до Tmax — а от Tmin до Tmax, результат тот же был...
  2. Почему то для центра кластера выбирается "взвешенная" дата партии — при таком раскладе ай ай ай…
    1 мелкая партия
    2 и 3 партии большие
    На первом этапе: 1 и 2 партии сливаются — центр смещается ко второй
    На втором этапе уже 4( 1 + 2) и 3 партия сливаются и тут ай ай ай ой ой ой. По факту 1 и 3 партия слились, что не допустимо по условиям задачи =)
    image

p.s. да в общем то неважно какой центр выбирать… что так, то эдак. Пока не будет информации о минимальной и максимальной даты в партии — будут некорректные слияния

1. разницы для 0 до Tmax и для от Tmin до Tmax не вижу. От Tmin можно прийти в 0, если от всех дат вычесть Tmin, как бы нормировать.
2. Что Вы понимаете под весом, и почему решили, что он взялся? Количество штук в партии при кластеризации не учитывается.
  1. тогда Tmax — уже будет не тот
  2. Дата результирующей партии зависит от количества изделий.

Давайте проще поступим — вы приведете исходные данные на которых ваш алгоритм сформирует меньше кластеров, чем предложенный выше.

Не согласен.
На вашем рисунке в случае 2 делимый интервал должен начинаться не в 0, а в Тmin. И тогда также получится три кластера.
Под 0 подразумевалось начало «островка».
Не думал, что это вызовет спор.
Нужно было написать еще Т = Тmах — Tmin для полной определенности.

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

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

image
Так в том и прикол, что у них есть этикетки с датами выпуска… по крайней мере все что в каталоге — с ними.

хорошо, тогда простой алгоритм какое число групп даст по этому рисунку:
4? Т поставил далеко в право, но смысл вроде не меняет.

3! Да верхней оценкой
Да простят меня пользователи Хабра за код. Можете тестировать до дыр =)


Код 1С
Функция Лог( Массив)
    Если Массив.Количество()>0 Тогда 
        Сообщить("Объединение партий");
        Для каждого флп_объеденить Из Массив Цикл
            Сообщить(Символы.Таб +  флп_объеденить);
        КонецЦикла;
        Сообщить("Конец объединение");
    КонецЕсли;
КонецФункции

Данные = Новый ТаблицаЗначений;
Данные.Колонки.Добавить("Дата");
Данные.Колонки.Добавить("Партия");

ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190101'), "1 партия"));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190130'), "2 партия"));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190201'), "3 партия"));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190228'), "4 партия"));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190301'), "5 партия"));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура("Дата, Партия", Дата('20190330'), "6 партия"));

Данные.Сортировать("Дата Возр");

флп_Объединяемые = Новый массив;
С = 30; //дней макисмум
МаксимальнаяДата = Дата('00010101');
Для каждого флп_строка Из Данные Цикл
    Если МаксимальнаяДата > флп_строка.Дата Тогда
        флп_Объединяемые.Добавить(флп_строка.Партия);
    Иначе
        Лог(флп_Объединяемые);
        флп_Объединяемые = Новый массив;
        МаксимальнаяДата = флп_строка.Дата + С*60*60*24;
        флп_Объединяемые.Добавить(флп_строка.Партия);
    КонецЕсли;
КонецЦикла;
Лог(флп_Объединяемые); //остаток

Вывод
Объединение партий
    1 партия
    2 партия
Конец объединение
Объединение партий
    3 партия
    4 партия
    5 партия
Конец объединение
Объединение партий
    6 партия
Конец объединение

Я думаю алгоритм в 10 строчек кода — нельзя назвать сложным

MinimaJack, спасибо за код. Да, я думал вы предлагаете просто разбивать на отрезки, так как предлагали брать целое при делении. Просто в каких-то примерах количество групп может быть целое при делении, а где-то целое +1. Не вник до конца в Ваше предложение.

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

Поясню на примере. Если в исходный пример добавить такие данные:
данные в коде 1С
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190101'), «1 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190130'), «2 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190130'), «3 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190201'), «4 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190301'), «5 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190301'), «6 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190301'), «7 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190304'), «8 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190304'), «9 партия»));
ЗаполнитьЗначенияСвойств(Данные.Добавить(), Новый Структура(«Дата, Партия», Дата('20190304'), «10 партия»));

то получится такой ответ:
Вывод 1С
Объединение партий
1 партия
2 партия
3 партия
Конец объединение
Объединение партий
4 партия
5 партия
6 партия
7 партия
Конец объединение
Объединение партий
8 партия
9 партия
10 партия
Конец объединение

Здесь алгоритм в статье вычислит такие группы: {5,6,7,8,9,10},{4,3},{1,2}, то есть максимальное количество элементов в группе равно 6, а простым алгоритмом 4. Чем больше остатков товаров в разных ячейках с одной партией (а такая ситуация очень популярна) то тем больше будет разрыв.

В статью внесу дополнения по условиям. MinimaJack и Ildarovich благодарю за горячее обсуждение.

Вы точно предоставили вывод своего алгоритма?
Почему не {5,6,7,8,9,10},{4,3,2},{1} — так ведь более оптимально...

да, прошу прощения. Такое разбиение как у Вас получится, опечатался. Алгоритм то жадный. Сам алгоритм не запускал на этих, так как немного другая структура данных на входе. Хотел показать, что наибольшее множество будет другим.
Наверное я что-то не так понял, но кажется что перемудрили. Извините и поправьте пожалуйста, если не разобрался в вашей проблеме )

Есть числа x1 < x2 <… < xn (даты) и надо найти покрытие минимальным числом отрезков длины не более c.
Мы знаем что x1 должен принадлежать какому-то элементу покрытия. Не умаляя общности можем считать что это левый край интервала длины c (всегда можем расширить интервал и сдвинуть его вправо не ухудшив ситуацию). После этого выкидываем точки которые попали в этот интервал, берём следующий минимум, это край следующего интервала. Повторяем, так находим искомое покрытие.

Почему так просто. Ваша модель покрывает больше чем надо, у вас просто подмножества с расстоянием. Не учитывается что даты это просто точки на отрезке (вместо рассмотрения абстрактного метрического пространства).
да, Ваш алгоритм очень похож на алгоритм в комментарии. По поводу его я ответил. Да, конечно, этот алгоритм более общий чем решаемая задача.
Only those users with full accounts are able to leave comments. Log in, please.