Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > C/C++/С#


Ответ
 
Опции темы Опции просмотра
Старый 23.08.2021, 22:15   #1 (permalink)
katerina00
Новичок
 
Регистрация: 23.08.2021
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Программа C++

На m одинаковых станках требуется обработать n деталей. Время
обработки детали j на любом из станков равно tj , j=1..n. Разбить
детали на m групп для обработки на m станках так, чтобы время
завершения обработки всех деталей было минимально.

Помогите, пожалуйста, с решением задачи
katerina00 вне форума   Ответить с цитированием

Старый 23.08.2021, 22:15
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Может быть решение проблемы скрывается в похожих темах

Программа
Программа на С
Программа

Старый 24.08.2021, 08:16   #2 (permalink)
AlexZir
support
 
Аватар для AlexZir
 
Регистрация: 19.08.2007
Адрес: Зея
Сообщений: 15,464
Записей в дневнике: 63
Сказал(а) спасибо: 148
Поблагодарили 178 раз(а) в 77 сообщениях
Репутация: 71264
По умолчанию

если детали одинаковые, то в каждой группе будет n%m деталей, хотя есть подозрение что всё не так очевидно и детали разные.
__________________
Убить всех человеков!
AlexZir вне форума   Ответить с цитированием
Старый 24.08.2021, 09:51   #3 (permalink)
Vladimir_S
Специалист
 
Аватар для Vladimir_S
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,718
Сказал(а) спасибо: 339
Поблагодарили 578 раз(а) в 206 сообщениях
Репутация: 112126
По умолчанию

Цитата:
Сообщение от AlexZir Посмотреть сообщение
если детали одинаковые, то в каждой группе будет n%m деталей, хотя есть подозрение что всё не так очевидно и детали разные.
Да ну, Лёша, кой уж там "одинаковые", не зря же для каждой дается время обработки. Задачка-то из серии "ой-ёй-ёй!". Даже не знаю, в каком направлении искать алгоритм — ну не тупым же перебором действовать (в таком случае счёт будет продолжаться, как выражаются поляки, "до морковкина заговенья"). Не говоря уж и С++, в коем я ни бум-бум. Хоть бы алгоритм найти!
__________________
With Mozilla Firefox - straight to communism!
Vladimir_S вне форума   Ответить с цитированием
Старый 24.08.2021, 10:13   #4 (permalink)
Vladimir_S
Специалист
 
Аватар для Vladimir_S
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,718
Сказал(а) спасибо: 339
Поблагодарили 578 раз(а) в 206 сообщениях
Репутация: 112126
По умолчанию

Впрочем, одна идея есть.

1. Находим время T обработки всех деталей НА ОДНОМ станке путём суммирования элементов массива tj.

2. Упорядочиваем массив tj по убыванию.

3. Идём по массиву "сверху вниз" (от наибольшего времени) до тех пор, пока суммарное время t1 (сумма пройденных элементов массива) не превысит значение T/m. Это будет загрузка первого станка.

4. Дальше повторяем процедуру m-1 раз, находя времена tm, и, таким образом, определим загрузку остальных станков.

Конечно, это может не быть "абсолютным минимумом" из-за самого хвоста (может даже оказаться, что последний станок не загружен вовсе!*) но, по крайней мере, что-то близкое к искомому. Можно, конечно, пытаться отработать и этот момент.
Пока так.
____________________
*Впрочем, в самом по себе таком факте ничего страшного нет. Представим себе, что у нас есть 5 деталей и 3 станка, при этом время обработки первой детали составляет 10 часов, а остальных — 2 часа. Тогда, пока будет обрабатываться первая деталь на первом станке, остальные (с запасом!) могут быть обработаны на втором станке, а третий станок не нужен.
__________________
With Mozilla Firefox - straight to communism!
Vladimir_S вне форума   Ответить с цитированием
Старый 24.08.2021, 12:06   #5 (permalink)
Николай_С
Радиоинженер
 
Аватар для Николай_С
 
Регистрация: 25.09.2012
Адрес: г.Дзержинск Нижегородской обл.
Сообщений: 23,686
Записей в дневнике: 7
Сказал(а) спасибо: 255
Поблагодарили 204 раз(а) в 64 сообщениях
Репутация: 98609
По умолчанию

М-м-м... Э-э-э...Ничего так задачка с беклнецным количеством неизвестных!
А ничего так, что имеется определённая технологическая последовательность обработки каждой детали? Например, нельзя нарезать внутреннюю резьбу не просверлив отверстие подходящего диаметра. Тут нужно сначала составить технологическую карту обработки каждого типа деталей, а уж потом распределять станки. Хотя... Если мы изучаем программирование, а не технологию... Можно и так, как предложил Владимир Игоревич.

P.s. Катюха, попадёшь к нам на форум, узнаешь много нового.
Николай_С вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Старый 24.08.2021, 13:10   #6 (permalink)
Fisher
Member
 
