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

Введение

1. Модели и методы в системе планово-профилактического ремонта

1.1. Сущность ППР и практика планирования

1.2. Существующие модели и методы решения задач 9 планирования ППР

1.3. Применение методов теории расписаний

1.4. Программные комплексы, используемые при планировании 18 ППР

1.5. Выводы

2. Локально-оптимальные решения в задаче построения графика 23 планово-профилактических работ

2.1. Математическая постановка задачи и формы целевой 23 функции

2.2. Локально-оптимальные решения и критерий

1 -оптимальности

2.3. Оценки 1-оптимального графика

2.4. Алгоритм построения 1-оптимального графика

2.5. Возможности улучшения 1-оптимального графика. 53 Условия 2-оптимальности

2.6. Случай 171=2. Условия оптимальности

3. Численные эксперименты и оценки

3.1. Алгоритм А. Время работы и погрешность

3.2. Алгоритм В. Сравнительные оценки

3.3. Модификации алгоритмов. Оценки и выводы

4. Программный комплекс «График планово-профилактических 97 работ»

4.1. Основные задачи и структура комплекса

4.2. Анализ нормативов и структура данных

4.3. Описание алгоритмов и примеры расчетов 111 Заключение 121 Литература 123 Приложения

Предмет исследования, цели и задачи

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

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

В ремонтном производстве, в отличие от основного, увеличение «выпуска продукции» (объема ремонтов) не является главной задачей. Наоборот, чем меньше объем ремонтов при надлежащем качестве, тем экономичнее труд ремонтников. В то же время, от постановки ремонтного дела и, особенно, от организации профилактического обслуживания зависят рациональное использование оборудования, качество изготовляемой продукции, бесперебойность и ритмичность производства. Практика отечественных и зарубежных предприятий показывает, что увеличение удельного веса затрат на текущий ремонт и обслуживание оборудования до 30-40% позволяет резко сократить суммарные расходы на содержание и эксплуатацию оборудования [37, 41]. Большие издержки производства из-за отказов и простоев оборудования, брака и сверхурочных часов, вызванных его неисправностью, показали, что совершенствование организации ремонта и обслуживания оборудования может дать значительные экономические выгоды. По мнению администрации предприятий компании Ford Motors «ремонт стал большим бизнесом, в котором заключена возможность получения больших прибылей» [10].

В машиностроении и металлообработке ремонтом производственного оборудования и изготовлением запасных частей занято свыше 19% всех рабочих. В ремонтных службах находится 25% всего парка металлорежущих станков, имеющихся в стране. Производительность труда рабочих ремонтных служб в 4-5 раз ниже производительности труда рабочих основного производства [41]. Ежегодно более 10-12% оборудования подвергается капитальному ремонту, 2025% - среднему и 90-100% - малому. На ряде предприятий расходы на ремонт и содержание оборудования составляют 6-8% себестоимости выпускаемой продукции. За весь срок службы для отдельных видов оборудования расходы на них в несколько раз превышают их первоначальную стоимость [81].

В результате возросшей сложности и точности оборудования, повышения уровня механизации производственных процессов увеличивается численность ремонтных рабочих с более высокой квалификацией (средний разряд рабочих ремонтных служб выше, чем разряд производственных рабочих на 13-16% [41]), что предполагает и более высокую оплату труда. В США большинство ремонтных рабочих оплачивается по ставкам на 20-25% выше средних ставок, применяющихся для станочников в основном производстве [10]. Неэффективная организация ремонтов, содержание персонала «про запас» резко снижает зарплату ремонтных рабочих (в России она ниже заработной платы рабочих основного производства на 18-30% [41]).

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

По подсчетам Международного института эксплуатации и ремонта в американском машиностроении на каждые 10 производственных рабочих приходится один ремонтник. В нашей стране это соотношение - 5:1 [41]. Существенная разница говорит о необходимости и возможности оптимизации численности ремонтного персонала на предприятиях, что в отечественной практике планирования ремонтных работ (составления планов-графиков) не наблюдается [37].

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

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

Цель диссертационного исследования - разработка эффективных методов составления графика планово-профилактических работ и оптимизации численности ремонтных служб. Здесь математическая оптимальность по какому-либо критерию не является определяющей. Специалист предприятия хочет иметь возможности целенаправленного улучшения графиков и их «визуальной» оценки для принятия решения. В то же время, критерии могут быть формализованы математически, и на этом основании предложены алгоритмы таких улучшений. Такой подход в контексте данной работы назван практической оптимизацией1.

С этой целью в работе решаются следующие задачи:

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

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

1 Термин «практическая оптимизация» введен в обиход авторами монографии [20] (оригинальное издание - Лондон, 1981) и включает в себя различные аспекты, связанные с выбором ограничений, целевой функции оптимизационной задачи и алгоритма ее решения. Более подробно эти вопросы обсуждаются ниже при обосновании выбора математической модели. практическим потребностям, аналитическая оценка их погрешности и сложности.

3. Тестирование алгоритмов на больших массивах специальным образом сгенерированных исходных данных.

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

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

В заключении перечислены основные результаты и выводы работы.

Часть материала, носящего иллюстративный характер, вынесена в приложения.

Нумерация формул внутри глав двойная - (номер параграфа.номер формулы). При ссылках на формулу другой главы впереди добавляется номер главы. Таблицы, рисунки и диаграммы нумеруются по порядку в пределах всей главы.

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

Основные результаты, выносимые на защиту

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

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

Заключение

Подведем кратко итоги работы.

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

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

С использованием полученных аналитических результатов предложены алгоритмы (названные алгоритмами А к В) нахождения 1-й 2-оптимальных решений. Даны оценки сложности этих алгоритмов.

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

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

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

1. Акбердина Р.А. Система экономики и планирования ремонтного производства на машиностроительных предприятиях. - Свердловск: Изд-во Урал, ун-та, 1990. - 85 с.

2. Алексеев А.О., Алексеев О.Г., Кулагин О.А. Экспериментальная оценка эффективности алгоритмов решения задачи М коммивояжеров //Экономика и математические методы. 1993. - № 3. - С.496-503.

3. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1984. - 310 с.

4. Бабаев Ф.Б. Повышение эффективности производства на основе внедрения оптимизационных задач АСУ //Машиностроитель. 1994. - N 11-12. -С.18-20.

5. Бабицкая Ф.С., Ковалев М.М., Федулов JI.B. Оптимизация календарных планов ремонта горных машин //Вопросы математического обеспечения в автоматизированных системах. Минск: НИИЭМП при Госплане БССР, 1979.- С.91-98.

6. Бакенрот В.Ю., Чефранов А.Г. Эффективность приближенных алгоритмов распределения программ в однородной вычислительной системе //Техническая кибернетика. 1985. - № 4. - С. 135-148.

7. Бекларян А.А., Борисова С.В. Об одной динамической модели замещения производственных мощностей //Экономика и математические методы. -2002. — № 3. — С.73-93.

8. Билецкий О.Б. Комбинаторный метод оптимизации расписаний и его реализация //Механизация и автоматизация управления. 1990. - № 2. - С.8-12.

9. Бондаренко В.А. О перестановочных расписаниях //Кибернетика. 1990. -№ 1. - С.81-84.

10. Борисов Ю.С. Организация ремонта и технического обслуживания оборудования. М.: Машиностроение, 1978. - 245 с.

11. Бурков В.Н., Дзюбко С.И., Ягупов А.А. Эффективный алгоритм решения одного частного случая обобщенной задачи «о камнях» //Автоматика и телемеханика. 1995. - № 7. -С.124-130.

12. Бэр К., Гольштейн Е.Г., Соколов Н.А. Метод отыскания седловой точки -функции, область определения которой содержится в многограннике //Экономика и математические методы. 2001. - № 3. - С.97-106.

13. Бэр К., Гольштейн Е.Г., Соколов Н.А. Об использовании метода уровней для минимизации выпуклых функций, не все значения которых конечны //Экономика и математические методы. 2001. - № 3. - С.97-106.

14. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (обзор) //Управляемые системы. 1984. - № 25. - С. 17-37.

15. Ван дер Варден Б.Л. Алгебра/ Под ред. Ю.И.Мерзлякова. М.: Наука, 1976. - 648 с.

16. Варакин А.С., Панишев А.В. Верхняя оценка длины расписания в двухуровневой многопроцессорной системе //Кибернетика. 1990. - № 6. -С.113-116.

17. Васильев Ф.П. Лекции по методам решения экстремальных задач. М.: Изд-во МГУ, 1974. - 374 с.

18. Вахакия Н.Н. Распределение заданий для параллельных машин с разным быстродействием //Автоматика и телемеханика. 1995. - № 2. -С.155-163.

19. Вороненко В.П., Забиякин С.В. Оптимизация грузопотока в механообраба-тывающих производствах //Автоматизация и современные технологии. -1994,-№ 8.-С. 16-19.

20. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. -509 с.

21. Гимади Э.Х., Залюбовский А.А. Асимптотически точный подход к решению одномерной задачи упаковки в контейнеры //Управляемые системы. -1984. № 25. - С.48-57.

22. Гихман И.И., Скороход А.В., Ядренко М.И. Теория вероятностей и математическая статистика. Киев: Вища школа, 1979. - 408 с.

23. Гольштейн Е.Г., Соколов Н.А. Новый метод решения многопродуктовой транспортной задачи //Экономика и математические методы. 1995. - № 2. - С.128-137.

24. Гордон B.C. Параллельные алгоритмы решения задач теории расписаний //Автоматика и телемеханика. 1992. - № 5. - С.97-106.

25. Гроппен В.О. Модели и алгоритмы минимизации стоимости решения некоторых задач на однородных многопроцессорных вычислительных комплексах //Автоматика и телемеханика. 1994. - № 11. - С. 136-142.

26. Грунина Г.С., Деменков Н.П. Решение многокритериальных задач оптимизации и принятия решений в нечеткой постановке //Информационные технологии. 1998.-№ 1. - С.13-19.

27. Долгий Ю.Ф., Близоруков М.Г. Динамические системы в экономике с дискретным временем //Экономика и математические методы. 2002. - № 3. -С.94-107.

28. Донской М.В., Иванов В.Г. Программные средства построения расписаний //Кибернетика. 1988. -№ 2. - С.112-114.

29. Единая система планово-предупредительного ремонта и рациональной эксплуатации технологического оборудования машиностроительных предприятий. М.: Машиностроение, 1967. - 132 с.

30. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. Москва: Наука, 1981. -208 с.

31. Емец О.А. Комбинаторная модель и приближенный метод с априорной оценкой решения оптимизационной задачи размещения разноцветных прямоугольников //Экономика и математические методы. 1993. - № 2. -С.294-304.

32. Емец О.А., Емец Е.М. Отсечения в линейных частично комбинаторных задачах оптимизации на перестановках //Экономика и математические методы. -2001. -№ 1. -С. 118-121.

33. Ершов Е.Б. Распространение коэффициента детерминации на общий случай линейной регрессии, оцениваемой с помощью различных версий метода наименьших квадратов //Экономика и математические методы. -2000. № 4. - С.102-117.

34. Жаргал Д., Батбаатар Н. О комбинированном алгоритме решения одной • задачи размещения //Экономика и математические методы. 1993. - № 3. -С.491-496.

35. Зак Ю.А. Оптимальное распределение технологических операций на сборочном конвейере //Кибернетика. 1990. -№ 4. - С.45-55.

36. Заславский А.А., Лебедев С.С. Использование специального метода ветвей и границ для решения целочисленной обобщенной транспортной задачи //Экономика и математические методы. 1995. - № 2. - С.137-142.

37. Ивуть Р.Б. Новые формы в организации и управлении ремонтным производством в США. Мн.: БелНИИНТИ, 1989.-48 с.

38. Ивуть Р.Б. Совершенствование управления ремонтным производством на предприятиях машиностроения /Под ред. Я.А.Гольбина.-Минск: Навука и тэхшка, 1991.-248 с.

39. Иозайтис B.C., Львов Ю.А. Экономико-математическое моделирование производственных систем. М.: Высшая школа, 1991. - 273 с.

40. Калачев В.Н., Кривоножко В.Е., Немчинов Б.В. Задачи планирования в гибких производственных системах //Автоматика и телемеханика. 1995. - № 6. - С.155-164.

41. Климов А.Н., Попова Л.Г. Организация ремонта производственного оборудования машиностроительных предприятий. Л.: Машиностроение, Ле-нингр. отделение, 1988. - 149 с.

42. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, Главная редакция физико-математической литературы, 1968. -496 с.

43. Компьютер и задачи выбора /Под ред. Журавлева Ю.И. М.: Наука, 1989. -208 с.

44. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздаг, 1988. - 480 с.

45. Лебедев С.С. Модификация метода Бендерса частично целочисленного линейного программирования //Экономика и математические методы. -1994. -№ 2. С.107-127.

46. Лебедева Т.Т., Сергиенко И.В., Солтан В.П. Об условиях совпадения локального и глобального минимумов в задачах дискретной оптимизации //Докл. АН СССР. -1985. 283, №2. - С. 287-289.

47. Мерензон М.Н. Алгоритм динамического программирования составления оптимального расписания для неоднородной многопроцессорной системы //Техническая кибернетика. 1986. -№ 1. - С. 17-20.

48. Методы оптимизации в экономико-математическом моделировании. М.: Наука, 1991.-394 с.

49. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации. -М.: Наука, 1983.-208 с.

50. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы. -М.: Наука, 1986.-210 с.

51. Норенков И.П. Генетические методы структурного синтеза проектных решений //Информационные технологии. 1998. - № 1. - С.9-13.

52. Нормы межремонтных периодов, структуры ремонтных циклов и содержание работ по видам ремонта машинного оборудования предприятий нефтеперерабатывающей и нефтехимической промышленности. Волгоград: ВНИКТИнефтехимоборудование, 1987. - 81 с.

53. Обзор. Сер. Автоматизированные системы проектирования и управления //Техническая кибернетика. 1986, вып.1. - 61 с.

54. Оптимизация планов производства /Лычагин М.В., Маркова В.Д., Миро-носецкий Н.Б. и др. Новосибирск: Наука, 1987. - 195 с.

55. Отраслевая система технического обслуживания и ремонта технологического и подъемно-транспортного оборудования. РД5.СУА.003.85. В 3-х книгах. - Ленинград, 1986.

56. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.-М.: Мир, 1985.-410 с.

57. Положение о планово-предупредительном ремонте технологического оборудования предприятий нефтеперерабатывающей и нефтехимической промышленности. Волгоград, 1977. - 187 с.

58. Попова Л.Г., Тюленев Б.А. Экономико-математические методы и вычислительная техника в ремонтном производстве //Машиностроитель. 1981. -N 1. - С.45-46.

59. Программный комплекс по учету и планированию показателей технического и ремонтного обслуживания оборудования энергопредприятий. -Инф. листок № 150-98. Кировский ЦНТИ, 1998. - 2 с.

60. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

61. Руднев Ю.П. Метод решения одной задачи календарного планирования с дискретным временем //Кибернетика. 1984. - № 5. - С.89-94.

62. Руководство по комплексной системе автоматизации управления предприятием «Галактика». Корпорация «Галактика», 2000. -С.45-47.

63. Сборник нормативов на ремонт оборудования предприятий промышленности и транспорта Главнижневолжскстроя. (Для заводов железобетонных изделий, деревообрабатывающих предприятий, ремонтно-механических заводов и мастерских). Волгоград, 1974. - 175 с.

64. Севостьянов С.П. Алгоритм с оценкой для задачи с маршрутами деталей произвольного вида и альтернативными исполнителями //Кибернетика. -1986. № 6. - С.74-79.

65. Седова С.В., Лебедев С.С. Новый алгоритм метода узловых векторов целочисленного программирования //Экономика и математические методы. -2002.-№ 1,-С. 121-132.

66. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988.-470 с.

67. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980. - 216 с.

68. Ситникова О.Д. Задача теории расписаний в многостадийной системе с параллельными приборами //Кибернетика. 1990. - № 6. - С. 114-116.

69. Старр М. Управление производством. М.: Прогресс, 1968. -543 с.

70. Сухарев А .Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, Главная редакция физико-математической литературы, 1986. -328 с.

