автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и оценка варианта планировки автоматической линии при машинном проектировании

ВВЕДЕНИЕ.

Глава I. СОСТОЯНИЕ ВОПРОСА'. ЦЕПЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ.

1.1. Автоматизация проектирования технологических систем и задачи размещения.

1.2. Задачи размещения и планировки

1.3. Математические методы решения задач размещения.

1.4. Цель и задачи исследования .

Глава 2". ИССЛЕДОВАНИЕ ОБЩЕЙ ЗАДАЧИ ПРОЕКТИРОВАНИЯ ' ПЛАНИРОВКИ ПОТОЧНЫХ ТЕХНОЛОГИЧЕСКИХ СИСТЕМ

2.1. Планировка поточных технологических систем как объект.,автоматизированного проектирования

2.2. Выявление параметров планировки и их отображение на структуру приведенных затрат.

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

2.4. Выводы.

Глава 3. РАЗРАБОТКА МЕТОДА ПРОЕКТИРОВАНИЯ

ПЛАНИРОВКИ ТЕХНОЛОГИЧЕСКОГО УЧАСТКА

3.1."Формализация, основных понятий и постановка задачи проектирования участка.

3.2. Анализ- модели проектирования планировки участка . V

3.3. Метод'решения задач проектирования планировки участка.Д 3.4. Оценка эффективности метода проектирования планировки участка

3.5. Выводы .• . Д

Глава 4. РАЗРАБОТКА МЕТОДА ПРОЕКТИРОВАНИЯ ПЛАНИРОВКИ поточных технолошческих систем

4.1. -Форг/ализация основных понятий и постановка задачи размещения участков поточных технологических систем

4.2. Анализ модели . . .'.

4.3. Задача о рядной планировке . . . .ч . . . . . . 149

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

4.5. Двухуровневый алгоритм размещения участков.

4.6. Выводы.•

Глава .5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ДВУХЭТАПНОГО МЕТОДА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ПЛАНИРОВКИ • ■ • ПОТОЧНЫХ ТЕХНОЛОГИЧЕСКИХ СИСТЕМ

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

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

5.3. Подсистема проектирования планировки поточных технологических'систем.

5.4. Выводы.

ВЫВОДЫ.

Основными направлениями экономического и социального развития СССР на 1981-1985 годы и на период до 1990 года было предусмотрено улучшение'структуры парка металлообрабатывающего оборудования в том числе "и за счет увеличения выпуска автоматических линий и комплексов, "существенно сократить сроки создания и освоения новой техники расширить автоматизацию проектно-конструктор-ских- работ с применением электронно-вычислительной техники".

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

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

1) был проведен обзор задач размещения и методов их решения;

2) сформулированы в содержательных терминах задачи, решаемые при проектировании планировки поточных Технологических систем;

3) осуществлена" формализация этих задач: а) разработана математическая модель планировки; б) произведен анализ критериев оценки качества проектирования планировки; в) произведен анализ структуры задач с целью их декомпозиции;

4) для формально поставленных задач: а) разработана методика их решения; б) предложенная методика реализована в эффективных вычислительных процедурах.

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

Новизна ее решения состоит в следующем:

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

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

Практическая ценность работы состоит в разработке и внедрении метода формального проектирования планировки, разработанных ■ \ на его основе алгоритмов и программ, входящих в4 подсистему проектпрования планировки. Применение подсистемы позволяет свести к минимуму участие человека в процессе проектирования планировки.

В результате выполненных исследований и разработок автор защищает:

- способ формального предетавления планировки поточных технологических систем;

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

- алгоритмы и программы для проектирования планировки участков и размещения участков на отведенной площади.

Работа выполнена на кафедре "Автоматизированное проектирование и управление" Московского станкоинструментального института.

ВЫВОДЫ

В данной работе:

1. Выделен класс линейных технологических систем. Для них рекомендован процесс построения критерия оценки варианта планировки на основе приведенных затрат.

2. Обоснована возможность построения двухуровневого метода оптимального проектирования планировки по этому критерию.

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

