Вход | Регистрация
 

Подскажите алгоритм или где почитать как распределить по очередям.

Подскажите алгоритм или где почитать как распределить по очередям.
Я
   RomaH
 
17.10.19 - 07:27
Суть
есть последовательно по одному наполняемый стек "пациентов"

у каждого пациента есть стек "кабинетов" которые он должен пройти
некоторые кабинеты не могут быть пройдены пока не пройдены другие кабинеты из стека

у каждого кабинета есть "выделенные явки" - некая приблизительная сетка которая строится на исторических данных
например терапевт принимает одного пациента за 7 минут, невролог за 8
есть начало работы кабинета, и окончание

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

ну и соответственно сетка приема должна быть максимально плотно занята.
 
 
   Garykom
 
1 - 17.10.19 - 07:30
(0) Диаграммы ганта, в 8-ке через бизнес процессы можно.
   Garykom
 
2 - 17.10.19 - 07:32
(1)+ Это реализация а вот сам алгоритм записи это уже задача на оптимизацию.
Или тупым перебором или классика в виде https://ru.wikipedia.org/wiki/Линейное_программирование
   Garykom
 
3 - 17.10.19 - 07:33
   RomaH
 
4 - 17.10.19 - 07:50
(3) ... сам понимаешь - это теория, долго и не реально для меня
и скорее всего не пойдет

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

вероятность и прочее

возможно есть промышленные алгоритмы для аналогичной задачи, но боюсь, скорее всего нет - ибо там нафиг не нужна "справедливость" - железной детали пофиг, что другая деталь прошла процесс обработки быстрее её - там упор на оптимизацию издержек
да и стек известен до начала расчета
   Тихий омут
 
5 - 17.10.19 - 08:03
(0) Если не секрет - медкомиссии? Что-то больно быстро прием у одного специалиста завершается
   RomaH
 
6 - 17.10.19 - 08:13
(5) я так понимаю у вас докторская по профпатологии?
   RomaH
 
7 - 17.10.19 - 08:16
(5) и как это там ...

все персонажи выдуманы и совпадения случайны
   Тихий омут
 
8 - 17.10.19 - 08:23
(6) Та не, куда там, таблицу умножения и ту выучить не могу, кажный раз считать в уме приходится:) Просто поинтересовался. Есть опыт работы с медициной, так у нас приемы _так быстро_ никогда не завершаются. Да и сетка расписания с такими мелкими квантами времени больно объёмная должна получиться.
   Галахад
 
9 - 17.10.19 - 08:34
(0) А в чем проблема-то? Если это очередь, то у каждого посетителя не так уж и много вариантов.
   Тихий омут
 
10 - 17.10.19 - 08:36
Была похожая задача при автоматизации аппаратного кабинета офтальмолога, но у вас условия явно пожёстче
   Сияющий в темноте
 
11 - 17.10.19 - 22:09
задача зависит от множества неочевидных условий
например,по одному мы добавляем пациентов или группой.
просто,если по одному,тоткто первый пришел,того и тапки.
направлять имеет смысл к врачу,у которого максимальная загруженность,если он после какого то,то к ним.
опять же,получив максимальную оптимизацию по N пациентов мы,скорей всего,получим очень неоптимизированное решение для N+1
   tesseract
 
12 - 17.10.19 - 22:13
(0)  Это задача коммивояжера.  В любом современном учебнике обход графов разжеван до мелочей.
   Кирдашьян
 
13 - 17.10.19 - 22:30
(0) Так как у тебя стек пациентов заранее не известен, записывай каждого во все ближайшие кабинеты в порядке их освобождения, с учетом уже записанных кабинетов и временем их прохождения. Очень просто.
   palsergeich
 
14 - 17.10.19 - 22:45
Не называейте стеком то что им не является https://ru.wikipedia.org/wiki/Стек
А так да, это нужно построить граф зная верштны связи и жесткость.
Но так как количество врачей общее не думаю что больше 50 - тупой перебор будет весьма эффективен.
   такт
 
15 - 17.10.19 - 23:13
   RomaH
 
16 - 18.10.19 - 07:02
(14) спасибо - буду знать, как то упустил про LIFO
   RomaH
 
17 - 18.10.19 - 07:10
(14) но... от туда же: "В некоторых языках (например, Lisp, Python[3]) стеком можно назвать любой список,"
поэтому можно я буду называть список (список он уже известен) пациентов стеком?

(15) почти, но не то

из вики:
https://ru.wikipedia.org/wiki/Задача_планирования_для_поточной_линии

Определение

Даны n {\displaystyle n} n требований и m {\displaystyle m} m машин для их обработки. Заданы следующие ограничения:

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

с 1-й до m {\displaystyle m} m-ой;


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

(11) "направлять имеет смысл к врачу,у которого максимальная загруженность" - а вот это попробуем
   RomaH
 
18 - 18.10.19 - 07:17
(15)
    Open shop, открытая линия — для каждого требования задано своё подмножество машин, на каждой из которых оно должно обслуживаться некоторое время. Порядок обслуживания на этих машинах произвольный. Задаются разнообразные целевые функции.
    Job shop, рабочий цех — для каждого требования задано своё упорядоченное подмножество машин (маршрут), на которых оно должно обслуживаться в заданном порядке. Задаются разнообразные целевые функции.
    Flow shop, потоковая линия — все машины упорядочены — M 1 , M 2 , … , M m {\displaystyle M_{1},M_{2},\dots ,M_{m}} {\displaystyle M_{1},M_{2},\dots ,M_{m}} и каждое требование проходит все машины в этом порядке. Расписание задано перестановкой требований. Как правило, минимизируется общее время обслуживания требований.
    Задача с директивными сроками — для каждого требования задан момент поступления, время обслуживания и директивный срок окончания обслуживания. Порядок обслуживания на приборах произвольный. Необходимо найти расписание, соблюдающее директивные сроки. При существовании такого расписания можно ставить задачу минимизации числа прерываний.

