spamsink: (Default)
[personal profile] spamsink
Имеется несколько принтеров с одинаковыми, кроме скорости печати, характеристиками, и одна очередь заданий на печать. Скорости известны. Покажите, что оптимальный алгоритм назначения принтеров для выполнения заданий "несправедлив", а "справедливый" - неоптимален.

Date: 2007-11-17 07:45 pm (UTC)
From: [identity profile] kdv2005.livejournal.com
Я не понял вопрос. Что именно нужно показать?
Правильно ли я понимаю, что оптимальный алгоритм -- давать задание на печать самому быстрому из свободных принтеров? Тогда, конечно, самый быстрый принтер будет печатать больше всех. Он, вдобавок и освобождается в среднем быстрее других, вот ему и подбрасывают.

А что такое справедливый алгоритм?

Date: 2007-11-17 08:59 pm (UTC)
From: [identity profile] spamsink.livejournal.com
Оптимальный алгоритм должен максимизировать пропускную способность группы принтеров, включая периоды, когда не все принтеры используются, а справедливый - минимизировать недовольство пользователей (рассмотреть недовольство временем ожидания завершения задания и порядком выполнения заданий). Справедливость с точки зрения принтера не интересует. :)

Date: 2007-11-17 10:18 pm (UTC)
From: [identity profile] kdv2005.livejournal.com
По-моему, не зная, кто, насколько и как часто грузит принтеры, а также не имея utility function их недовольства (я хотел было сказать функция полезности, но в приложении к неудовольствию как-то по идиотски звучит) о справедливости говорить трудно.

А оптимальным должен быть алгоритм жадины, который я и описал. Или я ошибаюсь?

Date: 2007-11-17 11:19 pm (UTC)
From: [identity profile] spamsink.livejournal.com
Оптимальным мне кажется алгоритм, который выбирает, с учетом уже стоящих в очереди заданий, тот принтер, на котором поступившее задание завершится раньше всего. А справедливым - обеспечивающий последовательность завершения заданий, которая была бы, если бы все принтеры были так же быстры, как самый быстрый (+ и их было бы бесконечно много).

Date: 2007-11-18 01:52 am (UTC)
From: [identity profile] kdv2005.livejournal.com
По-моему, в оптимальном алгоритме, при добавлении задания в непустую очередь могут меняться предписания для всех заданий. Скажем, если в голове очереди стоит большое задание, а за ним несколько маленьких, то (в некоторых случаях) имеет смысл их отправить на печать первыми и подождать пока освободиться более производительный принтер, чтобы на него уже послать большое задание. Наверное, можно подобрать параметры входящего потока заданий можно так, чтобы имело смысл придерживать большие задания даже при наличии свободных принтеров, если они медленные. Что-то я запутался, не вижу, как это учесть в общем алгоритме, без дополнительных данных. Все-таки, какова постановка вопроса? Мы оптимизируем наихудший случай? Типичный? А про справедливый я пока еще не думал.

Date: 2007-11-18 02:03 am (UTC)
From: [identity profile] spamsink.livejournal.com
По-моему, в оптимальном алгоритме, при добавлении задания в непустую очередь могут меняться предписания для всех заданий.

Возможно. Я, правда, имел в виду гораздо более простой способ показать желаемое.

Date: 2007-11-18 02:25 am (UTC)
From: [identity profile] kdv2005.livejournal.com
Я прошу прощения. Я тормоз, и меня обычно увлекают не поиски изящного трюка, решающего головоломку, а возможность досконально разобраться в вопросе. Я очень ценю тех, кто умеет решать задачи первым способом (и их решения вызывают мое искреннее восхищение), но сам обычно произвожу на свет занудство вроде вышеприведенного.

Хотя, на мой взгляд, хорошо сидели.

Date: 2007-11-18 02:40 am (UTC)
From: [identity profile] spamsink.livejournal.com
Я не знаю, рассматривалась ли эта задача где-либо в общем виде (было бы интересно когда-нибудь узнать), но то, что в общем случае оптимальный алгоритм != справедливому, легко показывается на примере N=1.

Date: 2007-11-18 02:26 am (UTC)
From: [identity profile] kdv2005.livejournal.com
Кстати, в задаче про яйца появилась ссылка на ответ и решение.

Profile

spamsink: (Default)
spamsink

June 2025

S M T W T F S
1 2 34567
891011121314
15161718192021
22232425262728
2930     

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 5th, 2025 06:07 pm
Powered by Dreamwidth Studios
OSZAR »