Регистрация: 09.01.2014
Адрес: Казань
Сообщений: 1,760
Сказал(а) спасибо: 2
Поблагодарили 2 раз(а) в 1 сообщении
Репутация: 13937
По умолчанию

АГА! Тяжёлая артиллерия подтянулась!
Цитата:
Сообщение от Николай_С Посмотреть сообщение
Тут нужно сначала составить технологическую карту обработки
Или, для начала, в условиях оговорить, что все-ли детали одинаковые или столько-то видов деталей, если видов несколько, то, хотя-бы, к примеру, оговорить процентное соотношение по трудоёмкости изготовления этих видов деталей. Думаю - как-то так. Иначе - по воде вилами.
__________________
Нешто я да не пойму? При моём-то при уму?.. Чай, не лаптем щи хлебаю! Сображаю, что к чему.
Fisher вне форума   Ответить с цитированием
Старый 24.08.2021, 13:24   #7 (permalink)
AlexZir
support
 
Аватар для AlexZir
 
Регистрация: 19.08.2007
Адрес: Зея
Сообщений: 15,464
Записей в дневнике: 63
Сказал(а) спасибо: 148
Поблагодарили 178 раз(а) в 77 сообщениях
Репутация: 71264
По умолчанию

Цитата:
Сообщение от Fisher Посмотреть сообщение
все-ли детали одинаковые или столько-то видов деталей, если видов несколько, то, хотя-бы, к примеру, оговорить процентное соотношение по трудоёмкости изготовления этих видов деталей
Ну а я о чём выше написал-то?
Цитата:
Сообщение от AlexZir Посмотреть сообщение
если детали одинаковые, то в каждой группе будет n%m деталей, хотя есть подозрение что всё не так очевидно и детали разные
__________________
Убить всех человеков!
AlexZir вне форума   Ответить с цитированием
Старый 24.08.2021, 13:25   #8 (permalink)
AlexZir
support
 
Аватар для AlexZir
 
Регистрация: 19.08.2007
Адрес: Зея
Сообщений: 15,464
Записей в дневнике: 63
Сказал(а) спасибо: 148
Поблагодарили 178 раз(а) в 77 сообщениях
Репутация: 71264
По умолчанию

Цитата:
Сообщение от Николай_С Посмотреть сообщение
Ничего так задачка с беклнецным количеством неизвестных
Да не, Николай, с точки зрения программирования "черного ящика" количество неизвестных в этой задаче всё-таки конечное и ограничивается значением n
По условию:
станков m
деталей n
время обработки одной детали tj
j выбирается из списка {1..n}, то есть для каждой детали в списке назначено своё время обработки.
Решение задачи можно свести к сортировке списка (массива) по убыванию и последующему распределению элементов по времени обработки.
Есть ещё идея одна: проссумировать элементы списка, разделить сумму на количество станков, тем самым получаем среднюю нагрузку на 1 станок, потом перебрать значения времени обработки деталей в сравнении с вычисленной средней нагрузкой.
__________________
Убить всех человеков!
AlexZir вне форума   Ответить с цитированием
Старый 24.08.2021, 14:25   #9 (permalink)
Николай_С
Радиоинженер
 
Аватар для Николай_С
 
Регистрация: 25.09.2012
Адрес: г.Дзержинск Нижегородской обл.
Сообщений: 23,686
Записей в дневнике: 7
Сказал(а) спасибо: 255
Поблагодарили 204 раз(а) в 64 сообщениях
Репутация: 98609
По умолчанию

Цитата:
Сообщение от Fisher Посмотреть сообщение
АГА! Тяжёлая артиллерия подтянулась!
И это ещё Македоныча нет снами. Он бы сейчас точно "развернул" на примере курей.

Детали д.б. разнотипные, станки тоже. Иначе задача не имеет смысла. Так вот и надо бы определиться с типами.
Николай_С вне форума   Ответить с цитированием
Старый 24.08.2021, 16:17   #10 (permalink)
Vladimir_S
Специалист
 
Аватар для Vladimir_S
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,718
Сказал(а) спасибо: 339
Поблагодарили 578 раз(а) в 206 сообщениях
Репутация: 112126
По умолчанию

Коля, ну что за трёп, ей-Богу? Задачка всё-таки на программирование, а не на составление реальной технологической карты.
Цитата:
Сообщение от Николай_С Посмотреть сообщение
Детали д.б. разнотипные
Так и есть. Характеризуются разными (данными!) временами обработки.
Цитата:
Сообщение от Николай_С Посмотреть сообщение
станки тоже
Это ещё зачем? По условию задачи станки одинаковые, смысл задания — оптимально их загрузить.
Цитата:
Сообщение от Николай_С Посмотреть сообщение
Иначе задача не имеет смысла.
Очень даже имеет. Условия вполне достаточны для однозначного решения.
__________________
With Mozilla Firefox - straight to communism!
Vladimir_S вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 07:27.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.