Задачи календарного планирования

Содержание 
 

I. Введение………………………………………………………………….стр. 3 

II. Современное состояние вопроса. Актуальность проблемы

  составления оптимального  расписания ………………………………стр. 4 

III. Программное обеспечение календарного планирования и контроля. 

Анализ рынка………………………………………………………… ...стр. 6 

Базовые функциональные возможности системы календарного

планирования………………………………………………………… ...стр. 8 

IV. Применение метода ветвей и границ для задач календарного планирования. 

Понятие о  методе ветвей и границ…………………………………  …стр. 11 

Применение  метода ветвей и границ для задач  календарного планирования……………………………………………………………стр. 18 

V. Список использованной литературы……………………………… стр. 23 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

Современное состояние вопроса 

Актуальность  проблемы составления  оптимального расписания

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

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

     В середине 50-х годов XX века начались систематические и весьма глубокие исследования по построению и анализу  математических моделей календарного планирования и по разработке методов принятия плановых решений с использованием таких моделей. Среди первых успехов исследований следует отметить разработанные в те годы методы сетевого планирования. Получен был также ряд интересных результатов в области изучения систем массового обслуживания. В это же время появляется термин «теория расписаний».

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

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

      - в оперативно-календарном планировании при составлении план-графиков загрузки оборудования;

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

      - в производственной логистике для планирования объемов и мест складирования производственных заделов;

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

      - при составлении расписаний занятий  в вузе, приземления самолетов,  движения поездов, обслуживании клиентов и.т.д.

      Теории  расписаний использует характерный для исследования операций модельный переход к анализу реальных процессов. Изучаемые в рамках теории расписаний модели отражают специфические ситуации, возникающие при календарном планировании различных видов целенаправленной человеческой деятельности. Классическая, наиболее распространенная задача теории расписаний, решаемая с применением компьютера, называется операционно-сетевой. Объект планирования — производственный участок, состоящий из нескольких групп разнотипных станков. Задан также план выпуска деталей по номенклатурам, количеству и срокам. Заготовки поступают партиями известного объема в плановые моменты времени. Необходимо найти расписание прохождения партий по участку с наименьшим отклонением от плана выпуска. Такая задача решается методом имитационно-расчетного моделирования работы участка на компьютере по характерным моментам времени (начало, окончание обработки каждой партии на каждой операции). Основной подход к решению задачи - выбор определенной партии из очереди заготовок на технологическую операцию в момент окончания обработки на станке с соответствующим технологическим номером предыдущей партии.  
Выбор производится с учетом значений функции приоритета (эвристики). Выбор эвристик - сложная исследовательская и методическая задача, так как имеется множество видов производств и задач их планирования.  
В операционно-сетевой задаче, являющейся задачей более высокого уровня, чем описанная, участок рассматривается как единое целое. Он является, например, заготовительным для сборочного конвейера, задающего темп потребления деталей всех номенклатур в единицу времени.  
Естественно, участок не может подавать детали на сборку синхронно с темпом их расхода. Заготовительное производство выпускает детали партиями, каждая из которых расходуется на фиксированном промежутке времени, который называется периодом оборота задела. В стационарном производственном цикле, т.е. при идеальных условиях, когда нет поломок оборудования, недопоставок материалов, неудачных наладок, приводящих к браку и.т.п., периодичность выпуска всех партий постоянна.  
В реальных условиях выбор объемов партий и моментов их запуска в производство - постоянно решаемая задача оперативного планирования. От ее решения в значительной степени зависит эффективность работы участка. Заметим только, что увеличение объемов партии приводит к задержке выпуска номенклатур, «замораживанию» материалов в деталях, которые потребуются еще не скоро, а снижение объемов партии приводит к увеличению количества переналадок, т.е. потерям рабочего времени, фонда оплаты труда и к повышению вероятности выпуска некондиционных деталей.

      Теория расписаний, как указывалось выше, возникла в 50-е годы прошлого столетия. Не случайно, что интерес к теории расписаний в конце XX века значительно сократился, что вызвано новыми требованиями производства. В настоящее время, в связи с оживлением промышленного производства, наблюдается возрастание интереса к решению задач  
составления расписаний. Однако, как отмечается многими авторами, появились новые реальные задачи теории расписаний, решение которых вызывает определенные трудности.  
В стране в последние годы произошли колоссальные изменения, которые требуют пересмотра отношения к теории расписаний.  
Начиная с 90-х годов прошлого века, развитие промышленности у нас в стране прекратилось, и началась ее стагнация. Интерес к теории расписания снизился. Однако наблюдаемое оживление промышленности в настоящее время требует повышения ее конкурентоспособности, а, следовательно, повышения качества организации и управления. Поэтому следует ожидать повышения актуальности совершенствования методов оперативно-календарного планирования.

      Внимание  ученых к проблеме в какой-то мере отражает актуальность проблемы и поэтому, на наш взгляд, требуется анализ публикаций. В качестве источника для анализа использовалась библиография монографии. Библиография источника содержит 839 источников, из которых 411 — на русском языке. Как видно, количество публикаций достаточно для получения надежных выводов.  
Задачами проведенного анализа публикаций явились:  
          - анализ распределения количества публикаций по теории расписаний во времени;  
          -классификация решаемых задач;  
          -методы решения задач;  
          -опыт использования методов;  
          -новые сферы применения теории расписаний.  
каждый человек. Можно утверждать, что научная проблема может быть рассмотрена как система, и поэтому можно предположить, что она будет развиваться , как и любая система, проходя последовательно этапы зарождение — развитие - стабилизация - деградация - смерть. Деградация и «смерть» проблемы означает, что проблема решена и уже не существует.  
Можно наблюдать , на наш взгляд, «искусственную смерть», вызванную известными политическими событиями, снижением востребованности результатов научных исследований. В последние годы промышленность начала оживляться, и в печати стали вновь появляться публикации по теории расписаний.

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

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

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

     Анализ  рынка 

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

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

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

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

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

     Западные  обзоры программного обеспечения для  управления проектами традиционно  разделяют программы доступные  на рынке в две широкие группы: системы "высшего» класса (стоимостью свыше $1000 и более простые системы (продающиеся по цене ниже $1000)).