4. Показано, что задача локальной планировки участков формулируется как задача распределения-размещения. Выявлены конструктивные ограничения, позволяющие свести ее к'задаче, разрешимой за полиномиальное время. Найден эффективный метод решения задачи планировки участков. .

5. Установлено, что эффективными методами решения задачи размещения участков на отведенной площади являются: а) метод с ограничениями на структуру рассматриваемых вариантов -сведение к полиномиальноразрешимому случаю; б) двухэтапный метод, разработанный на основе "поиска в глубину" на дереве вариантов с использованием метода отсечений для ограничения перебора и эвристической оценочной функции для его направления.

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

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

1. Абрайтис Л.Б., Шейнаускас Р.И.-, Жилевичюс В.А. .

2. Автоматизация проектирования ЗВМ. М., Сов.радио, 1978.-269с.

3. Башта Г.М. Гидропривод и гидропневмоавтоматика. М., Ыашиностроение, 1372.320с.

4. Винарский В.Я., Пономаренко Л.Д., Турчанов Н.Н. Поверхности уровня Ф-функции и сумма Минковского. Харьков, Маш АН УССР Препринт 174, 1982.-33с.

5. Вороничев Н.М., Тартаковский Н.Э., Генин В.Б. Автоматическиелинии из агрегатных станков. М., Машиностроение, 1979.-488с.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., Мир, 1982.-416с.

7. Егоров В.А. Системная автоматизация проектирования приборостроительных предприятий. Л., Машиностроение4, 1978.-312с.

8. Ещенко В.Г. О реализации наязыке высокого уровня математического обеспечения пакета программ РАЗМЕЩЕН!®.

9. Прогршлммрование, $ 2, 1983.- 8. -Исследование операций, т.2. Модели и применения. (Под ред. Моудера Дж., Элмаграби С.) М., Мир, 1981.-678с.

10. Кристофидес Н. Теория графов. Алгоритмический подход. М., Мир, 1978 .-432с.

11. Кузнецов М.М., Волчкевич Л.й.', Замчалов 1С.П. Автоматизация производственных процессов. (Под ред. Шаумяна Г.А.) М., Высшая школа, 1978.-432с. • ■

12. Лисяк В.В., Молдавский Л.И. Алгоритм автоматизированного синтеза геометрии. БИС. Электронная техника. Серия 3:

13. Микроэлектроника, Вып.1, 1983.

14. Майника Э. Алгоритмы.оптимизации на сетях и графах. М.,Мир, 1981.- 323с.

15. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М., Наука, 1974.-303с.

16. Михалевич B.C., Волкович B.JI. Вычислительные методы исследования и проектирования сложных систем. М., Наука, IS82.-268C.

17. Михалевич B.C., Шор Н.З. и др. Вычислительные методы выбора оптимальных'проектных решений. Киев, Наукова Думка, 1977.-178с.16.-Моисеев H.H. Математические задачи системного анализа. М., Наука, 1981487с.

18. Моисеев H.H., Хачатуров В.Р. Автоматизация проектирования освоения новых нефтедобывающих районов. В кн. "Автоматизированные системы проектирования". М., ВЦ АН-СССР, 1977

19. Нильсон Н. Искусственный интеллект. Методы поиска решений. М., Мир, 1973.- 270с.

20. Норенков И.П. Введение в автоматизированное проектирование технических з^стройств и систем. М., Высшая школа, 1980.- 311с.

21. Норенков И.П., Маничев В.П. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М., Высшая школа, 1983. 272с.

22. Операционная система ОС-PB: Руководство программиста.

23. В 6-ти томах. Калинин, Научно-производственное объединение "Центрпрограммсистем", I981-1982.

24. Петренко A.M.,. Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М., Сов.радио, 1979.- 256с.

25. Попов Д.Р., Митрофанов В.Г. Алгоритм планировки станочных участков при машинном проектировании. В.сб.: Системы управления станками и автоматические линии. М., ВЗМИ, т.16, с.115-121, 1983. .