71. Танаев B.C., Гордон B.C., Шафранский Я.Н. Теория расписаний. Одностадийные системы. М.: Наука, 1984. - 381 с.

72. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука,1975. - 256 с.

73. Теория расписаний и вычислительные машины: Пер. с англ. /Под ред. Э.Г.Коффмана. -М.: Наука, 1984. 334 с.

74. Терехов А.И. Многокритериальные методы планирования крупномасштабных кадровых систем (обзор) //Экономика и математические методы. 1995. - № 4. - С.139-152.

75. Тимковский В.Г. Дискретная математика в мире станков и деталей. Введение в математическое моделирование задач дискретного производства. -М.: Наука, 1992.- 144 с.

76. Тимковский В.Г. К сложности составления расписания произвольной системы //Техническая кибернетика. 1985. - № 3. - С. 102-109.

77. Фейгин Л.И. Оценка величины горизонта планирования при нечетких длительностях операций //Техническая кибернетика. 1986. -№ 3. - С.23-27.

78. Финкелыдтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

79. Чефранов А.Г., Бакенрот В.Ю. Об эффективности двух классов алгоритмов оперативного планирования в многопроцессорных вычислительных системах //Кибернетика. 1985. - № 5. - С.48-51.

80. Эвристические методы календарного планирования. Киев: Техника, 1980,- 176 с.130

81. Экономика, организация и планирование промышленного производства: Учебное пособие для вузов. М.: Машиностроение, 1990. - 345 с.

82. Экономико-математические модели в организации и планировании промышленного предприятия. Ленинград: Изд-во ЛГУ, 1982. - 386 с.

83. Aarts Е., Lenstra J.K. Local Search in Combinatorial Optimization. John Wiley & Sons. - 1997. - 182 p.

84. Cavalcante C., Carvalho de Souza C. Scheduling projects with labor constraints //Discrete Applied Math. -2001. V. 112, Issues 1-3. - P.27-52.

85. Gordon A.D. A survey of constrained classification //Comput. Stat. Data Anal. -1996.-21, № 1,-P. 17-29.

86. Gordon A.D. Methods of constrained classification //Annal. donnes et inf. cours commis communeur. Fontainbleau, 1979. - S.e. - 1980. -P.161-171.

87. Ibaraki J. Integer programming formulation of combinatorial optimization problems //Discrete Math. 1976. - 16, № 1. - P.39-52.

88. Lammers J. Workshop in Maintenance Management. Lecture Notes. L. A. University of California. - 1984. - 328 p.

89. Mann L. Maintenance Management. D. C. Health and Company. - 1976. -281 p.

90. Stevenson W. Production/Operations Management. IRWIN. - 1986. - 827 p.

91. Pentium-233/64RAM *****************

92. Пример WORK101, периодов 12, объектов 200

93. Идеальное среднее 4 802 9.8 3 Абсолютное отклонение 77 82.8 3 Относительная погрешность 16.20 % Подготовка файлов: 0.16 сек. Итерация 1

94. Столбцы 11 05 Уменьшение на 20627505.00 Время: 0.00 сек. Итерация 2

95. Столбцы 02 04 Уменьшение на 17184832.00 Время: 0.0 6 сек. Итерация 3

96. Столбцы 06 09 Уменьшение на 5254689.50 Время: 0.00 сек.1. Итерация 27

97. Столбцы 05 03 Уменьшение на 0.50 Время: 0.00 сек. Итерация 28

98. Столбцы 09 06 Уменьшение на 0.50 Время: 0.00 сек. Идеальное среднее 48029.83 Абсолютное отклонение 0.833 Относительная погрешность 0.00 %

99. ОБЩЕЕ ВРЕМЯ: 0.77 сек. **********************

100. Пример WORK102, периодов 12, объектов 200

101. Идеальное среднее 48029.83 Абсолютное отклонение 40399.83 Относительная погрешность 84.11 % Подготовка файлов: 0.11 сек. Итерация 11. Столбцы 01 12

102. Уменьшение на 243405214.00 Время: 0.05 сек. Итерация 21. Столбцы 01 12

103. Уменьшение на 158331973.50 Время: 0.00 сек. Итерация 31. Столбцы 0 2 11

