Parallel task scheduling (original) (raw)
Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel.
| Property | Value |
|---|---|
| dbo:abstract | Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel. Veltman et al. and Drozdowski denote this problem by in the three-field notation introduced by Graham et al. P means that there are several identical machines running in parallel; sizej means that each job has a size parameter; Cmax means that the goal is to minimize the maximum completion time. Some authors use instead. The origins of this problem formulation can be traced back to 1960. For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than unless . (en) |
| dbo:wikiPageID | 62925989 (xsd:integer) |
| dbo:wikiPageLength | 15959 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1101474287 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preemption_(computing) dbr:Open-shop_scheduling dbr:Strong_NP-completeness dbc:Packing_problems dbr:Pseudo-polynomial_time dbr:Optimal_job_scheduling dbr:Computer_science dbr:Partition_problem dbr:Makespan dbc:Optimal_scheduling dbr:Flow_shop_scheduling dbr:Notation_for_theoretic_scheduling_problems dbr:Bin_packing_problem dbr:Operations_Research dbr:Optimization_problem dbr:Job_shop_scheduling dbr:Strip_packing_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Scheduling_problems |
| dct:subject | dbc:Packing_problems dbc:Optimal_scheduling |
| rdfs:comment | Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel. (en) |
| rdfs:label | Parallel task scheduling (en) |
| owl:sameAs | wikidata:Parallel task scheduling https://global.dbpedia.org/id/CwgJ1 |
| prov:wasDerivedFrom | wikipedia-en:Parallel_task_scheduling?oldid=1101474287&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Parallel_task_scheduling |
| is dbo:wikiPageRedirects of | dbr:Parallel_task_scheduling_problem |
| is dbo:wikiPageWikiLink of | dbr:Optimal_job_scheduling dbr:Parallel_task_scheduling_problem |
| is foaf:primaryTopic of | wikipedia-en:Parallel_task_scheduling |