Программа C++
На m одинаковых станках требуется обработать n деталей. Время
обработки детали j на любом из станков равно tj , j=1..n. Разбить детали на m групп для обработки на m станках так, чтобы время завершения обработки всех деталей было минимально. Помогите, пожалуйста, с решением задачи |
если детали одинаковые, то в каждой группе будет n%m деталей, хотя есть подозрение что всё не так очевидно и детали разные.
|
Цитата:
|
Впрочем, одна идея есть.
1. Находим время T обработки всех деталей НА ОДНОМ станке путём суммирования элементов массива tj. 2. Упорядочиваем массив tj по убыванию. 3. Идём по массиву "сверху вниз" (от наибольшего времени) до тех пор, пока суммарное время t1 (сумма пройденных элементов массива) не превысит значение T/m. Это будет загрузка первого станка. 4. Дальше повторяем процедуру m-1 раз, находя времена tm, и, таким образом, определим загрузку остальных станков. Конечно, это может не быть "абсолютным минимумом" из-за самого хвоста (может даже оказаться, что последний станок не загружен вовсе!*) но, по крайней мере, что-то близкое к искомому. Можно, конечно, пытаться отработать и этот момент. Пока так. ____________________ *Впрочем, в самом по себе таком факте ничего страшного нет. Представим себе, что у нас есть 5 деталей и 3 станка, при этом время обработки первой детали составляет 10 часов, а остальных — 2 часа. Тогда, пока будет обрабатываться первая деталь на первом станке, остальные (с запасом!) могут быть обработаны на втором станке, а третий станок не нужен. |
М-м-м... Э-э-э...Ничего так задачка с беклнецным количеством неизвестных!
А ничего так, что имеется определённая технологическая последовательность обработки каждой детали? Например, нельзя нарезать внутреннюю резьбу не просверлив отверстие подходящего диаметра. Тут нужно сначала составить технологическую карту обработки каждого типа деталей, а уж потом распределять станки. Хотя... Если мы изучаем программирование, а не технологию... Можно и так, как предложил Владимир Игоревич. P.s. Катюха, попадёшь к нам на форум, узнаешь много нового. ;) |
АГА! Тяжёлая артиллерия подтянулась!
Цитата:
|
Цитата:
Цитата:
|
Цитата:
По условию: станков m деталей n время обработки одной детали tj j выбирается из списка {1..n}, то есть для каждой детали в списке назначено своё время обработки. Решение задачи можно свести к сортировке списка (массива) по убыванию и последующему распределению элементов по времени обработки. Есть ещё идея одна: проссумировать элементы списка, разделить сумму на количество станков, тем самым получаем среднюю нагрузку на 1 станок, потом перебрать значения времени обработки деталей в сравнении с вычисленной средней нагрузкой. |
Цитата:
Детали д.б. разнотипные, станки тоже. Иначе задача не имеет смысла. Так вот и надо бы определиться с типами. |
Коля, ну что за трёп, ей-Богу? Задачка всё-таки на программирование, а не на составление реальной технологической карты.
Цитата:
Цитата:
Цитата:
|
Часовой пояс GMT +4, время: 07:12. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.