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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 10.08.2012. Сдан: 2011. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


 
    Содержание 
     

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

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

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

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

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

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

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

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

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

Введение 

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

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

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

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

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

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

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

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

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

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

         Анализ  рынка 

         Для управления проектами были разработаны первые программы почти сорок лет назад.
         Первые  системы позволяли представить  проект в виде сети, рассчитать ранние и поздние даты начала и окончания  работ проекта и отобразить работы на временной оси в виде диаграммы  Ганта. Позже в системы были добавлены возможности ресурсного и стоимостного планирования, средства контроля за ходом выполнения работ. В основе данных систем лежали алгоритмы сетевого планирования и расчета временных параметров проекта по методу критического пути.
         Долгое время ограничивалось использование систем традиционными областями – крупными строительными, инженерными или оборонными проектами и требовало профессиональных знаний. За последнее десятилетие ситуация в области использования ПО календарного планирования резко изменилась.
         В связи с повышением мощности и снижением стоимости персональных компьютеров, а также, при участии таких корпораций, как Microsoft и Symantec, буквально заваливших рынок дешевыми системами для управления проектами, программное обеспечение и методики управления, доступные раньше только состоятельным организациям, пришли на рабочие столы и вошли в повседневную практику менеджеров и сотрудников средних и малых компаний.
         Сейчас  на рынке представлено значительное количество универсальных программных пакетов для персональных компьютеров, автоматизирующих функции планирования и контроля календарного графика выполнения работ.
         Западные  обзоры программного обеспечения для  управления проектами традиционно  разделяют программы доступные  на рынке в две широкие группы: системы "высшего» класса (стоимостью свыше $1000 и более простые системы (продающиеся по цене ниже $1000)).
           В последние годы развитие информационных технологий практически свело на нет различия между системами по объемным показателям мощности систем (размеры планируемого проекта по работам и ресурсам, скорость пересчета проекта). Даже дешевые пакеты сегодня способны поддерживать планирование проектов, состоящих из десятков тысяч задачи использующих тысячи видов ресурсов. Изучая матрицы сравнения основных функций систем, также достаточно трудно найти существенные пробелы в той или иной системе. Выявить отличия в реализации отдельных функций часто удается лишь при детальном изучении и тестировании системы.
         Правильнее разделить пакеты календарного планирования на профессиональные и настольные (непрофессиональные). Профессиональные системы предоставляют более гибкие средства реализации функций планирования и контроля, но требуют больших затрат времени на подготовку и анализ данных и, соответственно, высокой квалификации пользователей. Второй тип пакетов адресован пользователям-непрофессионалам, для которых управление проектами не является основным видом деятельности. От пользователей, использующих пакеты планирования лишь время от времени при необходимости спланировать небольшой комплекс работ или ввести фактические данные по проекту трудно ожидать серьезных затрат времени и усилий на то, чтобы освоить и держать в памяти какие-либо специфические функции планирования или оптимизации расписаний. Для них более важным является простота использования и скорость получения результата.
         Современные системы календарного планирования, распространяемые на рынке, обеспечивают основной набор функциональных возможностей, которые включают в себя:
         Средства проектирования структуры работ проекта,
         средства  планирования по МКП,
         средства  ресурсного планирования (описание, назначение и оптимизация загрузки ресурсов),
         некоторые возможности стоимостного анализа,
         средства  контроля за ходом исполнения проекта,
         средства  создания отчетов и графических  диаграмм.  

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

  
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

           Описания глобальных параметров планирования проекта. Описание логической структуры комплекса работ. Средства описания комплекса работ проекта, связей между работами и их временных характеристик. Многоуровневое представление проекта. Поддержка календаря проекта. Назначение временных параметров планирования задач. Средства поддержки информации о ресурсах и затратах по проекту и назначения ресурсов и затрат отдельным работам проекта. Ведение списка наличных ресурсов, номенклатуры материалов и статей затрат. Поддержка календарей ресурсов. Назначение ресурсов работам. Календарное планирование при ограниченных ресурсах. Средства контроля за ходом выполнения проекта. Фиксация плановых параметров расписания проекта в базе данных. Ввод фактических показателей состояния задач. Ввод фактических объемов работ и использования ресурсов. Сравнение плановых и фактических показателей и прогнозирование хода предстоящих работ. Графические средства представления структуры проекта, средства создания различных отчетов по проекту. Диаграмма Ганта (часто совмещенная с электронной таблицей и позволяющая отображать различную дополнительную информацию). PERT диаграмма (сетевая диаграмма). Создание отчетов, необходимых для планирования и контроля. Различия между пакетами могут заключаться в поддерживаемых ими вычислительных платформах, мощности, наличии дополнительных средств, и в качестве реализации предоставляемых ими функций.
         Оценка  мощности пакета включает в себя тестирование качества работы системы (скорость вычислений, печати, изменения экранов) и качество представления информации по проекту (диаграммы Ганта и PERT), а также оценку полноты и гибкости функций, необходимых для разработки плана и оперативного управления.
         При оценке мощности системы для управления проектами обычно оцениваются следующие  основные функциональные возможности:
         1. Средства описания комплекса работ проекта, связей между работами и их временных характеристик:
         Поддержка календаря проекта (максимальный размер календаря, наиболее поздняя дата, максимальное количество праздников в одном календаре, возможность задавать рабочие дни недели и различные рабочие дни для различных недель, возможность задавать обычные рабочие часы);
         Ограничения, накладываемые на работы проекта (типы работ (Как Можно Раньше, Как Можно  Позже, работы с фиксированной датой начала/окончания), возможность планирования выполнения работ по индивидуальным календарям);
         Возможности назначения временных характеристик (максимальная длительность отдельной  задачи, максимальная длительность проекта, единицы времени, доступные в системе, задачи-вехи, вычисляемые резервы времени (полный, свободный), возможность системы автоматически присваивать длительность отдельным задачам, возможность привязки длительностей задач к объему назначенных ресурсов);
         Связи между задачами (максимальное количество предшествующих и последующих задач, допустимые типы связей, допустимые типы задержек/перекрытий);
         Максимально допустимое количество задач в проекте, длина имени задачи, возможности  кодирования, возможность автоматического  пересчета, многоуровневое представление проекта.
         2.  Средства контроля за ходом выполнения проекта.
         Средства  отслеживания состояния задач проекта (фиксация плана расписания проекта, средства поддержки фактических  показателей состояния задач (процент  завершения));
         Средства контроля за фактическим использованием ресурсов (бюджетное количество и стоимость ресурса, фактическое количество и стоимость ресурса, количество и стоимость ресурсов, требуемых для завершения работы);
         Средства  стоимостного анализа состояния  проекта и анализа на основе выполненных объемов работ.
         3.Средства поддержки информации о ресурсах и затратах по проекту и назначения ресурсов и затрат отдельным работам проекта.
         Информация  о ресурсах (максимальное количество ресурсов на проект. Возможность описания различных типов ресурсов (складируемые и не складируемые, статьи затрат, номенклатура материалов). Поддержка ресурсов с фиксированной стоимостью и ресурсов, стоимость которых зависит от длительности их использования. Поддержка информации о требуемых и доступных объемах ресурса. Возможность задания нормального и максимального объемов ресурса, возможность задания переменного объема ресурса, возможность задания индивидуальных календарей ресурсов);
         Назначение  ресурсов задачам (максимальное количество ресурсов на задачу, возможность задания частичного использования ресурсов, возможность задания задержек при использовании ресурса);
         Календарное планирование при ограниченных ресурсах (выделение перегруженных ресурсов и использующих их задач, разрешение ресурсных конфликтов, автоматическое/командное выравнивание ресурсов, выбор ресурсов для выравнивания, выравнивание с учетом приоритетов задач, выравнивание с учетом ограничений повремени или с учетом ограничения на ресурс, оптимальность полученных планов). 

         4. Удобные графические средства представления структуры проекта (диаграмма Ганта, сетевая диаграмма, иерархическая диаграмма проекта), а также средства создания различных отчетов по проекту.
         Диаграмма Ганта (отображение критического пути, расчетных и фактических дат начала и окончания работ, резервов работ, возможность изменения временной шкалы, отображение текущей даты, отображение составных задач, отображение дополнительной информации);
         PERT диаграмма (отображение критического пути, расчетных и фактических дат начала и окончания работ, длительности, резервов работ, отображение многоуровневости детализации задач, возможность задания различных типов сетевой диаграммы, ручное и автоматическое размещение работ и связей, определение дополнительной информации);
         Средства  создания отчетов (отчеты по состоянию  выполнения расписания, отчеты по ресурсами  по назначению ресурсов, профили загрузки ресурсов. Отчеты по затратам (могут включать стоимость отдельных задач, детализацию стоимости задач по ресурсам, стоимость ресурса по задачам, запланированную и фактическую стоимость), отчеты по денежным потокам, отчеты для анализа фактического состояния выполнения задач проекта и сравнения с запланированным);
         Кроме того, следующие дополнительные возможности должны быть рассмотрены при выборе пакета планирования:
         Сортировка  данных (максимальное количество критериев, сортировка по кодам задач и датам);
         Критерии  отбора данных (исключающий и выделяющий отбор);
         Возможности печати (типы принтеров, плоттеры, многостраничный отчет);
         Средства  обмена данными (поддержка технологии клиент/сервер, стандартов SQL и ODBC, интеграция с ресурсами Web, импорт/экспорт (ASCII, dBase, Lotus, другие системы для управления проектами);
         Работа  в сети;
         Работа  с несколькими проектами (многопроектное планирование, объединение проектов, связь проектов, максимальное количество связанных проектов, совместное ресурсное планирование);
         Языки программирования и разработки макроопределений.
         Важными для пользователя являются простота изучения и использования системы, а также качество дополнительной консультационной поддержки данной системы на рынке. 
     

  
 
 
 
 
 
 
 
 
 
 

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

          Метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
          Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
    Алгоритм  решения:
          Первоначально  находим симплексным  методом  или  методом искусственного базиса оптимальный план задачи без учета  целочисленности переменных. Пусть  им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(Xo).
          Если  же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0) ? F(X) для всякого последующего плана X.
          Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент
          есть  дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу , либо больше или равно ближайшему большему целому числу
            + 1.
          Определяя эти числа, находим симплексным  методом решение двух задач линейного  программирования:
     
     
     
     
     
     
     
     
     
     
     

          Найдем  решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:
    1.   Одна  из  задач  неразрешима,   а другая имеет целочисленный  оптимальный план. Тогда этот  план и значение целевой функции  на нем и дают решение исходной  задачи.
    2. Одна  из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
    3. Обе  задачи разрешимы. Одна из задач  имеет оптимальный целочисленный  план, а в оптимальном плане  другой задачи есть дробные  числа. Тогда вычисляем значения  целевой функции на этих планах  и сравниваем их между собой.  Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.
          Если  же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять  одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).
    и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.