Unrelated-machines scheduling (original) (raw)
Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized (usually, the makespan should be minimized). The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj (where sj is the speed of machine j), and identical-machines scheduling - in which pi,j = pi (the same run-time on all machines).
| Property | Value |
|---|---|
| dbo:abstract | Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized (usually, the makespan should be minimized). The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj (where sj is the speed of machine j), and identical-machines scheduling - in which pi,j = pi (the same run-time on all machines). In the standard three-field notation for optimal job scheduling problems, the unrelated-machines variant is denoted by R in the first field. For example, the problem denoted by " R| |
| dbo:wikiPageExternalLink | http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/pqr_nop/pqr_nop/ |
| dbo:wikiPageID | 68032323 (xsd:integer) |
| dbo:wikiPageLength | 13331 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087923205 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Max-min_item_allocation dbr:Egalitarian_item_allocation dbr:Genetic_algorithm dbr:Configuration_linear_program dbr:Optimal_job_scheduling dbr:Simulated_annealing dbr:Computer_science dbr:Identical-machines_scheduling dbr:Partition_problem dbr:Makespan dbr:Tabu_search dbc:Optimal_scheduling dbr:Weighted_arithmetic_mean dbr:Local_search_(optimization) dbr:Dynamic_programming dbr:Polynomial-time_approximation_scheme dbr:FPTAS dbr:Operations_Research dbr:Optimization_problem dbr:Knapsack_problem dbr:Randomized_rounding dbr:Uniform-machines_scheduling dbr:Truthful_job_scheduling |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:Scheduling_problems |
| dct:subject | dbc:Optimal_scheduling |
| rdfs:comment | Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized (usually, the makespan should be minimized). The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj (where sj is the speed of machine j), and identical-machines scheduling - in which pi,j = pi (the same run-time on all machines). (en) |
| rdfs:label | Unrelated-machines scheduling (en) |
| owl:sameAs | wikidata:Unrelated-machines scheduling https://global.dbpedia.org/id/FqzVR |
| prov:wasDerivedFrom | wikipedia-en:Unrelated-machines_scheduling?oldid=1087923205&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Unrelated-machines_scheduling |
| is dbo:wikiPageWikiLink of | dbr:Egalitarian_item_allocation dbr:Configuration_linear_program dbr:Optimal_job_scheduling dbr:Fully_polynomial-time_approximation_scheme dbr:Matroid-constrained_number_partitioning dbr:High-multiplicity_bin_packing |
| is foaf:primaryTopic of | wikipedia-en:Unrelated-machines_scheduling |