close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Созданные в данной работе файлы содержат поля,
значениями которых являются выражения, используемые при создании системы меню, компоненты структурной формулы, уравнения границы
области и ее участков в виде логических формул,
описания геометрических, физических и аналитических объектов и др.
Для реализации указанной системы знаний используется система управления базами данных
Visual FoxPro 5.0. Общение пользователя с системой организовано в форме диалога, который обеспечивает поиск в базе знаний необходимой информации, обработку ее, построение программы на
языке RL, выдачу результатов на средства отображения информации.
Разработанная система основана на правилах или
имеет вывод, использующий сопоставление по
образцу. Такие системы называют продукционными. Знания в системе представлены набором правил, имеющих вид:
если <условие>, то <действие>,
где условие задано на экране, а действие ? совокупность команд, управляющих ходом решения задачи.
Так, выбор структуры решения задачи осуществляется с использованием правил следующего вида:
ЕСЛИ краевые условия первого рода
И точное удовлетворение краевым условиям
И
ТО
тело однородное
выбрать структуру 1,
где структура 1 находится в одном из файлов базы
правил. Вся необходимая пользователю в ходе
диалога информация отображается на экране в виде
системы меню и вопросов.
УДК 621.391(07), 658.12.512.011
ЗАДАЧА СОСТАВЛЕНИЯ
ОПТИМАЛЬНОГО РАСПИСАНИЯ
ФОРМИРОВАНИЯ СБОРНЫХ
ПАЧЕК ПРИ ЭКСПЕДИРОВАНИИ
ИЗДАНИЙ
КУЗЬМЕНКО В.М., НЕНЬКО Л.Ф.
Пользователь выбирает маршрут решения краевой
задачи, осуществляя выбор пунктов меню и вводя
ответы на вопросы, задаваемой системой. В зависимости от выбора пользователя система выбирает
алгоритм, а затем строит программу решения поставленной задачи. Для информирования пользователя о ходе процесса решения задачи предусмотрена система подсказок-сообщений, а также визуализация результатов.
Система ориентирована не на специалистов, а в
первую очередь на инженеров-технологов, конструкторов, испытателей, может применяться в научных исследованиях, инженерных расчетах и учебном процессе.
Литература: 1.Грицюк Е.М., Шевченко Л.П. Регионально-аналитический метод моделирования тепловых
процессов в поршнях ДВС// Вестник ХГПУ, 1999,
Вып. 47. С.142-144. 2.Кокорева Л.В., Перевозчикова О.Л.,
Ющенко Е.Л. Диалоговые системы и представление
знаний. К.: Наук. думка, 1993. 445 с.
Поступила в редколлегию 25.04.2000
Рецензент: д-р техн. наук, проф. Авраменко В.П.
Грицюк Екатерина Марковна, аспирантка кафедры
информатики Харьковского государственного технического университета строительства и архитектуры.
Научные интересы: разработка специализированных
диалоговых систем. Адрес: Украина, 61002, Харьков,
ул. Сумская, 40, тел. 40-29-25.
Шевченко Людмила Петровна, канд. физ.-мат. наук,
доцент, заведующая кафедрой информатики Харьковского государственного технического университета
строительства и архитектуры. Научные интересы: разработка специализированных диалоговых систем. Адрес: Украина, 61002, Харьков, ул. Сумская, 40, тел. 4029-25.
Пачки n l * , сформированные на поточных линиях
z
обработки газет, поступают на ручной участок, где
из них в контрольные сроки t ? §Ё ? l ·ё формируются
© ij №
сборные пачки nijl §Ё nijl §Ё ?ijl h ·ё ·ё , т.е. поступле№№
©
©
ние пачек n l * задаётдля ручного участка некоторое
z
l
Aijl по формированию сбормножество работ A
Рассматривается задача составления оптимального
расписания формирования сборных пачек при экспедировании периодических изданий. Разработан эвристический алгоритм составления расписания, основой
которого являются теоремы теории расписаний. Алгоритм используется в АС почтовой связи.
l
ных пачек nij . Каждая такая работа Aijl характериl
зуется: W ij ? продолжительностью формирования
l
l
сборных пачек nij ; aij ? количеством затрат труда
Процесс экспедирования периодических изданий
включает следующие основные операции: прием
тиражей изданий, сортировка по местам накапливания и обработки, формирование сборных пачек
и посылов в адрес получателей, формирование
посылов по маршруту доставки, отправки получателям. При управлении экспедированием необходимо решать задачи выбора оптимального количества поточных линий обработки изданий, оптимального ритма экспедирования и оптимального
графика формирования сборных пачек.
? l
в единицу времени; t §Ё nij ·ё ? контрольным сро© №
ком окончания формирования сборной пачки.
Несвоевременность выдачи сборных пачек приводит к потерям по формированию маршрутов, котоl
рые могут быть оценены штрафом D ij за сдвиг
момента времени формирования сборной пачки.
Ручной участок в z -м промежутке времени располагает ресурсами P?? , которые необходимо равномерно использовать в планируемом промежутке
времени, т. е. необходимо обеспечить равномерную
РИ, 2000, № 2
59
загрузку бригад в планируемом промежутке времени z z 1, Z . Отклонение от суммарной величины
используемых ресурсов P?? оценивается удельной
величиной E штрафа.
l
Работы по формированию сборных пачек nij
независимы между собой и не допускают разрывов
при выполнении.
Необходимо определить такую последовательность
l
формирования сборных пачек nij , чтобы сумма
штрафов за сдвиг сроков окончания работ по
формированию сборных пачек была минимальной,
т.е. максимально стабилизировать выполнение работ в заданные сроки. Кроме того, необходимо
свести к минимуму колебания ресурсов, используемых в любой момент времени вокруг заданной
величины, т.е. стабилизировать использование имеющихся ресурсов.
В такой постановке данная задача является многоцелевой задачей теории расписаний и согласно [1]
носит название задачи стабилизации. В [1] предлагается следующий подход к ее решению, который
основан на использовании метода динамического
программирования [2]. Решение задачи рассматривается в динамике, при этом весь процесс делится
t?
на - шагов с величиной шага оптимизации S
.
-
Решение достигается при минимальном значении
целевой функции:
F3
min
-
¦ fS zS \ ? R ?? , zS ,
(1)
z1 ,..., z- S 1
где zS ? множество работ на S-м шаге оптимизации
S 1,- ; fS zS ? функция общих затрат за сдвиг
работ множества zS ; \ S R ?? , zS ? функция
общих затрат за отклонение суммарной величины
используемых ресурсов от R ?? .
Ограничениями в задаче являются следующие условия:
Данный алгоритм решения задачи (1) ? (4) не может
быть использован при оперативном управлении
работой ручного участка, так как имеет длительное
время выполнения [1]. Используя этот алгоритм
при планировании работы ручного участка, удается
получить на каждый плановый промежуток времени ? ?? оптимальный объём ресурсов R '?? (бригад
l
рабочих), перечень работ Aij по формированию
l
сборных пачек nij и последовательность их выдачи
для формирования маршрутов отправки. Необходимо так распределить выполнение этих работ
между исполнителями, чтобы свести к минимуму
несвоевременность выдачи сборных пачек для
формирования маршрутов, т.е. минимизировать
функцию:
F c min ¦ D lij[t * (n lij ) t k (n lij )]
,
(6)
l ,i, j
где t * §Ё n l ·ё ? фактическое время выдачи сборной
© ij №
l
пачки nij .
Рассмотрим более подробно особенности данной
l
задачи. Каждая сборная пачка nij характеризуется
контрольным сроком окончания t ? §Ё n l ·ё форми© ij №
рования и моментом готовности к формированию
t ? §Ё nijl ·ё , который определяется моментом
© №
§
·
?
§
t Ё nijl ·ё t ? Ё n l * ё фактического поступления на
© №
© z №
ручной участок последней из стандартных пачек
n l * , из которых должна быть сформирована сборz
ная пачка. Так как формирование сборных пачек
и передача их на формирование маршрутов отправl
ки происходит в порядке следования заявок ?ij h ,
то для каждой пачки n l * имеется набор сборных
z
l
l
пачек nij с возрастающим резервом времени d ij :
l
* zS Aij ;
(2)
S 1
a li1 d a li 2 d ... d a lij d ...; a lij t k ( ? lij ) t ? ( ? lij ) . (7)
i Џ I [J i const | ai const | J i { 0 mod S | ni { 0 mod S ];
Время формирования каждой из сборных пачек
(3)
l
l
является линейной функцией ее размера: J ij qnij
Єt J i
є
i Џ I t Џ 1,2,..., m « z ? z ‡ » .
(4) ( q ? коэффициент, учитывающий размерность
«? t
»
¬
ј
l
сборной пачки). Так как размер сборной пачки nij
Алгоритм решения задачи (1)-(4) состоит [1] в
l
определении таблицы оптимальных стратегий z ?
известен заранее, то величины W ij известны перед
путём вычисления по рекуррентному соотношению:
началом решения задачи. Каждая из сборных пачек
§
·
O? H?
min { ¦ D i ai ti готова к формированию в момент t ? Ё n i * ё прихода
z №
z ? pl iЏ z 'pl?
©
l
стандартной пачки n * , т. е. одновременно готовы
¦ D i ai E | V ¦ a i | z
к формированию только те из сборных пачек,
iЏ?? pl
iЏ z ? pl
l
которые входят в данную стандартную пачку n * :
z
+ O? 1 H ? 1 }.
(5)
­
Ѕ
N l ®n1l , n 2l ,..., n l * ѕ, z * 1, Z ? ;
z ї
Ї
По таблице оптимальных стратегий определяется
наилучший вариант последовательности выполне(8)
¦ nl *
¦ §Ё ?ijl h ·ё,
ния работ с точки зрения минимизации функции
№
©
z
*
,
i
Џ
I
j
Џ
J
z ЏZ ?
(1) при заданном начальном соотношении H1 .
60
РИ, 2000, № 2
где N l ? множество стандартных пачек, из которых
состоит тираж издания, отправляемый для формиl
рования сборных пачек; ?ij ? заявка на формирование сборной пачки; h ? ее минимально-допустимый размер.
Основными ограничениями задачи являются:
l
1) сборная пачка формируется W ij времени без
перерыва:
(9)
t * (n lij ) t P (nlij ) W lij ,
l · ? момент начала формирования
здесь t P §Ё nij
ё
© №
сборной пачки;
2) каждая сборная пачка готова к формированию в
момент прихода её соответствующей стандартной
пачки:
(10)
t P (n lij ) t t ? (n lZ *); n lij Џ n lZ * ;
3) сборные пачки формируются последовательно
друг за другом:
t * (n lij ) d t P (n lij 1) ;
(11)
4) исполнитель не может одновременно выполнять
более чем одну операцию по формированию сборной пачки:
l , ? ( l1 ) d
{(i, j , l ) : {i1 , j1 , l1 ) : k l1
i1 j1 k ij t n i1 j1
(12)
d t ? (n lij ) d t * (n l1 )} z ‡} ‡ .
i1 j1
Анализ характеристик технологического процесса
формирования сборных пачек на ручном участке
l
показывает, что при D ij const минимум функционала (6) достигается путем минимизации среднего
временного смещения L . Функционал (6) может
быть представлен в следующем виде:
F c D lij min ¦ [t * ( ? lij ) t ? ( ? lij )]
.
(13)
i, j , l
Сумму в выражении (13) представим в виде:
¦ [t * ( ? lij ) t ? ( ? lij )] N ( ? lij h) u
l , i, j
¦ [t * ( ? lij ) t ? ( ? lij )]
l , i, j
u
N ( ? lij h) L,
N ( ? lij h)
l
где N §Ё ?ij h ·ё ? общее количество сборных пачек.
©
№
F c D lij N ( ? lij h) min L .
Тогда
(14)
Следовательно, (6)-(12) сводится к задаче составления оптимального расписания при формировании
сборных пачек на R '?? рабочих местах. При этом,
согласно изложенному, оптимальным будет то из
расписаний, для которого минимально средневременное смещение L .
Правила составления подобных расписаний для
параллельно работающих исполнителей с одинаковой и разной производительностью получены в [3].
Однако они могут быть использованы при
t ? §Ё nijl ·ё 0 . Результаты составления расписаний
© №
РИ, 2000, № 2
?§ l ·
при t Ё nij ё z 0 , приведенные в [4,5], позволяют
© №
предложить для решения поставленной задачи следующий алгоритм, основанный на использовании
ряда теорем теории расписаний [4]:
1) определяется ресурс времени работы исполнитеR c py
?
p
¦ t r ; r py 1, R ?? ; 2) для минимилей: t
??
r py 1
зации L согласно теореме 3.3 [4] все сборные пачки
l
nij
сортируются в соответствии с возрастанием
плановых сроков;3) в результате сортировки воз? § l · ? § l 1 ·
можно следующее: а ? равенство t Ё ?ij ё t Ё ?ij ё
© №
©
№
плановых сроков готовности сборных пачек. В этом
случае, если Pl Pl 1 , то первой формируется
l
сборная пачка с меньшим J ij . Если же Pl z Pl 1 ,
то первой формируется сборная пачка с большим
? § l · ? § l 1 ·
приоритетом; б ? если t Ё ?ij ё t Ё ?ij ё , но
©
№
© №
1
1
?
l
l
?
l
l
§
·
§
·
t Ё ?ij ё J ij ! t Ё ?ij ё J ij , то первой форми©
№
© №
руется сборная пачка с высшим приоритетом, а если
Pl Pl 1 , то первой формируется сборная пачка с
l
меньшим J ij ; 4) производится перераспределение
сборных пачек для участков расписания, где максимальное запаздывание формирования сборных
пачек равно нулю (согласно теореме 3.5 [4]); 5)
*§ l ·
производится совмещение моментов t Ё ?ij ё и
© №
t ? §Ё nijl ·ё ; 6) после распределения всех сборных
© №
пачек производится разбиение промежутка времеp p
p
ни t p на отрезки t1 , t 2 , ..., t ' .
R ??
В результате выполнения алгоритма производится
распределение множества работ по формированию
сборных пачек Al
Aijl между исполнителями
? l
согласно контрольным срокам t §Ё nij ·ё .
© №
Литература: 1. Щербак А.Ф., Левин Г.Л., Волчек Б.А. К
вопросу решения одного класса задач теории расписаний / Кибернетика, 1973. №5. С.126-127. 2. Черчмен У.,
Акоф Р., Арноф Л. Введение в исследование операций.
М.: Экономика, 1970. 208 с. 3. Бурдюк В.Я., Шкурба В.В.
Теория расписаний. Задачи и методы решения/ Кибернетика, 1971. №1. С.89-102. 4. Конвей Р.В., Максвелл
В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.
360 с. 5. Шкурба В.В. О задачах упорядочения/ Кибернетика, 1967. № 2. С. 68-73.
Поступила в редколлегию 10.04.2000
Рецензент: д-р техн. наук, проф. Борячок М.Д.
Кузьменко Виктор Михайлович, канд. техн. наук, профессор университета, профессор каф. системотехники
ХТУРЭ. Научные интересы: математическое и имитационное моделирование технологических процессов
Адрес: Украина, 61166, Харьков, пр.Ленина 14, тел. 4093-06,19-76-36.
Ненько Леонид Федорович, директор дирекции обработки и перевозки почты УГППС ?УКРПОЧТА?. Научные
интересы: системы автоматизированного управления и
информационные технологии. Адрес: Украина, 04999,
Киев, ул. Петрозаводская, 2, тел. 220-06-74, 246-64-54.
61
Документ
Категория
Без категории
Просмотров
4
Размер файла
219 Кб
Теги
оптимальное, пачек, расписание, составление, экспедирование, задачи, издание, формирование, сборных
1/--страниц
Пожаловаться на содержимое документа