(0) содержит условия из трех, кроме потоковой линии
   Йохохо
 
19 - 18.10.19 - 07:23
(17) нумеровать по приходу не вариант? пришел, получил код, сидишь смотришь на монитор, ждешь код+кабинет, сходил - вернулся, сел, смотришь на монитор
можно характеризовать каждый кабинет матожиданием и дисперсией, и на момент записи накапливать ошибку и _рекомендовать_ прийти пораньше или записывать на более позднее окно сразу
   RomaH
 
20 - 18.10.19 - 07:35
(19) этот вариант требует изменения в инфраструктуре (розетки, провода, мониторы, терминал)
а так да - тут задача оптимизации сразу "улетучивается"

... у нас даже были закуплены планшеты в качестве мониторов над кабинетами лет пять назад что-ли, но все уперлось в провода на 220v
   RomaH
 
21 - 18.10.19 - 07:39
(19) "сходил - вернулся, сел, смотришь на монитор"
сел? сходил?
у нас это коридор шириной 2 метра и длиною метров 70 ...
   hhhh
 
22 - 18.10.19 - 07:42
(17) что-то не из реальной жизни задача. Пациент сам выбирает время, когда ему удобнее. Кто-то может с утра, кто-то после обеда. Пациенты даже очень склочные бывают. Если он знает, что талончиков еще до фига, ему надо после обеда, А программа емк лепит один вариант, на 8 утра, он вам всю поликлинику разнесет.
   Йохохо
 
23 - 18.10.19 - 07:46
(21) и сидят вдоль стен? РФИД браслетики некрасивые вешать
если это проф обследование, например, то приёмы можно тасовать. Т.е. оперативно менять расписание и плясать от текущей нагрузки кабинетов, а не планов посетителей
   RomaH
 
24 - 18.10.19 - 07:48
(23) да - вдоль стен
РФИД - чем поможет? и оно дорогое
   Йохохо
 
25 - 18.10.19 - 07:54
(24) найти его в коридоре и пригласить, они дальнобойные бывают, несколько метров
   Фрэнки
 
26 - 18.10.19 - 08:59
Я из условия задачи не понял только одного : а что будет параметром управления, т.е. куда и что указывать в качестве значений управления?
   Cyberhawk
 
27 - 18.10.19 - 09:11
Недавно решал более простую задачу, при поиска наткнулся на этот сайт. Он мне хоть и не особо помог (ибо задача была проще чем любая из там представленных), но полезным показался: http://algolist.manual.ru/
Твой раздел - "Математика - Комбинаторика и перебор" скорее всего.
   Фрэнки
 
28 - 18.10.19 - 09:28
будет просто забавно, если задача будет в учетной системе каким-то образом решена, а в рабочем процессе фактические движения будут осуществляться по прежнему произвольным образом, т.к. исполнение каждого отдельного движения не получит связи с найденным решением.
   Garykom
 
29 - 18.10.19 - 09:39
(28) Фактически задача сводится к равномерному наполнению очередей к разным врачам.
На точных графиках не получится потому что задержавшись у одного врача к следующему пропускает свое окно и т.д.
   Йохохо
 
30 - 18.10.19 - 09:41
(29) когда характерное время от Х до 3Х задача скорее не имеет решения без корректировки в реальном времени
 
 Рекламное место пустует
   fisher
 
31 - 18.10.19 - 10:05
Ну, я бы начал "набивку" очередей от узкого места. Узкими местами являются кабинеты с минимально возможным количеством приемов (исходя из времени на прием и размера "окон" приема"). Там можно еще чуть-чуть оптимизировать порядок "узости" кабинетов, учитывая возможное "расстояние" кабинетов до конца цепочки в порядке их прохождения. "Набивать" бы их начал от конца графика к началу. "Нормируем" порядок прохождения кабинетов у каждого пациента таким образом, чтобы с учетом возможного изменения порядка прохождения "узкие" кабинеты оказались в конце. Соответственно, пациент у которого оказывается самое долгое время прохождения остальных кабинетов после самого "узкого" кабинета и принимается последним в очереди, а окончание прохождения всех его оставшихся кабинетов подгадывается под конец приема. Ну и примерно в том же духе набивать рюкзак дальше, пока не упремся в начало работы или не "забьем" самый "узкий" кабинет. Если не уперлись, а пациенты кончились - сдвигаем всех к началу дня.
   fisher
 
32 - 18.10.19 - 10:08
Корректировку "хвоста" тоже можно будет в конце сделать, если туда кого-то еще можно будет воткнуть... В общем обычная набивка, к которой можно будет оптимизации прикручивать по итогам анализа результатов.
   Фрэнки
 
33 - 18.10.19 - 10:10
// некоторые кабинеты не могут быть пройдены пока не пройдены другие кабинеты из стека

это из топика условие
   Garykom
 
34 - 18.10.19 - 10:18
(33) Угу обычные электронные очереди по сути без назначения точного времени.
Посещение каждого врача по талончику с номером, на выходе от врача выдается талончик к следующему врачу.

Учитывая очередность посещения из всего списка.
Т.е. на выходе может быть направлен или к зависимому или если очередь туда уже забита то просто к свободному к которому не надо заранее цепочку пройти.
   fisher
 
35 - 18.10.19 - 10:18
(33) И что? Это ограничение учитывается при "тасовке" цепочки прохождения по каждому пациенту и все...


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.