2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Как составить расписание ?
Сообщение10.07.2014, 11:55 
Есть множество заданий $\mathbb{J}$, которые должны быть выполнены. Для заданий заданы:
- $w_j, j \in \mathbb{J}$ - важность (вес)
- $[t_s,t_f]_j, j \in \mathbb{J}$ - директивный период выполнения.
Есть множество ресурсов $\mathbb{I}$, которые можно задействовать для выполнения заданий. Для ресурсов заданы:
- $c_i(t), i \in \mathbb{I}$ - стоимость как функция времени
- $\gamma_{ij}, i \in \mathbb{I}, j \in \mathbb{J}$ - средняя интенсивность выполнения задания $j$ ресурсом $i$
- $p_{ij}(t)= 1-e^{-t\gamma_{ij}}, i \in \mathbb{I}, j \in \mathbb{J}$ - вероятность выполнения задания $j$ ресурсом $i$ за время $t$
- $u_{jik}, j \in \mathbb{J}, i,k \in \mathbb{I}$ - время переналадки ресурса $j$ с задания $i$ на задание $k$

Необходимо распределить ресурсы по заданиям (составить расписание) так, чтобы максимизировать сумму мат. ожиданий, при этом на одно и то же задание можно распределить несколько ресурсов при этом интенсивность выполнения задания есть сумма интенсивностей. Прерывания заданий не допускаются. Переключения ресурсов должны учитывать время переналадки:
$[x,y]_{ij}, i \in \mathbb{I}, j \in \mathbb{J}$ - искомый период обслуживания задания $j$ ресурсом $i$

Основной критерий оптимизации - максимизация суммы мат.ожиданий:
$\mathbb{M}= \sum_{j \in \mathbb{J}}M_j= \sum_{j \in \mathbb{J}}w_j(1-e^{-\sum_{i \in \mathbb{I}}(\|[x,y]_{ij}\|\gamma_{ij})}) \to \max$

Дополнительный критерий- минимизация по стоимости:
$\mathbb{C}= \sum_{j \in \mathbb{J}, i \in \mathbb{I}}(c_i(\|[x,y]_{ij}\|)) \to \min$

Порядок количества заданий и ресурсов $10^3$. Полный перебор нереален даже с дискретным временем. Пробовал линейное и динамическое программирование, но для общего случая найти решения не получается. Прошу помощи, help!

 
 
 
 Re: Как составить расписание ?
Сообщение10.07.2014, 23:34 
А «порядок» количества элементов в $u_{jik}$ равен $10^9$ ?

Задачу, вероятно, можно сформулировать как "частично-целочисленную нелинейную", но решить ее будет несколько затруднительно...

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group