Оптимизированные алгоритмы взвешенного интервального планирования - PullRequest
Новая
       15

Оптимизированные алгоритмы взвешенного интервального планирования

0 голосов
/ 20 июня 2019

У меня есть n задач, которые должны быть запланированы на данный период. У каждой задачи есть самое раннее время начала, оптимальное время начала, самое позднее время окончания, продолжительность и вес приоритета. Задачи не могут перекрываться. Требование состоит в том, чтобы запланировать как можно больше заданий, максимально приближенных к их оптимальному времени запуска, и отдавать приоритет более взвешенным задачам, где не все задачи могут быть выполнены. Я ознакомился с планированием интервалов, а также с расписанием взвешенных интервалов, но я не сталкивался с алгоритмами, которые также включают в себя концепцию оптимального времени запуска. Может кто-нибудь указать мне библиотеку Python, которая может сделать это, или описание подходящего алгоритма, который я мог бы кодировать сам? [применение - это планирование астрономических изображений, при этом время начала и окончания - это время, когда каждый объект поднимается и садится в небе, и оптимальное время, когда объект находится на своей максимальной высоте; с весом, являющимся приоритетом, назначенным астрономами для каждого объекта].

1 Ответ

0 голосов
/ 24 июня 2019

Это должно быть очень легко моделировать и решать с помощью CP Optimizer (https://pypi.org/project/docplex/). С помощью этого инструмента все, что вам нужно, это сформулировать вашу задачу как комбинаторную задачу оптимизации, и автоматический поиск решит ее (и доказать оптимальность решение, если экземпляр не слишком большой).

Вот пример, как я бы сформулировал эту проблему в CP Optimizer (я приведу небольшой пример): 

N = range(20)

EST = [166, 157, 118, 254, 213, 73, 100, 38, 113, 84, 43, 257, 74, 246, 73, 242, 207, 223, 242, 122] 
OST = [205, 195, 134, 256, 252, 157, 106, 44, 167, 84, 85, 266, 121, 256, 110, 310, 229, 262, 286, 162] 
LET = [259, 233, 172, 267, 269, 175, 111, 48, 197, 91, 97, 292, 147, 289, 127, 313, 238, 319, 346, 177] 
D = [9, 7, 5, 1, 9, 9, 4, 2, 3, 2, 9, 8, 3, 1, 7, 2, 3, 4, 4, 2] 
W = [0.254, 0.811, 0.479, 0.27, 0.968, 0.036, 0.373, 0.887, 0.855, 0.61, 0.855, 0.708, 0.376, 0.434, 0.834, 0.978, 0.354, 0.4, 0.128, 0.208] 
P = [1.46, 1.47, 9.29, 0.32, 5.43, 5.02, 8.1, 8.35, 7.79, 0.79, 3.86, 4.33, 7.16, 0.86, 5.82, 1.88, 2.16, 0.04, 9.37, 9.36]

# PROBLEM FORMULATION

from docplex.cp.model import *
model = CpoModel()

# Decision variables: x[i] is the ith observation
x = [ interval_var(size=D[i], optional=True) for i in N]

# Cost expression
cost = sum([start_eval(x[i], CpoSegmentedFunction((-W[i],0),[(OST[i],0,W[i])]), P[i]) for i in N])

# Objective: minimize cost
model.add(minimize(cost))

# Constraints
model.add([EST[i] <= start_of(x[i], EST[i])] for i in N)
model.add([end_of(x[i]) <= LET[i]] for i in N)
model.add(no_overlap(x))

# PROBLEM RESOLUTION

sol = model.solve(trace_log=True, LogPeriod=1000000, TimeLimit=30)

# DISPLAY OF SOLUTION

for i in N:
    s = sol.get_var_solution(x[i])
    if s.is_absent():
        print('Task ' + str(i) + ' not scheduled')
    else:
        print('Task ' + str(i) + ' scheduled on [' + str(s.get_start()) + ',' +  str(s.get_end()) + ')')

В данных:

  • EST: самое раннее время начала задач наблюдения
  • OST: оптимальное (идеальное) время начала задач наблюдения
  • LET: самое позднее время окончания задач наблюдения
  • Д: продолжительность наблюдательных заданий
  • W: временный вес задач наблюдения (вес для расстояния до оптимального времени начала, если наблюдение запланировано)
  • P: штраф за невыполнение задач наблюдения

Исполнение выглядит так: 


 ! ----------------------------------------------------------------------------
 ! Minimization problem - 21 variables, 41 constraints
 ! LogPeriod            = 1000000
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 83.4 (before), 83.4 (after)
 !  . Memory usage      : 476.1 kB (before), 476.1 kB (after)
 ! Using parallel search with 8 workers.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed    W       Branch decision
                        0         21                 -
 + New bound is 0
 ! Using iterative diving.
 ! Using temporal relaxation.
 *      92.86000       21  0.04s        1      (gap is 100.0%)
 *      7.209000      176  0.04s        1      (gap is 100.0%)
 *      7.208000      231  0.04s        1      (gap is 100.0%)
 *      5.831000      284  0.04s        1      (gap is 100.0%)
 *      2.114000      470  0.04s        1      (gap is 100.0%)
        2.114000      470          1    1   F        -
 + New bound is 2.113788 (gap is 0.01%)
 ! ----------------------------------------------------------------------------
 ! Search completed, 5 solutions found.
 ! Best objective         : 2.114000 (optimal - effective tol. is 0.0002114)
 ! Best bound             : 2.113788
 ! ----------------------------------------------------------------------------
 ! Number of branches     : 171602
 ! Number of fails        : 9172
 ! Total memory usage     : 4.3 MB (4.2 MB CP Optimizer + 0.0 MB Concert)
 ! Time spent in solve    : 0.06s (0.06s engine + 0.00s extraction)
 ! Search speed (br. / s) : 2860024.7
 ! ----------------------------------------------------------------------------
Task 0 scheduled on [205,214)
Task 1 scheduled on [195,202)
Task 2 scheduled on [134,139)
Task 3 not scheduled
Task 4 scheduled on [252,261)
Task 5 scheduled on [153,162)
Task 6 scheduled on [106,110)
Task 7 scheduled on [44,46)
Task 8 scheduled on [167,170)
Task 9 not scheduled
Task 10 scheduled on [85,94)
Task 11 scheduled on [266,274)
Task 12 scheduled on [121,124)
Task 13 not scheduled
Task 14 scheduled on [110,117)
Task 15 scheduled on [310,312)
Task 16 scheduled on [229,232)
Task 17 scheduled on [262,266)
Task 18 scheduled on [286,290)
Task 19 scheduled on [162,164)
...