Предположим, у нас есть n рабочих мест для планирования, и мы хотим найти порядок планирования рабочих мест, чтобы достичь наименьших общих потерь. Каждое задание имеет три свойства: (b,l,k), где b указывает время прихода каждого задания, l указывает время, необходимое для выполнения, а k - коэффициент. Когда работа выполняется, она не может быть прервана , и у нас просто есть одна машина. Время ожидания задания определяется как время подачи - время прихода. Мы определяем потерю работы как время ожидания, умноженное на k.
Например, у нас есть три задания: (0,10,1), (2,3,5), (4,7,3). Если мы следуем его начальному порядку 1,2,3, то потеря каждой работы составляет 0, (10-2)×5=40, (13-4)×3=27, соответственно, а общие потери составляют 67. Однако, если мы будем следовать порядку 2,3,1, мы можем получить меньшие общие потери 0+12+3=15 , Это означает, что хотя первая работа приходит в момент 0, мы не справляемся с ней. Вместо этого, пока мы не закончим третью работу, мы выбираем первую работу для планирования. Вот подробное объяснение следующего порядка 2,3,1
Я думаю, что эта проблема имеет некоторое сходство с алгоритмом SJF в операционной системе, но также сильно отличается друг от друга.
Вот основная часть моего мышления. По сути, я придумала жадный алгоритм . Я сохраняю deque, чтобы сохранить работу, которая наступит раньше, но не будет выполнена своевременно. Когда нам нужно выбрать работу для планирования, я рассматриваю рабочие места в deque и рабочие места, которые приходят, когда работа выполняется. Я сравниваю потери между этими работами, чтобы найти работу, чтобы получить дополнительные потери. Ну ... мой английский не очень хорош. Если кто-то хочет узнать больше, перейдите на мой репозиторий github
Интересно, существует ли алгоритм динамического программирования или другой эвристический алгоритм для получения лучшего приближенного решения?
Ниже приведена основная часть моего кода, написанная в C++:
vector<int> order;
deque<seg> q;
int curr_idx = 0, curr_time = 0;
long long total_loss = 0;
while (curr_idx < n || !q.empty()) {
//当所有任务都已入队，直接处理队中任务
if (curr_idx == n) {
//计算队中所有k之和
int k_sum = 0;
for (auto &s : q) {
k_sum += s.k;
}
while (!q.empty()) {
//比较选择哪个任务可以带来最小的*新增*损失
int min_loss = INT_MAX;
deque<seg>::iterator min_it = q.begin();//换成auto也行
for (auto it = q.begin();it != q.end();it++) {
int loss = it->last*(k_sum - it->k);
if (loss < min_loss) {
min_it = it;
min_loss = loss;
}
}
order.push_back(min_it->beg);
total_loss += min_loss;
curr_time += min_it->last;
k_sum -= min_it->k;
q.erase(min_it);
}
break;
}
//系统初始情况或者期间没有任务及时到来
//推进当前时间，相当于指针在时间轴往前跑，直到找到一个新的任务
//while用来将同时刻的任务全部入队
if (q.empty()) {
int time = segs[curr_idx].beg;
while (curr_idx < n&&segs[curr_idx].beg == time)
q.push_back(segs[curr_idx++]);
curr_time = q.front().beg;
}
int k_sum = 0;
for (auto &s : q) {
k_sum += s.k;
}
//比较选择哪个队中任务可以带来最小的*新增*损失
int min_loss = INT_MAX;
deque<seg>::iterator min_it = q.begin();//换成auto也行
int lower_idx = -1;
bool in_queue = true;
for (auto it = q.begin();it != q.end();it++) {
int loss = it->last*(k_sum - it->k);//若选当前任务，当其执行完毕时的队列其他任务新增损失
int idx = curr_idx;
//区间内到达任务由于目前在处理it任务而造成的新增损失
while (idx < n&&segs[idx].beg <= curr_time + it->last) {
loss += (curr_time + it->last - segs[idx].beg)*segs[idx].k;
idx++;
}
if (loss < min_loss) {
min_loss = loss;
min_it = it;
in_queue = true;
}
//开始比较是否可以先执行在后续区间内的任务能带来更小的损失
for (int i = curr_idx;i < n&&segs[i].beg <= curr_time + it->last;i++) {
//队列中所有任务由于继续等待造成的新增损失
int end_time = segs[i].beg + segs[i].last;
int loss2 = (end_time - curr_time)*k_sum;
for (int j = curr_idx;j < n&&segs[j].beg <= end_time;j++) {
if (j != i)
loss2 += (end_time - segs[j].beg)*segs[j].k;
}
if (loss2 < min_loss) {
min_loss = loss2;
in_queue = false;
lower_idx = i;
}
}
}
total_loss += min_loss;
//区间内没有可以造成更小损失的任务，执行队内任务
if (in_queue) {
curr_time += min_it->last;
order.push_back(min_it->beg);
q.erase(min_it);
while (curr_idx < n&&segs[curr_idx].beg <= curr_time) {
q.push_back(segs[curr_idx]);
curr_idx++;
}
}
else {
order.push_back(segs[lower_idx].beg);
curr_time = segs[lower_idx].beg + segs[lower_idx].last;
//将该任务前的到达任务入队，并注意跳过该任务
while (curr_idx < n&&segs[curr_idx].beg <= curr_time) {
if (curr_idx != lower_idx)
q.push_back(segs[curr_idx]);
curr_idx++;
}
}
}