Метод критического пути. Алгоритм критического пути с модификациями. Реализация метода критического пути на Python

January 29, 2019 17:20

Метод критического пути - это инструмент для планирования расписания. Модификацией алгоритма критического пути в условиях неопределенности называется ситуация, когда в матрице загрузки на i-ой строке и в j-ом столбце стоит бесконечность. 
Ограничения метода:
каждая строка должна содержать хотя бы одно значение не равное бесконечности. В приведенном случае будут рассматриваться однородные и неоднородные матрицы.

Существует 3 модификации:

1. все строки матрицы сортируются в порядке убывания элементов отличных от бесконечности. 

2. все строки матрицы сортируются по количеству бесконечностей в строке.

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

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

Реализация на Python (однородные матрицы):

from functools import cmp_to_key
from numpy import nanmax, nan, isinf, inf, sum
from random import randrange, choice, randint


def process_next_row(rowa, rowb):
    rows_sum = sum([rowa, rowb], axis=0)
    min_from_rows_sum = min(rows_sum)
    min_from_rows_sum_index = list(rows_sum).index(min_from_rows_sum)
    rowa[min_from_rows_sum_index] = min_from_rows_sum


def crit(matrix):
    row = matrix.pop()
    max_exclude_inf = nanmax(list(map(lambda x: nan if isinf(x) else x, row)))
    max_exclude_inf_index = row.index(max_exclude_inf)

    row = [0] * len(row)
    row[max_exclude_inf_index] = max_exclude_inf

    while matrix:
        process_next_row(row, matrix.pop())
    return row


def form(mat): return '\n'.join(map(str, mat))

def infcmp(x, y):
    if x.count(inf) == y.count(inf):
        return min(x) - min(y)
    return x.count(inf) - y.count(inf)

N, M = int(input("rows: ")), int(input("cols: "))
a, b = map(int, input("a, b: ").split())

R = list(range(a, b))

T = [[inf] * M for i in range(N)]

for row in T:
    num = choice(R)
    row[choice(range(len(row)))] = num 
    
    for i in range(M):
        if choice([True, False]):
            row[i] = num


T1 = sorted(T, key=min, reverse=True)
T2 = sorted(T, key=lambda row: row.count(inf), reverse=True)
T3 = sorted(T, key=cmp_to_key(infcmp), reverse=True)

M1, M2, M3 = crit(list(reversed(T1))), crit(list(reversed(T2))), crit(list(reversed(T3)))

print()
print('Original matrix:')
print(form(T))
print()

print('Modification 1')
print(form(T1), M1, max(M1), sep='\n\n')
print()

print('Modification 2')
print(form(T2), M2, max(M2), sep='\n\n')
print()

print('Modification 3')
print(form(T3), M3, max(M3), sep='\n\n')
print()

Реализация на Python (неоднородные матрицы):

from functools import cmp_to_key
from numpy import nanmax, nan, isinf, inf, sum
from random import randrange, choice, randint


def process_next_row(rowa, rowb):
    rows_sum = sum([rowa, rowb], axis=0)
    min_from_rows_sum = min(rows_sum)
    min_from_rows_sum_index = list(rows_sum).index(min_from_rows_sum)
    rowa[min_from_rows_sum_index] = min_from_rows_sum


def crit(matrix):
    row = matrix.pop()
    max_exclude_inf = nanmax(list(map(lambda x: nan if isinf(x) else x, row)))
    max_exclude_inf_index = row.index(max_exclude_inf)

    row = [0] * len(row)
    row[max_exclude_inf_index] = max_exclude_inf

    while matrix:
        process_next_row(row, matrix.pop())
    return row


def form(mat): return '\n'.join(map(str, mat))
def sum_ignore_inf(row): return sum([val for val in row if not isinf(val)])

def infcmp(x, y):
    if x.count(inf) == y.count(inf):
        return sum_ignore_inf(x) - sum_ignore_inf(y)
    return x.count(inf) - y.count(inf)


N, M = int(input("rows: ")), int(input("cols: "))
a, b = map(int, input("a, b: ").split())

inf_freq = 3

R = list(range(a, b))

T = [[choice(R + [inf] * inf_freq)  for j in range(M)] for i in range(N)]

for row in T:
    if all(isinf(val) for val in row):
        row[choice(range(len(row)))] = choice(R)

T1 = sorted(T, key=sum_ignore_inf, reverse=True)
T2 = sorted(T, key=lambda row: row.count(inf), reverse=True)
T3 = sorted(T, key=cmp_to_key(infcmp), reverse=True)

M1, M2, M3 = crit(list(reversed(T1))), crit(list(reversed(T2))), crit(list(reversed(T3)))


print()
print('Original matrix:')
print(form(T))
print()

print('Modification 1')
print(form(T1), M1, max(M1), sep='\n\n')
print()

print('Modification 2')
print(form(T2), M2, max(M2), sep='\n\n')
print()

print('Modification 3')
print(form(T3), M3, max(M3), sep='\n\n')
print()

Входные данные:

  • rows: 10 (число строк)
  • cols: 4 (число столбцов)
  • a,b: 10 20 (промежуток, два числа через пробел)

Пример работы программы (нажмите для увеличения):

Алгоритм критического пути
Метод критического пути