183810 (596705), страница 3

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

Текст из файла (страница 3)

Рис 1.2

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

1.2.3 Сетевые графики

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

Таблица 1.1

Таблица очередности

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

Рис 1.3

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

Рис 1.4

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

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

1. Математический аппарат решения задач календарного планирования

1.3.1 Общая характеристика задач календарного планирования

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

Уже первые попытки математического решения задач календарного планирования показали, что для такого рода задач нужна, можно сказать, «новая математика» и что задачи подобного рода, по-видимому, в ближайшее время во многом изменят содержание самой математики.

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

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

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

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

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

1.3.2 Модели линейного программирования

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

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

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

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

Данциг поясняет эту идею на таком примере.

Пусть имеются две детали и d₂, в каждой из которых по две операции. Время обработки каждой операции равно единице, маршруты деталей следующие:

Иными словами, первая операция детали d₁ обрабатывается на первом рабочем месте R₁ вторая операция детали d₁ и первая операция детали d₂ обрабатываются на R₂, вторая операция d₂ обрабатывается на R₃.

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

В этом случае первая деталь может обрабатываться одним из следующих способов:

Введем неизвестные

Тогда, очевидно, для нашей задачи

.

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

где - начало периода.

Для рассматриваемого примера эти условия могут быть записаны в стандартной форме (табл. 1.2).

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

Таблица 1.2

Условия для задачи

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

Характеристики

Список файлов ВКР