Пожалуйста, помогите в общем методе решения задач планирования производства. Информация дана ниже.

Добрый день. Вопрос мой будет касаться практической задачи пологистике (исследованию операций).
Суть задачи такова: завод выпускает продукцию 8 видов, при переходе от изготовления i-го вида продукции к j-му необходимо определенное время (задано в условии). Также известна продолжительность изготовления каждой из видов конструкций. В плановый период необходимо выполнить определенное количество конструкций каждого вида. Задана продолжительность бесперрывной работы оборудования при изготовления каждой из конструкции.
Необходимо определить очередность выпуска продукции, при которой общее время их изготовления будет минимальным.
Пожалуйста, помогите с составлением математическом модели и подскажите метод решения подобных задач (планирования производства).
Насколько я понимаю, количество конструкций в плановый период это ограничение. А вот как составить целевую функцию, не могу понять.
И еще: эту задачу можно решить методом ветвей и границ?

Примечание:
пожалуйста, если не сложно приведите алгоритм на языке С. К тому же, решение задачи коммивояжера перебором или методом ветвей и границ технически не подходит.

Ответы:

Odomontois

Уважаемый, это классическая задача комивояжёра.
В данном случае имеем полносвязный граф, где продукции - вершины, рёбра имеют вес равный времени перехода.
Найти путь, проходящий через все вершины, имеющий минимальный вес.
Решается она, в общем, случае только перебором, т.к. относится к классу NPC
Но в данном случае перебор, учитывая ничтожное кол-во вершин вполне приемлем.
Классический алгоритм таков - в некой хешированной структуре хранятся на i-м шаге пары
из числа k - последней продукции выпущенной заводом и двоичного вектора, характеризующего какие товары уже выпущены.
Им соответствую числа - минимальное время, требуемое на выполнение данного.
И строим новую такую структуру, добавляя по одному ещё недобавленному товару.
После 8-го шага выбираем из 8-ми получившихся элементов, имеющий минимальную величину.
Если надо, могу привести код на С Java C# Python ABAP или какой вам там понравится, не считая паскаля.

Odomontois

Уважаемый, это классическая задача комивояжёра.
В данном случае имеем полносвязный граф, где продукции - вершины, рёбра имеют вес равный времени перехода.
Найти путь, проходящий через все вершины, имеющий минимальный вес.
Решается она, в общем, случае только перебором, т.к. относится к классу NPC
Но в данном случае перебор, учитывая ничтожное кол-во вершин вполне приемлем.
Классический алгоритм таков - в некой структуре данных хранятся на i-м шаге пары
из числа k - последней продукции выпущенной заводом и двоичного вектора, характеризующего какие товары уже выпущены.
Им соответствую числа - минимальное время, требуемое на выполнение данного.
И строим новую такую структуру, добавляя по одному ещё недобавленному товару.
После 8-го шага выбираем из 8-ми получившихся элементов, имеющий минимальную величину.
Если надо, могу привести код на С Java C# Python ABAP или какой вам там понравится, не считая паскаля.

16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

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

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.