Brutal Force Method for Assignment Problems (2020)
Solve a Job Assignment (or Assembly Sequencing, or TSP problem) problem by using brutal force method to enumerate all possible solutions and compute their objective values. Report the best solution and objective value.
- Read the input files from a text file with the format given at the end of this document.
- Loop through each possible assignment, evaluated its setup time, and display the content of the assignment on the UI.
- Recursive function is required in your code to systematically constitute all compositions of the jobs in difference sequences.
| 7 | n |
| 14 5 8 7 6 10 8
2 12 6 5 9 4 3 7 8 3 9 8 11 4 2 4 6 10 7 9 3 5 8 10 14 3 5 9 4 8 7 6 10 8 7 3 5 7 8 6 4 7 |
c00~c0(n-1) c10~c1(n-1) c20~c2(n-1) c30~c3(n-1) c40~c4(n-1) c50~c5(n-1) c60~c6(n-1) |
- In addition, report the best solution and the minimal setup time.
Job Assignment Problem:
A company has n machines and n jobs to be processed. Each job must be assigned with exactly one machine to process the job. The setup time for a machine to process a job is dependent on the job and the machine. Assume thatC=Ci, j , Ci, j is the setup time of machine j to process job i. The company wants to minimize the total setup time. Let a solutionx=x0,x1,L,xn−1, xj 0,1,L,n−1xj xj such that job
n−1
xj is assigned to machine j. Therefore, the total setup time of the given solution x isT=Cx j , j , which is to
j=0
be minimized.
The benchmarks of job assignment problems are defined files with file extension “aop”. Sample file:
