Способ определения входящих потоков грузов в один исходящий поток на логистическом складе - RU2749385C1

Чертежи

Описание

Область техники, к которой относится изобретение

За последние несколько лет требования, запросы потребителей и развитие новых технологий оказали значительное влияние на внутрискладские логистические операции. Постоянный рост спроса побуждает основных логистических операторов становиться все более гибкими к требованиям клиентам. В этой связи, жизненно важным аспектом деятельности логистических операторов является использованием усовершенствованных и оптимизированных решений по маршрутизации, хранению и комплектации заказов. Фирма SAVOYE, производитель оборудования для комплектации заказов клиентов, специализируется на автоматизации и компьютеризации логистических складов и постоянно совершенствует, оценивает свои решения.

Управление логистическим складом включает в себя закупку материалов, прием и управление потоками и запасами. Сокращение времени доставки заказа клиента часто означает сокращение времени его перемещения. Как отмечают De Koster, R., Le-Duc, T. и Roodbergen K.J. в статье «Проектирование и управление комплектования заказа на складе: обзор литературы» (2007 г.), European Journal of Operational Research 182 (2), 481-501, 50% времени комплектования (времени подготовки) заказа клиента затрачивается на его перемещение. Поэтому необходимо, прежде всего, взглянуть на основной аспект, с которым сталкиваются складские логистические операторы, а именно, на оптимизацию перемещаемых потоков для обеспечения максимально возможной производительности. Настоящее изобретение сосредоточено более конкретно на пересечении потоков грузов (упаковок, коробов, контейнеров и т.д.). Задача состоит в максимизации пропускной способности конечного потока (также называемого исходящим потоком или выходным потоком) посредством объединения различных входящих потоков (входных потоков), поступающих из разных мест.

Уровень техники

Техническая задача

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

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

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

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

Предлагаемое и описанное ниже решение дает ответ на этот набор технических задач и обладает новизной и изобретательской способностью по сравнению с известными моделями задач планирования, описанными, например, в:

• Runwey Cheng, MitsuoGen и Yasuhiro Tsujimura, Учебный обзор задач планирования работ с использованием генетических алгоритмов --- Часть I. Представление, Технологический институт Асикага, Асикага 326, Япония; и

• Imran Ali Chaudhry и Abid Ali Khan, Исследовательский обзор: обзор гибких способов планирования работы, Международные транзакции в исследовании операций, 2015 г.

Пример применения

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

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

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

Одним иллюстративным и не исчерпывающим примером конкретного применения является GTP Intelis PTS (система лотков для комплектования заказа Intelis «груз к человеку»), предложенная фирмой SAVOYE. Это комплексное автоматизированное решение для комплектации заказов клиентов, в котором автоматизированная система 3 хранения и извлечения (или удаления) на основе «челночной» операции (называемая Intelis PTS системой) позволяет осуществлять подачу груза на станции 4 комплектования (также называемые GTP станциями) на очень высоких скоростях. Таким образом, роль автоматизированной системы (Intelis PTS) состоит в том, чтобы сохранять и получать входящие и исходящие грузы, содержащие предметы, необходимые для эффективного выполнения заказов клиентов на GTP станциях. Автоматическая система состоит из нескольких складских стеллажей (также называемых PTS проходами, которые, однако, не следует путать с дорожками (в смысле конвейеров), транспортирующих входящие потоки в контексте настоящего изобретения (см. пояснения ниже), каждый из которых состоит из челноков и подъемников, позволяющих перемещать эти грузы вперед и назад соответственно на входных конвейерах 5₁, 5₂ и выходных конвейерах 2₁, 2₂. Эти различные входные и выходные конвейеры все соединены коллектором 1, который поставляет груз на станции 4 комплектования, как можно видеть на фиг.50 (например, с тремя станциями 4₁, 4₂ и 4₃ комплектования).

Для связи с контекстным определением, приведенным выше, выходные конвейеры 2₁, 2₂ автоматизированной системы 3 образуют конвейеры (также называемые «дорожками»), транспортирующие входящие потоки грузов, эти входящие потоки объединяются на коллекторе 1 в исходящие потоки грузов.

Другими словами, перемещение груза с одного места на другое, который поступает в автоматизированную систему 3, и выходят из нее, управляется посредством коллектора. Следовательно, используется несколько потоков ввода груза (также называемые входящими потоками в настоящем разделе описания) на выходных конвейерах 2₁, 2₂ автоматизированной системы 3, причем все они поступают в коллектор.

Дополнительно, когда потоки грузов, которые возвращаются в автоматизированную систему 3 (через входной конвейер 5₁, 5₂), проходят через тот же коллектор 1, мы имеем пример мешающих потоков, называемых в данном конкретном случае обратными потоками. Эти мешающие потоки очень интересны, потому что они удаляются после прохождения всех зон ввода, тем самым, образуя свободные пространства для некоторых потоков ввода, но не для других. Как подробно описано здесь ниже, один вариант осуществления предложенного решения относится к управлению, насколько это возможно, этими мешающими потоками для заполнения этих пустых пространств, а не для их формирования.

Далее приведено описание решений, предлагаемых в этом примере настоящего изобретения.

Текущие решения

Существующие решения

- известное решение A с желаемой окончательной последовательностью: в этом случае ввод груза на коллектор следует четко определенному порядку, соответствующему ожидаемой окончательной последовательности после объединения груза. Если эта конечная последовательность, желаемая на выходе из коллектора, например, образована грузом, имеющим порядковые номера 1, 2, 3 и т.д. (здесь ниже называется «груз 1», «груз 2» и т.д.), то груз 1 будет введен по приоритету, за которым следует груз 2, только если груз 1 находится ниже по потоку от груза 2 на коллекторе, за ним следует груз 3, только если груз 2 находится ниже по потоку от груза 3 на коллекторе, и так далее и т.д.;

- известное решение B без желаемой окончательной последовательности: каждый первый груз каждого потока ввода вводится в коллектор, как только появляется место в его зоне ввода.

Недостатки, связанные с этими решениями

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

Несколько этапов этого известного решения A показаны на фиг.1. В этом примере мы рассматриваем желаемую конечную последовательность 1, 2, 3, 4. Чтобы соответствовать этой последовательности, невозможно вводить груз 1, 2, 3 и 4 одновременно на коллектор. На этапе 0 установка активируется. Мгновенно в коллектор вводятся груз 1 и 2. Эта операция стала возможной, потому что поток ввода груза 1 находится ниже по потоку потока ввода груза 2. Грузы 1 и 2 находятся на коллекторе, разделенные расстоянием между дорожками (конвейерами), с которых они поступают. Коллектор движется вперед без изменений до этапа 1, на котором груз 2 проходит перед зоной ввода потока, содержащего груз 3. С этого момента и далее груз 3 вводится в коллектор непосредственно за грузом 2. Можно отметить, что свободное пространство, оставшееся между грузами 1 и 2, осталось прежним и никогда не будет заполнено. На этом же этапе 1 груз 4 вводится непосредственно в коллектор с пространством между ним и грузом 3. На этапе 2 показаны свободные пространства, оставленные этим известным способом ввода груза;

- известное решение B: один из недостатков известного решения B состоит в том, что наиболее дальняя по потоку дорожка (конвейер) будет вводить свои грузы непрерывно, в то время как остальные должны быть ограничены только заполнением оставшихся свободных пространств; еще один недостаток известного решения B состоит в том, что оно предлагает систему управления, которая в действительности работает только тогда, когда коллектор (транспортер исходящего потока) имеет скорость, намного превышающую скорость дорожек (конвейеров), транспортирующих входящие потоки (во сколько раз больше, так как есть входящие потоки для ввода). В известном решении B скорости дорожек (конвейеров) должны быть ограничены. Теперь, в данном контексте, количество потоков ввода увеличивается быстрее, чем механическая скорость коллектора. Этого известного решения B больше недостаточно, и не обеспечивает оптимизацию пропускной способности исходящего потока.

Раскрытие сущности изобретения

В первом конкретном варианте осуществления изобретения предлагается способ объединения в пределах логистического склада k входящих потоков груза, транспортируемого соответственно k конвейерами, называемыми дорожками

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

- k дорожки относятся к типу «первым пришел - первым ушел», которые распределены вдоль коллектора и пронумерованы от a₁ до a_k в одном смысле движения коллектора, и

-

представляет собой зависящее от времени расстояние между дорожками a_i и a_k, выраженное в блоках времени, каждая из которых соответствует одному временному интервалу (также называемому «временным шагом») коллектора,

причем способ выполняется системой управления по меньшей мере один раз, данное выполнение выполняется в момент Tb и содержит:

- получение набора L, содержащего n грузов, распределенных в момент времени Tb на k дорожках, которые должны быть введены в коллектор для формирования выходной последовательности σ, при этом каждый из n грузов идентифицируется одним порядковым номером в пределах выходной последовательности σ, каждая из k дорожек, содержит упорядоченный набор, упорядоченный в порядке возрастания порядковых номеров h_i грузов, которые необходимо вводить один за другим в коллектор;

- вычисление времени t₀, в которое первый груз σ₁ последовательности σ проходит перед дорожкой a_k;

- вычисление времени ввода в коллектор каждого из n грузов набора L по следующей формуле:

, где:

-

груз набора L и поступающий из j-й позиции в дорожке a_i, , ,

- σ (u) является порядковым номером груза u в выходной последовательности σ;

- управление коллектором и k дорожками для ввода n грузов в коллектор в соответствии с n временем ввода

.

Согласно одной конкретной характеристике первого варианта осуществления

представляет собой зависящее от времени расстояние между дорожками a_i и a_i', выраженное в блоках времени, каждая из которых соответствует промежутку времени коллектора, и способ, кроме того, содержит следующие этапы:

- для каждого груза

, приходящего с дорожки a_i, вычисление времени прохождения груза перед дорожками от a_i до a_k, при этом время ввода T (u) груза в коллектор известно;

- для каждой дорожки

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

- для каждого управляемого мешающего груза p мешающего потока, управляемого средством управления, расположенного вдоль коллектора и перед дорожкой a_g(p)в смысле движения коллектора, при

, a_g(p) также является первой дорожкой движения коллектора, перед которой проходит управляемый мешающий груз:

a) инициализация t временем

