Abstrakt. Problemet med icke förebyggande schemaläggning en uppsättning av rn delvis beställda uppgifter på n identiska processorer som är föremål för interprocessor kommunikationsförseningar studeras i ett försök att minimera makespan. En ny heuristisk, kallad Earliest Task First (ETF), designas och analyseras. Det visas att de makespan wEx-genererade av ETF alltid uppfyller Eq.. (2 1/n wopti) + C, där Wopti) är den optimala makepan utan att överväga kommunikationsförseningar och C är kommunikationskraven över några omedelbara föregångare-omedelbara efterföljare par längs en kedja. En algoritm tillhandahålls också för att beräkna C. Tids komplexiteten hos Algoritm ETF är O (nm2).
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. REF föreslår en algoritm som kallas Earliest Task First (ETF).
Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}