Решение задачи о расписании обработки деталей СГРК.КП.П-41.21.ПЗ

‍

              F= Σ c_{ij +} x_{j  => max}

              x_i ≥ 0

              x_{i – целые числа}

                _{j =} (1,n), i = (1,m) 

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

     Чтобы получить целочисленное решение  нужно использовать метод Гомори, который состоит в следующем:

     1. Находим решение задачи обычным симплекс методом без учета целочислености  переменных.

     2. После нахождения оптимального плана задачи просматриваем столбец. P₀ , или среди чисел этого столбца нет дробных. То найденый план является оптимальным планом задачи целочисленного программирования. Если в аптимальном плане задачи в столбце В имеются дробные числа, то к системе ограничения добавляют неравенства вида  

  1. Σ f (a_j ^*) x_j ≥ f (b_i ^*) 

     a_j ^* и b_i ^* это преобразованные исходные величины a_j ^* b_i ^* значений которых, берутся из последней таблицы.

f (a_ij ^*) и f (b_i ^*) – это дробные части данных дробных значений имеют несколько переменных, то дополнительные неравенства определяется наибольшие дробной частью.

3. Используя двойственный симплекс метод, находим решения двойственной задачи полученной из основной задачи в результате присоединения к ней дополнительного ограничения.

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

4 КОНКРЕТНЫЙ МЕТОД РЕШЕНИЯ 

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

     Для обработки n (k = 1, …… n) деталей иметься m (i = 1, ……. m) станков. Каждая деталь должна пройти обработку в некоторой последовательности на всех станках. Задано время t_ik обработки k-й деталей на i-м станке (некоторые t_ik = 0, если k-я деталь не обрабатывается на i-м станке). При этом необходимо выполнить следующие условия:

     1) На одном станке единовременно  может обрабатываться только  одна деталь;

     2) Для каждой детали указан определенный  порядок обработки;

     3) Производственные операции неделимые, т.е. начавшаяся на определенном станке обработка детали должна быть закончена не прерываясь.

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

         Условия (2.1) можно свести к  обычным ограничениям с помощью  введения альтернативных переменных  y_iyk, принимающих значения 0 или 1. Введем некоторую постоянную T, заведомо большую общей даты выполнения всех работ.

         Тогда альтернативные условия (2.1) равносильны следующей системе неравенств

         (T+t_ik)y_ijk+X_ij≥X_jr+t_jr             (4.1) 

                                 (T+t_ik)(1- y_ijk)+ X_jj≥X_jr+t_jr      (4.2) 
 
 

      Действительно, если бы X_jr≥X_jj (что противоречило бы условию 1), то из (4.1) получили бы (T+ t_ik) y_ijk≥ t_jr,что возможно лишь при y_ijk=1,но тогда из (4.2) получили бы противоречивое неравенство 0 ≥ y_ijk.

         При y_ijk=0 получаем из (11’) X_ij≥ X_jr+t_jr, т.е. второе из неравенств (2.1),а из (11”) – неравенство T≥х_jj-х_ik, которое выполняется всегда исходя из определения Т. Аналогично при y_ijk=1 получаем из (11”) х_ik≥ х_jj+ t_jj [первое неравенство (2.1)], а из (4.1) – тривиальное неравенство Т≥ х_ik≥ х_jj.

          Таким образом, если j-я деталь поступает на обработку на i-й станок после k-й, то y_ijk=0, а если до k-й, то y_ijk=1. Следовательно, для каждого i и любых двух деталей (I и k) необходимо, чтобы из двух переменных y_ijk и y_ikj одна равнялась нулю и другая – единице. Этого можно добиться, введя дополнительные ограничения 
 

     y_ijk + y_ikj=1     (4.3) 

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

        Теперь можем сформулировать  окончательно следующую модель  целочисленного программирования: минимизировать z=t при условиях (2.2), (4.1), (4.2), (4.3), условиях неотрицательности и целочислености переменных х_ik, y_ijk и t.

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

         Решения. Алгоритм Джонсона для составления оптимального плана обработки на двух станках сводится к следующему простому правилу:

     1) располагают данные t_ik в двух строках таблицы;

     2) находят среди  всех t_ik наименьшее;

     3) если min{ t_ik }= t_2k0, то k₀-ю деталь помещают на последнее место;

     4) если оказывается  несколько равных  минимальных чисел,  то выбирают деталь  с меньшим номером  . Если min{ t_ik }= t_ik2= t_2k0, то k₀-ю деталь помещают первой;

     5)после  выполнения n. 2-4 вычеркивают k₀-й столбец и продолжают ту же процедуру с оставшимися 2n-2 величинами t_ik, начиная с n, 2. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5 РЕШЕНИЕ ЗАДАЧИ

5.1 Решение задачи без применения ЭВМ 

Задание:

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

 

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

      

Решение задачи: 

 

Ответ:

В минимальном  времени обработки на двух станках = 319 единиц.

Время простоя второго станка = 5.

Чистое  время = 314    
 
 
 
 
 
 
 

5.2 Блок-схема задачи

 
 
 
 
 

                                                 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5.3  Программа 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5.4  Решение задачи не ЭВМ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЗАКЛЮЧЕНИЕ 

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

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

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

1. Кузнецов Ю.Н.

Математическое  программирование. Учебное пособие  для вузов. М, «Высшая школа», 1976г. 

2. Хазанова Л.Э. Математическое Моделирование в экономике: Учебное пособие. М.: Издательство Век, 1998год.