Модификации морфологического моделирования для задач пла нирования при позаказиой системе производства однотипной продукции
Рассмотрим модификацию метода морфологического ящика на упрощенном примере. Предположим, что цех получает задание на производство продук ции не в штуках, а в виде заказов, включающих изделия, одинаковые по трудоемкости изготовления, но имеющие определенные отличительные особенности (например, различную окраску, комплектацию и т.п.). Так может планироваться производство приборов разного рода, специаль ного оборудования, автомобилей для экспорта, специализированных интегральных элементов электронных устройств и т.д. Для простоты допустим, что речь пойдет о сборочном цехе и о про изводстве достаточно крупных изделий, объемы заказов которых исчис ляются в штуках. Пусть требуется выполнить следующие заказы: Z1 = 10, Z2 = 20, Z3 = = 30, Z4 = 40, Z5 = 50, Z6 - 60 (объемы заказов даны в условных едини цах; это могут быть либо изделия большого размера, либо объемы в тысячах штук и т.п.). Для их выполнения в цехе имеются три взаимоза меняемые сборочные линии, по которым заказы нужно распределить по возможности более равномерно, но в то же время не дробить заказы на части, так как это усложняет ведение документации и учет поставок про дукции заказчику. Эта задача может быть отнесена к классу задач загрузки оборудо вания. При постановке данной задачи с применением математического про граммирования целевая функция может, например, иметь следующий вид: I ф./-Х«//-^/ л min, (3) где Ф. - общий фонд времени работыу-го вида оборудования (в данном случае линий сборки) в плановом периоде; Л'. - количество изготавливаемых изделий /-го вида; а.. - трудоемкость изготовления одного изделия /-го вида нау-м виде оборудования. Таким образом, даже если не выполнять одно из требований задачи - не делить заказы на изделия, то и в этом случае задача не может быть представлена в форме наиболее исследованной и имеющей стандартное программное обеспечение задачи линейного программирования, раз ность в выражении (3) может менять знак (возможна либо недогрузка, либо перегрузка оборудования), т.е. целевая функция немонотонна и ее минимизация не имеет смысла. Разумеется, существуют подходы к ре шению задач в такой постановке. Однако применяемые приемы затруд няют понимание моделей и интерпретацию результатов на практике. Известны эвристические алгоритмы решения этой задачи. Напри мер, задаваясь Ф. и х. и зная (из нормативно-справочной информации) ^/.., вычисляют фактическую трудоемкость изготовления всех изделий Т., коэффициенты загрузки оборудования /i, его пропускной способности Г|, перегрузку и недогрузку оборудования Ал'^ -Ах., по значениям кото рых судят о необходимости изменения х-. Процедура повторяется до тех пор, пока не получены приемлемые значения +Ах. и -Ах.(рис. 2). В таком эвристическом алгоритме можно учесть больше факторов производственного процесса; например, при вычислении можно учесть коэффициенты сменности, износа и переналадки оборудования и т.п. Однако и этот алгоритм не позволяет выполнить одно из требова ний, содержащихся в условиях данной задачи, - не дробить заказы. Это требование можно выполнить, поставив задачу целочисленного про граммирования с булевыми переменными. Однако такая постановка в еще большей мере усложнит практическое использование модели. Можно предложить и другие эвристические алгоритмы: расположить заказы в порядке возрастания и соединять крайние или просуммировать объемы заказов и разделить на число линий сборки, а затем пытаться подобрать усредненный объем. 499 Ввод х.,Ф^.,а„ 1 ^г^/«(/^- Л=7./Ф. , = Ф./Т^. Хф/=^-'' 1 Дефицит ' -Дх,. = х,-Хф,. —"^ Резерв + Дх,. = Хф.-х. Выводг|, /7,-Ах^., + Лх^. Рис.2 Однако, во-первых, при большом числе заказов эти алгоритмы так же нереализуемы, а во-вторых, если в приводимом примере первый за каз имеет объем не 10, а 20 единиц, то сумма не делится на 3 без дробле ния не только заказов, но и изделий. Рассмотрим возможность применения для решения этой за дачи метода морфологического ящика*. Сформируем из заказов морфологическую матрицу - МЯ (табл. 1). Формировать МЯ будем не из векторов-строк, как в исходном варианте Ф. Цвикки, а из векторов-столбцов, что удобнее для ра ботников плановых подразделений (похоже на привычные для них таблицы планов загрузки производств, кварталов и т.п.). При формировании столбцов можно предложить какой-либо принцип объединения заказов в группы. Например, в одном из вариантов применения этого метода при формировании МЯ для распределения заказов по кварталам было предложено объединить заказы в группы с учетом заказчиков * Впервые задача была исследована и программно реализована студен тками И.Н. Фаенсон (на примере распределения заказов по кварталам) и Г.И. Корсуновой (на примере распределения заданий на выполнение проек тов в НПО). 500 и приоритетности выполнения их заказов, и получены следую щие группы: экспортные заказы, заказы для других отраслей и внутриотраслевые заказы. В рассматриваемой задаче заказы вначале объединим подряд в 2 группы: А = <Z1, Z2, Z3> яВ = <Z4, Z5, Z6> (табл. 1, a). Если приемлемое решение не будет получено, то МЯ можно перефор мировать, объединив заказы по-другому. На основе полученной матрицы-«ящика» можно, комбинируя элементы столбцов (по одному из каждого столбца), образовать возможные размещения заказов по линиям сборки (обозначен ным в МЯ L = <Л1, Л2, Л3>), из которых далее нужно сформи ровать требуемое решение или варианты решения по принципу, приведенному на рис. 1, в, т.е. решение должно состоять из трех размещений, отражающих загрузку всех трех линий сборки; при этом один и тот же заказ не может планироваться для выполне ния более чем на одной линии, и все заказы должны быть выпол нены и войти в решение. Идея исключения заказов выбранных вариантов иллюстрируется табл. 1, в. Т а б л и ц а 1 [~L Л1 Л2 ЛЗ А 1\ =20 22 = 20 Z3 = 30 В 74 = 40 1 75 = 50 76 = 60 1 ДО Л1 Л2 ЛЗ 7Ж1) 71 72 73 0Щ\) 20 20 30 ZBO) 74 75 76 OZBQ) \ 40 1 50 60 1 \Щ) Л! Л1 Л1 Л2 Л2 Л2 ЛЗ 1 ЛЗ 1 ЛЗ ZA(l) 1 1 1 2 2 2 3 3 3 ZBO) 4 5 6 4 5 6 4 5 6 S 60 70 80 60 70 80 70 80 90 Вариант решения 1 — + — — - + — — + 2 — + — — - + + 3 i — — + - + — — + Для автоматизации перебора вариантов размещений с повто рениями нужно образовать разные массивы для символьной и чис ловой информации, т.е. отделить массивы наименований заказов ZA и ZB, которые нужно хранить и представлять ЛПР в символь- 501 ном виде, и объемы заказов OZA и OZB (числа), и связать массивы ZA - OZA и ZB - OZB общими переменными (табл. 1, б). Для со кращения перебора можно также связать общей переменной с мас сивом L один из массивов заказов. Принципиальный алгоритм получения размещений с повто рениями приведен на рис. 3, а. Пользуясь этим алгоритмом, мож но получить область допустимых решений, т.е. возможных раз мещений заказов по линиям. Если эта область получается очень большой, то в алгоритм можно ввести ограничения по суммарному объему S заказов, выполняемых на одной линии SMIN и SMAX (рис. 3, 5), варьи руя которыми, можно расширять и сужать область допустимых решений. Далее применяют алгоритмы для исключения выбранных ва риантов на каждом очередном шаге (первоначально эти алгорит мы были названы алгоритмами «вычеркивания»), которые при ведены на рис. 3, <? и г. На практике крайне редко бывают ситуации, когда удается по лучить абсолютно одинаковую загрузку линий (или станков, квар талов и т.п.). Поэтому задача ставится как задача минимизации перегрузки или недогрузки оборудования, плановых периодов. При этом, как видно из табл. 1, в, может получиться несколь ко вариантов решения, которые в отношении первоначального количественного критерия (числа изделий) равноценны. Для уточнения решения можно ввести дополнительные крите рии - трудоемкость, объем реализуемой продукции или прибыль от ее реализации и т.п., с помощью которых можно ограничивать область допустимых решений аналогично рассмотренному. Кроме того, можно далее ввести качественные критерии. На пример, из двух равноценных вариантов с перегрузкой одной из линий можно выбрать вариант с перегрузкой линии, на которой производятся хорошо отработанные конструкции изделия, и, напротив, недогрузить линию, на которой производится вновь осваиваемое изделие. Аналогично при решении задачи загрузки плановых перио дов можно выбрать вариант, в котором недогружен летний квар тал, на который приходится наибольшее число отпусков, или учесть критерий пожелания приоритетного заказчика выполнить его заказ пораньше. 502 Ввод L, ZA, ZB, OZA, OZB, N Для / от 1 до Л/ с шагом 1 Для J от 1 до Л/ с шагом 1 S = OZA(I) + OZB(J) Вывод L(l), ZA(I), ZB(J), S Ввод L, ZA, ZB, OZA, OZB, N Ввод SMIN, SMAX Для / от 1 до Л/ с шагом 1 Ввод L, ZA, ZB, OZA, OZB, N Ввод Л1, 81 Для / от 1 до Л/ с шагом 1 Ввод L, ZA, ZB, OZA, OZB, N ввoцA^,в^.AZB2 Для / от 1 до Л/ с шагом 1 Для J от ^ до N с шагом 1 S = OZA(I) + OZB(J) Да Вывод Ц1), ZA(I), ZB(J), S Нет Рис.3 503 Таким образом, применяя морфологические! подход, получа ем человеко-машинную процедуру принятия решений, которая позволяет в интерактивном режиме выбирать варианты решения, последовательно уточнять критерии, а при необходимости - воз вратиться и переформировать МЯ. Отметим, что с помощью морфологического подхода факти чески получена методика постепенного ограничения области до пустимых решений. Иными словами, морфологический подход оказался методом активизации, который помогает ЛПР в поста новке задачи и организации поиска ее решения, т.е. в постепен ной формализации задачи. В математическом отношении рассмотренная процедура не является процедурой оптимизации. Ее можно квалифицировать как постепенно ограничиваемый перебор. В реальных условиях принципы постановки задачи и разра ботки алгоритмов сохраняются, но конкретизируются с учетом особенностей задач и условий производства. Особая необходи мость в использовании морфологического подхода возникает в условиях разнотипного производства.
Ви переглядаєте статтю (реферат): «Модификации морфологического моделирования для задач пла нирования при позаказиой системе производства однотипной продукции» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