, где представляет возможное время поступления первого управляемого мешающего груза перед дорожкой a_k, если этот груз не приостановлен (т. е. помещен в состояние ожидания);

b) вычисление времени

, ,…, прохождения управляемого мешающего груза перед дорожками от a_g(p) до a_l(p), причем a_l(p) является последней дорожкой в смысле движения коллектора, перед которой проходит управляемый мешающий груз;

с) если ни одно из времени

, ,…, не принадлежит соответственно наборам , ,…, , вычисление фиктивного времени прохода управляемого мешающего груза p перед дорожкой a₁ по следующей формуле: ;

d) если одно из времени

, ,…, принадлежит соответственно одному наборов увеличение t на один блок времени и повторение этапов b), c) и d) с новым значением t;

- управление средством управления для ввода во время

каждого управляемого мешающего груза p перед дорожкой a_g(p).

Во втором конкретном варианте осуществления изобретения предлагается способ объединения в пределах логистического склада k входящих потоков груза, транспортируемых соответственно k конвейерами, называемыми дорожками

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

- k дорожки относятся к типу «первым пришел - первым ушел» и распределены вдоль коллектора и пронумерованы от a₁ до a_k в смысле движения коллектора, и

-

представляет собой зависящее от времени расстояние между дорожками a_i и a_k, выраженное в блоках времени, каждая из которых соответствует одному промежутку времени коллектора,

способ выполняется системой управления, по меньшей мере, один раз, причем данное выполнение выполняется в момент Tb и содержит:

- получение набора L, содержащего n грузов, распределенных в момент Tb на k дорожках, которые должны быть введены в коллектор для формирования выходной последовательности σ, при этом каждый из n грузов идентифицируется одним порядковым номером в выходной последовательности σ, каждая из k дорожек содержит упорядоченный набор в порядке возрастания порядковых номеров h_i грузов, которые необходимо вводить один за другим в коллектор;

- для каждой дорожки

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

- без учета наборов

, , вычисление времени t₀, в котором первый груз σ₁ выходной последовательности σ проходит перед дорожкой a_k;

- для первого груза σ₁ выходной последовательности σ, в предположении, что первый груз σ₁ поступает с дорожки a_i:

а) инициализация t значением t₀;

b) если ни одно из времени

, , ,…, не принадлежит соответственно наборам , , ,…, , вычисление времени ввода первого груза σ₁ в коллектор по следующей формуле: , где ;

c) если одно из времени

, , ,…, принадлежит соответственно одному из наборов , , ,…, , увеличение t на один блок времени и повторение этапов b) и c) с новым значением t;

- для каждого следующего груза σ_c выходной последовательности σ,

{2, ..., n}, в предположении, что следующий груз σ_c поступает с дорожки a_i:

a') увеличение t на один блок времени с использованием t для вычисления времени ввода предшествующего груза σ_c-1;

b') если ни одно из времени

, , ,…, не принадлежит соответственно наборам , , ,…, , вычисление время ввода следующего груза σ_c в коллектор по следующей формуле: , где ;

c') если одно из времени

, , ,…, принадлежит соответственно одному из наборов , , ,…, , увеличение t на один блок времени и повторение этапов b') и c') с новым значением t;

- управление коллектором и k дорожками для ввода n грузов в коллектор в соответствии с n временем T (u),

ввода.

В соответствии с одной конкретной характеристикой второго варианта осуществления этап управления коллектором и k дорожек для ввода n грузов в коллектор в соответствии с n временем T (u),

ввода, предшествуют следующие этапы:

- вычисление t_min по следующей формуле:

;

- если

, изменение n времени ввода по следующей формуле: .

Согласно одной конкретной характеристике второго варианта осуществления,

представляет собой зависящее от времени расстояние между дорожками a_i и a_i', выраженное в блоках времени, каждая из которых соответствует временному интервалу коллектора, и способ дополнительно содержит следующие этапы:

- для каждого груза

, поступающего с дорожки a_i, вычисление времени прохождения груза перед дорожками от a_i до a_k, при этом известно время T(u) ввода груза в коллектор;

- для каждой дорожки

, получение набора V_i, содержащего, с одной стороны, каждое время прохождения одного из грузов перед дорожкой a_i, а с другой стороны, набор U_i времени недействителен для ввода одного из грузов дорожки a_i в коллектор;

- для каждого управляемого мешающего груза p мешающего потока, управляемого средством управления, расположенными вдоль коллектора и перед дорожкой a_g(p)в смысле движения коллектора, при

, a_g(p) также является первой дорожкой движения коллектора, перед которой проходит управляемый мешающий груз:

a) инициализация t временем

, где представляет возможное время поступления первого мешающего груза перед дорожкой a_k, если этот груз не приостановлен;

b) расчет времени

, ,…, прохождения управляемого мешающего груза перед дорожками от a_g(p)до a_l(p),где a_l(p) является последней дорожкой в смысле движения коллектора, перед которым проходит управляемый мешающий груз;

с) если ни одно из времени

, ,…, не принадлежит соответственно наборам , ,…, , вычисление фиктивного времени прохода управляемого мешающего груза p перед дорожкой a₁ по следующей формуле: ;

d) если одно из времени

, ,…, принадлежит соответственно одному из наборов увеличение t на один блок времени и повторение этапов b), c) и d) с новым значением t;

- управление средством управления для ввода в момент времени

каждого управляемого мешающего груза p перед дорожкой a_g(p).

В соответствии с одной конкретной характеристикой первого или второго варианта осуществления изобретения время t₀ вычисляется по следующей формуле:

, где:

-

груз из набора L', содержащего грузы, размещенные в первой позиции дорожек, расположен в соответствии с направлением движения коллектора, от дорожки a₁ до дорожки a_i1, содержащей первый груз σ₁ выходной последовательности σ.

Согласно одной конкретной характеристике первого или второго варианта осуществления, способ выполняется итеративно, каждая новая операция выполняется в новый момент времени Tb, вычисляемый по следующей формуле:

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

Согласно одной конкретной характеристики первого или второго варианта осуществления способ выполняется итеративно, каждая новая операция выполняется в новый момент времени Tb, определяемый как момент, в который не загружается выходная последовательность σ предшествующей операции выполнения в предшествующий момент Tb, расположена на участке коллектора, простирающейся от первой дорожки a₁ до дорожки

, эта дорожка содержит первый груз выходной последовательности σ нового выполнения в новый момент Tb.

Согласно одной конкретной характеристики первого или второго варианта осуществления, способ выполняется итеративно, каждая новая операция выполняется в новый момент времени Tb, вычисляемый по следующей формуле:

, причем:

-

, являющийся последним грузом, исходящий из )-й позиции в дорожке выходной последовательности σ предшествующего выполнения в предшествующий момент Tb, и

-

получается путем увеличения на один блок времени предшествующего момента Tb.

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

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

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

Краткое описание чертежей

В нижеследующем описании, приведенном в качестве ориентировочного и не исчерпывающего примера, делается ссылка на прилагаемые чертежи, из которых:

Фиг. 1 - показывает существующий способ вставки грузов в заданном последовательном порядке;

Фиг. 2 - является изображением двух дорожек (конвейеров), одного коллектора и одного груза (коробки);

Фиг. 3 - представляет собой изображение двух дорожек (конвейеров), одного коллектора и одного груза (ящика);

Фиг. 4 - представляет собой изображение исследуемой системы на дорожках движения.

Фиг.5 - является схемой системы с идентификацией груза по их порядковому номеру;

Фиг. 6 - показывает точку отправления и точку ввода;

Фиг.7 - показывает совпадающие точки без потерь относительно общей конфигурации;

Фиг.8 - показывает разрез коллектора на интервалы (позиции или слоты);

Фиг.9 - показывает желаемую выходную последовательность, ожидаемую при разделении коллектора;

Фиг.10 - показывает блок времени, ассоциированный с диапазоном коллектора, относительно продолжительности ввода груза;

Фиг. 11 - показывает расстояния между потоками ввода в виде целых чисел;

Фиг. 12 - показывает расстояния между потоками ввода, которые не обязательно должны быть целыми числами;

Фиг. 13 - представляет собой схему коллектора с точками ввода, расположенными последовательно на каждом интервале;

Фиг. 14 - показывает пример коллектора с четырьмя дорожками, которые размещены последовательно в соответствии с интервалом коллектора;

Фиг. 15 - является диаграммой Ганта, относящейся к производству и предоставляющая данные, которые должны быть вычислены по формуле;

Фиг.16 - показывает пример коллектора с четырьмя дорожками, которые размещены произвольным образом;

Фиг. 17 - представляет собой диаграмму Ганта, относящуюся к производству с любыми неуказанными расстояниями между дорожками;

Фиг. 18 - показывает пример коллектора и двух дорожек с идентификаторами груза;

Фиг.19 - показывает пример коллектора и двух дорожек с последовательными идентификаторами порядковых номеров;

Фиг.20 - показывает пример коллектора и двух дорожек с идентификаторами порядковых номеров;

Фиг.21 - показывает изображение коллектора в момент 0;

Фиг. 22 - показывает изображение коллектора в момент 1;

Фиг.23 - показывает изображение коллектора в момент 2;

Фиг. 24 - показывает изображение коллектора в момент 3;

Фиг.25 - показывает пример FIFO списка, ассоциированного с тремя дорожками;

Фиг. 26 - показывает достижимую последовательность, ожидаемую на коллекторе;

Фиг.27 - показывает первый груз потока, относящийся к точке ввода, составляющий часть FIFO списка;

Фиг.28 - показывает первый груз потока, не привязанный к точке ввода, не составляющий часть FIFO списка;

Фиг.29 - показывает груз в непрерывном удержании после первого груза, составляющий часть FIFO списка;

Фиг.30 - показывает грузы в непрерывном удержании после первого груза, не составляющий часть FIFO списка;

Фиг. 31 - показывает пример партии для обработки;

Фиг.32 - показывает расчет времени ввода и обработки партии 1;

Фиг. 33 - показывает процесс обработки партии;

Фиг.34 - показывает окончание обработки партии 1 и формирование партии 2;

Фиг.35 - показывает окончание обработки партии 2 и ее применение;

Фиг.36 - является схемой алгоритма в общем случае с неуправляемым мешающим потоком;

Фиг. 37 - показывает пример мешающего потока: грузы, окрашенные серым цветом, возвращаются в PTS;

Фиг. 38 - показывает пример коллектора с четырьмя неуказанными дорожками с неуправляемым мешающим потоком;

Фиг. 39 - является диаграммой Ганта с пространствами, образующими неуправляемым мешающим потоком;

Фиг.40 - является схемой алгоритма 4;

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

Фиг. 42 - представляет собой схему Ганта ввода, показывающую пространства, которые будут использоваться для мешающего груза;

Фиг. 43 - представляет собой схему Ганта при выборе размещения мешающего груза;

Фиг.44 - показывает структуру системы управления согласно одному конкретному варианту осуществления изобретения;

Фиг.45 - является схемой алгоритма 5;

Фиг.46 - является блок-схемой алгоритма способа объединения k входящих потоков в один исходящий поток согласно первому конкретному варианту осуществления на основании алгоритма 2;

Фиг.47 - является блок-схемой алгоритма способа объединения k входящих потоков в один исходящий поток согласно второму конкретному варианту осуществления на основании алгоритма 3 (проиллюстрированного на фиг.36);

Фиг.48 - является блок-схемой алгоритма способа объединения k входящих потоков в один исходящий поток согласно третьему конкретному варианту осуществления на основе алгоритма 4 (проиллюстрированного на фиг.40);

Фиг.49 - является блок-схемой алгоритма способа объединения k входящих потоков в один исходящий поток согласно четвертому частному варианту осуществления на основании алгоритма 5 (проиллюстрированного на фиг.45);

Фиг. 50 - показывает пример использования.

Осуществление изобретения

Параметры системы управления

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

Фиг.2 представляет собой изображение, показывающее две дорожки (конвейеры) 2₁, 2₂, один коллектор 1 и один груз (ящик или коробка) 6. Фиг.3 представляет собой модельный вид элементов, представленных на изображении на фиг.2 (и сохранены те же числовые ссылочные позиции).

Обозначения

Таблица ниже представляет собой обзор обозначений.

Таблица 1

Количество потоков ввода (входящие потоки) системы

k дорожки (конвейеры), каждая из которых транспортирует упорядоченный набор грузов в данный момент

Количество грузов, находящийся на дорожке (конвейере) a_i

Общее количество груза, вводимого в коллектор

Набор груза, который нужно ввести в коллектор

Груз

, поступающий с j^th позиции в дорожке a_i

Требуемая выходная последовательность, упорядочивание всех грузов

Позиция груза

в выходной последовательности

груз последовательности

, принадлежащий

означает вычисление

для груза

Набор грузов, размещенных на первой позиции дорожек, находящийся между дорожкой

и дорожкой, содержащей первый груз последовательности

(т.е.

)

Время начала движения груза

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

Время ввода груза

в коллектор, совпадающее с точкой ввода, в которой груз физически поступает на коллектор

Время, требуемое для перемещения на расстояние между точкой отправки и точкой ввода для груза на дорожке

Временной блок, соответствующий разделению (или сегментации) коллектора на временные интервалы (также называемые временными позициями или временными слотами) The date 0Время, в которое может быть начата операция ввода груза в коллектор (время принимает форму первого незанятого места на этом коллекторе)

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

Расстояние в «интервалах» между дорожкой

и дорожкой

Расстояние в «интервалах» между дорожкой

и дорожкой

Обозначения на дорожках конвейерной системы

Для конфигурации системы в данный момент каждая дорожка будет содержать упорядоченный набор груза. Пусть k будет числом дорожек в нашей системе, каждая дорожка пронумерована от a₁ до a_k в смысле движения коллектора. Эти дорожки, соответственно, имеют количество h_i груза, представленного списком «первым пришел - первый ушел» (FIFO), которые необходимо вводить по одному в коллектор.

Пример приведен на фиг. 4. Направление движения коллектора 1 справа налево, это направление указано стрелкой. Каждая дорожка пронумерована и содержит упорядоченные грузы, которые необходимо вводить один за другим снизу вверх в коллектор. Таким образом, в этом примере мы имеем k = 3 с

и

Обозначения вводимых грузов

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

груз u, принадлежащий L, поступает из j-й позиции на дорожке a_i.

Дополнительно, σ является выходной последовательностью, в которой эти грузы должны быть упорядочены после того, как все они введены в коллектор. Функция σ(u) определяет позицию груза u в этой последовательности. Таким образом, каждый груз может быть идентифицирован одним «порядковым» номером от 1 до n, соответствующим позиции в требуемой выходной последовательности (σ). Таким образом будет определяться груз. Можно отметить, что в этом случае легко проверить, достижима ли последовательность: для каждой дорожки достаточно иметь упорядоченный список груза, идентифицированных порядковыми номерами в порядке возрастания, которые не обязательно являются последовательными.

Допустим, теперь необходимо определить набор L', специально сгруппировав вместе первые грузы, ожидаемые в окончательной выходной последовательности, помещенные в первую позицию дорожек

, где i₁ является номером дорожки, содержащей первый груз этой последовательности σ. Этот набор объединяет все грузы, которые могут быть первым грузом последовательности, которая будет введена в коллектор. Действительно, груз на первой позиции на дорожке, расположенной выше по потоку от дорожки, содержащей первый груз в последовательности, вероятно, будет введен первым, в то же время находясь позади первого груза в конечном потоке коллектора. Однако груз на первой позиции в дорожках ниже по потоку от дорожки, содержащей первый груз, никогда не будет введен до этого первого груза в коллектор.

На фиг.5 показана схема, эквивалентная схеме на фиг.4, в которой берется достижимая последовательность σ = {id21, id31, id22, id11, id23, id32, id33, id34, id12}. В этом примере n = 9, поэтому каждый груз имеет уникальный порядковый номер, позволяющий идентифицировать ее, в то же время быстро узнавая желаемую позицию в последовательности σ. Фиг.5 сразу позволяет увидеть, что выбранная последовательность достижима, действительно:

и Дополнительно, используется конкретный набор

Время отправления и время ввода

Как ранее было объяснено, каждая дорожка соответствует потоку ввода в данный момент, представленному как столбец FIFO, относящийся к коллектору. Однако на складе может случиться так, что груз, ожидающий ввода, находится на некотором расстоянии от коллектора. Пусть точка отправления обозначает место, в котором этот груз ожидает команды на перемещение дорожки (конвейер), проиллюстрированный точкой, прикрепленной к столбцу FIFO, и пусть точка ввода обозначает пространство коллектора, в которое первым поступит груз в процессе действительно ввода в этот коллектор, что показано точкой, относящейся к коллектору на фиг.6.

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

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

Структура данных

Разделение системы отвода (коллектор): блок времени (временной интервал)

Система отвода (или коллектор) будет рассматриваться как система с временными интервалами (например, сортировщик), также называемыми слотами или позициями.