26. Попов Д.Р. Автоматизация проектирования планировки участков, ' М., МГЦНТИ, вып. В 422-84, 1984.-4с.

27. Попов Д.Р. Проектирование размещения участков автоматических линий на ЭВМ. М., МГЦНТИ, вып. 423-84, 1984.-4с.

28. Проектирование монтажных плат на ЭВМ. (под ред. Морозова -К.К.) М., Сов.радио, 1979. 223с.

29. Рейнгольд Э., Нивергельдт Ю., Део Н. Комбинаторные алгоритмы. М., Мир, 1980, 476с.

30. Стоян 1С.Г. Об одном обобщении функции плотного размещения. ДАН УССР, В 8, 1980.

31. Стоян Ю.Г. Об одном отображении комбинаторных множеств в Евклидово пространство. Харьков, ИМаш АН УССР,^Препринт tè 173, 1982. 33с.

32. Стоян Ю.Г. Основная задача геометрическогочпроектирования. Харьков, ИМаш АН УССР, Препринт tè 181, 1982.- 36с.

33. Стоян Ю.Г., Винарский В.Я. Алгебро-топологические свойства ^-объектов. Харьков, ИМаш АН УССР, Препринт.'Ж66, 1981.-34с.

34. Стоян Ю.Г., Гиль Н. Методы и алгоритмы размещения плоских геометрических объектов. Киев, НауковаДумка, 1976.- 247с.

35. Стоян Ю.Г., Панасенко А.А. Периодическое размещение геометрических объектов. Киев, Наукова Думка, 1978. 175с.

36. Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев, Наукова Думка, 1980. 206с.

37. Стояк Ю.Г., Яковлев C.B. Исследование сходимости метода•'■•-"" "сужаждахоя окрестностей. Харьков, ИМаш АН УССР, Препринт ' ' 1$ 168, 1981.- 43с.

38. Тищенко Н.М. Введение в проектирование сложных систем автоматики. М., Высшая школа, 1976. 305 с.

39. Трубин В.А. Два класса задач размещения на древовидных сетях. Кибернетика $ 4, 1983.

40. Тютин А.А. Улучшенный алгоритм размещения интегральных схем на'плате. Ж АН УССР, Препринт № 72-8, 1972.

41. Цветков В.Д. Системно-структурное моделирование и автоматизация проектирования технологических процессов. Минск, Машиностроение, 1979. 261 с.

42. Янев Н.И. 0 решении простой задачи размещения. Журнал выч. матем. и мат. физики, т.21, В 3, 1981.

43. Carrie A.S. , Moore I.M. Impact of list processors ard graph, theory on use of computers for solving facilities design problem. Proceedings of the 4th Intern. Conf. on Productions Research, Amsterdam, 1978.

44. Chalmet L.G., Francis R.L., Kolen A. Finding Efficient Solutions .for Rectilinear Distance Location Problems Efficiently. European Iourn. of Oper. Research, N6,1981.

45. Chandrasekaran R., Tamir A.'Polinomially Bounded Algorithms for Locating p-Centers on a Tree., Math. Programming, v.22, pp.304-315, 1982. .

46. Christofides N. , Galliani G., Stefanini L. An algorithm for the Maximal Planar Graph Problem based on Lagrangean Relaxation. Math. Programming, H5, 1981.

47. Christofides N., Whitlock C. An Algorithm for.Two-Dimensional Cutting Problems. Operations Research, v.25, N1, 1977.

48. Cinar U. Facilities Planning: A systems Analysis and Space Allocation Approach.-in: Spartial Synthesis in Computer -Aid Building Design (ed.' Eastman C.M.), Wiley, N.Y.,1975«

49. Cooper L. Solution of generalized location eguilibrium models, journal of Regional Science, v.7,- N1, 1967*

50. Dawson R. Computerised space management helps containoffice plan costs. Bank systems an^d egiupment, N2,1982..

51. Eilon S., Deziel D.P. Siting a distribution center. Management Science, v.12, N6, 1966.

52. Facilities Relative Allocation Technigue (FRAT). Intern. Journ. Prod. Research, v.11, pp.185-194, 1973.

53. Fonlds L.R.' Technigues for facilities layout: decidingwich Pairs of activities Should be adjacent. Manag. Sci., . V.29, N12, 1983. ' ■

54. Foulds L.R., Robinson D.F. Graph theoretic'heuristies for Plant Layout Problem. Int.ffourn. of Prod. Res., v.16, pp. 27-37, 1978.

55. Francis R., White A. Facility layout and location. Prentice Hall, Englewood Cliffs, New Serseg, 1974.

56. Galle P. An algorithm for Exhaustive Generation of Building Floor-Plans. CAD, v.24, pp.813-824, 1981.

57. Hakimi S.L. Optimum distribution of Switching Centers in Communication Network and Some Related Graph Theoretic

58. Problems. Oper.Re's., v.15, N4, 1965.

59. Hakimi S.L., Kariv 0. An Algorithmic Approach to Network Location Problems, I,II,SIM lournal of Applied Math., v.37, pp.513-538, 539-560, 1979.

60. Hakimi S.L., Schmeichel E.F., Pierce I.G. On p-Centers in Networks. Transportation Science, v.12, N1, '1978.

61. Handler G.Y., Mirchandani P.B. Location on Networks: Theory and Algorithms, The MIT Press, Caribrige, Massachusets,1979.

62. Hitchings g.g. Analogue Technigues for Optimal location of a main facility inrelation to ancillary facilities. Intern.

63. Uourn. of Production Research, v.7, N3, -1967.

64. Hitchings g.g., Cottam m. An efficient.heuristic procedure for Solving the layont design problem. Omega', ~v.N1, "1976.64.. Hsu W.L., Nemhauser G.L. Ease and hard bottleneck location problems. Discrete Appl. Math., N1, 1979.

65. Johnson R.-V. Spacecraft for Multi-Floor Layont Planning. Management Science, v.28, N4, 1982.

66. Katz I.N., Cooper L. Facility Location in the presence of Forbidden Regions.' Report OREM 79006, 79011, Southern Methodist University, 1979.

67. Kuenne R.E., Soland R.M. The multisource Weber Probiem: Exact Solutions by Branch and. Bound. IDA Economic Papers, H.Williams (ed.), Program Analysis Division, Arlington, Virginia, 1971.

68. Larson R.S., Sadig G. Facility Locations with Barriers to travel. Operations Research, v.31, N4.

69. Leesley M.E. (ed.). Computer aided process plant design. Gulf Publishing Company, Houston, Texas, 1982. •

70. Mc Giruiis L.F, . A. Survey of recent results for a class of facilities location problems. AIIE Transactions, v«9j N1 1' 1977.

71. Moon D,, Chaudhry S.S. An analysis of network location problems with distance constraints. Manag. Sei., v.30, N"3, 1934.

72. Muther R. Systematic layout planning. Caimers,Boston,1973. 73« Sahni S., Gonzalez T. P-complete Approximation Problems.

73. Jour. Assoc. Comp. Math., v.23,' N4, 1976,

74. Sherali A.D., Shetty C.M. The Rectilinear Distance Location-Allocation Problem.'.AHE Transactions, v.9, N2, 1977.

75. Shier D.R., Bearing P.M. Optimal locations for a Class of Nonlinear, Single-Facility Location Problems on a Network. Operations Research, v.31>.N2, 19S3.

76. Tansel B.C., Francis R.L., Lowe T.J. Location on Networks: A Survey. Management Science,, v.29, N4, pp.482-311, 1983.

77. Tansel B.C., Francis R.L., Lowe T.J., Chen M.L. Duality and Distance Constraints for. the Nonlinear p-Center Problem and Covering Problem on a Tree Network. Oper.Res., v.30, pp.725-744, 1982. .

78. Wang P.Y. Two algorithms for Constrained'Two-Dimensional Cutting Stock Problems. Operations Research, v.31> N3,1983. '