книги / Управление большими системами. УБС-2017

Информационные технологии в управлении техническими системами и технологическими процессами

технологического маршрута, а использование ресурсов формализуется совокупностями ограничений (3) и (10). Таким образом, полученные М оптимизационных задач можно свести к одной задаче ЛП или ЦЛП, включающей в себя все ограничения по всем m =1, , M типам ресурсов. Рассмотрим, как при

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

3.1.МОДИФИКАЦИЯ ЗАДАЧИ В НЕПРЕРЫВНОМ ВРЕМЕНИ

Задача (1)–(4) сформулирована относительно перемен-

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

только группы ограничений (3). Количество неравенств (3) увеличивается пропорционально количеству типов располагаемых ресурсов цеха М. Расширенная группа ограничивающих неравенств имеет вид

3.2.МОДИФИКАЦИЯ ЗАДАЧИ В ДИСКРЕТНОМ ВРЕМЕНИ

Разбивка временного горизонта задачи планирования на

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

223

261

Управление большими системами. Выпуск XX

4. Оценка влияния многоресурсности на скорость решения задачи планирования

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

4.1.ВЫЧИСЛИТЕЛЬНЫЕ РЕСУРСЫ МОДЕЛИРОВАНИЯ

Вычислительные эксперименты проводились с применени-

ем ПК на базе процессора Intel Core i7 8 ядер, 32 Гб ОЗУ; выполнение программного кода осуществлялось на виртуальной машине VMWare Workstation 11 c ОС Windows Server 2008 R2,

которой было выделено 4 процессорных ядра и 8 Гб ОЗУ.

4.2.РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ

Исходные данные для моделирования процессов планиро-

вания представлены в табл. 1.

Таблица 1. Исходные данные для моделирования

Информационные технологии в управлении техническими системами и технологическими процессами

Окончание табл. 1

ЗАДАЧА С ДВУМЯ ТИПАМИ РЕСУРСОВ

Результаты моделирования рассмотренной задачи планирования на примере модели ЛП с одним и двумя типами ресурсов представлены в табл. 2–3 и на рисунке.

Таблица 2. Результаты планирования с одним типом ресурса

Таблица 3. Результаты планирования с двумя типами ресурса

225

263

Управление большими системами. Выпуск XX

Рис. Время решения задачи для одноресурсной (пунктирная линия) и многоресурсной (сплошная линия) задачи

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

5.Заключение

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

226

264

Информационные технологии в управлении техническими системами и технологическими процессами

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

Литература

1.ЕВГЕНЕВ Г.Б., ГАВРЮШИН С.С., ХОБОТОВ Е.Н. Методы тактического планирования деятельности предприятий // Основы автоматизации технологических процессов и произ-

водств. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2015. – 479 с.

2.ЛАЗАРЕВ А.А., НЕКРАСОВ И.В., ПРАВДИВЕЦ Н.А. Опти-

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

ния // Теория расписаний и методы декомпозиции. Танаевские чтения: тр. 7-й Междунар. науч. конф.; Беларусь, Минск, 2016; ОИПИ НАН Беларуси. – Минск, 2016. – С. 108–113.

3.О’ЛИРИ Д. ERP-системы: Современное планирование и управление ресурсами предприятия. Выбор, внедрение, эксплуа-

тация / пер. с англ. Ю.И. Водяновой; ООО «Вершина». – М., 2004. – 272 с.

4.ПРИЛУЦКИЙ М.Х., КУМАГИНА Е.А. Оптимальные стра-

тегии распределения ресурсов в сетевых структурах // Вест-

ник Нижегородского университета им. Н.И. Лобачевского. Сер. Математическое моделирование. Оптимальное управле-

ние. – 2014. – № 1(1). – 272 с.

5.Технико-экономическое планирование с применением элек- тронно-вычислительных машин / О. КОЗЛОВА, Г. БРОД-

СКИЙ, В. ДУДОРИН, С. МИТИН, Л. НИКОНОВА, Н. СА-

ЛОМАТИН // Применение электронно-вычислительных машин в управлении производством. – М.: Мысль, 1965. – 509 с.

6.ARTIGUES C., DEMASSYE S, NERON E. Resource-cons- trained project scheduling: models, algorithms, extensions and applications. – ISTE Ltd, 2008. – 308 p.

227

265

Управление большими системами. Выпуск XX

7.JOZEFOWSKA J., WEGLARZ J. Perspectives in modern project scheduling. – Springer Science+Business Media, LLC, 2006. – 453 p.

8.McCLELLAN M. Applying manufacturing execution systems. – Boca Raton, Florida, The St.Lucie Press, LLC, 1997. – 208 p.

9.RILEY E. Manufacturing execution system (MES). An examination of implementation strategy // A thesis presented to the faculty of California Polytechnic State University. – San Luis Obispo, 2013. – 55 p.

MULTI-TYPE RESOURCE JOB-SHOP SCHEDULING PROBLEM: COMPARING REALIZATION TECHNIQUES AND APPROACHES

Alexander Lazarev, Institute of Control Sciences of RAS, Moscow, Doctor of Science, professor (jobmath@mail.ru).

Ivan Nekrasov, Institute of Control Sciences of RAS, Moscow, Cand.Sc. (ivannekr@mail.ru).

