Uniform-machines scheduling (original) (raw)
Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run-time
| Property | Value |
|---|---|
| dbo:abstract | Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run-time of job j on machine i is pi,j = pj / si. In the standard three-field notation for optimal job scheduling problems, the uniform-machine variant is denoted by Q in the first field. For example, the problem denoted by " Q| |
| dbo:wikiPageExternalLink | http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/pqr_nop/pqr_nop/ |
| dbo:wikiPageID | 3302845 (xsd:integer) |
| dbo:wikiPageLength | 14077 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1049750550 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Open-shop_scheduling dbr:Order_theory dbr:Optimal_job_scheduling dbr:Computer_science dbr:Identical-machines_scheduling dbr:Partition_problem dbr:Makespan dbc:Optimal_scheduling dbr:Weighted_arithmetic_mean dbr:Lattice_(order) dbr:Dynamic_programming dbr:Flow_shop_scheduling dbr:Polynomial-time_approximation_scheme dbr:FPTAS dbr:Identical_machine_scheduling dbr:Operations_Research dbr:Optimization_problem dbr:Knapsack_problem dbr:Longest-processing-time-first_scheduling dbr:List_scheduling dbr:Job_shop_scheduling dbr:Partial_ordering dbr:Longest_processing_time dbr:Truthful_mechanism |
| dbp:wikiPageUsesTemplate | dbt:Scheduling_problems |
| dct:subject | dbc:Optimal_scheduling |
| rdfs:comment | Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run-time (en) Optymalne szeregowanie zadań dla wielu procesorów jest jednym z trudnych (NP-zupełnych) optymalizacyjnych zagadnień w informatyce. Jest jednocześnie jednym z problemów zaskakująco prostych w sformułowaniu i bardzo praktycznych. (pl) |
| rdfs:label | Optymalne szeregowanie zadań dla wielu procesorów (pl) Uniform-machines scheduling (en) |
| owl:sameAs | wikidata:Uniform-machines scheduling dbpedia-pl:Uniform-machines scheduling https://global.dbpedia.org/id/4repc |
| prov:wasDerivedFrom | wikipedia-en:Uniform-machines_scheduling?oldid=1049750550&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Uniform-machines_scheduling |
| is dbo:wikiPageRedirects of | dbr:Uniform_machine_scheduling dbr:Parallel-machines_scheduling dbr:Minimum_makespan_problem dbr:Related-machines_scheduling |
| is dbo:wikiPageWikiLink of | dbr:Uniform_machine_scheduling dbr:Optimal_job_scheduling dbr:Fully_polynomial-time_approximation_scheme dbr:Longest-processing-time-first_scheduling dbr:Multifit_algorithm dbr:Unrelated-machines_scheduling dbr:Truthful_job_scheduling dbr:Parallel-machines_scheduling dbr:Minimum_makespan_problem dbr:Related-machines_scheduling |
| is foaf:primaryTopic of | wikipedia-en:Uniform-machines_scheduling |