W czerwcu 2002 donoszono ze szkół ponadgimnazjalnych o blokowaniu się miejsc w szkołach powodujące wydłużenie rekrutacji do połowy lata.....
W czerwcu 2002 opinia publiczna kraju została zaalarmowana przez doniesienia ze szkół ponadgimnazjalnych o blokowaniu się miejsc w szkołach uniemożliwiające szybkie decydowanie o przyjmowaniu zwłaszcza do lepszych liceów ogólnokształcących w wielkich miastach Polski. W Politechnice Poznańskiej problem rozpoznano jako brak koordynacji naboru do szkół i zalecono budowę zintegrowanego systemu naboru w skali regionu - miasta, a nawet całego kraju. Zrealizowano prototyp demonstrujący przyszły system, zainteresowano władze oświatowe Poznania oraz Poznańskie Centrum Superkomputerowe jako wykonawcę systemu. W trakcie konstruowania prototypu okazało się, że algorytm dotychczas znany z rekrutacji informatyków w Politechnice Poznańskiej trzeba przekonstruować na przypadek ogólniejszy jako algorytm klonowania podań. Ostatecznie system naboru obejmujący całe miasto po raz pierwszy zadziałał w Poznaniu w czerwcu 2003 wzbudzając entuzjazm kandydatów i prasy, a w kolejnych latach rozpowszechnił się w wielu miastach Polski i jest stosowany rokrocznie.
Wielu absolwentów gimnazjów spotkała niemiła niespodzianka, gdy w czerwcu 2002 przyszli pod szkoły, do których kandydowali i zamiast odnaleźć się na listach przyjętych musieli zadowolić się jedynie miejscami na listach rezerwowych. Co gorsza kolejne dni nie przynosiły poprawy i dopiero po kilku tygodniach okazało się, że liczba miejsc w szkołach jest wystarczająca. Przerażenie stresującą sytuacją absolwentów i ich rodziców udzieliło się prasie, która publikowała alarmistyczne artykuły(1).
Bezpośrednim powodem tego zamieszania było umożliwienie absolwentom gimnazjów kandydowania do dowolnej liczby szkół, zamiast jednej, jak w latach poprzednich. I tak liczba podań wzrosła kilkakrotnie, gdyż nawet najlepsi uczniowie "zabezpieczali się" kandydując do wielu szkół. I to właśnie ich podania, którymi zostali przyjęci do wielu szkół naraz, zablokowały miejsca dla pozostałych kandydatów. Przewidziany przez Ministerstwo Edukacji mechanizm odblokowywania miejsc polegający na skreślaniu kandydata jeśli w ciągu trzech dni od powiadomieniu o przyjęciu do szkoły nie złożył oryginałów dokumentów przypieczętowując wybór działał bardzo wolno ponieważ wielu uczniów musiało czekać na kilkakrotne kolejne zwolnienie się miejsc zanim zostali przyjęci.
Rozwiązanie tego problemu z pomocą systemu informatycznego to najlepsze wyjście. Jednak istotne przyspieszenie procesu rekrutacji można osiągnąć jedynie gdy system informatyczny będzie "wiedział" jakiego wyboru dokonałby uczeń, gdy proponuje mu się miejsca w kilku szkołach. W ten sposób cykl zwalniania z trzech dni skraca się do ułamków sekund. Praktycznym rozwiązaniem tego problemu okazało się być wymaganie od kandydatów by szkoły, do których chcą kandydować podawali w postaci uporządkowanej od tej najbardziej ich interesującej do najmniej.
Z podobnym problemem spotkały się już w 1998 roku władze dziekańskie na kierunku informatyka, który po trzecim roku studiów dzielił się na pięć specjalności. Studenci mieli rozmaite zainteresowania, ale często rozkładały się nierównomiernie, co przy dopuszczeniu do swobodnego wyboru prowadziłoby do przepełnienia jednych specjalności i konieczności likwidacji innych. Zastosowano więc metodę polegającą na deklarowaniu przez studentów kolejno preferowanych specjalności, a o kolejności przydziału decydowała średnia ocen uzyskana w trakcie dotychczasowych studiów. Oczywiście informatycy, którzy mieli dokonywać naboru od razu wyręczyli się komputerem.
Algorytm naboru na specjalności polegał na uporządkowaniu studentów od tych z największą średnią do tych z najmniejszą. Następnie w kolejności od najlepszego studenta wybierano mu najbardziej pożądaną z jeszcze wolnych specjalności (1).
Program według tego algorytmu został zakodowany w nietypowym języku programowania AWK i działał jednostanowiskowo. Studenci pisali swoje preferencje na kartkach, a wybierany spośród nich komitet wyborczy wprowadzał dane i drukował wyniki. Wydruki w czytelny sposób pokazywały proces naboru umożliwiając zainteresowanym jego ręczną kontrolę.
W 2002 okazało się, że problem naboru do szkół ponadgimnazjalnych jest bardziej złożony niż problem wyboru specjalizacji na informatyce. Wynika to z tego, że każda szkoła może dać konkretnemu uczniowi inną liczbę punktów kwalifikacyjnych. W tych warunkach potrzebny był nowy, bardziej rozbudowany algorytm naboru. Również wyliczanie punktów kwalifikacyjnych nie jest sprawą prostą i tu również aż prosi się komputerowe wspomaganie tego procesu. Ponadto przygotowując się do komputeryzacji naboru w Poznaniu w 2002 roku zdecydowano się wyliczać punkty uzależniając to od konkretnej klasy w szkole. Uzasadnieniem było stwierdzenie, że dopiero klasy wyznaczają profil, który jest zazwyczaj znacznie bardziej ważny dla kandydata niż szkoła, do której ma uczęszczać. Do tego profil klasy umożliwia uzależnienie liczby punktów kwalifikacyjnych od konkretnych przedmiotów i osiągnięć.
W ten sposób program organizujący nabór dysponuje zestawem formatek ekranowych pozwalających wpisać do systemu całą charakterystykę kandydata wymaganą przepisami by wyliczyć punkty kwalifikacyjne i dalej uruchomić algorytm naboru (2).
1. Pojawiają się tu pola identyfikacyjne, z których najważniejszym jest numer PESEL - wygodny i jednoznaczny identyfikator kandydatów w serwisie. Program oczywiście sprawdza poprawność numeru(sumę kontrolną) i jego zgodność z datą urodzenia i płcią. Ponieważ pojawiają się w naszym systemie edukacyjnym obcokrajowcy nie posiadający numeru PESEL, więc przewidziano na ich użytek generowanie unikalnego PESELa o poprawnym formacie.
2. Kolejnym elementem formularza są oceny ze świadectw, które początkowo wpisywano ręcznie, a w późniejszym okresie stało się możliwe ich kopiowanie z systemów szkolnych dysponujących tymi danymi z etapu edukacji gimnazjalnej. Ułatwieniem we wdrożeniu takiego modelu byłoby przyjęcie, że dane kandydatów wpisuje się jeszcze w gimnazjum. Jednak zwykle w systemach naboru decyduje się by dane wpisywały lub weryfikowały szkoły ponadgimnazjalne, do których kandydują uczniowie.
3. Często kontrowersyjnym elementem wpisywanym do systemu by wyznaczyć punkty kwalifikacyjne są osiągnięcia uczniów we współzawodnictwie międzyszkolnym i dodatkowych pracach na rzecz szkoły. Ze względów dokumentacyjnych do serwisu wpisuje się słowny opis osiągnięcia, który nie jest analizowany przez oprogramowanie oraz jego kwalifikację rangi osiągnięcia wybieraną z menu, która właśnie jest używana do wyliczenia punktów.
4. Wreszcie do systemu należy wpisać wybrane przez kandydata szkoły czy też oddziały szkolne w kolejności jaka przez niego jest preferowana. Zazwyczaj następuje to przez wybór z menu kolejnych szkół z ewentualną późniejszą edycją ich kolejności, usuwaniem czy dołączaniem innych.
Spośród wymienionych w punktach 1,2 i 3 są danymi, które powinny wprowadzać, a przynajmniej weryfikować szkoły. Natomiast dane z punktu 4 są predestynowane do wprowadzania ich bezpośrednio przez kandydatów. Początkowo wszystkie dane podawano na papierowych formularzach załączając świadectwa szkolne. W późniejszym okresie wprowadzano wpisywanie wszystkich danych przez kandydatów przez internet jednak z ich weryfikacją przez szkoły na podstawie dokumentów papierowych. Tak wprowadzone dane były gromadzone w bazach danych systemu naboru, a jednocześnie służyły do wyliczania punktów kwalifikacyjnych. Algorytm wyliczania punktów polega zazwyczaj na sumowaniu osiągnięć, które łącznie nie przekraczały 200 punktów. Wyjątkiem byli laureaci olimpiad stopnia centralnego, którzy z tego tytułu otrzymywali 200 punktów bez doliczania punktów z innych przyczyn.
Do dalszego przetwarzania brano pod uwagę związaną z PESEL-em listę szkół(ściślej ich jednoznacznych identyfikatorów w serwisie), z których każdej przypisywano liczbę punktów kwalifikacyjnych wyliczonych dla danego ucznia.
1. Dokonuje się klonowania podań - tj. powielania dla każdego ucznia do każdej z interesujących go szkół i umieszczania ich w specyficznej dla danej szkoły kolejce.
2. Porządkuje się niezależnie każdą z kolejek począwszy od kandydatów o największej liczbie punktów kwalifikacyjnych w dół.
3. Wyznacza się wszystkich kandydatów, których podanie po raz pierwszy trafiło na miejsce w kolejce punktowane przyjęciem do szkoły i dołącza się do kolejki NOWI.
4. Z początku kolejki NOWI pobiera się podanie jednego ucznia.
5. Wszystkie podania tego ucznia z dowolnych szkół, które są mniej przez niego pożądane od tej wybranej, która jest najbardziej pożądana są usuwane z list.
6. W wyniku usuwania podań kolejki skracają się i na miejsce punktowane przyjęciem trafiają nowe podania.
7. Jeśli w kroku 6 nastąpiła zmiana to następuje powrót do kroku 3.
8. Kandydaci na miejscach premiowanych przyjęciem zostają zakwalifikowani do tych właśnie szkół, a ci którzy takich podań nie mają pozostają nie przyjęci.
Prześledźmy działanie powyższego algorytmu na przykładzie. Niech uczniowie oznaczeni są kolejnymi liczbami 1,2, ..., 9 jako ich numerami PESEL. Kandydują oni do szkół oznaczonych: a,b, ...,h, z których każda może przyjąć tylko jednego ucznia. Oto listy preferencji szkół poszczególnych uczniów:
Kandydat 1. szkoła h, szkoła a, szkoła d, szkoła c, szkoła f
Kandydat 2. szkoła a, szkoła e, szkoła b
Kandydat 3. szkoła b, szkoła e, szkoła c, szkoła d
Kandydat 4. szkoła e, szkoła a, szkoła f, szkoła g
Kandydat 5. szkoła g, szkoła h, szkoła e, szkoła f
Kandydat 6. szkoła c, szkoła d, szkoła e
Kandydat 7. szkoła d, szkoła a, szkoła f, szkoła h
Kandydat 8. szkoła b, szkoła a, szkoła f, szkoła h
Kandydat 9. szkoła e, szkoła a, szkoła f, szkoła h
Po wpisaniu ocen i innych osiągnięć uczniów, które dla uproszczenia rozważań tu pominiemy, okazuje się, że szkoły przydzieliły uczniom następujące punkty kwalifikacyjne:
Kandydat 1 zdobył: w szk. h pkt. 134, w szk. a pkt. 135, w szk. d pkt. 133, w szk. c pkt. 134, w szk. f pkt. 134
Kandydat 2 zdobył: w szk. a pkt. 133, w szk. e pkt. 129, w szk. b pkt. 130
Kandydat 3 zdobył: w szk. b pkt. 131, w szk. e pkt. 130, w szk. c pkt. 131, w szk. d pkt. 130
Kandydat 4 zdobył: w szk. e pkt. 128, w szk. a pkt. 132, w szk. f pkt. 132, w szk. g pkt. 130
Kandydat 5 zdobył: w szk. g pkt. 128, w szk. h pkt. 129, w szk. e pkt. 127, w szk. f pkt. 130
Kandydat 6 zdobył: w szk. c pkt. 130, w szk. d pkt. 129, w szk. e pkt. 131
Kandydat 7 zdobył: w szk. d pkt. 128, w szk. a pkt. 131, w szk. f pkt. 131, w szk. h pkt. 128
Kandydat 8 zdobył: w szk. b pkt. 129, w szk. a pkt. 130, w szk. f pkt. 129, w szk. h pkt. 131
Kandydat 9 zdobył: w szk. e pkt. 126, w szk. a pkt. 129, w szk. f pkt. 128, w szk. h pkt. 130
Algorytm klonowania zatem sporządził dla każdej ze szkół i uporządkował następujące kolejki:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand.3=130, kand.2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand.8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
Kolorem czerwonym oznaczono kandydatów, którzy mogą zostać przyjęci do danej szkoły. Kolejka podań jest zatem następująca: a=1,b=3,c=1,d=1,e=6,f=1,g=4,h=1.Widać, że kandydat nr 1 został przyjęty, aż do pięciu szkół i nasz algorytm rozpoznając, że najbardziej pożądaną przez niego i już osiągniętą jest szkoła "h" usunie pozostałe podania:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand. 2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand. 8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
Spowoduje to wejście na pierwsze miejsca w kolejkach kolejnych kandydatów dołączanych również do kolejki NOWI: a=2,c=3,d=3,f=4. Ale przedtem trzeba rozważyć kandydata nr 3 i usunąć pozostałe jego podania:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand.2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand. 8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
dołączając też do kolejki NOWI: c=6,d=6. Ponieważ kandydat 6 chce najbardziej do szkoły c, więc pozostałe można skreślić:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand.2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand. 8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
dołączając też do kolejki NOWI: e=2,d=7. Kandydat 4 chciałby do szkół e lub a, ale na razie nie ma dla niego miejsc. Natomiast ponieważ może zostać przyjęty do f więc można skreślić g.
Kolejka do szkoły a. kand.1=135, kand.2=133,4=132,7=131,8=130,9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand.8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand.2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand. 8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
dołączając też do kolejki NOWI: e=2,g=5. Kolejny element do rozpatrzenia to a=2, które pozwala skreślić b,e:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand. 2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand.8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
dołączając też do kolejki NOWI: e=4. Rozpatrujemy f=4:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand. 2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand.8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
dołączając też do kolejki NOWI: f=7. Rozpatrujemy g=5:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand. 2=129, kand.4=128, kand.5=127, kand.9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand.7=131, kand.5=130, kand. 8=129, kand.9=128
Kolejka do szkoły g. kand. 4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
Rozpatrujemy f=7:
Kolejka do szkoły a. kand.1=135, kand.2=133, kand.4=132, kand.7=131, kand.8=130, kand.9=129
Kolejka do szkoły b. kand.3=131, kand.2=130, kand. 8=129
Kolejka do szkoły c. kand.1=134, kand.3=131, kand.6=130
Kolejka do szkoły d. kand.1=133, kand.3=130, kand.6=129, kand.7=128
Kolejka do szkoły e. kand.6=131, kand. 3=130, kand. 2=129, kand.4=128, kand.5=127, kand. 9=126
Kolejka do szkoły f. kand.1=134, kand.4=132, kand. 7=131, kand.5=130, kand.8=129, kand.9=128
Kolejka do szkoły g. kand.4=130, kand.5=128
Kolejka do szkoły h. kand.1=134, kand.8=131, kand.9=130, kand.5=129, kand.7=128
Tym sposobem problem naboru został rozstrzygnięty:
Kandydat 1. przyjęty do szkoły h
Kandydat 2. przyjęty do szkoły a
Kandydat 3. przyjęty do szkoły b
Kandydat 4. przyjęty do szkoły e
Kandydat 5. przyjęty do szkoły g
Kandydat 6. przyjęty do szkoły c
Kandydat 7. przyjęty do szkoły d
Kandydat 8. przyjęty do szkoły f
Kandydat 9. nie przyjęty do żadnej szkoły z braku miejsc
W praktyce występują niekiedy problemy z uczniami o jednakowej liczbie punktów kandydującymi do tej samej klasy i system może albo ich wszystkich przyjąć albo odrzucić, co niekiedy wymaga powiększenia limitów. W trakcie naboru może się okazać, że dla pewnej klasy jest za mało uczniów by ją utworzyć, a gdzie indziej brakuje klas o danymi profilu. Wszystkie te problemy na bieżąco rozwiązuje spotkanie dyrektorów szkół, w czasie którego algorytm klonowania podań jest wielokrotnie wywoływany, aż do osiągnięcia zadowalających rezultatów. Algorytm klonowania podań w naborze dla całego miasta został po raz pierwszy zastosowany w Poznaniu w 2003 roku (3), a później jego użycie powtarzało się również dla wielu innych miast Polski. W kolejnych latach okazało się, że systemy skomputeryzowane przydadzą się również do naboru w: gimnazjach, szkołach podstawowych, przedszkolach, żłobkach i szkołach policealnych https://nabor.pcss.pl/wdrozenia.shtml. Stosuje się je także w szkołach wyższych np.: http://www.put.poznan.pl/rekrutacja/rekrutacja-elektroniczna. Jednak we wszystkich tych innych przypadkach stosuje się inne algorytmy dostosowane do charakteru rekrutacji.
Bibliografia
1. Urbański A.P., Nawrocki J.,(2003) „Algorytmy sprawiedliwego i efektywnego naboru edukacyjnego”, Materiały konferencji EDI-EC, Łódź, Acta Universitas Lodziensis, FOLIA OECONOMICA 167, pp.429-442 (in Polish).
2. Mazurek C., Stroiński M., Urbański A.P., (2004)“A Client-Server System for Mass Recruitment to Secondary Schools in a Metropolitan Area”, eAdoption and Knowledge Economy(eds. P.Cunningham and M.Cunningham), Vienna, IOS Press, pp.1801-1808.
3. Urbański, A.P. (2004) "Cywilizacja Internetu", Nakom, Poznań,.