This HTML5 document contains 58 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Antoon_Kolen
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
dbr:Interval_scheduling
rdf:type
dbo:Disease yago:Abstraction100002137 yago:WikicatSchedulingAlgorithms yago:Algorithm105847438 yago:Act100030358 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Event100029378
rdfs:label
Interval scheduling
rdfs:comment
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be processed by some machine (or, equivalently, scheduled on some resource). For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap on the machine/resource. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.
dcterms:subject
dbc:Optimal_scheduling
dbo:wikiPageID
7570573
dbo:wikiPageRevisionID
1059529651
dbo:wikiPageWikiLink
dbr:Identical-machines_scheduling dbr:Boolean_satisfiability_problem dbr:Job_stream dbc:Optimal_scheduling dbr:2-SAT dbr:Single-machine_scheduling dbr:Algorithm dbr:Computer_science dbr:Throughput dbr:Independent_set_(graph_theory) dbr:Optimal_job_scheduling dbr:Linear_programming_relaxation dbr:Interval_graph dbr:Greedy_algorithm dbr:MaxSNP dbr:Intersection_graph dbr:Earliest_deadline_first_scheduling dbr:2-satisfiability dbr:Charging_argument dbr:NP-complete dbr:Maximum_disjoint_set
owl:sameAs
wikidata:Q17092629 yago-res:Interval_scheduling freebase:m.0265mbd n17:fT8m
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Short_description dbt:Scheduling_problems
dbo:abstract
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be processed by some machine (or, equivalently, scheduled on some resource). For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap on the machine/resource. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap. The interval scheduling maximization problem (ISMP) is to find a largest compatible set, i.e., a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible, that is, to maximize the throughput. It is equivalent to finding a maximum independent set in an interval graph. A generalization of the problem considers machines/resources. Here the goal is to find compatible subsets whose union is the largest. In an upgraded version of the problem, the intervals are partitioned into groups. A subset of intervals is compatible if no two intervals overlap, and moreover, no two intervals belong to the same group (i.e., the subset contains at most a single representative of each group). Each group of intervals corresponds to a single task, and represents several alternative intervals in which it can be executed. The group interval scheduling decision problem (GISDP) is to decide whether there exists a compatible set in which all groups are represented. The goal here is to execute a single representative task from each group. GISDPk is a restricted version of GISDP in which the number of intervals in each group is at most k. The group interval scheduling maximization problem (GISMP) is to find a largest compatible set - a set of non-overlapping representatives of maximum size. The goal here is to execute a representative task from as many groups as possible. GISMPk is a restricted version of GISMP in which the number of intervals in each group is at most k. This problem is often called JISPk, where J stands for Job. GISMP is the most general problem; the other two problems can be seen as special cases of it: * ISMP is the special case in which each task belongs to its own group (i.e. it is equal to GISMP1). * GISDP is the problem of deciding whether the maximum exactly equals the number of groups. All these problems can be generalized by adding a weight for each interval, representing the profit from executing the task in that interval. Then, the goal is to maximize the total weight. All these problems are special cases of single-machine scheduling, since they assume that all tasks must run on a single processor. Single-machine scheduling is a special case of optimal job scheduling.
gold:hypernym
dbr:Problems
prov:wasDerivedFrom
wikipedia-en:Interval_scheduling?oldid=1059529651&ns=0
dbo:wikiPageLength
14810
foaf:isPrimaryTopicOf
wikipedia-en:Interval_scheduling
Subject Item
dbr:Interval
dbo:wikiPageWikiLink
dbr:Interval_scheduling
dbo:wikiPageDisambiguates
dbr:Interval_scheduling
Subject Item
dbr:Maximum_disjoint_set
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
dbr:Activity_selection_problem
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
dbr:Dynamic_programming
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
dbr:Interval_graph
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
dbr:Single-machine_scheduling
dbo:wikiPageWikiLink
dbr:Interval_scheduling
Subject Item
wikipedia-en:Interval_scheduling
foaf:primaryTopic
dbr:Interval_scheduling