Wyniki wyszukiwania dla: SZEREGOWANIE ZWARTE

• Compact scheduling of zero-one time operations in multi-stage systems.

  Publikacja

  • K. Giaro
  • M. Kubale

  - Rok 2004

  Rozważamy szeregowanie zwarte na maszynach dedykowanych z zero-jedynkowymi operacjami w modelu otwartym, przepływowym i mieszanym. Harmonogramy zostały zmodelowane przy pomocy pokolorowań krawędzi grafu konfliktów z pewnymi dodatkowymi ograniczeniami. Dowodzimy NP-trudności problemów w przypadku ogólnym oraz prezentujemy przegląd znanych wielomianowych algorytmów szeregujących dla systemów o specyficznej budowie.