Організація багатоетапного сортування поштових одиниць

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

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

Організація багатоетапного сортування поштових одиниць

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

Крім власне сортування повинно бути забезпечене упакування ПО до ОПЗ різних рівнів ієрархії.

Традиційна стратегія багатоетапного автоматизованого сортування заснована на низхідному сортуванні ПО в ОПЗ вищих рівнів ієрархії до підпорядкованих їм ОПЗ нижчих рівнів ієрархії та фактично повторює традиційну стратегію ручного сортування ПО.

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

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

Цифрами на рис. 3.2 позначені:

0 - несортована сукупність ПО G;

1 - сортувальні групи першого етапу сортування ;

2 - робочі комірки проміжного зберігання сортувальних груп або упаковок сортувальних груп першого етапу сортування ;

3 - сортувальні групи другого етапу сортування ;

4 - робочі комірки проміжного зберігання сортувальних груп або упаковок сортувальних груп другого етапу сортування ;

5 - сортувальні групи третього етапу сортування ;

6 - робочі комірки проміжного зберігання сортувальних груп або упаковок сортувальних груп третього етапу сортування ;

7 - упаковки сортувальних груп третього етапу сортування 

8 -упаковки сортувальних груп другого етапу сортування , що містять у собі упаковки сортувальних груп третього етапу сортування;

9 - упаковки сортувальних груп першого етапу сортування  , що містять у собі упаковки сортувальних груп другого етапу сортування

, що, у свою чергу, містять у собі упаковки сортувальних груп третього етапу сортування 

Рисунок 3.2 - Традиційна схема триетапного сортування й упакування ПО

У залежності від порядку формування й упакування сортувальних груп можливі два основні методи організації багатоетапного сортування.

Згідно з першим методом упакування сортувальних груп виконується лише після повного завершення їхнього формування.

Загальний порядок сортування й упакування сортувальних груп за першим методом передбачає наступні дії:

Кількість комірок складає;

кількість комірок складає;

кількість комірок складає.

Загальна кількість комірок для тимчасового збереження неупакованих або упакованих сортувальних груп за першим методом складає

У табл. 3.11 наведено приклад триетапного низхідного сортування ПО за першим методом за наявності п = 10 накопичувачів АЛСМ . Для скорочення записів підетапи другого і третього етапів сортування, на яких відсутні сортувальні групи, не зазначені. Цифри, за якими провадиться сортування, підкреслені.

Таблиця 3.11 - Приклад триетапного низхідного сортування ПО за першим методом

Згідно з другим методом формування сортувальних груп чередується з їх упакуванням.

Загальний порядок сортування й упакування сортувальних груп за другим методом передбачає наступні дії:

Кількість комірок  складає п;

кількість комірок  складає п;

кількість комірок  складає п.

Загальна кількість комірок для тимчасового збереження неупакованих або упакованих сортувальних груп за другим методом складає

У табл. 3.12 наведено приклад триетапного низхідного сортування ПО за другим методом. Початкові дані збігаються з наведеними у табл. 3.11.

Таблиця 3.12 - Приклад триетапного низхідного сортування ПО за другим методом

Традиційній стратегії багатоетапного низхідного сортування ПО властивий ряд принципових недоліків, основними з яких є:

- необхідність застосування  програм сортування (при  кількість таких програм складе 10101);

- необхідність застосування від  робочих комірок для проміжного зберігання сортувальних груп або упаковок сортувальних груп між етапами сортування (при  кількість робочих комірок складе від 300 до 1010100);

- необхідність розвантаження п накопичувачів ЛЛСМ після виконання сортування по кожній зпрограм сортування (при  кількість таких розвантажень складе 1010100);

- необхідність почергової подачі відсортованих груп ПО з індивідуальних робочих комірок на вхід АЛСМ для виконання подальших етапів сортування;

- необхідність формування відправок ПО до відповідних ОПЗ з відсортованих груп ПО, що зберігаються в різних індивідуальних робочих комірках;

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

- багаторазове (в десятки разів на другому, в сотні разів на третьому етапі сортування) падіння реальної продуктивності АЛСМ, обумовлене її вимушеними простоями під час багатократних розвантажень накопичувачів при зміні програм сортування.

