Talk:Job-shop problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

[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)
Retrieved from "http://en.wikipedia.org../../../j/o/b/Talk%7EJob-shop_problem_4d55.html"