Megelőzési feltételeket tartalmazó ütemezési feladatok párhuzamosítása mohó algoritmusok által generált rendezés-kongruenciák segítségével

Szerzők

  • Körei Attila Miskolci Egyetem
  • Szilágyi Szilvia Miskolci Egyetem

DOI:

https://doi.org/10.35925/j.multi.2019.1.18

Kulcsszavak:

részbenrendezett halmaz, lineáris kiterjesztés, párhuzamos ütemezés, rendezés-kongruencia

Absztrakt

Az ütemezési problémák egy alternatív megközelítését jelentik azok az eljárások, amelyek a diszkrét matematika eszközeivel dolgoznak. A részbenrendezett halmazok rendezés-kongruenciáinak tanulmányozásakor világossá vált, hogy a minimális lineáris rendezés-kongruenciák jól alkalmazhatók ütemezési feladatok megoldására. Ez a metódus nemcsak akkor használható, ha egy gép dolgozik, hanem kiterjeszthető olyan esetekre is, amikor egymással párhuzamosan több egységnyi kapacitású gép dolgozhat. Cikkünkben a megelőzési feltételeket tartalmazó ütemezési feladatokra olyan optimális vagy közel optimális megoldást adó algoritmusokat mutatunk be, amelyek a megoldást minimális lineáris kongruencia formájában állítják elő.

##submission.downloads##

Megjelent

2019-10-07