На фиг.8 показано разделение коллектора на временные интервалы (позиции или слоты).

Таким образом, задачей настоящего изобретения является получение максимальной пропускной способности упорядоченного исходящего потока посредством заполнения интервалов коллектора, как показано на фиг.9.

Далее рассматривается блок времени, соответствующий этому временному интервалу, который разделяет коллектор в зависимости от скорости его движения. Блок времени, называемый «временным интервалом», соответствует продолжительности, необходимой для того, чтобы точка коллектора переместилась точно на физическое расстояние, соответствующее одной позиции. Расстояние, определенное для этой позиции, соответствует размеру груза плюс безопасное расстояние. Это безопасное расстояние должно быть отрегулировано в соответствии с потребностями специалистов в данной области техники и для соблюдения следующего условия (проиллюстрировано на фиг. 10).

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

Расстояние от системы ввода

Как показано на фиг.11,

определяется как соответствующее количеству интервалов времени коллектора (системы отвода) между дорожкой a_i и последней дорожкой a_k, как показано на следующих чертежах с k = 3. Как показано на фиг.12, это число может быть не целым. .

Временное расстояние между двумя дорожками a_i и a_j обозначается как

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

Модель ассоциированного предприятия

В следующей таблице приведены обозначения модели предприятия.

Таблица 2

}Набор из n работ, ассоциированный с моделью предприятия.

груз последовательности

обозначен как

, который занимает

место на дорожке

и ассоциирован с работой

Набор

машин модели предприятия. Дорожка

ассоциирована с машиной

.

Перечень

последовательных операций, ассоциированных с работой

, при этом известно, что операция

должна выполняться на машине

.

Для каждой выходной последовательности σ мы моделируем систему как модель предприятия с n работами и k машинами. Каждый груз последовательности

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

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

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

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

Решение для последовательно равномерно распределенных дорожек

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

для всех {1, …, k-1}.

Моделирование системы как планирование работы предприятия

Приведено описание моделирования системы как задача планирования работы предприятия в данном конкретном случае.

Каждый из n грузов ассоциирован с работой

с нумерацией в соответствии с порядковым номером груза. Таким образом, если σ_u соответствует u-му грузу в последовательности σ, то ассоциированная работа является Операции этих работ должны обрабатываться набором из k машин {M₁, ..., M_k}. Операция может быть назначена только одной машине в момент времени. Каждая машина ассоциирована с дорожкой (т.е. потоком ввода), которая может выполнять только одну операцию в момент времени. Можно напомнить, что эти дорожки пронумерованы {a₁, ..., a_k} от восходящего к нисходящему (то есть в соответствии с перемещением коллектора).

Таким образом, груз σ_u, вводимый в коллектор из дорожки a_i, будет проходить перед каждой дорожкой a_j с j в {i, i + 1, …, k}. Этот механизм представлен тем фактом, что каждая работа, ассоциированная с грузом на дорожке a_i, состоит из k - i + 1 единичных операций

для последовательной обработки без ожидания. Каждую операцию нужно запланировать на определенной машине. Таким образом, если операция (обрабатываемая машиной M_i) начинается в момент t, операция (обрабатывается машиной M_{{i + 1}}) начинается в момент t + 1 и т.д., и, наконец, операция (обрабатываемая машиной M_k) начинается в момент t + k - i.

Если момент начала первой операции

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

Можно отметить, что каждая работа состоит, по меньшей мере, из одной операции на последней машине M_k (поскольку каждый груз проходит перед, по меньшей мере, последней дорожкой

). Последовательность операций, запланированных на машине M_k, точно соответствует порядку, в котором грузы будут проходить перед последней дорожкой, и их время отправления соответствует моменту, когда эти грузы пройдут перед этой последней дорожкой ввода. Вот почему, если груз u находится перед грузом v в данной выходной последовательности, последняя операция u должна начаться перед последней операцией v на .

Назначением отсутствия места на коллекторе является отсутствие простоя между операциями машины M_k.

Принцип алгоритма, позволяющего получить время ввода

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

Во-первых, предполагая, что первый груз последовательности поступает с дорожки a_i, операции

, ассоциированные с этой работой, начинаются в моменты t, t + 1, ... t + k - i времени.

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

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

Эта процедура применяется итеративно к каждому из следующих работ заданной последовательности.

Реальные моменты времени ввода в коллектор получают непосредственно с момента начала первой операции каждой работы. Используемый временной блок определен в настоящем документе ранее («временной интервал» коллектора).

Расчет времени ввода по формуле

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

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

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

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

Доказательство: пусть 0 будет временем начала ввода груза. Допустим, t₀ будет временем, когда первый груз последовательности (т.е. σ₁) проходит перед дорожкой a_k. Отметим, что первый груз, вводимый в коллектор, обязательно является грузом в начале дорожки, расположенной от дорожки a₁ до дорожки σ₁. Пусть

является подмножеством груза.

Следовательно, для любого груза

мы знаем, что если бы груз был введен во время x, он прошел бы перед дорожкой a_k во время x + k-i. Имеем x≥0, поскольку мы не можем ввести груз до времени 0. Теперь, по определению t₀, груз u пройдет перед дорожкой a_k во время То есть .

Отсюда выводим, что для всех

Мы ищем самое раннее время, позволяющее проверить все эти ограничения, поэтому:

Алгоритм 1 здесь ниже предоставляет время ввода T(u), то есть время ввода каждого груза u в коллектор. Используемый временной блок является «временным интервалом», определенный выше. Алгоритм 1 дает формулу для расчета этих временных моментов ввода, если потоки вводятся на каждое последовательное место коллектора (см. фиг.14).

Алгоритм 1

: Расчет времени ввода без нарушения потока в одном частном случае

Требуется:

Для всех

выполнить

для всех

выполнить

окончить для

окончить для

вернуть

Пример

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

Рассмотрим конфигурацию системы следующим образом (см. фиг.14): k = 4 дорожки, содержащие два или три груза. Каждый груз идентифицируется уникальным порядковым номером с помощью выходной последовательности σ = (1,2,3,4,5,6,7,8,9), которая представляет собой достижимую последовательность.

В этом упрощенном случае мы можем представить решение для предприятия в виде диаграммы Ганта, так что каждая строка соответствует одной машине. Тот факт, что каждый груз проходит мимо машин последовательно, представлен тем фактом, что порядковый номер каждого груза появляется в последовательных ячейках слева направо в таблице (см. фиг.15). Дополнительно, первое появление каждого груза указывает его время ввода, заданное формулой для привязки шкалы времени к моменту 0, определенному выше. Напомним, что время 0 соответствует моменту первого возможного ввода груза. Предоставлена также возможность установки времени t₀ в соответствии с определением и можно получить вычислением. Напомним, что t₀ является моментом времени, когда первый груз последовательности (σ₁) проходит перед дорожкой k = 4, а именно, номером 1, когда операция работы 1 выполняется машиной M₄.

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

Решение для дорожек с любым неуказанным распределением

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

. Будет обозначен как (как определено выше).

Расчет времени ввода по формуле

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

Вновь рассмотрим время 0 как время первого возможного ввода. В это время груз u дорожки i, введенный во время x, прибывает перед дорожкой a_kво время x + Δi. Таким образом, получаем самый ранний момент времени, в который первая груз последовательности проходит перед дорожкой a_k по формуле

Алгоритм 2: Расчет времени ввода без нарушения потока в общем случае

Требуется:

Для всех

выполнить

для всех

выполнить

окончить для

окончить для

вернуть

На фиг. 46 представлена блок-схема алгоритма способа объединения k входящих потоков в один исходящий поток согласно первому частному варианту осуществления на основе алгоритма 2. Способ выполняется системой управления, по меньшей мере, один раз. Данный способ выполняется момент Tb и содержит следующие этапы:

- получение (этап 461) набора L, содержащего n грузов, распределенных в момент времени Tb на k дорожках и которые должны быть введены в коллектор для формирования выходной последовательности σ, причем каждый из n грузов идентифицируется одним порядковым номером в пределах выходной последовательности σ, каждая из k дорожек содержит упорядоченный набор, упорядоченный в порядке возрастания порядковых номеров h_i грузов, которые необходимо вводить один за другим в коллектор;

- вычисление (этап 462) времени t₀, в которое первый груз σ₁ выходной последовательности σ проходит перед дорожкой a_k;

- вычисление (этап 463) времени ввода в коллектор для каждого из n грузов набора L согласно следующей формуле:

, где

-

груз набора L и поступающий с j-й позиции в дорожке a_i, ,

- σ (u) является порядковым номером груза u в выходной последовательности σ;

- управление (этап 464) коллектором и k дорожками для ввода n грузов в коллектор в соответствии с n временем T (u),

ввода.

6.2.2 Пример

Рассмотрим пример, аналогичный приведенному ранее в параграфе «Пример», на этот раз без учета дорожек.

Рассмотрим конфигурацию системы следующим образом (см. фиг.16): k = 4 дорожки, содержащие два или три груза. Каждый груз идентифицируется уникальным порядковым номером как функция выходной последовательности σ = (1,2,3,4,5,6,7,8,9), которая представляет собой достижимую последовательность. Мы знаем расстояние от каждой дорожки до последней:

.

На фиг. 17 представлено представление решения в виде диаграммы Ганта. На этот раз две последовательные машины должны быть разнесены на столько строк на количество «интервалов времени» между двумя соответствующими последовательными дорожками. Поэтому решение представляет собой таблица с 13 (

строками. При вычислении имеем , что фактически по определению в момент 11 на графике.

Для простоты понимания приводим пример с междорожечными расстояниями, которые являются целыми значениями, но можно принимать нецелые значения в числах «интервалов времени».

Описание одного варианта осуществления

Список группируемых элементов

Каждый поток ввода (входящий поток) представлен дорожкой, содержащей список груза в порядке FIFO. Количество дорожек может варьироваться от 2 до k, и список дорожек i содержит h_i груза (h_i может быть нулевым). Всего необходимо объединить в коллектор n грузов. Возьмем для примера (см. фиг.18): k = 2, h₁ = h₂ = 5 и n = 10.

Дополнительно, оставаясь общим случаем, возьмем решения этого общего случая с Δ₁ = 1 и Δ₂ = 0.

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

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

Возможно разработать различные способы определения выходной последовательности «по умолчанию»:

- удалить поочередно по одному грузу с каждой дорожки,

- удалить груз в зависимости от их поступления в поток ввода,

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

- и т.п.

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

На фиг.19 показан пример последовательности (σ' = (8,4,5,2,7,6,1,9,3,10)), являющейся результатом вычисления, сводящего к минимуму неупорядоченность. Указанные номера не являются порядковыми номерами в конечной последовательности, а являются порядковыми номерами по отношению к заказам клиентов, которые должны быть отобраны.

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

Поскольку всегда можно присвоить один порядковый номер от 1 до n всем грузам, соответствующий их позиции в конечной последовательности σ, то возможно отображать грузы с этими порядковыми номерами, чтобы идентифицировать их и охарактеризовать их полностью (см. фиг.20). Фиг.19 и фиг.20 эквивалентны. Выходная последовательность σ = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) действительно позволяет увидеть порядок груза в порядке возрастания для каждого потока ввода (доказательство выполнимости последовательности).

Сохраним эту конфигурацию, чтобы продолжить изучение примера.

Получение t₀

В данном примере L' объединяет грузы с номерами 1 и 5.

Мы ищем максимум между

, и получаем t₀ = 0.

Расчет времени ввода (по формуле)

Объяснение результата на изображениях

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

Конфигурация коллектора в момент 0 (см. фиг.21) соответствует первому действительному вводу груза, в данном случае, груза 1 (потому что t₁ = 0), даже, если это не всегда так. Следует отметить, что действительно первая груз последовательности не обязательно является первым грузом, вводимым в коллектор.

Груз 2 должен быть введен в момент 1, что означает, что он находится на коллекторе после перемещения коллектора на один шаг, как показано на фиг.22.

Груз 3 вводится в момент 2, как показано на фиг.23.

Грузы 4 и 5 вводятся в момент 3, как показано на фиг.24.

И так далее.

Обработка партий грузов

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

Рабочая партия груза

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

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

Заполнение списков FIFO дорожек

Для каждой дорожки есть список грузов с уникальным порядковым номером для каждого груза. Эти порядковые номера грузов обязательно являются номерами, которые на дорожке имеют возрастающий порядок, но не обязательно идут подряд (из-за определения достижимой заданной последовательности).

На фиг.25 показан пример списка FIFO, ассоциированного с тремя дорожками.

На фиг.26 показана окончательная достижимая последовательность, ожидаемая на коллекторе.

Можно напомнить, что каждая дорожка соответствует потоку ввода, представленному в виде столбца FIFO, прикрепленного к коллектору, с его точкой ввода, обозначенной черной точкой на схемах.

Список FIFO грузов, учитываемых в дорожке для фиксированной конфигурации системы, устанавливает порядок грузов, ожидающих в точке ввода этой дорожки, в соответствии со следующими условиями:

- груз, учтенный во время анализа, ожидают в точке ввода (представлены черной точкой на следующих чертежах) (фиг.27: первый груз потока, прикрепленный к точке ввода и, следовательно, составляющий часть списка FIFO; фиг.28: первый груз потока, не привязанный к точке ввода и, следовательно, не входящий в список FIFO);

- учтенные во время анализа грузы находятся в «непрерывном» удержании за первым грузом, составляющим часть списка FIFO (фиг.29: второй груз в непрерывном удержании за первым грузом, составляющий часть списка FIFO; фиг.30: груз в непрерывном удержании за первым грузом, не входящий в список FIFO).

Определение партий

Работа партиями соответствует набору грузов из списка FIFO всех дорожек (это набор L из n грузов). Однако эти грузы соответствуют статической картине нашей системы в данный момент, в соответствии с правилами предшествующего абзаца. Присутствующие в системе в данный момент грузы, не соответствующие правилам заполнения списков FIFO, позже будут отнесены к другой партии.

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

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

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

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

В примере, показанном на фиг.31, первая партия будет состоять из грузов: 1, 2, 3, 4, 5, 6, 7, 8, 9. Следующая партия может быть: xx, yy или 9, xx, yy,…, или снова 7, 8, 9, xx, yy,… (но не 8, xx, yy, ни 7, 9, xx, yy).

Динамическая обработка партий

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

Расчет времени ввода первой партии

На фиг.32 показан пример первой партии для выходной последовательности σ = (1,2,3,4,5,6,7,8,9,10) с грузами 2, 6, 7 и 8 (для которых время ввода обозначено как Время 4, Время 8, Время 9 и Время 10, соответственно) на дорожке a₃, груза 1, 3 и 5 (для которых время ввода обозначены как Время 0, Время 2 и Время 4, соответственно) на дорожке a₂ и груза 4 и 9 (для которых время ввода обозначено как Время 0 и Время 5 соответственно) на дорожке a₁.

Своевременный ввод партии

Пока коллектор, ожидающий наивысшего порядкового номера (в данном случае № 9, обведенный кружком на фиг.32 и 33), не поступил перед дорожкой ввода, которая находится дальше всего вверх по потоку (т.е. дорожка a₁), обработка следующей партии не производится. Обработка грузов первой партии продолжается по мере прохождения времени, при вводе груза во время ввода, рассчитанного заранее, как это видно в верхней и нижней частях фиг.33.

Формирование очередной партии и статический расчет будущих моментов времени ввода

Когда последний отмеченный интервал последнего груза последовательности первой партии поступает перед дорожкой a₁, это является сигналом для формирования следующей партии. Эта партия состоит из всех допустимых грузов каждого списка FIFO для каждой дорожки в соответствии с правилами, описанными выше.

На фиг.34 показано формирование следующей партии, состоящей из шести новых грузов, которые появились на дорожках и пронумерованы от 1 до 6 (порядковые номера новой выходной последовательности, желательной для новой партии).

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

Конфигурация статической системы, взятая в «Время 5», как показано на фиг.34, используется (в качестве входных данных) для алгоритма. Эта конфигурация определяется следующим образом: k = 3 дорожки, содержащие шесть появившихся новых грузов (принадлежащих к новой партии). Каждый новый груз идентифицируется уникальным порядковым номером в зависимости от новой выходной последовательности этой новой партии: σ = (1,2,3,4,5,6). Это достижимая последовательность. Нам известны временные расстояния относительно последней дорожки: Δ₁ = 6, Δ₂ = 3 и Δ₃ = 0.

Время 0 фиксируется одновременным вводом двух новых грузов с номерами 1 и 4 (в дорожки a₂ и a₁ соответственно). Начиная с этого начала отсчета времени, алгоритм дает время T (u) ввода для каждого из шести новых грузов u этой новой партии.

Связь между временем ввода партии и текущим реальным временем

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

Общая для всех партий шкала времени позволяет связать ввод всех грузов в динамическую систему. Временной блок этой шкалы времени является «временной интервал» коллектора, как определено выше. Пусть «Время» будет временем, полученным из этой общей шкалы времени, и время 0 представляет собой время начала операций в системе.

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

Для этого необходимо знать время (также называемое «Tb»), в которое был запущен вызов алгоритма и (или, по меньшей мере, одно из) первый груз или грузы партии, которые должны быть введены раньше на коллектор, которые обозначен σ_*. Время 0 партии соответствует действию ввода этого груза

, и это действительно выполняется динамической системой точно через интервалы времени после вызова.

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

, фактическое время (время вызова алгоритма) в этом случае Время 5 (т.е. Tb = 5) плюс позиция первого введенного груза новой партии, введенной в новую последовательность (в данном случае это груз 1, следовательно, нам нужно добавить σ (1) = 1) плюс расстояние между дорожкой a₁ и той, которая содержит первый введенный груз (в данном случае Δ_1,2 = 3). Отметив, что груз 4 новой партии также сначала вводится в коллектор (одновременно с грузом 1 новой партии), мы могли бы выбрать ее и добавить σ (4) + Δ_1,1 = 4; это фактически то же самое, что и сложение σ (1) + Δ_1,2 = 1 + 3 = 4.

Для динамического приложения выполняется линейное преобразование времени ввода следующим образом:

В этом случае самое раннее время первого груза новой последовательности, проходящей перед a_k, будет точно

, где первый груз новой последовательности, который будет введен в коллектор (не обязательно первый груз новой последовательности). Теперь мы знаем, что t₀ является максимумом, достигаемый именно этим грузом u_*, что дает . Таким образом, мы знаем, что первый груз новой последовательности пройдет перед a_k в в общей шкале времени.

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

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

В приведенном выше примере момент Tb = 5 точно соответствует условию, и поэтому мы могли бы вызвать алгоритм

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

В итоге нашу систему можно представить, как показано на фиг.35. В общей шкале времени:

- время ввода грузов 6, 7 и 8 предшествующей партии обозначается как Время 8, Время 9 и Время 10 соответственно; и

- время ввода грузов 1, 2, 3, 4, 5 и 6 новой партии обозначается как Время 9, Время 10, Время 14, Время 9, Время 13 и Время 11 соответственно.

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

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

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

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

В следующей таблице приведены новые обозначения мешающих потоков.

Таблица 3

Мешающий поток

Общее количество мешающих грузов

Номер последней дорожки, перед которой проходит мешающий груз p

Номер первой дорожки, перед которой проходит мешающий груз p

Список запрещенных моментов времени для ввода груза по дорожке

Упорядоченный перечень мешающего груза

мешающий груз мешающего потока

Период между мешающим грузом u и мешающим грузом v в мешающем потоке в количестве «интервалов» в данный момент

Время поступления первого мешающего груза мешающего потока перед дорожкой

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

Расстояние между мешающим грузом p и последней дорожкой

во время

Время, когда мешающий груз p «фиктивно» вводится перед дорожкой

. (Фиктивно, если

, потому что в этом случае груз p не пройдет перед дорожкой

Моделирование системы с неуправляемым мешающим потоком

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

Формирование списка недействительных моментов времени

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

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

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

Идея решения для дорожек, которые последовательно распределены надлежащим образом

Данную техническую задачу планирования в предприятии со списком недействительных моментов времени для каждой машины можно решить, выполнив почти те же этапы, что и ранее в параграфе «Расчет времени ввода по формуле».

Подход в конкретном случае дорожек, распределенных надлежащим образом, по интервалам конвейера.

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

, ассоциированных с работой, начинаются с времени , начиная с времени t, что позволяет иметь времена соответственно на каждой машине , которые свободны (т.е. без препятствий).

Затем, операции работы, соответствующие следующему грузу последовательности, будут планироваться, прежде всего, путем выполнения операции, которая должна быть обработана на машине

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

Эта процедура применяется итеративно к каждой из следующих работ заданной последовательности.

Реальные моменты времени введения грузов в коллектор выводятся непосредственно с начала первой операции каждой работы. Блок времени используется, как определен выше.

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

Идея решения с неуправляемым мешающим потоком в общем случае

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

Следует посчитать, что возможно начать планирование работ с момента 0 и далее. Не следует забывать, что необходимо следовать определенному последовательному порядку выполнения операций машины M_k, в то же время минимизируя время простоя этой машины.

Для начала, допустим, что

обозначает самый ранний момент времени, в который работа, ассоциированная с первым грузом последовательности, может быть назначена машине , если у нее не было мешающего потока. Пусть грузы будут запланированы в порядке, заданном требуемой последовательностью, без учета мешающего потока, и затем время ввода будет изменено в следующем порядке. Действительно, можно отметить, что планирование груза σ_c оказывает влияние исключительно на груз σ_c', так что

Для работы, ассоциированной с грузом u, сначала планируют выполнение операции на машине

. Эта операция будет запланирована на t₀, если груз σ₁, иначе сразу после (без времени простоя) предшествующей операции, запрограммированной на . Предполагая, что эта операция на начинается в момент t, операция на машине (если она существует) планируется в момент . Затем операция на машине (если она существует) планируется в момент и так далее, и так далее, пока все операции не будут запрограммированы. Если операция не может быть выполнена в эти времени, указанные во время препятствия, должны перезапуститься планирование (всех) работ, сдвинув момент t выполнения операции, которая должна быть обработана на машине в блок времени (т.е. одно место, интервал или слот).

Эта процедура применяется итеративно к каждой из следующих работ заданной последовательности.

При необходимости необходимо сместить время 0 и время t₀, чтобы они соответствовали своему определению. Поскольку смещение времени 0 должно соответствовать первому возможному введению груза в коллектор, это отразится на всех графиках планирования (моменты времени ввода), которые, в свою очередь, будут смещены.

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

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

Алгоритм в общем случае

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

Время 0 соответствует самому первому грузу, введенному в коллектор. Время t₀ всегда является временем, когда первый груз последовательности проходит перед дорожкой a_k. Общая формула для

остается в силе, если нет конфликта с мешающим потоком во время ввода первого груза последовательности.

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

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

В этом алгоритме мы используем упрощенное обозначение «

» для определения груза u, соответствующей c-му грузу в последовательности σ, также определяемой ее позицией j в дорожке a_i.

Алгоритм 3: Расчет времени ввода с неуправляемыми мешающими потоками

Требуется:

// Задать значения U_i, вычисления будут производиться в каждом конкретном случае

// Теоретическое вычисление t₀

// Теоретическое время прохождения σ₁ перед дорожкой a_k

для c = от 1 до n сделать

установить

сделать {// Планирование груза σ_c во избежание всех препятствий

проверка = верно

для всех от z = k до z = i, z- - сделать

если (

), затем проверка = ложно;

окончание для

если (проверка = ложно) затем {

последний = последний + 1;

если (c = 1) затем t₀ = t₀ + 1; // t₀ изменяется, если препятствие

} окончание если

} когда (проверка = ложно);

T (u) = последний -Δ_i // Окончательное время ввода для груза σ_c

последний = последний + 1 // Теоретическое время прохождения

перед дорожкой a_k

окончание для

// Возможный сдвиг времени 0

set

to

если (

), затем

для

сделать

окончание для

окончание

возврат

На фиг.36 показан график алгоритма 3.

На фиг.47 представлена блок-схема алгоритма способа объединения k входящих потоков в один исходящий поток согласно второму частному варианту осуществления на основании алгоритма 3 (проиллюстрированного на фиг.36). Способ выполняется системой управления, по меньшей мере, один раз. Данная операция выполняется в момент времени Tb и содержат следующие этапы:

- получение (этап 471) набора L, содержащего n грузов, распределенных в момент Tb на k дорожках и которые должны быть введены в коллектор для формирования выходной последовательности σ, причем каждый из n грузов идентифицируется одним порядковым номером в пределах выходной последовательности σ, каждая из k дорожек содержит упорядоченный набор в соответствии с возрастающим порядком порядковых номеров h_i грузов, которые необходимо вводить один за другим в коллектор;

- для каждой дорожки a_i,

{1, ..., k}, получение (этап 472) набора U_i моментов времени, недействительных для ввода одного из грузов дорожки a_i в коллектор из-за неуправляемого мешающего груза или иного препятствия временного интервала коллектора;

- без учета наборов U_i,

вычисление (этап 473) времени t₀, в которое первый груз σ₁ выходной последовательности σ проходит перед дорожкой a_k;

- для первого груза σ₁ выходной последовательности σ, предполагают, что первый груз σ₁ поступает с дорожки a_i (этап 474):

а) инициализация t значением t₀;

b) если ни одно из времени

