ПРОИЗВОДСТВЕННАЯ ЛОГИСТИКА ПОЧТОВОЙ СВЯЗИ

Анализ методов сортировки почтовых единиц

Сортировка ПО - ключевая функция производственной логистики почтовой связи.

Задача сортировки ПО относится следующим образом.

АЛСМ (или сортировочная шкаф) содержит п накопленные в Поток ПО Р, поступающей на обработку, должен быть разделен на потоки по направлениям сортировки ,

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

Известно, что т> п, в результате чего ПО могут сортироваться по этапам, то есть проходить через АЛСМ несколько раз.

Будем рассматривать как вероятности потоков ПО по направлениям сортировка

Если ПО, адресованная по направлению проходит этапов сортировки, то общий объем сортировки

где S - среднее количество сортировок одной ПО.

Оптимальная стратегия сортировки ПО может быть сформулирована как стратегия минимизации общего объема сортировка

или как стратегия минимизации среднего количества сортировок одной ПО

Сумма как сумма вероятностей полной группы событий.

В дальнейшем будем использовать такую нумерацию потоков , за которой , а , благодаря чему и S будут автоматически дополнительно минимизироваться.

Количество сортировок ПК определяется многими факторами, среди которых:

- Общее количество направлений сортировки (ОПЗ)

- Максимальное количество накопителей АЛСМ;

- Время, может быть выделен для обработки ПК в ОПЗ;

- Количество уровней иерархии ОПЗ;

- Количество направлений сортировки (ОПЗ) на каждом из уровней иерархии;

- Нормативные сроки пересылки ПК между ОПЗ и тому подобное.

Теоретически количество т направлений сортировки ПК и количество п накопителей АЛСМ связанные с минимально возможным количеством к этапов сортировки очевидными соотношениями

Так, при т = 1000000, п = 100, к = logl00l000000 = 3 (первый этап сортировки - разделение ПК на 100 групп по 10000 направлений в каждой, второй этап сортировки - разделение каждой группы, сформированной на первом этапе сортировки, на 100 групп по 100 направлений в каждой, третий этап сортировки - разделение каждой группы, сформированной на втором этапе сортировки, на 100 групп по одному направлению в каждой).

Следует подчеркнуть, что указанная минимальное количество этапов сортировки может быть реализована лишь при условии его выполнения в одном ОПЗ. При выполнении сортировки в различных ОПЗ количество направлений сортировки определяется не количеством накопителей АЛСМ, а количеством ОПЗ, в которых такое сортировка производится. В результате реальное количество сортировок ПК зависит от структуры МПЗ и может существенно превышать минимальную.

Возможны два основных метода сортировки ПО: метод выделения направлений и метод группировки направлений.

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

ПО по направлению N и будут сортироваться

раз, где - значение X, округленное до ближайшего большего целого числа.

Исходя из этого, общее количество этапов сортировки составит

с учетом того, что ПО последнего направления сортировки автоматически остаются в n -м накопленные, а среднее количество сортировок одной ПО

Согласно второму методу на каждом этапе сортировки ПО делятся по направлениям сортировки на л групп, каждая из которых направляется в соответствующий накопитель, каждая из указанных групп ПО на следующем этапе сортировки вновь делится на л групп, пока в каждом накопленные не окажутся ПО только одного направления.

Подавая количество направлений сортировки в виде

получим среднее количество сортировок одной ПО

причем ПО по направлениям пройдут этапов сортировки, а ПО по направлениям этапов сортировки, в результате чего среднее количество сортировок одной ПО составит

Значение г может быть получено из выражения где - целая часть X.

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

На рис. 3.1 приведены примеры сортировки ПО на 100 направлений при наличии 10 накопителей ( а - методом выделения направлений б - методом группировки направлений; в - комбинированным методом). Цифры в овалах - группы направлений; цифры в кругах - выделены направления; цифры в прямоугольниках - этапы сортировки.

Среднее количество сортировок одной ПО составляет:

- В схеме рис. 3.1, а

- В схеме рис. 3.1, б

- В схеме рис. 3.1, в

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

Возьмем за основу схему рис. 3.1, б, в которой

Начальное распределение направлений сортировка по накопителями