104. Уменьшение на 139141478.00 Время: 0.0 0 сек.1. Итерация 109

105. Столбцы 01 03 Уменьшение на 0.50 Время: 0.0 6 сек. Итерация 110

106. Столбцы 02 04 Уменьшение на 0.50 Время: 0.00 сек. Идеальное среднее 48029.83 Абсолютное отклонение 3.833 Относительная погрешность 0.01 % ОБЩЕЕ ВРЕМЯ: 2.80 сек.

107. Pentium-233/64RAM *****************

108. Пример W0RK105, периодов 12, объектов 1000

109. Идеальное среднее 240149.17 Абсолютное отклонение 38914.17 Относительная погрешность 16.20 % Подготовка файлов: 0.4 4 сек. Итерация 11. Столбцы 11 05

110. Уменьшение на 146159613.00 Время: 0.05 сек. Итерация 21. Столбцы 11 04

111. Уменьшение на 170046036.00 Время: 0.11 сек. Итерация 31. Столбцы 02 05

112. Уменьшение на 106118635.00 Время: 0.11 сек.1. Итерация 52

113. Столбцы 02 11 Уменьшение на 0.50 Время: 0.16 сек. Итерация 53

114. Столбцы 06 10 Уменьшение на 0.50 Время: 0.11 сек. Идеальное среднее 240149.17 Абсолютное отклонение 0.833 Относительная погрешность 0.00 %

115. ОБЩЕЕ ВРЕМЯ: 6.37 сек. **********************

116. Пример WORK106, периодов 12, объектов 1000

117. Идеальное среднее 24014 9.17 Абсолютное отклонение 201999.17 Относительная погрешность 84.11 % Подготовка файлов: 0.49 сек. Итерация 11. Столбцы 01 12

118. Уменьшение на 1306324318.00 Время: 0.11 сек. Итерация 21. Столбцы 01 12

119. Уменьшение на 1261675194.00 Время: 0.11 сек. Итерация 31. Столбцы 01 12

120. Уменьшение на 1217026070.00 Время: 0.06 сек.1. Итерация 436

121. Столбцы 08 0 9 Уменьшение на 0.50 Время: 0.17 сек. Итерация 4 37

122. Столбцы 0 5 0 8 Уменьшение на .0.5 0 Время: 0.16 сек. Идеальное среднее 240149.17 Абсолютное отклонение 1.167 Относительная погрешность 0.00 %

123. ОБЩЕЕ ВРЕМЯ: 4 3.23 сек. ************************

124. Pentium-233/б4RAM *****************

125. Пример W0RK107, периодов 12, объектов 2000

126. Идеальное среднее 480298.33 Абсолютное отклонение 77828.33 Относительная погрешность 16.20 % Подготовка файлов: 0.77 сек. Итерация 11. Столбцы 11 05

127. Уменьшение на 303074748.00 Время: 0.16 сек. Итерация 21. Столбцы 11 05

128. Уменьшение на 281563704.00 Время: 0.17 сек. Итерация 31. Столбцы 11 04

129. Уменьшение на 360088560.00 Время: 0.16 сек.1. Итерация 81

130. Столбцы 07 0 9 Уменьшение на 2.00 Время: 0.17 сек. Итерация 82

131. Столбцы 10 12 Уменьшение на 1.00 Время: 0.16 сек. Идеальное среднее 480298.33 Абсолютное отклонение 0.667 Относительная погрешность 0.00 %

132. ОБЩЕЕ ВРЕМЯ: 18.2 9 сек. ***********************

133. Пример WORK108, периодов 12, объектов 2000

134. Идеальное среднее 480298.33 Абсолютное отклонение 403998.33 Относительная погрешность 84.11 % Подготовка файлов: 0.83 сек. Итерация 11. Столбцы 01 12

135. Уменьшение на 2 634973198.00 Время: 0.16 сек. Итерация 21. Столбцы 01 12

136. Уменьшение на 2590324074.00 Время: 0.17 сек. Итерация 31. Столбцы 01 12

137. Уменьшение на 2 545674950.00 Время: 0.16 сек.1. Итерация 851

