Последовательность заданий со временем выполнения задания, сроками и штрафами - PullRequest
Новая
       40

Последовательность заданий со временем выполнения задания, сроками и штрафами

0 голосов
/ 13 мая 2018

Существует N заданий со сроками исполнения, сроками и штрафами, если задание не укладывается в срок. Время выполнения, срок и штраф могут варьироваться в зависимости от каждой работы. Только одна работа может быть выполнена в то время. И все работы должны быть выполнены. Задача состоит в том, чтобы отсортировать задания (график), чтобы штраф был минимальным.

У вас есть идеи для алгоритма или даже вы могли бы поделиться некоторыми примерами кода? Я действительно застрял с этой задачей.

Ответы [ 2 ]

0 голосов
/ 14 мая 2018

Я полагаю, что штраф, если задание пропускает свой крайний срок, является константой w_j, которая зависит от задания j, но не от его значения задержки.В общем случае задача - это NP Hard (в классических обозначениях alpha|beta|gamma это 1||sum_j w_j U_j).Это полиномиальный в особом случае, все веса w_j равны (минимизируя количество поздних заданий).

Вероятно, вы можете найти много очень эффективных алгоритмов для решения конкретной проблемы.Если вас интересуют общие формулировки для решения этой проблемы, вы можете попробовать CP Optimizer [1], в OPL формулировка для ее решения будет выглядеть следующим образом: 

int n = ...;
int  dd[j in 1..n] = ...; // Deadline for job j
int  pt[j in 1..n] = ...; // Processing time for job j
float w[j in 1..n] = ...; // Penalty for late job j

dvar interval job[j in 1..n] size pt[j]; // Decision variables

minimize sum(j in 1..n) ( w[j]*(endOf(job[j])>=dd[j]) );
subject to {
  noOverlap(all(j in 1..n) job[j]);
}

Вот еще лучшая формулировка в использовании CP Optimizer с использованиемпонятие необязательной переменной-интервала: вы максимизируете ожидаемую сумму выполненных интервалов / действий, которые должны заканчиваться до крайнего срока: 

int n = ...;
int  dd[j in 1..n] = ...; // Deadline for job j
int  pt[j in 1..n] = ...; // Processing time for job j
float w[j in 1..n] = ...; // Penalty for late job j

dvar interval job[j in 1..n] optional in 0..dd[j] size pt[j]; // Decision variables

minimize n - sum(j in 1..n) ( w[j]*presenceOf(job[j]) );
subject to {
 noOverlap(all(j in 1..n) job[j]);
}

[1] П. Лабори, Дж. Роджери, П. Шоу,П. Вилим.IBM ILOG CP оптимизатор для планирования.Журнал Ограничений.Апрель 2018, том 23, выпуск 2, с. 210–250.http://ibm.biz/Constraints2018.

0 голосов
/ 13 мая 2018

Название проблемы - «Проблема последовательности заданий», и хотя у меня нет собственного примера, которым вы могли бы поделиться, вы можете взглянуть на это https://www.geeksforgeeks.org/job-sequencing-problem-set-1-greedy-algorithm/

...