Vi anser att den klassiska online schemaläggning problem över enstaka och parallella maskiner med målet att minimera total viktad flödestid. Vi använder en intuitiv och systematisk analysmetod och visar att den viktade kortaste bearbetningstiden (WSPT) är en optimal online-algoritm med det konkurrenskraftiga förhållandet +1 för fallet med en maskin, och det är ( +(3/2)−(1/2 ))-konkurrenskraft för fallet med parallella maskiner ( > 1), där P är förhållandet mellan den längsta och den kortaste bearbetningstiden.
Dessutom är viktad kortaste bearbetningstid (WSPT) en O(Δ + 3 2 − 1 2m )-konkurrenskraftig algoritm REF för det mer allmänna problemet där varje uppgift har en vikt och målet är att minimera den totala viktade flödestiden.
WSPT's Competitive Performance for Minimizing the Total Weighted Flow Time: From Single to Parallel Machines
{'venue': None, 'journal': 'Mathematical Problems in Engineering', 'mag_field_of_study': ['Computer Science']}