при котором в каждый из накопителей А 1 , A 2 , ..., A I0 попадают ПО 10 направлений.

Выделим направление Вы которому соответствует распределение направлений сортировки

С распределения R 1 видно, что в накопитель А 1 попадают ПО одного направления, в накапливаемые направлений, в накопитель направлений.

С указанных 19 направлений на втором этапе сортировки выделяются 9 и на третьем этапе 10 направлений.

Таким образом, выделение направления В 1, то есть уменьшение на единицу количества его сортировок, приводит к увеличению на единицу количества сортировок 10 направлений ( ).

Очевидно, что при выполнении неравенства

выделение направления целесообразно, а при невыполнении - нецелесообразно.

Примеры сортировки ПО

Рисунок 3.1 - Примеры сортировки ПО

Если выделения направления целесообразно, выделим направление , которому соответствует распределение направлений сортировки

Выделение направления целесообразно, если выполняется неравенство

и нецелесообразно, если она не выполняется.

Если выделения направления целесообразно, выделим направление. , Которому соответствует распределение направлений сортировки

Выделение направления целесообразно, если выполняется неравенство и нецелесообразно, если она не выполняется.

Указанный процесс последовательного сравнения вероятностей направлений сортировки заканчивается, если очередная неравенство не выполняется (в случае выполнения всех неровностей получим схему рис. 3.1, а; в случае невыполнения первого неравенства - схему рис. 3.1, б; в случае выполнения первой, второй и третьей неровностей и невыполнение четвертой неровности - схему рис. 3.1, в ).

Выбор той или иной схемы сортировки определяется заданным распределением вероятностей направлений сортировки.

Рассмотрим три примера распределения вероятностей направлений сортировки ПО для п = 10 т = 100, которые приводят к указанным схем сортировки.

Пример 1. Вероятности направлений сортировки заданы как члены геометрической прогрессии, что приходит.

со знаменателем q и значением

Пусть , тогда ,

следовательно

Поскольку сумма вероятностей ,

то есть любая вероятность

вследствие чего выделение всех направлений сортировки целесообразно.

Схему сортировки для этого примера приведены на рис. 3.1, а.

Среднее количество сортировок одной ПО составляет

Пример 2. Все направления сортировки равновероятны Очевидно, что

вследствие чего выделение направлений сортировки нецелесообразно.

Схему сортировки для этого примера приведены на рис. 3.1, б.

Среднее количество сортировок одной ПО составляет

Пример 3. Вероятности направлений сортировки, как и в примере 1, заданные как члены геометрической прогрессии, что приходит.

Сумма к членов геометрической прогрессии

следовательно для нахождения суммы следует от суммы 100 членов прогрессии вычесть сумму ее 90 членов, для нахождения суммы следует от суммы 90 членов прогрессии вычесть сумму ее 80 членов и т.д.

Пусть , тогда

Сравниваем с :

Поскольку , выделение направления целесообразно.

Сравниваем с :

Поскольку , выделение направления В 2 целесообразно.

сравниваем с

Поскольку , выделение направления целесообразно.

Сравниваем с :

Поскольку , выделение направления нецелесообразно.

Таким образом, целесообразно выделение направлений сортировки Схему сортировки этого примера приведены на рис. 3.1, в.

Среднее количество сортировок одной ПО по сравнению с начальной схеме группировки направлений ( S = 2) уменьшается на и увеличивается на ,

следовательно

В общем случае для полного использования всех накопителей АЛСМ на последнем этапе сортировки количество направлений сортировки должна составлять

а количество направлений сортировки, перераспределяются между накопителями, где и и j - натуральные числа.

Для выполнения первого условия количество направлений сортировки т может дополняться некоторым количеством фиктивных направлений с нулевыми вероятностями, которое может быть найдено из выражения

а для выполнения второго условия - количество направлений сортировки, перераспределяются, должна быть кратной

Так, при , значение , следовательно для выполнения первого условия следует дополнить значение т до 541, а для выполнения второй - выбрать число направлений сортировки, перераспределяются между накопителями, из ряда 15, 30, 45 и т.д.

При цитировании материалов в рефератах, курсовых, дипломных работах правильно указывайте источник цитирования, для удобства можете скопировать из поля ниже:

Поделиться материалом

Содержание