Home > Search Results: keywords:"scheduling|approximation algorithms|makespan|uniform speeds"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.00 seconds. 
Two-phase scheduling with unknown speeds
 Minařík, Josef ; Sgall, Jiří (advisor) ; Eberle, Franziska (referee)
Speed-robust scheduling is a two-stage scheduling problem with a makespan objective. We are given processing times of n jobs, number of machines m and number of bags b. We have to group the jobs into bags that are to be scheduled on machines of currently unknown speed. The goal is to minimize the worst-case ratio of our makespan and makespan of an adversary who does not have to create bags and assigns jobs directly to machines. So far, the problem has been mostly studied for b = m. We generalize previously known results for infinitesimal jobs (called sand) and prove that the best achievable competitive ratio is mb mb−(m−1)b . We present an algorithm for the case of identical jobs (called bricks) with competitive ratio at most 1.6 in the case b = m, improving the best previously known value of 1.8. We introduce a new category called p-pebbles, those are jobs with processing time at most p times the average load of a machine. Pebbles are half way between sand and the general case (called rocks). We present an algorithm for pebbles that has better robustness factor than the best known algorithm for rocks for small values of p (for p less than 2 − e e−1 in the case b = m). 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English