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

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

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