Как получить ArgMax набора в задаче MiniMax в AMPL - PullRequest
Новая
       71

Как получить ArgMax набора в задаче MiniMax в AMPL

0 голосов
/ 05 марта 2020

У меня есть минимаксная проблема, которую нужно решить в AMPL. У меня есть ряд процессоров (j) и процессов (i), с набором операций, которые должны выполняться каждым процессом последовательным образом (от процессора 1 до процессора N) на каждом процессоре с продолжительностью для каждая операция определяется как p[i,j]
Каждый процесс имеет ожидаемое время окончания.
Задача состоит в том, чтобы запланировать выполнение всех процессов на процессорах, чтобы минимизировало максимальную задержку (определенную как момент времени, когда выполнение заканчивается - ожидаемое время окончания). Для этого я попытался, как вы можете видеть в следующем фрагменте кода, минимизировать задержку max_delay, определенную в ограничениях. Проблема заключается в том, что при таком изменении она меняет каждую задержку, равную max_delay , что приводит к неправильному планированию.
Знаете ли вы другой способ решения проблемы? Я также думал о настройке max_delay >= argmax(delay[i]), но, честно говоря, я не знаю, правильно ли это и как реализовать функцию argmax в AMPL

Заранее спасибо за ответы, вот код, который я реализовал 


# Parameters
param r >= 0;                                                    # # of PROCESSORS
param T >= 0;                                                    # # of PROCESSES
param t_max >= 0;                                                # TIME max for TIME set

# Sets
set PROCESSES := 1..T;
set PROCESSORS := 1..r;
set TIME := 0..t_max;

# Other params
param D{PROCESSES} >= 0;                                          # exp. end
param p{PROCESSES, PROCESSORS} >= 0;                              # TIME for exec of operation p fro process i on processor j. 

# Variables
var USE{PROCESSES, PROCESSORS, TIME} binary;                
var end_time{PROCESSES} >= 0; 
var DELAY{i in PROCESSES} = end_time[i] - D[i];                   # array of delays
var max_DELAY integer >= 0;

# Constraints

# Constraint to define end_time
subject to end_time_constraint {i in PROCESSES}:
     sum{t in TIME} (t + p[i,r])*USE[i,r,t] <= end_time[i] ;

# constraint to grant a single execution 
subject to single_execution {i in PROCESSES, j in PROCESSORS} : 
    sum{t in TIME} USE[i,j,t]=1;

# Constraint to avoid multiple operation to execute at the same time
subject to operation_constraint {i in PROCESSES, t in TIME}:
    sum{j in PROCESSORS} USE[i,j,t]<=1;

# Constraint to grant the right execution order (operation od process i on processor j befor the one on j+1)
subject to order_constraint {i in PROCESSES, j in PROCESSORS, t in TIME}:
    sum{k in 0..t} USE[i,max(j-1, 1),k] >= USE[i,j,t];

# constraint to get the max delay over delays array

subject to max_DELAY {i in PROCESSES}:
    max_DELAY >= DELAY[i];

# constraint to avoid sovrapposition of processes
subject to non_sovrapp1 {t in TIME, j in PROCESSORS}:
    sum{i in PROCESSES, k in max(t-p[i,j]+1,0)..(t)} USE[i,j,k]<=1;

# constraint to avoid sovrapposition of processors
subject to non_sovrapp2 {i in PROCESSES, t in TIME} :
    sum{ j in PROCESSORS, k in max(t-p[i,j]+1,0)..(t)} USE[i,j,k] <= 1;

minimize min_DELAY : max_DELAY;

1 Ответ

0 голосов
/ 06 марта 2020

Часто мы используем комбинацию min-max и min-sum. По сути, это становится многоцелевой проблемой, для которой существуют стандартные подходы к решению. Один из таких подходов состоит в том, чтобы сначала решить проблему min-max, а затем решить вторую min-sum при условии, что max не ухудшится. В качестве альтернативы используйте формулировку взвешенной суммы. Для некоторых деталей (в другом контексте), см. ссылка .

...