Abstrakt. I detta dokument överväger vi problemet med schemaläggning på datorplattformar som består av flera oberoende organisationer, känd som Multi-Organization Scheduling Problem (MOSP). Varje organisation tillhandahåller både resurser och uppgifter och följer sina egna mål. Vi är intresserade av det bästa sättet att minimera makepanen på hela plattformen när organisationerna beter sig på ett själviskt sätt. Vi studerar komplexiteten i MOSP problemet med två olika lokala mål - makespan och genomsnittlig slutförande tid - och visar att MOSP är NP-Hard i båda fallen. Vi definierar formellt en självisk föreställning med hjälp av begränsningar av tidtabellerna. Vi bevisar att själviskt beteende tvingar en lägre gräns på 2 på approximationen förhållandet för den globala makepan. Vi presenterar olika approximationsalgoritmer av förhållande 2 som validerar själviska restriktioner. Dessa algoritmer utvärderas experimentellt genom simulering och uppvisar goda genomsnittliga prestanda.
Cohen m.fl. REF analyserade problemets komplexitet när organisationerna är lokalt intresserade av att minimera antingen makespan (MOSP(C max )) eller den genomsnittliga avslutningstiden (MOSP( C i )).
Analysis of Multi-Organization Scheduling Algorithms
{'venue': 'Euro-Par', 'journal': None, 'mag_field_of_study': ['Computer Science']}