Talk:Job-shop scheduling

(Redirected from Talk:Job shop scheduling)
Latest comment: 3 years ago by 85.249.24.74 in topic NP Hard

Merge proposal

edit

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)Reply

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)Reply

Merge proposal

edit

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)Reply

MergedU2fanboi (talk) 13:45, 8 May 2014 (UTC)Reply

Also merging the talk pages for completeness - following stuff came from job-shop problem Talk page. U2fanboi (talk) 13:53, 8 May 2014 (UTC)Reply

Q about the definition

edit

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 (talkcontribs) 00:42, 13 May 2011 (UTC)Reply

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)Reply

Rewrite needed

edit

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)Reply

I've begun a re-write... anyone want to help? --Sullivan.t.j 16:18, 19 September 2006 (UTC)Reply


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.

That depends on what you mean by "solve". A non-idling condition might avoid hanging, but might not guarantee optimality. The proof as given in the article is correct: TSP "is" (up to some kind of isomorphism) JSP with one machine, and TSP is an NP problem... in fact, it is NP-complete. Sullivan.t.j 02:37, 1 January 2007 (UTC)Reply
I would like to see a reduction from a TSP problem to a JSP problem, since it is not trivial to me how you would cope with the different traveltimes in TSP for say A to B and A to C, while in JSP you can only give one tail length per job. These differences create the problem in TSP, the trouble in JSP arrises from precedence relations and multiple machines. 19 December 2007 —Preceding unsigned comment added by 80.60.253.231 (talk) 10:22, 19 December 2007 (UTC)Reply
The analogue of "travel time" in TSP is the "cost function" in JSP. Sullivan.t.j (talk) 10:27, 19 December 2007 (UTC)Reply

NP Hard

edit

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) Reply

Omid Gholami — Preceding unsigned comment added by 37.214.43.81 (talk) 17:07, 4 February 2013 (UTC)Reply

If JSP is defined with arbitrary object function, as OSP in the article, then JSP is NP-hard wihtout any references to TSP. You must try all permutations from n!. But it is triviality. Thank you for references to p.s. of JSP. МетаСкептик12 (talk) 10:41, 25 April 2013 (UTC)Reply

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 (talkcontribs) 09:28, 30 July 2014 (UTC)Reply

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)Reply