Перебор: найти порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время

Помогите пожалуйста с задачкой на Прологе:
Имеется n деталей и m станков. Каждая деталь характеризуется временем обработки. Станок обрабатывает любую деталь сразу, все станки одинаковы. Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.
Знаю только, что решается перебором

0

Сообщение от aptem33 Знаю только, что решается перебором

А подробней, я вот перебора не вижу...

Добавлено через 7 минут

Сообщение от arlat я вот перебора не вижу

Да я вообще ничего не вижу...
"Станок обрабатывает любую деталь сразу, все станки одинаковы."
Простая сортировка деталей по времени и есть ответ.

Добавлено через 2 минуты

Сообщение от aptem33 Определить порядок обработки деталей на станках

ну разве в детали добавить кроме времени номер станка, после сортировки деталей по времени одна простая рекурсия

0

Сообщение от arlat Простая сортировка деталей по времени и есть ответ.

Число станков и деталей не одинаково, разве достаточно простой сортировки?
Допустим отсортируем по убыванию, а дальше что? Берём деталь с наименьшим временем и отдаём на обработку на тот станок который в данный момент свободен? Ох, что-то тяжело мне с логическим программированием.

Сообщение от arlat А подробней, я вот перебора не вижу...

Я говорю перебор потому что задача расположена в разделе "перебор", а вот как применить его я и сам не понял.

0

Дайте пример спецификации данных, что на входе и что на выходе.
Собственно, не понятно как в принципе можно решать задачу без спецификации.
И на каких данных тестировать, опять-таки...

0

Сообщение от arlat Дайте пример спецификации данных, что на входе и что на выходе.

К сожалению ничего такого не указано, но в качестве примера решения задач такого типа приводится вот такой код:
А вот рекомендации:
Выполняйте аналогично примеру в материалах лекции, начи-
ная с формальной постановки задачи как задачи CSP. Для задачи
о счастливых билетах вектор переменных V — это набор пере-
менных [A,B,C,D,E,F], Области значений всех переменных в
первоначальной постановке — числа из диапазона [0,1,2,…,9],
поэтому достаточно было запрограммировать всего один генера-
тор gen/1.
Буду очень благодарен, если Вы мне поможете, если не решить, так хотя бы понять как

0

Сообщение от aptem33 Ох, что-то тяжело мне с логическим программированием.

Да нет здесь никаких особых подходов.
1. сортируем по времени список деталей, по возрастанию
2. достаем из списка деталей и дополняем номером станка: 1 деталь - 1 время - 1 станок, ..., m деталь - m время - m станок, m+1 деталь - m+1 время - 1 станок и т.д. до n детали
на бейсике, право дело, можно написать, а на Прологе это уже надо хоть начать что-то, дальше подскажет кто-нибудь здесь

Добавлено через 2 минуты

Сообщение от aptem33 аналогично примеру в материалах лекции

плохой пример, по ходу лектор сам не очень в Прологе

Добавлено через 1 минуту

Сообщение от aptem33 К сожалению ничего такого не указано

Самостоятельно пример сделайте, на листочке, образно говоря.

Добавлено через 1 минуту
Да, первичную реализацию можно выкатить, но студент тоже должен думать, а не тупо спихивать материал.

0

Сообщение от arlat плохой пример, по ходу лектор сам не очень в Прологе

И я вот не могу связать пример с задачей, может для начала на Яве написать, а потом посмотрим, может что в голову придёт))

0

Сообщение от aptem33 может для начала на Яве написать

На листочке нарисуйте, без шуток.

Добавлено через 3 минуты
Кстати, да, на каком Прологе идет обучение?

0

Сообщение от arlat На листочке нарисуйте, без шуток.

Сейчас буду рисовать)

Сообщение от arlat Кстати, да, на каком Прологе идет обучение?

SWI-Prolog, хотя думаю, что это не принципиально

0

Сообщение от aptem33 SWI-Prolog, хотя думаю, что это не принципиально

Это как сказать У SWI есть такая вещь как онлайн

Добавлено через 5 минут

Сообщение от arlat У SWI есть такая вещь как онлайн

А режим Notebook это просто находка для выполнения и оформления лаб.

1

Сообщение от arlat Это как сказать У SWI есть такая вещь как онлайн

Спасибо) Протестирую

0

Ну явно в постановке задачи полная чушь

Добавлено через 5 минут
Вот после таких спецификаций и постановок задач, такие потом реализации и получаются.

Добавлено через 7 минут
Где здесь задача удовлетворения ограничений (Constraint Satisfaction Problem — CSP), ну помогите мне тупому, не вижу.

