Оптимизация расписания

Question

Я пытаюсь решить проблему линейного программирования, касающуюся планирования.Каждое задание имеет время начала r, время решения задачи p и вес w.Я должен минимизировать следующую функцию (C - время окончания задачи):

функция минимизации

С данными, представленными ниже Результат (массив C):

----- РЕЗУЛЬТАТ -----

12.0 - C[1]  
15.0 - C[2]   
16.0 - C[3]   
29.0 - C[4] 

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

 function findTimetable(timeForTask :: Array{Int}, weightForTask :: Array{Int}, momentForTask:: Array{Int} )
        model :: Model = Model(with_optimizer(GLPK.Optimizer))
        _size = size(timeForTask)[1]
        @variable(model, C[1: _size] >= 0, Int)

        @objective(model, Min, sum(weightForTask[i] * C[i] for i = 1 : _size))

        for i = 1 : _size
             @constraint(model, C[i] >= momentForTask[i] + timeForTask[i])
        end
        for i = 1 : _size - 1
            @constraint(model, C[i+1] >= C[i]  + timeForTask[i+1] )
        end

        println(model)
        optimize!(model)
        println(primal_status(model))
        println(objective_value(model))
        println("-----RESULT-----")
        for i in 1:_size
            println(value(C[i]))
        end
    end


  timeForTask = [2, 3, 1, 13] #p
  weightForTask  = [1, 1, 10, 2000] #w
  momentForTask  = [10, 9, 8, 1] #r

  findTimetable(timeForTask, weightForTask, momentForTask)

Заранее спасибо.

Answer 1

Стандартный метод состоит в том, чтобы ввести двоичную матрицу y_ij так, чтобы задача i предшествовала задаче j, если y_ij = 1. Тогда вы можете добавить ограничения

y_ij+y_ji = 1              for all i,j
C_j >= C_i+p_j-M(1-y_ij)   for all i,j

где M - достаточно большая константа (например, M = max_i r_i + sum_i p_i для дат выпуска r_i и времени обработки p_i).