Job-shop scheduling (original) (raw)
Le séquençage de tâches (en anglais job sequencing) est un des nombreux modèles d'ordonnancement d'atelier de production. En informatique théorique, et notamment en complexité des algorithmes, c'est la formulation d'un problème particulier d'ordonnancement considéré par Richard Karp dans sa célèbre description des 21 problèmes NP-complets.
| Property | Value |
|---|---|
| dbo:abstract | Unter einem Job Shop versteht man in der Maschinenbelegungsplanung eine Klasse von Modellen, bei denen auf m Maschinen n Aufträge zu fertigen sind. Ein Auftrag besteht dabei aus einer Folge von g Arbeitsgängen, die auf bestimmten Maschinen bearbeitet werden müssen. Dabei kann jeder Auftrag grundsätzlich auch mehrmals auf derselben Maschine bearbeitet werden oder auch manche Maschinen auslassen. Es handelt sich somit um Modelle von Produktionssystemen mit Werkstattfertigung. Wenn die Folge der Arbeitsgänge für jeden Auftrag identisch ist, handelt es sich um einen Flow-Shop, der ein Modell der Fließproduktion darstellt. Wird auf jeder Maschine die gleiche Folge von Aufträgen bearbeitet, handelt es sich um einen Permutations-Job Shop. Für den Fall, dass nur eine Maschine vorhanden ist, ergibt sich ein Ein-Maschinen Problem; falls die Aufträge aus nur einem Arbeitsgang bestehen, der auf einer beliebigen Maschine zu bearbeiten ist, handelt es sich um ein Maschinenbelegungsproblem mit parallelen Maschinen. (de) Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) 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 with varying processing power, 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 job-shop scheduling, each job consists of a set of operations O1, O2, ..., On which need to be processed in a specific order (known as precedence constraints). Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set (the machines in each set are identical). The name originally came from the scheduling of jobs in a job shop, but the theme has wide applications beyond that type of instance. This problem is one of the best known combinatorial optimization problems, and was the first problem for which competitive analysis was presented, by Graham in 1966. Best problem instances for basic model with makespan objective are due to Taillard. In the standard three-field notation for optimal job scheduling problems, the job-shop variant is denoted by J in the first field. For example, the problem denoted by " J3| |
| dbo:wikiPageExternalLink | http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/jobshop.dir/best_lb_up.txt https://www.mat.univie.ac.at/~neum/glopt/software_g.html https://link.springer.com/content/pdf/bfm%3A978-3-540-24804-0%2F1.pdf |
| dbo:wikiPageID | 16384086 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-pt:Escalonamento_de_Job_Shop |
| dbo:wikiPageLength | 18861 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109363089 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Open-shop_scheduling dbr:David_Shmoys dbr:Deadlock dbr:Dorit_S._Hochbaum dbr:Sequence-dependent_setup dbr:Genetic_algorithm_scheduling dbr:Genetic_algorithm dbr:NP-complete dbr:NP-hard dbr:Optimal_job_scheduling dbr:Lp_space dbr:Combinatorial_optimization dbr:Competitive_analysis_(online_algorithm) dbr:Computer_science dbr:Makespan dbc:Optimal_scheduling dbr:Disjunctive_graph dbr:Linear_programming dbr:AMPL dbr:Dynamic_programming dbr:Finite_set dbr:P=NP dbr:Flow-shop_scheduling dbr:List_of_NP-complete_problems dbr:Job_shop dbr:Bin_packing_problem dbr:Coffman–Graham_algorithm dbr:Polynomial-time_approximation_scheme dbr:Operations_Research dbr:Optimal_control dbr:Optimization_problem dbr:Set_(mathematics) dbr:Workflow dbr:Scheduling_(production_processes) dbr:Traveling_salesman_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Div_col dbt:Div_col_end dbt:ISBN dbt:Math dbt:Reflist dbt:See_also dbt:Generalize dbt:Scheduling_problems |
| dcterms:subject | dbc:Optimal_scheduling |
| rdf:type | owl:Thing |
| rdfs:comment | Le séquençage de tâches (en anglais job sequencing) est un des nombreux modèles d'ordonnancement d'atelier de production. En informatique théorique, et notamment en complexité des algorithmes, c'est la formulation d'un problème particulier d'ordonnancement considéré par Richard Karp dans sa célèbre description des 21 problèmes NP-complets. (fr) Job sequencing is een probleem uit de theoretische computerwetenschap en combinatoriek. (nl) Unter einem Job Shop versteht man in der Maschinenbelegungsplanung eine Klasse von Modellen, bei denen auf m Maschinen n Aufträge zu fertigen sind. Ein Auftrag besteht dabei aus einer Folge von g Arbeitsgängen, die auf bestimmten Maschinen bearbeitet werden müssen. Dabei kann jeder Auftrag grundsätzlich auch mehrmals auf derselben Maschine bearbeitet werden oder auch manche Maschinen auslassen. Es handelt sich somit um Modelle von Produktionssystemen mit Werkstattfertigung. Wenn die Folge der Arbeitsgänge für jeden Auftrag identisch ist, handelt es sich um einen Flow-Shop, der ein Modell der Fließproduktion darstellt. Wird auf jeder Maschine die gleiche Folge von Aufträgen bearbeitet, handelt es sich um einen Permutations-Job Shop. Für den Fall, dass nur eine Maschine vorhanden ist, ergibt (de) Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) 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 with varying processing power, 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 job-shop scheduling, each job consists of a set of operations O1, O2, ..., On which need to be processed in a specific order (known as precedence constraints). Each operation has a specific machine that it needs to be processed on and only one operation in a job c (en) Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае проблемы формулируются так:Задано некоторое множество работ (требований) с определённым набором характеристик: длительность обработки требования (простейший случай), стоимость обработки требования, момент поступления требования, директивный срок окончания обслуживания требования. Задано некоторое множество машин (приборов) , на которых требования должны обслуживаться в соответствии с некоторым порядком. Задачи теории расписаний можно разделить на две группы: (ru) Теорія розкладів — розділ дискретної математики, що вивчає проблеми впорядкування. У загальному випадку проблеми формулюються так: Дано деяку множину робіт (вимог) з певним набором характеристик: тривалість опрацювання вимоги (найпростіший випадок), вартість опрацювання вимоги, момент надходження вимоги, директивний термін закінчення опрацювання вимоги. Задано деяку множину машин (приладів) , на яких вимоги мають опрацьовуватися відповідно до деякого порядку. Задачі теорії розкладів можна розділити на дві групи: (uk) |
| rdfs:label | Job Shop (de) Séquençage de tâches (fr) Job-shop scheduling (en) Job sequencing (nl) Теория расписаний (ru) Теорія розкладів (uk) |
| rdfs:seeAlso | dbr:Johnson's_rule dbr:Multiprocessor_scheduling |
| owl:sameAs | wikidata:Job-shop scheduling dbpedia-de:Job-shop scheduling dbpedia-fa:Job-shop scheduling dbpedia-fr:Job-shop scheduling dbpedia-nl:Job-shop scheduling dbpedia-ru:Job-shop scheduling dbpedia-uk:Job-shop scheduling https://global.dbpedia.org/id/4oVzZ |
| prov:wasDerivedFrom | wikipedia-en:Job-shop_scheduling?oldid=1109363089&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Job-shop_scheduling |
| is dbo:wikiPageRedirects of | dbr:Job_Shop_Scheduling dbr:Job_shop_scheduling dbr:Job-shop_problem |
| is dbo:wikiPageWikiLink of | dbr:Open-shop_scheduling dbr:Job_Shop_Scheduling dbr:Optimal_job_scheduling dbr:Ant_colony_optimization_algorithms dbr:Simulated_annealing dbr:Flow-shop_scheduling dbr:List_of_NP-complete_problems dbr:Job_shop dbr:Job_shop_scheduling dbr:Job-shop_problem |
| is foaf:primaryTopic of | wikipedia-en:Job-shop_scheduling |