Разработка алгоритма планирования действий для максимального увеличения количества действий

Я работаю над алгоритмом планирования активности. Допустим, есть N видов деятельности. Каждое действие можно выполнить только в указанные сроки (например, с 8:00 до 17:00), и есть время, необходимое для завершения действия (например, 2 часа). Я хочу закончить как можно больше занятий за день, указав время начала и время окончания. Например.

  1. Мероприятие 1 (с 8 до 17) занимает 2 часа.
  2. Мероприятие 2 (7:00 - 11:00) длится 1,5 часа.
  3. Мероприятие 3 (с 11 до 15) длится 1 час.
  4. Мероприятие 4 (13: 00–15: 30) длится 1,5 часа.
  5. Мероприятие 5 (с 6 утра до 8 вечера) длится 3 часа.
  6. Мероприятие 6 (с 11:00 до 18:00) занимает 2 часа.
  7. Мероприятие 7 (14: 00–17: 00) занимает 1 час.
  8. Мероприятие 8 (19: 00–12: 00) занимает 1 час.

Я хочу заниматься как можно большим количеством занятий с 8 до 20 часов. Я просмотрел алгоритм жадного выбора активности, но мой случай немного отличается от этого. Любая помощь приветствуется!

Я пробовал эту логику:

Activity[] possibleActivities; // this has all the activities, Activity object has startTime, endTime and duration.
int dayStartTime= 8; //8am
int dayEndTime= 18; //6pm
Arrays.sort(possibleActivities); // sort the activities based on the startTime
int hours=dayStartTime;
List<Activity> dailyActitiy=new ArrayList<>();
for(Activity activity: possibleActivities){
    if(activity.startTime<=hours && hours<dayEndTime){
        dailyActitiy.add(activity);
        hours+=dailyActitiy.duration;
    }

 }
 return dailyActitiy;

java algorithm greedy
person Sameer Malhotra    schedule 05.03.2017    source источник
comment
Спасибо @ m69, добавил мой код. Не уверен, что это оптимальное решение.   -  person Sameer Malhotra    schedule 06.03.2017

Ответы (1)


arrow_upward
1
arrow_downward

В литературе по планированию это можно назвать проблемой планирования для одного компьютера с переменным временем обработки, датами выпуска и сроками выполнения. Этот вариант является NP-трудным (если я правильно читаю классическую литературу), поэтому я рекомендую целочисленное программирование через стандартный решатель.

Одна формулировка состоит в том, чтобы сделать переменную 0-1 для всех пар интервалов активности-времени (например, действие 2, которое составляет 1,5 часа между 7:00 и 11:00, получает переменные x (2,7-8: 30), x (2,7: 30: 00–9: 30), x (2,8–9: 30), x (2,8: 30–10 утра), x (2,9–10: 30), x (2,9: 30–11: 00)) с указанием следует ли выполнять действие в установленный временной интервал. Цель состоит в том, чтобы максимизировать сумму всех этих переменных. Есть два типа ограничений: для каждого действия сумма его переменных должна быть не более одной, чтобы каждое действие было запланировано не более одного раза; для каждой единицы времени (полчаса в примере) сумма всех переменных, содержащих эту единицу, должна быть не более одной, поэтому на каждый момент приходится не более одного запланированного действия.

person David Eisenstat    schedule 06.03.2017
comment
Привет, Дэвид, не могли бы вы указать мне на готовый решатель? Единственные, которые я смог найти, были платными, знаете ли вы, есть ли какая-нибудь библиотека с открытым исходным кодом, которую я мог бы использовать? - person Sameer Malhotra; 15.03.2017
comment
@SameerMalhotra См. Также gurobi.com/resources/switching-to- гуроби / решатели с открытым исходным кодом - person David Eisenstat; 16.03.2017