138. Столбцы 0 6 08 Уменьшение на 1.00 Время: 0.49 сек. Итерация 8 52

139. Столбцы 08 09 Уменьшение на 1.00 Время: 0.28 сек. Идеальное среднее 480298.33 Абсолютное отклонение 1.667 Относительная погрешность 0.00 % ОБЩЕЕ ВРЕМЯ: 14 8.30 сек.

140. Celeron-1000/128RAM *******************

141. Пример WORK105, периодов 12, объектов 1000

142. Идеальное среднее 240149.17 Абсолютное отклонение 38914.17 Относительная погрешность 16.20 % Подготовка файлов: 0.11 сек. Итерация 11. Столбцы 11 05

143. Уменьшение на 146159613.00 Время: 0.00 сек. Итерация 21. Столбцы 11 04

144. Уменьшение на 170046036.00 Время: 0.05 сек. Итерация 31. Столбцы 02 05

145. Уменьшение на 106118 635.00 Время: 0.00 сек.1. Итерация 52

146. Столбцы 02 11 Уменьшение на 0.50 Время: 0.00 сек. Итерация 53

147. Столбцы 06 10 Уменьшение на 0.50 Время: 0.05 сек. Идеальное среднее 24014 9.17 Абсолютное отклонение 0.833 Относительная погрешность 0.00 %

148. ОБЩЕЕ ВРЕМЯ: 1.4 2 сек. **********************

149. Пример WORK106, периодов 12, объектов 1000

150. Идеальное среднее 240149.17 Абсолютное отклонение 201999.17 Относительная погрешность 84.11 % Подготовка файлов: 0.11 сек. Итерация 11. Столбцы 01 12

151. Уменьшение на 1306324318.00 Время: 0.00 сек. Итерация 21. Столбцы 01 12

152. Уменьшение на 1261675194.00 Время: 0.05 сек. Итерация 31. Столбцы 01 12

153. Уменьшение на 1217026070.00 Время: 0.00 сек.1. Итерация 4 36

154. Столбцы 08 09 Уменьшение на 0.50 Время: 0.0 6 сек. Итерация 437

155. Столбцы 05 0 8 Уменьшение на 0.5 0 Время: 0.0 5 сек. Идеальное среднее 240149.17 Абсолютное отклонение 1.167 Относительная погрешность 0.00 %

156. ОБЩЕЕ ВРЕМЯ: 9.8 9 сек. **********************1. Celeron-1000/128RAM

157. Пример WORK107, периодов 12, объектов 2000

158. Идеальное среднее 480298.33 Абсолютное отклонение 77828.33 Относительная погрешность 16.20 % Подготовка файлов: 0.17 сек. Итерация 11. Столбцы 11 05

159. Уменьшение на 303074748.00 Время: 0.05 сек. Итерация 21. Столбцы 11 05

160. Уменьшение на 281563704.00 Время: 0.00 сек. Итерация 31. Столбцы 11 04

161. Уменьшение на 360088560.00 Время: 0.06 сек.1. Итерация 81

162. Столбцы 07 0 9 Уменьшение на 2.00 Время: 0.00 сек. Итерация 82

163. Столбцы 10 12 Уменьшение на 1.00 Время: 0.0 б сек. Идеальное среднее 480298.33 Абсолютное отклонение 0.667 Относительная погрешность 0.00 % ОБЩЕЕ ВРЕМЯ: 4.23 сек.

164. Пример WORK108, периодов 12, объектов 2000

165. Идеальное среднее 480298.33 Абсолютное отклонение 403998.33 Относительная погрешность 84.11 % Подготовка файлов: 0.17 сек. Итерация 11. Столбцы 01 12

166. Уменьшение на 2 634 97 3198.00 Время: 0.05 сек. Итерация 21. Столбцы 01 12

167. Уменьшение на 2590324074.00 Время: 0.О 6 сек. Итерация 31. Столбцы 01 12

168. Уменьшение на 2 5 4 5 674950.00 Время: 0.00 сек.1. Итерация 851

169. Столбцы 0 6 08 Уменьшение на 1.00 Время: 0.11 сек. Итерация 8 52

