Redan 1966, Graham visade att en enkel procedur som kallas lista schemaläggning ger en 2- approximation algoritm för det centrala problemet med schemaläggning företräde begränsade jobb på identiska maskiner för att minimera makespan. Fram till detta datum har den förblivit den bästa algoritmen och huruvida den kan eller inte kan förbättras har blivit ett stort öppet problem i schemaläggningsteorin. Vi tar itu med detta problem genom att etablera en ganska överraskande relation mellan tillnärmningen av det aktuella problemet och schemaläggningsprioritet begränsade jobb på en enda maskin för att minimera viktad slutförandetid. Mer specifikt, vi bevisar att om den enda maskinen problemet är svårt att approximera inom en faktor på 2 − då den anses parallella maskin problemet, även i fallet med enhet bearbetningstider, är svårt att approximation inom en faktor på 2 −  på, där  till 0 som tenderar att 0. Kombinera detta med Bansal & Khot nyligen hårdhet resultat för den enda maskinen problem ger att det är NP-hård att förbättra på approximation förhållandet som erhållits av Graham, förutsatt en ny variant av de unika spel gissning.
Det har sedan visats att det är NP-hård att förbättra på denna approximation förhållande, förutsatt att en ny variant av de unika spel antar REF.
Conditional hardness of precedence constrained scheduling on identical machines
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}