Ценообразование процессорного времени: различия между версиями

'''Теорема 2. Задача определения существования вальрасовского равновесия в задаче планирования заданий для процессора является NP-трудной в сильном смысле.'''

Теперь рассмотрим задачу планирования заданий, в которой все оценочные функции клиентов линейны. Предположим, что в момент времени t = 0 на одной машине запускается <math>n</math> заданий, время выполнения j-го задания составляет <math>s_j \in \mathbb{N}^+</math>, а вес <math>w_j \ge 0</math>. Целью планирования является минимизация взвешенного времени завершения <math>\sum_{i = 1}^n w_i t_i</math>, где <math>t_i</math> – время завершения задания <math>i</math>. Такая задача называется задачей MWCT (минимальное взвешенное время завершения).

'''Теорема 4. Если существует вальрасовское равновесие в задаче планирования заданий, то оно может быть приведено к равновесию с последовательным распределением и невозрастающим вектором равновесных цен.'''