Задачи календарного планирования производства: модель без дефицита, модель с дефицитом
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
способе составления расписаний.
Локальное правило календарного планирования это такое правило, которое используется рабочим-станочником при выполнении запланированных работ и требует от него только знания работ, ожидающих своей очереди перед его станком. Известно множество локальных правил, каждое из которых дает расписание, близкое к оптимальному для конкретной модели календарного планирования. Предпочтительность того или иного правила в зависимости от размерности задачи или от последовательности выполнения работ определить трудно. Во всех случаях определяется лишь расписание, близкое к условно оптимальному, т.е. оптимальному в условиях применения определенных локальных правил.
Наиболее широкое распространение за рубежом получила система CAPOSS (capacity planning and operations sequencing system), разработанная специалистами фирмы IBM. В системе реализуются функции долгосрочного и краткосрочного планирования, производится расчет времени изготовления заказов и составляется последовательность операций с использованием локальных правил, в том числе правила априорных приоритетов, в соответствии с которыми каждому заказу или операции присваивается приоритет, определяющий очередность их назначения на выполнение. В любом случае получается такой вариант расписания, близость которого к оптимальному остается не известной. Это связано с отсутствием информации как о характере изменения целевой функции в области допустимых расписаний, так и о границах этой области. Для определения оптимального решения существуют методы поиска, основанные на направленном переборе допустимых вариантов расписаний. Основными недостатками этих методов являются потребность в большом объеме оперативной памяти и продолжительное время решения задачи.
1.2 Постановка задачи календарного планирования
Назначение календарного планирования - конкретизировать производственный план предприятия и довести его до исполнителей (цехов, участков, рабочих мест). При этом оно должно обеспечить:
максимизацию загрузки оборудования и использования человеческих ресурсов;
минимизировать стоимость производства и хранения продукции;
удовлетворение спроса.
Календарное планирование предусматривает:
выпуск продукции при обычной и сверхурочной работе.
определение периода выпуска определенного количества продукции;
Сформулируем условия задачи календарного планирования.
Определен спрос на некоторую продукцию, он изменяется во времени. Спрос можно удовлетворить несколькими способами:
путем изменения уровня запаса при постоянном объеме производства,
за счет изменения объема производства при постоянном уровне запаса,
путем изменения и запаса, и выпуска.
Изменить объем производства можно, проводя сверхурочные работы, а изменения уровня запаса можно обеспечить за счет создания постоянного положительного запаса, либо за счет неудовлетворенного спроса.
Задача: отыскать календарный план производства на N этапов, минимизирующий суммарные затраты. Предполагаются нулевые затраты на оформление заказа для любого этапа. В общем случае допускается дефицит при условии, что весь задолженный спрос должен быть удовлетворен к концу этапа N.
Эти условия можно записать в виде транспортной задачи, т.е. в соответствии с 1.2 использовать методы линейного программирования. Поэтому целесообразно вначале рассмотреть транспортную задачу, а затем применить ее для решения задачи календарного планирования производства.
2. Транспортная задача линейного программирования
2.1 Постановка транспортной задачи
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2, . . . , Am в n пунктов назначения B1, B2, . . . , Bn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через cij тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в i-м пункте отправления, через bj - потребности в грузе в j-м пункте назначения, а через xij - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции
(1.1)
Поскольку переменные xij (i=1,m; j=1,n) удовлетворяют системам линейных уравнений и условию неотрицательности, обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 1.1 Всякое неотрицательное решение систем линейных уравнений, определяемое матрицей X=(xij) (i=1,m; j=1,n), называется планом транспортной задачи.
Определение 1.2. План X*=(xij*)(i=1,m; j=1,n), при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные транспортной задачи записываются в виде таблицы , как показано в таблице 1.
Таблица 1
Пункты отправления Пункты назначения Запасы B1. . . Bj . . . Bn A1c11 x11. . . c1j x1j . . . c1n x1n a1Ai ci1 xi1. . . cij xij . . . cin xin ai Am cm1 xm1. . . cmj xmj . . . cmn xmn am Потребности b1. . . bj . . . bn
Очевидно, общее наличи