Planificarea bazata pe cunostinte

1. Siteme bazate pe cunostinte – descriere

Sistemele bazate pe cunostinte sunt sisteme bazate pe tehnicile si metodele inteligentei artificiale. Componentele lor centrale sunt: baza de cunostinte si mecanismele de inferenta. Arhitectura holonica, care conduce sistemul este compusa dintr-o baza algoritmica, care programeaza operatiile conform unui algoritm euristic, si un mecanism de inferenta care preia sarcina de programare a operatiilor atunci cand anumite resurse(ex: roboti) nu sunt disponibile.
Un sistem bazat pe cunostinte(KBSS – Knowledge Base System for Scheduling) are urmatoarele caracteristici:

1. foloseste informatii din surse diferite care include experti umani, designeri si literatura;
2. este bazat pe o arhitectura care integreaza optimizarea si abordarea bazata pe cunostinte;
3. a fost dezvoltat pentru un mediu automat de productie. Problema programarii ordinelor care urmeaza a fi rezolvata poate fi clasificata ca o problema a atelierului bazat pe ordine cu un numar de resurse diferite, cum ar fi masini, unelte, grippere, utilaje de manipulat si nu in ultimul rand constrangeri de precedenta, date de finalizare

Structura KBSS

2. Baza algoritmica

In functie de performantele testate(Kusiak, 1990), sase reguli de programare au fost incorporate in algoritmul euristic:

1. Initializare:

Setare timp curent la t=0 si starea resursei sr_lq=1, q∈Q_l , l∈L
Setarea celor 4 seturi S₀ - S₃ respectiv operatiile os_i = 0, ...,3 non-executate(gol), executabile, ne-programabile(gol) si programabile

1. Din operatiile programabile se selecteaza o operatie o_α conform regulilor de prioritate de mai jos:

   • PR1: ns_αp = max{ns_ip}, p∈P, i∈S₃
   • PR2: no_αp = min{no_ip}, p∈P, i∈S₃
   • PR3: ni_αp = max{ni_ip}, p∈P, i∈S₃
   • PR4: nu_αp = max{nu_ip}, p∈P, i∈S₃
   • PR5: t_i = min{t_i⁽⁰⁾}, i∈S₃
   • PR6: selecteaza o operatie arbitrara o_α
2. programeaza operatia selectata in pasul 2
   • statusul operatiei devine “non-programabila”
   • statusul operatiilor o_α devine “non-executabila”
   • timpul de procesare ramas devine rt_α = t_α⁽⁰⁾
   •  starea resursei sr_lq=0 pentru r_lq∈R_α⁽⁰⁾, q∈Q_l, l∈L. Reactualizare S₃ si S₂. Daca S₃ ≠ ∅, mergi la pasul 2. Daca S₃ = ∅ si mai sunt resurse disponibile mergi la pasul 4; altfel, reactualizeaza multimea S₆, intra in mecanismul de inferenta (regulile ALT_PLAN genereaza un triplet OH alternativ).
3. Calculeaza timpul de terminare al fiecarei operatii programate dar neterminate la timpul curent. Seteaza timpul curent egal cu timpul de terminare al operatiei cu cel mai mic timp. Adauga aceasta operatie(sau operatii in cazul unei egalitati) setului de operatii terminate:

   • f_i = rt_i + t, i∈S₄
   • 
   • Seteaza statusul operatiei terminate si sterge operatia din S4
   • Seteaza starea resurselor  si timpul ramas rt_i = f_i - t, i∈S₄. Reactualizeaza S₃ si S₂.
4. daca S₃∪S₂ = ∅ opreste; altfel mergi la pasul 6
5. daca S₃ ≠ ∅, mergi la pasul 2. Daca S₃ = ∅ si nu mai sunt resurse disponibile mergi la pasul 4; altfel ractualizeaza multimea S₆, intra in mecanismul de inferenta pentru alocarea resurselor alternative.

3. Mecanismul de inferenta

Mecanismul de inferenta din KBSS controleaza procedura de declansare a regulilor din baza de cunostinte si procedura de generare a programului unui algoritm. Un avantaj al acestei arhitecturi in tandem este simplitudinea mecanismului de inferenta. Mecanismul de inferenta din KBSS foloseste o strategie de control de tip forward chain. Dandu-se o anumita clasa de reguli el incearca sa execute toate regulile care sunt legate de contextul considerat. Daca o regula este executata, ex: conditiile sunt adevarate, atunci actiunile regulii sunt executate. Unele reguli opresc cautarea daca mecanismul de inferenta si schimba controlul procesului la algoritm.
In procesul generarii programului, o operatie se poate sa nu fie procesata conform planului de procesare de baza din cauza indisponibilitatii unei resurse. Programarea euristica prezentata in acesta scectiune iese din pasii 3 si 6 si intra in mecanismul de inferenta al sistemului bazat pe conostinte. Mecanismul de inferenta din GAS executa urmatoarele multimi de reguli:

• SEL_ALG: selectia algoritmului de planificare adecvat
• ALT_PLAN:porneste si controleaza mecanismul de selectie al holonilor comanda alternativi pentru un ordin, declansat de indisponibilitatea unei resurse
• VAL_RES: evalueaza planurile facute de asamblare si decide daca se face o reprogramare pentru a imbunatati calitatea globala a solutiei. Functia makespan de performanta este folosita pentru aceasta C_max = max{C_i}, cu C_i = timpul de completare o_i∈OA_p, 1≤i≤f_p, p∈P

4. Folosirea simulatorului la planificare

Calcularea unei planificari valide si optimale este echivalenta cu gasirea unei succesiuni pentru executia operatiilor care intra in componenta unui ordin si asocierea in timp a acestor operatii cu resursele sistemului. Aceasta planificare trebuie sa indeplineasca doua cerinte: in primul rand sa fie valida si in al doilea rand sa optimizeze o anumita functie de cost.

Programul de planificare implementat foloseste un algoritm euristic, algoritmul de planificare bazat pe regulile de prioritate, pentru a genera planificarea ordinelor, iar partea de alocare in timp a resurselor se face folosind un simulator in care se observa evolutia in timp a ordinelor deja planificate. O operatie deja planificata si introdusa in simulator este considerata alocata unei resurse si nu mai poate fi scoasa din planificator. Cele 2 faze, planificarea si simularea, sunt interdependente deoarece in functie de gradul de ocupare al sistemului si in particular de gradul de ocupare al resurselor de procesare se face inserarea noilor palete in sistem (planificarea primei operatii), apoi pentru paletele deja existente se face planificarea urmatoarelor operatii.

Simulatorul grafic folosit in planificarea ordinelor

Ultima modificare 29.05.2008