Układanie grafiku - algorytm
patrykd
Od jakiegoś czasu zajmuję się układaniem grafiku dla redaktorów pewnego
serwisu internetowego. Dyżury pełnione są na 3 zmiany 7 dni w tygodniu
przez kilkunastu redaktorów. Pod koniec tygodnia każdy redaktor nadsyła mi
informacje, w jakie dni i na jakie zmiany może pełnić dyżur i ja na tej
podstawie układam dla nich grafik. Obecnie robię to zwyczajnie kombinując,
przekładając, tasując nadesłane przez nich terminy w dyżury. Nierzadko
zajmuje to "trochę" czasu i zastanawiałem się, czy nie można tego jakoś
uprościć. Tzn. dać się da na pewno, tylko mi chodzi o jakiś algorytm,
wzór, który mając dane nadesłane przez redaktorów, automatycznie utworzy
taki grafik.
Nie wiem jak to matematycznie przedstawić, ale dane od jednego redaktora
wyglądają mniej więcej tak:
redaktor1:
[1,0,0] po
[0,1,1] wt
[0,1,0] śr
[1,1,0] cz
[0,0,0] pi
[0,0,0] so
[0,0,1] ni
czyli redaktor1 może dyżurować w poniedziałek na pierwszą zmianę, wtorek
na drugą i trzecią itd.
Wstyd mi prosić o gotowe rozwiązanie, ale jeśli ktoś będzie miał ochotę
rzucić na to okiem i coś zasugerować, podpowiedzieć - byłoby miło.
Pozdrawiam
Damian Sobota
> Od jakiego� czasu zajmuj� si� uk�adaniem grafiku dla redaktorów pewnego
> serwisu internetowego. Dyşury pe�nione s� na 3 zmiany 7 dni w tygodniu
> przez kilkunastu redaktorów. Pod koniec tygodnia kaşdy redaktor nadsy�a mi
> informacje, w jakie dni i na jakie zmiany moşe pe�ni� dyşur i ja na tej
> podstawie uk�adam dla nich grafik. Obecnie robi� to zwyczajnie kombinuj�c,
> przek�adaj�c, tasuj�c nades�ane przez nich terminy w dyşury. Nierzadko
> zajmuje to "troch�" czasu i zastanawia�em si�, czy nie moşna tego jako�
> upro�ci�. Tzn. da� si� da na pewno, tylko mi chodzi o jaki� algorytm,
> wzór, który maj�c dane nades�ane przez redaktorów, automatycznie utworzy
> taki grafik.
>
> Nie wiem jak to matematycznie przedstawi�, ale dane od jednego redaktora
> wygl�daj� mniej wi�cej tak:
>
> redaktor1:
> [1,0,0] po
> [0,1,1] wt
> [1,1,0] cz
> [0,0,0] pi
> [0,0,0] so
> [0,0,1] ni
>
>
> na drug� i trzeci� itd.
>
Witam.
Nie napisałeś, jakie ograniczenia są nałożone na planowanie. Np. nie wiadomo,
ile maksymalnie dyżurów w tygodniu może mieć dany redaktor. Napisz to wszystko
tutaj, bo to jest ważne.
Pozdrawiam,
DS.
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
maziek
> Witam
>
> Od jakiegoś czasu zajmuję się układaniem grafiku dla redaktorów
nie trza wyważać drzwi, np: http://www.astar05.pl/plan.html
--
ukłony, maziek
WM
>
> Nie wiem jak to matematycznie przedstawiÄ , ale dane od jednego redaktora
> wyglÄ dajÄ mniej wiÄ cej tak:
>
> redaktor1:
> [1,0,0] po
> [0,1,1] wt
> [1,1,0] cz
> [0,0,0] pi
> [0,0,0] so
> [0,0,1] ni
>
Ułóż tabelę.
W każdym wierszu nr redaktora i jego zadeklarowane dni i zmiany.
nr..p123w123s123c123p123s123n123
--------------------------------
R1...100.011.010.110.000.000.001
Maciej Woźniak
Użytkownik "maziek" <m...@t.com> napisał w wiadomości
news:1ng57q4y0vxyk$.1ujj4onbrbym5.dlg@40tude.net...
Oczywiście, nie trzeba, są dobre gotowe
rozwiązania, szkoda, że zadanie do nich
niespecjalnie pasuje:(.
Osobiście zabrałbym się za ten problem
odwrotnie. To znaczy - nie: robię pusty
grafik i wypełniam, tylko: robię pełny
grafik i skreślam.
patrykd
> Uloz tabele.
> W kazdym wierszu nr redaktora i jego zadeklarowane dni i zmiany.
I co dalej z ta tabela? :-)
Pozdrawiam
patrykd
> Nie napisales, jakie ograniczenia sa nalozone na planowanie. Np. nie
> wiadomo, ile maksymalnie dyzurow w tygodniu moze miec dany redaktor.
> Napisz to wszystko tutaj, bo to jest wazne.
Liczba dyzurow teoretycznie jest nieograniczona (w granicach rozsadku), bo
najwazniejsze jest to, zeby kazda zmiana byla obsadzona. Grafik jednak
powinien byc tak ulozony, zeby dyzury bylo mozliwie rowno obdzielone
miedzy redaktorow, najbardziej optymalnie, jak sie tylko da. Robiac to
"recznie" po jakims czasie w koncu uzyska sie pozadany efekt, jednak mi
chodzi o automat, algorytm, ktory bylby w stanie wymyslic to sam.
Tak sobie dumam i sam juz nie wiem, czy zadanie to nie wymaga przypadkiem
prawdziwego myslenia i automatyzacja jest niewykonalna, a co najwyzej da
sie procedure ulatwic...
Pozdrawiam
patrykd
> Osobiscie zabralbym sie za ten problem
> odwrotnie. To znaczy - nie: robie pusty
> grafik i wypelniam, tylko: robie pelny
> grafik i skreslam.
Wszystko fajnie, tylko nijak nie moge z tego wyczytac algorytmu, ktory
aktomatycznie i "sprawiedliwie" dzielilby dyzury pomiedzy redaktorow :-)
Oczywiscie obecnie staram sie sobie pomagac tworzac takie tabelki w
arkuszach, wypelniam je deklaracjami i pozniej wykreslam, ale to jest
wlasnie tylko pomoc, a mi chodzi o automatyzacje. Tak jak napisalem w
innym poscie - mam juz watpliwosci, czy da sie procedure calkowicie
zautomatyzowac (poza wpisywaniem deklaracji, chociaz to akurat potrafilbym
zrobic), czy tylko uproscic tworzac tego typu tabelki...
Pozdrawiam
WM
Podsumuj kolumny i zapisz wyniki w dolnym wierszu.
Zacznij od planowania tych dyżurów, na które jest najmniej chetnych,
czyli tych o najmniejszych sumach.
Jeżeli jest do wyboru kilku redaktorów na dyzur, to wybieraj
pierwszego redaktora od góry, z listy najmniej obciążonych.
Listę najmniej obciążonych uaktualniasz (sortujesz) po każdym
wyborze na dany dyzur.
Pozdrawiam WM
Jakub Wróblewski
Użytkownik "patrykd" <patr...@interia.pl> napisał w wiadomości
news:op.uhd5b7mxdyvb90@lolek...
>
> Od jakiegoś czasu zajmuję się układaniem grafiku dla redaktorów pewnego
> serwisu internetowego. Dyżury pełnione są na 3 zmiany 7 dni w tygodniu
> przez kilkunastu redaktorów. Pod koniec tygodnia każdy redaktor nadsyła mi
> informacje, w jakie dni i na jakie zmiany może pełnić dyżur i ja na tej
> podstawie układam dla nich grafik.
Na oko problem wygląda na NP-trudny. W praktyce powinien wystarczyć taki
algorytm:
1. Sortujemy zmiany od najmniej obsadzonej.
2. Bierzemy kolejne zmiany i obsadzamy je tym redaktorem, który ma najmniej
przypisanych zmian. Albo losowym z nich, jeśli takich jest więcej.
Pozdrawiam,
Jakub Wróblewski
Marcin Gryszkalis
> Liczba dyzurow teoretycznie jest nieograniczona (w granicach rozsadku),
które program musiałby uwzględnić:
- ile dyżurów "pod rząd" może mieć jeden red.
- co jeśli żaden nie deklaruje obecności w jakimś terminie
- czy jest maksymalna liczba dyzurow w sumie
- czy jest maksymalna liczba red. na zmianie
- cos jeszcze?
> dyzury bylo mozliwie rowno obdzielone miedzy redaktorow
rowno ale jak najmniej czy jak najwiecej?
pozdrawiam
--
Marcin Gryszkalis, PGP 0x9F183FA3
jabber jid:m...@fork.pl, gg:2532994
http://the.fork.pl
Marcin Gryszkalis
> Na oko problem wygląda na NP-trudny. W praktyce powinien wystarczyć taki
> algorytm:
> 1. Sortujemy zmiany od najmniej obsadzonej.
> 2. Bierzemy kolejne zmiany i obsadzamy je tym redaktorem, który ma
> najmniej przypisanych zmian. Albo losowym z nich, jeśli takich jest
> więcej.
A ja zrobiłbym odwrotnie :)
1. zsumował wszystkie propozycje wszystkich redaktorów
2. zaczynając od najbardziej obsadzonej zmiany wyrzucał redaktorów
najbardziej obciążonych godzinami (dodatkowo trzeba uwzględnić szereg
warunków, o których mowa w postach obok).
Jeśli chcemy mieć super optymalnie to wybór zmiany i redaktora zamiast
losowy (albo pierwszy z brzegu) może powodować rozgałęzienie wariantów -
ale żeby się w to bawić trzebaby dobrze określić kryterium optymalności.
Łukasz Kalbarczyk
> Witam,
>
> Użytkownik "patrykd" <patr...@interia.pl> napisał w wiadomości
> news:op.uhd5b7mxdyvb90@lolek...
>>
>> Od jakiegoś czasu zajmuję się układaniem grafiku dla redaktorów pewnego
>> serwisu internetowego. Dyżury pełnione są na 3 zmiany 7 dni w tygodniu
>> przez kilkunastu redaktorów. Pod koniec tygodnia każdy redaktor nadsyła mi
>> informacje, w jakie dni i na jakie zmiany może pełnić dyżur i ja na tej
>> podstawie układam dla nich grafik.
>
> Na oko problem wygląda na NP-trudny. W praktyce powinien wystarczyć taki
> algorytm:
Do hetmanów jest trochę podobny.
Tam działają oidp całkiem dobrze algorytmy polegające
na jakimś tam ustawieniu i późniejszej minimalizacji konfliktów...
> 1. Sortujemy zmiany od najmniej obsadzonej.
> 2. Bierzemy kolejne zmiany i obsadzamy je tym redaktorem, który ma najmniej
> przypisanych zmian. Albo losowym z nich, jeśli takich jest więcej.
Przy zachłanności pewnie też trzeba będzie wracać i poprawiać.
--
ŁK (2008-09-14 13:27:11)
WM
> losowy (albo pierwszy z brzegu) może powodować rozgałęzienie wariantów -
> ale żeby się w to bawić trzebaby dobrze określić kryterium optymalności.
>
Mozna wprowadzić dodatkową punktację za zmiany nocne, świąteczne,
poniedziałkowe, podczas hitów telewizyjnych i klęsk żywiołowych ;-)
Każdy redaktor powinien mieć w cyklu rocznym tyle samo.
Ponadto redaktor powinien określić preferencje np:
1/Święta obchodzi katolickie, prawosławne czy jeszcze inne.
2/Ogląda olimpiady, parady czy seriale.
3/Jeździ na ryby, grzyby czy zloty hobbystów gdy jest dogodna pora.
patrykd
> - ile dyzurow "pod rzad" moze miec jeden red.
Jesli zadeklarowal, ze moze dyzurowac, a nie ma innych ochotnikow, to
niestety przypisywane sa mu te dyzury. Oczywiscie po przedstawieniu
takiego grafiku wszystkim redaktorom zazwyczaj znajduje sie jakas pomoc,
ale wstepnie ustawiane sa dyzury wolnemu redaktorowi, bez wzgledu na to,
ze to jego 5. dyzur z rzedu (w takiej sytuacji ten redaktor nie powinien
miec dyzurow w innych terminach, jesli byli inni chetni, ktorym przypisano
mniej dyzurow).
> - co jesli zaden nie deklaruje obecnosci w jakims terminie
Wstepnie ustawiany jest wakat, a pozniej kombinuje sie, co z tym zrobic.
Czasami bywa tak, ze serwisem zajmuje sie kilku redaktorow (po gidzinie,
czy jakos tak), ktorzy nie mogli zadeklarowac pelnego dyzuru. Ale to na
razie jest nieistotne, bo wstepnie po prostu ustawiony ma byc wakat.
> - czy jest maksymalna liczba dyzurow w sumie
Nie ma. Z doswiadczenia wiem, ze przy kilkunastu redaktorach, jeden nie ma
wiecej niz 3-4 dyzurow (choc zdarzaja sie wyjatki), ale jako takiego
maksimum nie ma.
> - czy jest maksymalna liczba red. na zmianie
Jednej zmianie przypisany ma byc jeden redaktor. Zdarza sie, ze dopisuje
sie drugiego, ale to mozna zrobic recznie (a nawet powinno sie, bo to
sytuacje wyjatkowe).
> - cos jeszcze?
Wydaje mi sie, ze nie, ale jesli beda jakies watpliwosci, pytania, to
postaram sie odpowiedziec.
> rowno ale jak najmniej czy jak najwiecej?
Jesli na jedna zmiane ma byc jeden redaktor, to rowno oznaczaloby jak
najmniej :-)
Pozdrawiam
Marcin Gryszkalis
W ramach odpoczynku od pracy dnia codziennego ;) pozwolilem sobie
zaimplementowac w 2 warianatach
1. losowy (wbrew pozorom zazwyczaj dosc skuteczny, 10000 wariantow zajmuje
mu kilka sekund i zazwyczaj znajduje najlepsze rozwiazanie)
2. "inteligentny" (ale tez oparty na losowaniu aby pominac zlosliwe
przypadki)
optymalizujemy odchylenie standardowe ilosci zmian przypadajacych na
redaktora
odpalasz
wersja inteligentna:
perl grafik.pl < input.txt
wersja losowa
perl grafik.pl 1 < input.txt
input.txt postaci (pierwsza kol. = nazwa red. + 21 zmian)
r01,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0
r02,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0
...
ciekaw jestem jak zadziala dla rzeczywistych danych a nie tylko moich
testowych losowych :)
Dr.Endriu
Marcin Gryszkalis
Dr.Endriu
A czy ktoś umie to przerobić na C++ ?
--
Pozdrawiam
Dr.Endriu
Marcin Gryszkalis
>> > W czym to jest napisane jeśli mozna wiedzieć ?
>> perl
> A czy ktoś umie to przerobić na C++ ?
Dr.Endriu
> pewnie tak, ale po co?
Bardzo bym prosił....
--
Pozdrawiam
Dr.Endriu
======================================= Nota moderatora:
Wątek niebezpiecznie dryfuje w stronę pl.praca.oferowana
Marcin Gryszkalis
>> > A czy ktoś umie to przerobić na C++ ?
>> pewnie tak, ale po co?
> Bardzo bym prosił....
chyba żartujesz sobie :) problemik wydał mi się ciekawy więc na szybko coś
napisałem w ramach rozrywki umysłowej, a to o czym teraz mówisz (co gorsza
nie wyjaśniając celu) to ciężka praca - a w sprawie pracy to możesz napisać
na priva najlepiej od razu z propozycją ceny, którą chcesz za to
zapłacić :)
Czy w regulaminie psm nie ma, że nie odrabia się tu prac domowych za innych?
patrykd
Niejako podsumowujac temat opisze dokladniej, jak na podstawie informacji
uzyskanych od Was rozwiazuje problem z grafikiem.
redaktor | zm1 | zm2 | zm3 | ... | zm20 | zm21 | suma
---------+-----+-----+-----+ +------+------+------
red-01 | 1 | 0 | 0 | ... | 1 | 1 | 5
red-02 | 0 | 0 | 1 | ... | 0 | 0 | 7
red-03 | 1 | 1 | 0 | ... | 1 | 0 | 11
red-04 | 0 | 1 | 0 | ... | 0 | 1 | 5
. | . | . | . | . | . | . | .
. | . | . | . | . | . | . | .
. | . | . | . | . | . | . | .
---------+-----+-----+-----+-----+------+------+------
suma | 3 | 2 | 5 | ... | 8 | 2 | x
Tak jak zalecaliscie, ustalanie grafiku rozpoczalem od najmniej obsadzonej
zmiany (najmniej deklaracji od redaktorow na te zmiane). W przypadku kilku
zmian o tej samej liczbie zgloszen kryterium bylo nastepujace:
1) Wybieralem redaktorow, ktorzy zadeklarowali sie na dana zmiane, wraz z
suma ich deklaracji i sortuje ich po tej sumie rosnaco, czyli (dla
powyzszego wycinka rozpiski redaktorow):
zm2: red-04 (5), red-03 (11)
zm21: red-01 (5), red-04 (5)
W tym przypadku najpierw przypisuje redaktora zmianie 21 (kolejno mniejsze
liczby deklaracji redaktorow).
2) Jesli zdarzyloby sie tak, ze wszyscy redaktorzy mieliby takie same
kolejne sumy deklaracji, wowczas rozszerzam kryterium wyboru. Robie
podobne zestawienie redaktorow jak w pkt. 1, ale dodatkowo spisuje sumy
deklaracji zmian, na ktorych redaktor moglby pelnic dyzur, i rowniez
sortuje je rosnaco, czyli (zalozmy, ze red-03 nadeslal 5 deklaracji):
zm2: red-04 (5)[2,2,4,5,7]
red-03 (5)[2,3,5,5,8]
zm21: red-04 (5)[2,2,4,5,7]
red-01 (5)[2,3,4,8,8]
W tym przypadku rowniez wybralbym zmiane nr 21. Dlaczego? W obydwu
zmianach redaktor 04 ma deklaracje dla kolejno gorszych zmian niz
pozostali redaktorzy (w zm2 red-04 ma "2,2,...", a red-03 "2,3,...",
natomiast w zm21 red-04 "2,2,...", a red-01 "2,3,..."). Bierzemy zatem pod
uwage kolejnych redaktorow. W zm21 red-01 ma "2,3,4,...", a w zm2 red-03
ma "2,3,5,...", czyli zadeklarowal kolejno lepiej obsadzone zmiany.
Jesli wszyscy redaktorzy mieliby identycznie obsadzone zmiany, wowczas
wybrana zostaje zmiana pierwsza od lewej (tutaj zm2).
W tym momencie mamy wybrana zmiane do obsadzenia i nalezy wybrac dla niej
redaktora.
Wybieramy tego, ktory nadeslal najmniej deklaracji, a jesli jest kilku z
najmniejsza liczba, wowczas przyjmujemy kryterium z pkt. 2, czyli w tym
przykladzie dla zmiany nr 2 przypisany zostanie red-04, poniewaz
zadeklarowal gorzej obsadzone zmiany ("2,2,..." przy "2,3,..." redaktora
1).
Ufff... mamy w koncu pierwsza obsadzona zmiane: zm21 - red-04.
Po tych operacjach zerujemy deklaracje red-04 (na wszystkich zmianach 0)
oraz deklaracje wszystkich redaktorow na zmianie 21 (na powyzszym wycinku
rozpiski red-01 mialby 0 przy zmianie 21). Nastepnie ponownie wyliczamy
sumy deklaracji redaktorow oraz sumy deklaracji na zmianach.
Powtarzamy powyzsza procedure na nowej (czesciowo wyzerowanej) rozpisce az
do momentu, kiedy wszystkie zmiany zostana obsadzone (grafik gotowy), lub
jesli zostana jakies nieobsadzone zmiany, ale nie bedzie kogo im
przydzielic.
------------
Jesli zostana nieobsadzone zmiany, przypisujemy jej redaktora, ktory
zglosil najwiecej wolnych terminow (chyba ze uchowal sie taki, ktory
dziwnym trafem nie dostal jeszcze dyzuru - nie wiem, czy to mozliwe,
ale...). Jesli takich jest kilku, to stosujemy podobne (ale odwrotne)
kryteria jak powyzej. Procedure powtarzamy, az wszystkie zmiany zostana
obsadzone. Jesli to bedzie niemozliwe, to po prostu zostana wakaty.
Tym razem pierwszenstwo maja redaktorzy z najwieksza liczba deklaracji,
poniewaz ogolne kryteria byly nastepujace:
1) utworzyc grafik rozdzielajac zmiany rowno pomiedzy mozliwie jak
najwieksza liczbe redaktorow (redaktorow raczej jest mniej, niz zmian),
2) jesli wszyscy redaktorzy dostana dyzury, to kolejne dyzury dajemy tym
redaktorom, ktorzy zglosili najwiecej deklaracji (w koncu teoretycznie
maja najwiecej wolnego czasu),
3) w dalszej kolejnosci staramy sie rowniez rowno przydzielac dyzury,
czyli jesli red-08 dostal juz dwa dyzury (bo mial najwiecej deklaracji),
to jesli przy kolejnej zmianie nadal on ma najwiecej deklaracji, w miare
mozliwosci wybieramy innego redaktora (zeby jeden nie mial 3 dyzurow, a
inni 1).
I tak do skutku...
Zdaje sobie sprawe, ze opis ten moze byc chaotyczny, ale chcialem to
wszystko dokladnie przedstawic - moze sie komus przyda. Co prawda
pewnosci, ze algorytm ten jest najbardziej optymalny, nie mam, ale wydaje
mi sie, ze tak jest... Jesli ktos ma uwagi, poprawki, to prosze pisac.
Jesli beda do powyzszego pytania, rowniez postaram sie odpowiedziec.
Pozdrawiam
M
>>> A czy ktoś umie to przerobić na C++ ?
>> pewnie tak, ale po co?
>
>
> Bardzo bym prosił....
A co to? Google ukradli, czy co?
http://www.indigostar.com/perl2exe.htm
http://search.cpan.org/~nwclark/perl-5.8.8/utils/perlcc.PL
...
M.