, , ,…, не принадлежит соответственно наборам , , ,…, , вычисление времени ввода первого груза σ₁ в коллектор по следующей формуле: , где ;

с) если одно из времени

, , ,…, принадлежит соответственно одному из наборам , , ,…, , увеличивая t на один блок и повторяя этапы b) и c) с новым значением t;

- для каждого следующего груза σ_c выходной последовательности σ,

{2, ..., n}, в предположении, что следующий σ_c поступает с дорожки a_i (этап 475):

a’) увеличение t на один блок, при этом t используется для вычисления времени ввода предшествующего груза σ_(c-1);

b') если ни одно из времени

, , ,…, не принадлежит соответственно наборам , , ,…, , вычисляя время ввода следующего груза σ_c в коллектор по следующей формуле: , где ;

c') если одно из времени,

, ,…, принадлежит соответственно одному из наборов , , ,…, , увеличивая t на один блок и повторяя этапы b') и c') с новым значением t;

- вычисление (476)

по следующей формуле:

- если

, модификация (477) n времени ввода по следующей формуле: ;

- подача команды (этап 478) коллектору и k дорожкам для ввода n грузов в коллектор в соответствии с n временем ввода T (u),

.

Описание одного конкретного варианта осуществления

Давайте посмотрим неуправляемый мешающий поток, уже присутствующий на коллекторе, не учтенный в конечном итоге требуемой последовательностью, потому что все мешающие грузы разгружаются до последней дорожки ввода. Это имеет место, например, в контексте фиг.50 (PTS Intelis GTP автоматизированная система) с управлением введения в коллектор грузов, поступающих из автоматизированной системы (PTS), но также и возвратом грузов, которые поступают в этот коллектор для возврата в автоматизированную систему (PTS) (см. параграф 2.2 в контексте этого возможного применения).