Abstract: This paper considers two basic approaches to formalize RCPSP problem: a discrete and continuous time problem settings. Both settings were initially formulated for a single-type resource case (for instance – a machine tool). We show how the single-type resource setting can be adopted to fit the multi-type resource case (for instance when we want to simultaneously schedule operations for machine tools, personnel, rigging, raw material, etc.). This research suggests a comparative analysis of both scheduling models for an enlarged multitype resource case. The comparison is conducted by such criteria as model adoption minimalism and the computational complexity increase ratio.

Keywords: RCPSP, job shop, MES, multi-type resource scheduling, integer linear programming, computational complexity.

228

266

Информационные технологии в управлении техническими системами и технологическими процессами

УДК 621.391:004.052 ББК 32.96

ИССЛЕДОВАНИЕ АЛГОРИТМОВ МЯГКОГО ДЕКОДИРОВАНИЯ В ПРИЕМНЫХ УСТРОЙСТВАХ ЭЛЕМЕНТОВ РАСПРЕДЕЛЕННЫХ СИСТЕМ УПРАВЛЕНИЯ

Фрейман В.И.1

(Пермский национальный исследовательский политехнический университет, Пермь)

Дубовцева Д.А.2

(Пермский национальный исследовательский политехнический университет, Пермь)

В данной статье рассмотрено построение модели итеративного декодирования в программе Microsoft Office Excel 2007 с поддержкой макросов и последующее применение модели для исследования алгоритмов мягкого декодирования в приемных устройствах элементов распределенных систем управления. На основе данных исследований выявлены зависимости и сделаны выводы.

Ключевые слова: турбокод, итеративное декодирование, составление модели.

1.Введение

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

1 Владимир Исаакович Фрейман, кандидат технических наук, профессор

(vfrey@mail.ru).

2 ДарьяАлександровнаДубовцева, студентка(dasha.dubovtseva@mail.ru).

229

267

Управление большими системами. Выпуск XX

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

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

Впервые турбокоды были предложены К. Берроу, А. Главьё и П. Ситимашимой в 1993 г. в статье «Кодирование и декодирование с исправлением ошибок вблизи предела Шеннона: Турбо-

коды» (англ. Near Shannon Limit Error–Correcting Coding and Decoding: Turbo Codes), опубликованной IEEE. До появления турбокодов широко использовался метод каскадного кодирования: сначала данные кодировались кодом Рида–Соломона, а затем сверточным кодом [1].

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

Microsoft Office Excel 2007 с поддержкой макросов.

2. Теоретические основы

2.1. СТРУКТУРА КОМПОЗИЦИОННОГО КОДА

Рассмотрим двухмерный код (композиционный код), изображенный на рис. 1. Структуру данного кода можно описать как массив данных, состоящий из k1 строк и k2 столбцов. В k1 строках содержатся кодовые слова, образованные k2 битами данных и n2 – k2 битами четности. Каждая из k1 строк представляет собой кодовое слово кода (n2, k2). Аналогично k2 столбцов содержат кодовые слова, образованные из k1 бит данных и n1 – k1 бит четности. Таким образом, каждый из k2 столбцов представляет собой кодовые слова кода (n1, k1). Различные участки структуры обозначены следующим образом: d – для данных,

230

268

Информационные технологии в управлении техническими системами и технологическими процессами

ph – для горизонтальной четности (вдоль строк) и pv – для вертикальной четности (вдоль столбцов). Фактически каждый блок битов данных размеров k1 x k2 кодирован двумя кодами – горизонтальным и вертикальным.

Еще на рис. 1 присутствуют блоки Leh и Lev. В них содержатся значения внешних LLR, полученные из горизонтального и вертикального кодов [2].

k2 n2 − k2

Рис. 1. Структура двухмерного композиционного кода

2.2. АЛГОРИТМ ИТЕРАТИВНОГО ДЕКОДИРОВАНИЯ

Для удобства вычислений используется логарифмическое отношение правдоподобия (log-likelihood ratio – LLR). Выходное LLR декодера имеет следующий вид:

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

1.Устанавливается априорное LLR L(d) = 0. То есть на первом шаге данные считаются равновероятными.

2.Декодируется горизонтальный код и вычисляется горизонтальное LLR (из уравнения (1)) Leh(d^) = L(d^) – Lc(x) – L(d),

231

269

Управление большими системами. Выпуск XX

где L(d^) – мягкое решение вне декодера; Lc(x) означает, что данный член LLR получается в результате канальных измерений, произведенных в приемнике; L(d) – априорное LLR бита данных d.

3.На этапе 4 вертикального декодирования устанавливает-

ся L(d) = Leh(d^).

4.Декодируется вертикальный код и вычисляется верти-

кальное LLR (из уравнения (1)): Lev(d^) = L(d^) – Lc(x) – L(d).

5.Для этапа 2 горизонтального декодирования устанавливается L(d) = Lev(d^). Затем повторяются этапы 2–5.

6.После достаточного для получения надежного решения количества итераций (т.е. повторения этапов 2–5) следует перейти к этапу 7.

7.Мягким решением на выходе будет

(2)L(d^) = Lc(x) + Leh(d^) + Lev(d^).

Решение при финальном декодировании каждого бита и его надежности зависит от значения L(d^) [2].

Схематично данный алгоритм можно описать следующим образом (рис. 2).

Рис. 2. Алгоритм итеративного декодирования

232

270