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

Теорема 1. В комбинаторном аукционе вальрасовское равновесие существует тогда и только тогда, когда оптимум IP равен оптимуму LPR. Размер задачи LP линейно зависит от общего числа XOR-заявок.

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

Теперь рассмотрим задачу планирования заданий, в которой все оценочные функции клиентов линейны. Предположим, что в момент времени t = 0 на одной машине запускается n заданий, время выполнения j-го задания составляет sj 2 N+, а вес wj > 0. Целью планирования является минимизация взвешенного времени завершения: Pni=1 witi, где ti – время завершения задания i. Такая задача называется задачей MWCT (минимальное взвешенное время завершения).

Теорема 3. В одномашинной задаче планирования заданий MWCT вальрасовское равновесие всегда существует, если m > EM + A, где m – общее количество процессорного времени, EM = Pin=1 si и A = maxk fskg. Равновесие может быть вычислено за полиномиальное время.