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

Я пытаюсь решить проблему линейного программирования о планировании. Каждая задача имеет время начала 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)

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


person PoorGuy    schedule 26.04.2019    source источник
comment
Я не понимаю, почему вы говорите, что ваша последняя задача должна выполняться первой, как вы хотели в своей линейной программе, которая C[i+1] >= C[i] + timeForTask[i+1] означает, что задача i+1 завершается после задачи i.   -  person JKHA    schedule 30.04.2019


Ответы (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).

person Marcus Ritt    schedule 05.05.2019