Аналіз методів сортування поштових одиниць

Размещено на http://www.allbest.ru/

Аналіз методів сортування поштових одиниць

Сортування ПО - ключова функція виробничої логістики поштового зв'язку.

Задача сортування ПО ставиться наступним чином.

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

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

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

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

Якщо ПО, адресована за напрямом , проходить етапів сортування, то загальний об'єм сортування

де S - середня кількість сортувань однієї ПО.

Оптимальна стратегія сортування ПО може бути сформульована як стратегія мінімізації загального об'єму сортування

або як стратегія мінімізації середньої кількості сортувань однієї ПО

Сума як сума ймовірностей повної групи подій.

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

Кількість сортувань ПК визначається багатьма факторами, серед яких:

- загальна кількість напрямів сортування (ОПЗ);

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

- час, що може бути виділений для оброблення ПК в ОПЗ;

- кількість рівнів ієрархії ОПЗ;

- кількість напрямів сортування (ОПЗ) на кожному з рівнів ієрархії;

- нормативні строки пересилання ПК між ОПЗ тощо.

Теоретично кількість т напрямів сортування ПК і кількість п накопичувачів АЛСМ пов'язані з мінімально можливою кількістю к етапів сортування очевидними співвідношеннями

Так, при т = 1000000, п = 100, к = logl00l000000 = 3 (перший етап сортування - поділ ПК на 100 груп по 10000 напрямів у кожній; другий етап сортування - поділ кожної групи, сформованої на першому етапі сортування, на 100 груп по 100 напрямів у кожній; третій етап сортування - поділ кожної групи, сформованої на другому етапі сортування, на 100 груп по одному напряму в кожній).

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

Можливі два основні методи сортування ПО: метод виділення напрямів і метод групування напрямів.

Згідно з першим методом на кожному з етапів сортування в кожний з п - 1 накопичувачів спрямовуються ПО чергових п - 1 напрямів, тобто виділяються п - 1 зазначених напрямів, решта направляється в п-й (збірний) накопи- чувач, з якого на наступному етапі сортування знову виділяються п - 1 напрямів, аж доки всі ПО не будуть відсортовані за своїми напрямами.

ПО за напрямом Ni будуть сортуватися

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

Виходячи з цього, загальна кількість етапів сортування складе

з урахуванням того, що ПО останнього напряму сортування автоматично залишаються в n-му накопичувані, а середня кількість сортувань однієї ПО

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

Подаючи кількість напрямів сортування у виді

одержимо середню кількість сортувань однієї ПО

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

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

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

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

Середня кількість сортувань однієї ПО складає:

- у схемі рис. 3.1, а

- у схемі рис. 3.1, б

- у схемі рис. 3.1, в

логістика поштовий напрям накопичувач

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

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

Початковий розподіл напрямів сортування за накопичувачами

за якого в кожний з накопичувачів А1, A2,...,AI0 потрапляють ПО 10 напрямів.

Виділимо напрям Ви якому відповідає розподіл напрямів сортування

З розподілу R1 видно, що в накопичувач А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 і т.д.

Размещено на Allbest.ru