StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POJob Shop Scheduling - class project -advice on references/alg. to use for implementing & getting experimental results
text
Body
copied!<p>I'm working on a project to implement and test a NP-Hard/Complete problem. I had a general idea to do something with scheduling and have read a lot about the Job Shop problem. I know there are famous test cases/benchmarks to use from the OR library. I have code in place (Java) to read in a test instance and store its data. Now I feel stuck in a loop trying to find an algorithm/way to create a schedule and then present an optimal schedule. I read a lot of academic papers but I usually get a little lost in them, especially with complex set notation. I wish I could find more examples of pseudo-code. I know this is a classic problem and I'm wondering if anybody has suggestions to straight-forward classic solutions to job shop - especially any that have pseudo-code examples as well. I don't need to do original research for this project. I just need to learn how to apply a known technique for solving a NP-Hard problem, write code, run test, present experimental results and comment on them. Any advice or help would be much appreciated.</p> <p>"A number of jobs have to be done and every job consists of using a number of machines for a certain amount of time. The problem is to find the best planning to do all the jobs on all the different machines in the shortest period of time."</p> <p>Example Problem Instance:</p> <p>Each row in the datalines section specifies a job by 10 pairs of consecutive numbers. Each pair of numbers defines one task of the job, which represents the processing of a job on a machine. For each pair, the first number identifies the machine it executes on and the second number is the duration. The order of the 10 pairs defines the sequence of the tasks for a job.</p> <p>"Lawrence 10x10 instance" (Table 6, instance 4); also called (seta4) or (A4)(Applegate and Cook; 1991) -10 machines numbered 0-9 -10 rows = 10 jobs --optimal: 842</p> <p>2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89</p> <p>4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21</p> <p>9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71</p> <p>1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55</p> <p>6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50</p> <p>7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52</p> <p>6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95</p> <p>0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8</p> <p>5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75</p> <p>9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload