Talk:Job-shop scheduling

Merge proposal

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)

Merge proposal

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)

MergedU2fanboi (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)

Q about the definition

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)

Rewrite needed

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.

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)

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)

The analogue of "travel time" in TSP is the "cost function" in JSP. Sullivan.t.j (talk) 10:27, 19 December 2007 (UTC)

NP Hard

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)

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)

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)

About this being the first problem where competitive analysis was performed

In the Article it says "[...]was the first problem for which competitive analysis was presented, by Graham in 1966[...]". This contradicts the article on competetive analysis which says "The classic on-line problem first analysed with competitive analysis (Sleator & Tarjan 1985) is the list update problem[...]"

Clearly one of those two statements is wrong if I understand them correctly. I'm not sure what to do about this. It looks like the paper linked with the first statement contains something that looks like a competetive analysis but I haven't got the time to take a closer look at it. JoghurtQuark (talk) 17:59, 21 December 2024 (UTC)