Talk:Job-shop problem

From Wikipedia, the free encyclopedia

WikiProject Systems
Systems science Portal
This article is within the scope of WikiProject Systems, which collaborates on articles related to Systems science.
Systems rating: Start Class Mid importance  Field: Operations research
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

[edit] 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)