Вход через социальные сети

  • 03.07.2012, 20:10
    0 up down
    Сообщение
    Разговор с заказчиком

    Разговор с заказчиком был очень смешным. Собственно, после этого разговора заказчиков я уже не видела, а необходимую информацию получала от коллег по хоздоговору.
    Появляется заказчик, в дорогом костюме, с ароматом французского парфюма (парфюм, к слову, был хороший), начальник какого-то отдела.
    - Вот это наш математик-постановщик, Светлана Ильдаровна, закончила мехмат МГУ...
    На автопилоте подумала. что шеф попутал, кого кому нужно представлять, но сказала "очень приятно", в ответ получила "маленький английский кивок". Так что заказчик остаётся анонимом Biggrin
    Когда дошло до дела, попыталась сделать 2 вещи.
    1. Объяснить заказчику, что нельзя формулировать задачу как обнаружение ВСЕХ орциклов в графе производственных заданий. Потому что задача класса E, циклов может оказаться экспоненциальное количество от размерности графа (граф состоял из 62000 дуг), т.е. мы запрашиваем большую информацию. чем можем использовать. А на самом деле мы просто хотим разомкнуть все орциклы путём удаления некоторого множества дуг за линейное время. Это сделать не удалось, поэтому в названии хоздоговора так и осталось "обнаружение циклов".
    2. В связи с незнанием Оракла выяснить, что является дугами, из которых этот граф строится. Заказчик сказал, что он не готов ответить на мой вопрос - приходите, когда будете готовы.

    Через день заказчик подготовил и распечатал целую презентацию, оказалось, что дугами являются производственные задания типа Позиция1/Склад1 -> Позиция2/Склад2, и входными данными для моего "пробника" будет список таких дуг.

    В окончательном виде техзадание приняло следующий вид.
    1. Пронумеровать вершины графа Позиция/Склад натуральными числами.
    2. Для представления графа создать динамическую структуру данных "списки инцидентности".
    3. В построенном графе обнаружить и напечатать все орциклы Biggrin за линейное время, конечно.
  • 03.07.2012, 20:33
    0 up down
    Сообщение
    Может оно и интересно с точки зрения математики, а практически выглядит сомнительно.
    В нормально спроектированной системе замкнутых циклов, ИМХО, не должно быть.
    Насколько непрерывным не было бы планирование, в системе всё равно есть дискретные события - поступление сырья, выход из строя оборудования и т.п.
    Произведённый брак - такое же дискретное событие. Условно говоря оператор жамкает кнопочку и вместо готовой продукции появляется сырьё спец. вида, планировать надо заново.
  • 03.07.2012, 21:24
    0 up down
    Сообщение
    Это недостаток Оракла, разумеется, что процедура расчёта себестоимости предполагала, что граф заданий является ациклическим. Вроде бы в более новых версиях он устранён.
    Вероятно, эта задача возникает ещё где-то. В интернете часто задают вопрос "Как найти фундаментальные ориентированные циклы".
    ЗЫ. Я просто выполняю просьбу модератора Smile

    Математическая постановка задачи

    После разговора с заказчиком возник некий когнитивный диссонанс - в договоре прописано обнаружение и печать всех орциклов, а я собираюсь печатать множество "обратных дуг", после удаления которых граф становится ациклическим. И для каждой обратной дуги печатать ровно один орцикл, который она замыкает. Однако все сомнения разрешил коллега, словами "на заборе тоже написано..."

    Математическая постановка задачи

    Производственные задания вида (Позиция_1|Склад_1) (Позиция_2|Склад_2),
    участвующие в расчете себестоимости, образуют множество E дуг (или ориентированных ребер) ориентированного графа G = . Множество вершин V состоит из пар вида (Позиция|Склад).
    Для машинного представления G ориентированного графа используются списки инцидентности следующих вершин, которые в алгоритме будут обозначаться L.
    Дано. Ориентированный граф G, заданный списками инцидентности L.
    Вопрос. Напечатать множество обратных дуг, для каждой дуги один замыкаемый ею цикл.
    Алгоритм. Поиск в глубину.
    Вычислительная сложность. O(nm).

    Описание поиска в глубину находится здесь
    http://magazine.sources.ru/2010/03/algoritm_graf/

    Демонстрационная программа в прикреплённом файле





    ______Oracle.rar
  • 04.07.2012, 01:04
    0 up down
    Сообщение
    Svetlana Fainshtein в 3.7.2012, 10:30 написал(а): link

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


    Процент брака предполагается малым. В таком случае достаточно провести оптимизацию без этих обратных дуг. Дальше при желании можно провести итерационную оптимизацию вместе с этими дугами, считая что они имеют константу на входе.
  • 04.07.2012, 01:31
    0 up down
    Сообщение
    Их процедура (расчёта себестоимости) в случае зацикливании действительно запускалась несколько раз. В хоздоговоре был текст "не более 10 минут на один проход", т.е. они не ожидали, что всё можно сделать за один проход.

    Оракл не годится для планирования металлургического производства, никто, кроме нашего комбината, им не пользуется. Что касается процента брака, то прокат в принципе не возможен без брака. Решала другую задачу, про планирование очерёдности проката, множественный многокритериальный коммивояжер. Там как ни разбивай слябы по последовательностям, обязательно будут нарушены какие-то технологические ограничения - переход от широкого к узкому, от тонкого к толстому и т.д., поэтому решение изначально приходится искать в области недопустимых решений, с нарушением ограничений, т.е. браком.
  • 01.07.2016, 01:11
    0 up down
    Сообщение

    Swetlana в 03.07.2012, 19:30 написал(а): link
    Для устранения такой ситуации необходимо разработать процедуру обнаружения циклов в производственных заданиях.

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