Фиг.37 иллюстрирует эту конфигурацию с мешающими грузами (отмеченными крестиком) возвратного потока (составляющего неуправляемый мешающий поток), который возвращается в автоматизированную систему (PTS).

В соответствии с этой конфигурацией мы делаем два наблюдения:

- никакой мешающий груз обратного потока (и, следовательно, мешающего потока) не будет проходить перед последней дорожкой; и

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

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

Рассмотрим поток Fn’ мешающего груза, уже имеющихся в коллекторе, и выгружаемых из коллектора между дорожками ввода. Этот мешающий поток, называемый обратным потоком, соответствует грузам, которые должны возвращаться на склад в автоматизированной системе (PTS). Эти мешающие грузы действительно должны проходить перед одной или несколькими дорожками ввода. Для каждого мешающего груза p этого обратного потока (мешающего потока) g_p (и l_p соответственно) обозначают номер первой дорожки (и последней дорожки соответственно), перед которой проходит мешающий груз p. Могут использоваться два способа, позволяющих вычислять недействительные моменты времени (U_i) ввода, вызванные обратным потоком как функция известных данных.

В этом конкретном варианте осуществления g_p = 1 и l_p p и l_p.

- либо в вышеупомянутом конкретном случае обратного потока мы знаем время поступления (обозначенное t_r) первого мешающего груза обратного потока (мешающий поток) перед дорожкой с номером a₁ (или снова машина M₁). Нам также известен порядок, в котором мешающие грузы этого обратного потока распределяются по коллектору (назовем эту последовательность σ’), и продолжительность между каждым мешающим грузом и другим мешающим грузом этого мешающего потока. Пусть σ’_p предоставляет p-й мешающий груз обратного потока, и σ’(u, v) образует продолжительность между мешающим грузом u и мешающим грузом v в мешающем потоке в количестве «интервалов».

Затем моменты

перегружены для машины M₁ и образуют U₁.

- для машины

, перегруженными временем являются

- другим способом контроля ситуации является копирование «перегруженных» (или недействительные) моменты времени U_i машины M_i мешающего груза u, которые l (u) ≥i + 1, и добавить ко всем этим моментам Δ_{(i, i + 1)}, чтобы получить список перегруженных моментов времени U_{(i + 1)} для машины M_{(i + 1)}.

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

времени 0, которую мы обозначим как . Используя эти моменты времени, вычисляют значения следующим образом:

Для всех

{1, …, k} сделать Ui = ∅;

Для всех p

F сделать

Для всех

{g_p, …, l_p} сделать

;

Окончание для

Окончание для

Вернуть

Примеры

Вернемся к конфигурации примера параграфа 6.2.2.

Допустим, k = 4 дорожки, содержащие два или три груза. Каждый груз идентифицируется уникальным порядковым номером как функция выходной последовательности σ = (1,2,3,4,5,6,7,8,9). Это достижимая последовательность. Мы знаем расстояния от каждой дорожки до последней:

и

Как показано на фиг.38, предполагается, что в данное время существует три временных интервала коллектора, занятые мешающими грузами A, B и C. Мы знаем, что эти мешающие грузы проходят перед определенными дорожками и после этого выгружаются из коллектора. Грузы A и B проходят перед дорожками a₁ и a₂. Наконец, груз C проходит перед всеми дорожками a₁, a₂ и a₃. Таким образом, имеем

и , а также .

Иллюстрируется состояние системы на время 0, когда первый груз партии будет введен в первое незанятое место коллектора. На схеме незанятое место коллектора является свободным, крестики указывают позиции, занятые грузами предшествующей партии, и буквы обозначают мешающий груз мешающего потока. Позиция мешающего потока во время 0 позволяет вывести следующие фрагменты информации:

и

Мешающий груз B заставляет груз 4 сдвигаться во времени на одну позицию и оставляет свободное место в конечном потоке коллектора. Затем мешающий поток C заставляет груз 7 сместиться еще на одну позицию, оставляя свободное место позже в окончательном потоке коллектора.

На фиг.39 представлена диаграмма Ганта, иллюстрирующая решение, предложенное в этом случае. Мы можем видеть, что если бы мешающий поток управлялся (и не управлялся), первое свободное пространство могло быть заполнено дорожкой a₃ или a₄, и второе свободное пространство заполнено только дорожкой a₄. Таким образом, можно было бы избежать свободных пространств и увеличить пропускную способность конечного потока (исходящего потока) коллектора.

Моделирование системы с управляемым мешающим потоком

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

Формулирование технической задачи

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

), в которое мешающий груз p вводится перед дорожкой a₁, чтобы не нарушать исходящий поток (исходящий поток, образованный объединением потоков ввода), то есть, предотвратить образование свободного места в выходном потоке.

Идея алгоритма решения

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

Общий алгоритм

Алгоритм 4, подробно описанный здесь ниже, предоставляет моменты времени ввода грузов, а также управление мешающим потоком. Вводимые грузы составляют последний поток коллектора. Их ввод решается без учета мешающего потока. Затем мы определим, когда пропустить грузы мешающего потока, учитывая, что в данное время введенные груза играют ту же роль, что и неуправляемый поток в алгоритме 3, описанном выше. Таким образом, мы можем использовать ту же технологию, что и ранее предложенную, с вычислением наборов.

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

Можно вспомнить, что

дает расстояние между мешающими грузами p и p' во время 0, и tr дает время без ожидания прибытия 1-й груза мешающего потока перед дорожкой с номером a₁.

В этом алгоритме мы используем упрощенное обозначение «

» для определения груза u, соответствующей c-му грузу последовательности σ, также определяемой позицией j в дорожке a_i.

Алгоритм 4: Расчет времени ввода груза управляемых мешающих потоков.

Требуется:

// Теоретическое вычисление t₀

для всех

{1, …, k} сделать

для всех

{1, …, hi} сделать

установить u = a_i (j)

для всех

{i, …, k} сделать

окончание для

окончание для

окончание для

установить

// Прибытие первого мешающего груза перед a₁

для всех p =

сделать // Груз определяется по их месту в σ_f

сделать {

проверка = верно

для i = g_p - l_p сделать

если (t + Δ₁-Δ_

), затем проверить = ложно; t ++; перерыв;

окончание для

} когда (проверка = ложно);

// Возможное ожидание прибытия p + 1

окончание для

Вернуть

На фиг.40 представлена схема алгоритма 4, описанного выше.

На фиг.48 представлена блок-схема алгоритма способа объединения k входящих потоков в один исходящий поток согласно третьему конкретному варианту осуществления на основании алгоритма 4 (проиллюстрированного на фиг.40). Способ выполняется системой управления, по меньшей мере, один раз. Данная операция выполняется в момент времени Tb и содержит следующие этапы:

- для каждого груза u = a_i (j)

поступающего из дорожки a_i, вычисление (этап 481) времени прохождения груза перед дорожками от a_i до a_k, время введения T(u) груза в известный коллектор;

- для каждой дорожки a_i,

{1, ..., k} получение (этап 482) набора V_i, содержащего каждый момент времени прохождения одного из грузов перед дорожкой a_i;

- для каждого управляемого мешающего груза p мешающего потока, управляемого с помощью средства управления, расположенного вдоль коллектора и имеющего дорожку a_g(p)в смысле движения коллектора, при g_(p)

{1, .. ., k}, a_g(p) также является первой дорожкой в смысле движения коллектора, перед которой проходит управляемый мешающий груз (этап 483):

a) инициализация t временем

, где представляет возможный момент времени поступления, если первый управляемый мешающий груз не будет приостановлен перед дорожкой a_k;

b) вычисление времени

, ,…, прохождения управляемого мешающего груза перед дорожками от a_g(p) до a_l(p), причем a_l(p) является последней дорожкой в смысле движения коллектора, перед которой проходит управляемый мешающий груз;

с) если ни один из моментов времени

, ,…, не принадлежит соответственно наборам , ,…, , вычисление фиктивного времени прохода управляемого мешающего груза p перед дорожкой a₁ по следующей формуле: ;

d) если один из моментов времени

, ,…, принадлежит соответственно одному из наборов увеличивая t на один блок и повторяя этапы b), c) и d) с новым значением t;

- подача команды (этап 484) средству управления для ввода в момент времени

каждого управляемого мешающего груза p перед дорожкой a_g(p).

Описание одного конкретного варианта осуществления

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

Допустим, k = 4 дорожки с двумя или тремя грузами. Каждый груз идентифицируется одним порядковым номером как функция выходной последовательности σ = (1,2,3,4,5,6,7,8,9). Это достижимая последовательность. Мы знаем расстояния от каждой дорожки до последней:

. Мешающий поток состоит из таких груза A, B, C, что , , and .

В это время мешающий поток можно контролировать. На фиг.41 мы можем видеть контрольную точку этого мешающего потока, представленную вертикальным прямоугольником непосредственно перед дорожкой a₁.

Фиг.42 представляет собой иллюстрацию в виде диаграммы Ганта решения без учета мешающего потока («решение чистого ввода»).

