Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
#1

В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) - C++

23.07.2013, 21:53. Просмотров 1813. Ответов 25
Метки нет (Все метки)

Есть задачка:
Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При i=1,..,M задание i требует ti времени для его выполнения. Определить оптимальный порядок заданий, т.е. такой, который дает возможность завершить все задания в кратчайшее время.
Я прикинул, и у меня есть 2 способа решения задачи, но 1 долгий, а второй рассматривает не все варианты.
1) Полный перебор перестановок, и вывод только тех последовательностей, время выполнения которых минимально, но допустим при 14 задачах мы имеем 87 178 291 200 вариантов последовательностей и они будут очень долго перебираться.

2) Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2013, 21:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) (C++):

Разработать программную систему для имитации процесса обслуживания заданий в вычислительных системах - C++
Для вычислительной системы (ВС) с одним процессором и мультипрограммным режимом выполнения поступающих заданий требуется разработать...

Нужно написать программу для составления расписания - C++
всем привет) нужно сделать программу для составления расписания в универе, к примеру для одной - двух групп на неделю, и все это потом...

Посоветуйте программу для составления блок схем по коду программы. - C++
Здравствуйте, подскажите пожалуйста кто работал с такими программами. Я лично пользовался Code Visual to Flowchart (программа хорошая, но...

Разработать программу для составления списка неуспевающих студентов - Pascal ABC
Разработать программу для составления списка неуспевающих студентов. Текст документа я написал а вот программу немогу написать. Помогите...

Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету равна средне-арифмитической по трем циклам - Turbo Pascal
Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету равна средне-арифмитической по трем циклам....

Разработать приложение для автоматизации составления тестов - Visual Basic
Разработать приложение для автоматизации составления тестов: Пароль: 123 Помогите пожалуйста сделать 1) сложение строк с...

25
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:18 #2
Цитата Сообщение от DaskOFF Посмотреть сообщение
Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.
Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.
1
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:27  [ТС] #3
Цитата Сообщение от Dani Посмотреть сообщение
Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.
процессоры одинаковые, следовательно, очередная задача выполняется одинаковое время на любом из них

Перестановки. Допустим изначальная последовательность загрузки задач следующая: {1, 2, 3, 4, 5}
вот варианты перестановок(всего их будет 5! = 120) : {1, 2, 3, 5, 4} {1, 2, 5, 3, 4} {1, 2, 5, 4, 3} и т.д.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:29 #4
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
1
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:39  [ТС] #5
Цитата Сообщение от Dani Посмотреть сообщение
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
ну как, получаю перестановку и в этом порядке добавляю задачи на первый освобождающийся процессор
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:41 #6
Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?
1
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:50  [ТС] #7
Цитата Сообщение от Dani Посмотреть сообщение
Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?
ограничений нет, в том то и дело, заданий может быть 100, именно поэтому я и в растерянности, первый находит все варианты, но очень долго для 100 он несколько лет наверно будет подбирать последовательности.

а по моему варианту если будет (N - порядок задач, а T время их выполнения)
N = {3, 4, 1, 2}
T = {8, 8, 4, 3}
то тут уже получается 2 решения
1 - {3, 4, 1, 2}
2 - {4, 3, 1, 2}

вот как эти все варианты перебрать из полученной последовательности N я не знаю, а если узнаю не факт, что это будет быстро, хотя и быстрее, чем порождать все перестановки
0
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 07:03 #8
все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша):
сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример:
4 7 2 5 7 9 2 1 5 6 8 3 2 7 8
9 8 8 7 7 7 6 5 5 4 3 2 2 2 1
первый процессор получил: 9 7 4 3 2
второй процессор получил: 8 7 6 2
третий процессор получил: 8 7 5 2 1
вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше)
1
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
24.07.2013, 07:08 #9
ваша задача максимизировать количество таких моментов ti, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно.
для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени.
то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N2), решается динамикой. N - количество процессов.
1
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 07:16 #10
Цитата Сообщение от salam Посмотреть сообщение
это требует O(N2), решается динамикой.
вы уверены в том что нельзя быстрее?
1
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 07:56 #11
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным.
Посмотрите книгу

Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)

эта задача из темы экстремальных задач на графах.
4
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
24.07.2013, 13:08 #12
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
я дал грубую оценку. сейчас попробую точнее определить сложность решения, которое я подразумевал.
другого, более быстрого, решения этой задачи лично я не вижу. не могу отрицать, что оно существует. но вариант "отсортировать и попорядку..." точно не полностью корректный.

Добавлено через 16 минут
Цитата Сообщение от Thinker Посмотреть сообщение
Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)
эта задача из темы экстремальных задач на графах.
я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
24.07.2013, 13:12 #13
Thinker, что значит "экстремальные задачи"? np-полные?
1
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
24.07.2013, 13:29 #14
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
в общем получается что-то вроде O(N * SumT), где N - количество процессов, SumT - суммарное время их выполнения. в масштабах этой задачи время маленькое.
1
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 13:37 #15
Цитата Сообщение от salam Посмотреть сообщение
O(N * SumT)
а что тут делает SumT?
а можно алгоритм увидеть?

Добавлено через 52 секунды
странно просто, если время задач измеряется в секундах то ок, если то же самое только в годах, то что-то не очень
1
24.07.2013, 13:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2013, 13:37
Привет! Вот еще темы с ответами:

Разработать программу для сохранения списка покупателей бытовой техники в виде файла - Visual C++
#8 с файлами у меня проблемы, а написать нужно. Помогите, пожалуйста. Правила Форума: Перепечатывайте задание на форум ...

Волшебный пинок в правильном направлении - Java
Помогите разобраться с ошибкой, я учусь пока и мои потуги не смогли решить проблему и что делать я не знаю,(плохо искал, наверное), вот...

Направьте, пожалуйста, в правильном направлении - Java EE
На данный момент в Java я нахожусь только на начальном уровне, до Java EE ещё не добрался. Конечная цель создание сайта с использованием...

Разработать приложение для генерации (проверки) заданий типа А13 - Lazarus
Подскажите, как решить это задание? Наиболее интересует используемая таблица. Разработать приложение в среде VBA (или Lasarus) для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru