![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||||||
|
This and job-shop problem are about the same thing. U2fanboi ( talk) 13:28, 20 March 2014 (UTC) Merged - I moved any other info from job-shop problem to here and set a redirect. U2fanboi ( talk) 13:50, 8 May 2014 (UTC)
Johnson's algorithm is not really for job shops, it solves flow-shop, which is a particular case (all tasks in the same order) 193.52.209.252 ( talk) 08:43, 3 November 2009 (UTC)
I don't think there's anything on this page not on job shop scheduling. However, I prefer this title. U2fanboi ( talk) 13:26, 20 March 2014 (UTC)
Merged U2fanboi ( talk) 13:45, 8 May 2014 (UTC)
Also merging the talk pages for completeness - following stuff came from job-shop problem Talk page. U2fanboi ( talk) 13:53, 8 May 2014 (UTC)
I don't think that the definition of a job shop problem is correct. In a job-shop problem, the order in which a job must be performed on the machines is fixed, for each job. The definition given here corresponds to an open-shop problem. —Preceding unsigned comment added by Houseofwealth ( talk • contribs) 00:42, 13 May 2011 (UTC)
If "Statement of the problem" can be called a definition, then it is the definition of open-shop problem. See interwiki articles. МетаСкептик12 ( talk) 12:01, 25 April 2013 (UTC)
At the moment, the article consists of a one-line definition and a big example. I think the definition is at least incomplete: the term "job-shop problem" usually refers to a scheduling problem, which is combinatorial optimization, not linear programming. The example is treated in great detail in a way that is fit for a text book, but not for an encyclopaedia. Finally, the example is abandoned half way. -- Jitse Niesen ( talk) 06:30, 8 June 2006 (UTC)
I've begun a re-write... anyone want to help? -- Sullivan.t.j 16:18, 19 September 2006 (UTC)
Also, the Hardness proof is incorrect. The "job shop problem with one machine", either with minimum makespan or total processing times, is not an hard problem. Any non-idle schedule will solve the first and SPT will solve the second.
I've removed the following. It should be rephrased since there's a direct contradiction with the paragraph above this. Both are true by the way but you can't make a statement and say it's nonsense in the next line. ;)
The above statement is more or less nonsense. Of course the traveling salesman problem (TSP) is NP-hard. However the polynomial reduction of a general TSP into JSP with a single machine is far from clear. In particularly the Job-shop problem on a single maschine is polynomial solveable in many cases. http://www-desir.lip6.fr/~durrc/query/, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6538, http://www.informatik.uni-osnabrueck.de/knust/class/. — Preceding unsigned comment added by 81.21.138.36 ( talk) 09:33, 20 April 2012 (UTC)
Omid Gholami — Preceding unsigned comment added by 37.214.43.81 ( talk) 17:07, 4 February 2013 (UTC)
A more general problem cannot be proven to be NP-hard when one of its special cases is NP-hard, likewise a more special problem may not be NP-hard if its general problem is NP-hard. There needs to be a polynomial time reduction from the JSP to the TSP to show that it is NP-hard. But this must be done for each variant separately. — Preceding unsigned comment added by DonAndre ( talk • contribs) 09:28, 30 July 2014 (UTC)
This is still unclear because sequence-dependent setup is still not defined. I can guess what it means in order to make the connection to TSP, but I shouldn't have to. Also, there must be a simple argument that does not require sequence-dependent setup since this seems non-central to job scheduling. I mean I could take any problem and add some assumptions and make it NP-hard. Why is this sequence-dependent assumption important?
NP-hardness explaination is false here and I appreciate if someone remove it or replace with right explaination (based on 3-partition problem or etc). — Preceding unsigned comment added by 85.249.24.74 ( talk) 08:39, 11 January 2021 (UTC)