170. Столбцы 08 09 Уменьшение на 1.00 Время: 0.05 сек. Идеальное среднее 480298.33 Абсолютное отклонение 1.667 Относительная погрешность 0.00 % ОБЩЕЕ ВРЕМЯ: 34.93 сек.

171. Pentium-233/64RAM ******************

172. Пример WORK102, периодов 12, объектов 200

173. Идеальное среднее 4 6275.00 Абсолютное отклонение 38829.00 Относительная погрешность 83.91 % Подготовка файлов: 0.16 сек. АЛГОРИТМ А Итерация 11. Столбцы 01 12

174. Уменьшение на 225530864.00 Время: 0.0 0 сек. Итерация 21. Столбцы 01 12

175. Уменьшение на 180881740.00 Время: 0.06 сек.1. Итерация 109

176. Столбцы 09 10 Уменьшение на 1.00 Время: 0.06 сек. Итерация 110

177. Столбцы 05 06 Уменьшение на 0.50 Время: 0.11 сек. Идеальное среднее 46275.00 Абсолютное отклонение 8.000 Относительная погрешность 0.02 % ВРЕМЯ А: 2.81 сек.

178. Итерация АЛГОРИТМА В: столбцы 12 03 Абсолютное отклонение 6.000 Относительная погрешность 0.01 % ВРЕМЯ В: 0.11 сек.1. АЛГОРИТМ А1. Итерация 111

179. Столбцы 12 05 Уменьшение на 3.00 Время: 0.06 сек.1. Итерация 115

180. Столбцы 06 07 Уменьшение на 0.50 Время: 0.06 сек. Идеальное среднее 46275.00 Абсолютное отклонение 1.000 Относительная погрешность 0.00 % ВРЕМЯ А: 0.17 сек. ГРАФИК ОПТИМАЛЬНЫЙ

181. ОБЩЕЕ ВРЕМЯ: 3.0 9 сек. ' ********************************

182. Пример WORK105, периодов 12, объектов 500

183. Идеальное среднее 115687.50 Абсолютное отклонение 97 07 2.50 Относительная погрешность 83.91 % Подготовка файлов: 0.22 сек. АЛГОРИТМ А Итерация 11. Столбцы 01 12

184. Уменьшение на 597314003.00 Время: 0.05 сек. Итерация 21. Столбцы 01 12

185. Уменьшение на 552664879.00 Время: 0.06 сек.1. Итерация 221

186. Столбцы 05 06 Уменьшение на 0.50 Время: 0.38 сек. Итерация 222 . Столбцы 09 10 Уменьшение на 0.50 Время: 0.33 сек. Идеальное среднее 115687.50 Абсолютное отклонение 8.500 Относительная погрешность 0.01 % ВРЕМЯ А: 12 . 90 сек.

187. Итерация АЛГОРИТМА В: столбцы 12 01 Абсолютное отклонение 7.500 Относительная погрешность 0.01 % ВРЕМЯ В: 0.16 сек.1. АЛГОРИТМ А1. Нет 1-приводимых1. ВРЕМЯ А: 0 сек.

188. Итерация АЛГОРИТМА В: столбцы 12 02 Абсолютное отклонение 3.500 Относительная погрешность 0.00 % ВРЕМЯ В: 0.16 сек.1. АЛГОРИТМ А1. Итерация 223

189. Столбцы 02 05 Уменьшение на 3.00 Время: 0.06 сек. Итерация 224

190. Столбцы 05 06 Уменьшение на 1.00 Время: 0.22 сек. Идеальное среднее 115687.50 Абсолютное отклонение 2.500 Относительная погрешность 0.00 % ВРЕМЯ А: 0.28 сек.

191. Итерация АЛГОРИТМА В: столбцы 12 01 Абсолютное отклонение 1.500' Относительная погрешность 0.00 % ВРЕМЯ В: 0.17 сек.1. АЛГОРИТМ А1. Нет 1-приводимых1. ВРЕМЯ А: 0 сек.

192. Итерация АЛГОРИТМА В: нет 2-приводимых ВРЕМЯ В: 0 сек.

193. ГРАФИК 2-ОПТИМАЛЬНЫЙ ОБЩЕЕ ВРЕМЯ: 13.67 сек