Добавлено через 17 минут
Вот хотя бы добавить:
m станков запускаются на рабочую смену;
время обработки соответствует расходу энергии;
обработать n деталей так, чтобы за каждую смену суммарный расход энергии был близок к оптимальному.
И то, надо бы еще как-то развернуть, что такое оптимальный расход энергии:
при обработке деталей каждой сменой перепад в суммарном расходе энергии за смену при переходе от смены к смене должен стремится к минимальному.
Но это не про минимальное время, и не про сортировку, тут хоть как-то уже похоже на задачу удовлетворения ограничений.
Это так, нахрапом... Формулировка таких задач должна очень тщательно прорабатываться.

Добавлено через 2 минуты

Сообщение от aptem33 Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.

А формально типа да, великий и могучий русский язык, только за кадром остался час лекции

Добавлено через 6 минут

Сообщение от aptem33 в качестве примера решения задач такого типа приводится вот такой код

ну да, здесь идет подбор, но чего именно, - из списка чисел подобрать таких шесть, где сумма первых трех из них будет равна сумме оставшихся трех. Удача (lucky), если генерация (gen) соответствует ограничению (p).

Добавлено через 8 минут
вот откуда уши торчат

Добавлено через 5 минут
Рекомендация прежняя, показать на листочке использование ограничения в этой задаче, на самых простых данных, типа два станка, и, ну там 6-8 деталей.

1

arlat, Вам тоже задача покоя не даёт?)

Добавлено через 25 минут
arlat, Вот кстати, нашёл в другой книге:
Имеется n деталей и m станков. Каждая деталь характеризуется
временем обработки (для каждой детали время обработки на всех стан-
ках одинаково). Станок в каждый момент времени обрабатывает только
одну деталь. Детали на каждом станке обрабатываются последовательно.
Необходимо определить такое назначение деталей на станки, чтобы вре-
мя окончания обработки последней обрабатываемой детали было бы ми-
нимальным.
Рекомендация: вершиной дерева перебора будет n – вектор. Тогда
значение i-ой координаты этого вектора будет совпадать с номером стан-
ка, на который мы назначили i-ую деталь. В корень дерева мы положим
0-вектор.

Добавлено через 1 минуту
Может это что-то даст, но точно не мне)

Добавлено через 2 минуты
http://edu.usfeu.ru/Uploads/Me... 031_54.pdf

0

Единственное, что могу предположить, это такой формат входных данных:
details=[5,10,2,17,4,5,9,22], где цифры - это время обратобки деталей. То есть, у нас 8 деталей, для каждой свое время обработки.
Станков, допутим, 2.
Тогда решение выглядит довольно просто(если перебором):
- на первый станок одну деталь, на второй все остальные. считаем наибольшее время из двух станков, комбинацию деталей по станкам, сохраняем.
- на первый станок одну деталь, но другую....
- ....
- на первый станок 2 детали...
- на первый станок 2 детали, но другие...
....
в результате наименьшее время и комбинация деталей по станкам, нам доступны.
по временам вычисляем порядковые номера деталей из входного списка, выдаем результат.
можно с самого начала зазипать два списка - входной и [1,2,..] чтобы вконце проще было определять порядковые номера правильного ответа.

0

Сообщение от aptem33 чтобы время окончания обработки последней обрабатываемой детали было бы минимальным

+

Сообщение от aptem33 Рекомендация

это совсем не то же самое, что

Сообщение от aptem33 когда все детали будут обработаны за минимальное время

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

Добавлено через 9 минут

Сообщение от arlat тут да, есть о чем подумать

опять-таки нужно примерно знать, что препод хочет.
перебором, ну очень плохо, тут какую-то методику надо применять, я не знаю какую, но точно не просто перебором.
на ум приходит, что после сортировки по возрастанию, закидывать детали по очереди min время / max время, как закончились станки, следующий проход наоборот max время / min время.
но все это голословно, надо экспериментировать в попытке найти оптимальное решение, в чем и состоит применение методик искусственного интеллекта

Добавлено через 12 минут
Или сначала сложить время обработки всех деталей и разделить на количество станков, найдем среднее.
При составлении векторов для станка, останавливать очередную итерацию, если сумма вектора больше среднего.
Или это не среднее должно быть, а другим способом вычисленное ограничение, ограничение (!), в чем и есть суть, - уйти от полного перебора.

Добавлено через 4 минуты

Сообщение от arlat это можно уйти в переполнение стека легко

и времени выполнения тоже

Добавлено через 8 минут
Нет min/max не очень.
Можно по возрастанию, исключаю детали из списка в станки, потом по убыванию оставшегося списка деталей, потом опять по возрастанию.
Теоретически, строго минимальное все равно надо искать на полном переборе, но какое-то ограничение должно быть, а может и не одно.

Добавлено через 1 минуту

Сообщение от aptem33 Вам тоже задача покоя не даёт?

Да не особо, просто это хоть что-то, по сравнению с той лабудой, которую здесь выкладывают, как задачи

0