Ідея пропонованої стратегії автоматизованого багатоетапного безупинного сортування ПО полягає у заміні традиційного низхідного порядку сортування ПО (від ОПЗ вищого рівня ієрархії до ОПЗ нижчого рівня ієрархії) висхідним порядком сортування (від ОПЗ нижчого рівня ієрархії до ОПЗ вищого рівня ієрархії).

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

Розглянемо принцип безупинного сортування ПО детальніше на прикладі триетапного сортування.

Важливо підкреслити, що кількість напрямів безупинного сортування на кожному з її етапів дорівнює п (у традиційному сортуванні, як вже наголошувалося, кількість напрямів сортування складає: на першому етапі - п; на другому етапі - ; на третьому етапі - ).

Довільний напрям сортування Nc за триетапного безупинного сортування представляється у виді сукупності напрямів сортування на кожному з цих етапів . багатоетапний сортування поштовий

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

Так, при п - 100, кожний з напрямів сортування подається двозначними числами від 00 до 99, а конкретний напрям сортування - деяким числом, наприклад, Nc = 652907, де N1 = 65 - номер напряму сортування, що відповідає ОПЗ першого рівня ієрархії; N2 = 29 - номер напряму сортування, що відповідає ОПЗ другого рівня ієрархії; = 07 - номер напряму сортування, що відповідає ОПЗ третього рівня ієрархії.

Підкреслимо, що хоча всі напрями сортування, що представляють всі ОПЗ першого рівня ієрархії (група цифр N/), всі ОПЗ другого рівня ієрархії (група цифр N2) і всі ОПЗ третього рівня ієрархії (група цифр N3) мають нумерації, що збігаються, індивідуальність кожного конкретного напряму сортування визначається комбінацією цифр усіх груп (у наведеному прикладі Nc = 652907 розглядається як напрям сортування, представлений цим шестизначним числом).

Пропоновану схему безупинного триетапного сортування й упакування ПО наведено на рис. 3.3.

Рисунок 3.3 - Пропонована схема автоматизованого триетапного сортування й упакування ПО

Цифрами на рис. 3.3 позначені:

0 - несортована сукупність ПО G;

1 - сортувальні групи першого етапу сортування за цифрами N3 напрямів

сортування ;

2 - об'єднання сортувальних груп першого етапу сортування в порядку зростання значень цифр напрямів сортування ;

3 - сортувальні групи другого етапу сортування за цифрами  напрямів сортування ;

4 - об'єднання сортувальних груп другого етапу сортування в порядку зростання значень цифр  напрямів сортування ;

5 - сортувальні групи третього етапу сортування за цифрами  напрямів сортування ;

6 - упаковки сортувальних груп за цифрами  напрямів сортування ;

7 - упаковки сортувальних груп за цифраминапрямів сортування , що містять у собі упаковки сортувальних груп за цифрами  напрямів сортування ;

8 - упаковки сортувальних груп за цифрами  напрямів сортування , що містять у собі упаковки сортувальних груп за цифрами N2 напрямів сортування , що, у свою чергу, містять у собі упаковки сортувальних груп за цифрами N3 напрямів сортування  

Загальний порядок сортування й упакування сортувальних груп за пропонованим методом передбачає наступні дії:

У табл. 3.13 наведено приклад безупинного триетапного сортування ПО при поданні кожної з груп напрямів сортуванняоднією десятковою

цифрою (усього при цьому можливо 1000 напрямів сортування від 000 до 999). Цифри напрямів, за якими провадиться сортування, підкреслені. Початкові дані збігаються з наведеними у табл. 3.11.

Таблиця 3.13 - Приклад безупинного триетапного сортування ПО

Після закінчення третього етапу сортування в накопичувачах   отримані групи ПО, відсортовані за всіма трьома цифрами напрямів сортування; відсутність ПО в накопичувачахсвідчить про відсутність ПО, що спрямовуються у відповідні ОПЗ першого рівня ієрархії (і, природно, в підпорядковані їм ОПЗ другого і третього рівнів ієрархії).

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

Для зручності такого розподілу може виявитися доцільною установка розподілювальних карток між сортувальними групами ПО при зміні значень цифр у покажчиках напрямів сортування і А2 в процесі виконання третього етапу сортування за покажчиком напрямів сортування N.

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

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

У табл. 3.14 наведено основні показники традиційної і пропонованої стратегій багатоетапного сортування ПО при п = 100, r = 3.

Таблиця 3.14 - Показники багатоетапного сортування ПО

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

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