Решение алгоритма с учетом мешающего потока сводится к перемещению мешающего груза в прямоугольники серого цвета, оставленные пустыми решением чистого ввода. Груз A беспрепятственного проходит, как только он достигает контрольной точки мешающего потока, в то время как груз B удерживается в течение одного блока времени. Это ожидание позволяет побудить мешающий груз B пройти в свободные пространства ввода непосредственно перед вводом груза 5. Это также относится к грузу C и грузу 8 последовательности.

Фиг.43 представляет собой иллюстрацию решения в виде диаграммы Ганта, предложенного для управления мешающим потоком (т.е. путем выбора размещения мешающего груза). Грузы B и C больше не образуют свободного пространства в конечном потоке коллектора. Они были размещены в ключевых местах, так что свободное пространство, которое они оставляют первоначально, затем заполнялось вводом совместимого по времени груза. Путем управления мешающим потоком мы показали, что можно избежать появления свободных пространств на коллекторе.

Моделирование системы с неуправляемым мешающим потоком и управляемым мешающим потоком

Если одновременно присутствуют, по меньшей мере, хотя бы один неуправляемый мешающий поток и хотя бы один управляемый мешающий поток, выполняются следующие операции.

Отличают неуправляемые мешающие грузы от управляемых мешающих грузов следующим образом:

- пусть S будет набором s неуправляемого мешающего груза, которым в обязательном порядке разрешается проходить без управления в зону ввода дорожек коллектора, каждый из которых идентифицируется уникальным порядковым номером, соответствующим позиции в порядке поступления (обозначается как

).

Допустим,

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

Наконец, наборы

задают время недоступности прохода перед дорожкой a_i для грузов.

- пусть F обозначает набор f мешающего груза, которым разрешено проходить под управлением в зону ввода дорожек коллектора, каждый из которых идентифицируется уникальным порядковым номером, соответствующим позиции в порядке прибытия (обозначается как σ_f).

Допустим,

обозначает расстояние от каждого мешающего груза p F до последней дорожки во время Tb, и пусть g_p и l_p соответственно обозначают номер первой и последней дорожки, перед которой возникает мешающий груз p, должен пройти.

Наконец, наборы

дают времени недоступности прохода перед дорожкой a_i для этих управляемых мешающих грузов.

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

Алгоритм 5: Расчет времени ввода грузов и грузов управляемого мешающего потока с учетом неуправляемого мешающего потока:

Требуется:

// Теоретическое вычисление t₀

// Вычислить значения U_i:

для всех p = 1 до s сделать

для всех

сделать

// груз p перед a_i

окончание для

окончание для

// Вычислить значения T (u)

последний = t₀// Теоретическая время прохождения σ₁ перед дорожкой a_k

для u = от 1 до n сделать

установить u = a_i (j)

сделать {// Планирование u-го груза σ

проверка = верно

для всех z = k à z = i, z- - сделать

если (

), затем проверить = ложно;

окончание для

если (проверка = ложно) затем {

последний = последний + 1;

если (u = 1), затем t₀ = t₀ + 1;

} окончание, если

} когда (проверка = ложно);

T (u) = последний -Δ_i // Окончательный момент времени ввода для груза u

последний = последний + 1 // Следующее место перед a_k

окончание для

// Возможный сдвиг времени 0

set

to

если

, затем

для

сделать

окончание для

окончание если

// вычислить значения V_z:

для u = от 1 до n сделать

установить u = a_i (j)

для все

{i, …, k} сделать

окончание для

окончание для

для всех

{1, …, k} сделать

окончание для

// вычисляем значения

установить

// Поступление первого мешающего груза перед a₁

для всех p = 1 - f сделать// Груз определяется по ее месту в σ_f

сделать {

проверка = верно

для i = g_p - l_p сделать

если

, затем проверка = ложно; t ++; перерыв;

окончание для

} в то время, как (проверка = ложь);

// Возможное ожидание поступления p + 1

окончание для

Возврат

На фиг.45 представлена схема алгоритма 5, описанного выше.

Фиг.49 является блок-схемой алгоритма способа объединения k входящих потоков в один исходящий поток согласно четвертому конкретному варианту осуществления на основании алгоритма 5 (проиллюстрированного на фиг.45). Способ выполняется системой управления хотя бы один раз. Данная операция выполняется в момент времени Tb и содержит следующие этапы:

- для каждого груза u = a_i (j)

поступающего из дорожки a_i, вычисление (этап 491) времени прохождения груза перед дорожками от a_i до a_k, время T (u) введения груза в известный коллектор;

- для каждой дорожки a_i,

{1, ..., k}, получение (этап 492) набора V_i, содержащего, с одной стороны, каждое время прохождения одного из грузов перед дорожкой a_i, а с другой стороны, набора U_i моментов времени, недействительных для ввода одного из грузов дорожки a_i в коллектор;

- для каждой управляемого мешающего груза p мешающего потока, управляемого с помощью средства управления, расположенного вдоль коллектора и перед дорожкой a_g(p) в смысле движения коллектора, при

a_g(p) также является первой дорожкой коллектора, по которой проходит управляемый мешающий груз (этап 493):

a) инициализация t временем

, где представляет возможное время поступления, если первый управляемый мешающий груз перед дорожкой a_k не будет приостановлен;

b) вычисление времени

, ,…, , ,…, прохождения управляемого мешающего груза перед дорожками от a_g(p) до a_l(p), причем a_l(p) является последней дорожкой в смысле движения коллектора, перед которой проходит управляемый мешающий груз;

с) если ни один из моментов времени

, ,…, не принадлежит соответственно наборам , ,…, , вычисление фиктивного времени прохода управляемого мешающего груза p перед дорожкой движения a₁ по следующей формуле: ;

d) если один момент времени

, ,…, принадлежит соответственно одному из наборов , увеличивая t на один блок времени и повторяя этапы b), c) и d) с новым значением t;

- подача команды (этап 494) средству управления для ввода в момент времени

каждого управляемого мешающего груза p перед дорожкой a_g(p).

Заключение

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

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

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

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

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

Пример системы управления

Предлагаемое решение представляет собой способ объединения в пределах логистического склада k входящих потоков грузов, транспортируемых соответственно k конвейерами, называемыми дорожками a_i с

{1, ..., k}, в один исходящий поток грузов, транспортируемых другим конвейером, называемым коллектором.

Способ объединения выполняется системой управления. Например, центральная система управления складом или WCS.

На фиг.44 представлена структура системы 90 управления согласно одному конкретному варианту осуществления изобретения. Эта система управления содержит оперативную память 92 (например, RAM), блок 91 обработки, например, оснащенный процессором и управляемой компьютерной программой 930, хранящейся в постоянном запоминающем устройстве 93 (например, ROM или жесткий диск).

При инициализации кодовые инструкции компьютерной программы, например, загружаются в оперативную память 92, и затем выполняются процессором блока 91 обработки для реализации способа объединения согласно изобретению (согласно любому из различных описанных вариантов осуществления, описанных ранее). Блок 91 обработки вводит фрагменты информации 94, относящейся к входящим потокам. Процессор блока 91 обработки обрабатывает информацию 94 и генерирует на выходе инструкции или команды 95, используемые для управления (команды) различными элементами, содержащиеся в системе, особенно дорожками, коллектором, средством управления и т.д.

Фиг.44 иллюстрирует только один конкретный способ из нескольких возможных способов реализации технологии изобретения в любом из его вариантов осуществления. Действительно, система управления одинаково хорошо реализована на перепрограммируемой вычислительной машине (например РС, процессор DSP, микроконтроллер и т.д.), выполняющей программу, содержащую последовательность инструкций, или на специализированной вычислительной машине (например, набор логических вентилей, таких как FPGA, ASIC или любой другой аппаратный модуль).

Если система управления выполняется с помощью перепрограммируемой вычислительной машины, соответствующая программа (то есть последовательность инструкций) может быть сохранена на съемном носителе данных (например, на гибком диске, CD-ROM или DVD-ROM) или несъемном, этот носитель данных частично или полностью читается компьютером или процессором.

Реферат

Изобретение относится к области информационных технологий, а именно к подготовке и выполнению оптимизированных решений по маршрутизации, хранению и комплектации заказов. Технический результат заключается в оптимизации пропускной способности исходящего потока грузов. Способ объединения k входящих потоков грузов, на логистическом складе, соответственно транспортируемых k конвейерами, называемыми дорожками aiс{1, ..., k}, в один исходящий поток грузов, транспортируемых другим конвейером, называемым коллектором: при этом дорожки k относятся к типу «первым пришел-первым ушел», распределены вдоль коллектора и пронумерованы от a1до akпо направлению движения коллектора, и является зависящим от времени расстоянием между дорожками aiи ak, выраженным в блоках времени, каждый из которых соответствует одному интервалу времени коллектора, вычисляют время ввода в коллектор каждого из n грузов набора L согласно и подают команду коллектору и k дорожкам для ввода n грузов в коллектор в соответствии с n временами ввода. 2 н. и 7 з.п. ф-лы, 3 табл., 50 ил.

Формула