It is well known that sequencing problems are notoriously difficult to solve. There are two kinds of sequencing problems: traveling salesperson problem and shop scheduling problem. Today I’d like to introduce how to solve those kinds of problems using Excel Solver.
1 INDEX function
The index function can be used to return a value from within a table. Here is the syntax for the INDEX function.
|INDEX(array, row_num, column_num)|
|array||A range of cells.
If the array contains only one row or column, the corresponding row_num or column_num is optional.
If the array has more than one row and more than one column, INDEX returns the entire row or column when only row_num or column_num is used.
|Row_num||Selects the row in the array from which to return a value.|
|Column_num||Selects the column in the array from which to return a value.|
It returns the value in the cell at the intersection of row_num and column_num if both the row_num and column arguments are used. For example, the intersection of the first row and second column of table C3:G6 is cell D2 and the value in cell D2 is 0. Therefore, the INDEX function returns 0 in cell I3. You can look into other cells from I4 through I6 to figure how the INDEX function works.
2 Travelling Salesperson Problem
Suppose that Jack is a salesman who lives in Dallas. He needs to visit each of the cities listed in the below table and then return to Dallas. Please note that the data in the below table are only dummy data. In what order should Jack visit the cities to minimize the total distance he travels?
2.1 Set up model
To set up the model, distances between cities have been entered into cells from D3 through N13. For example, the distance between Boston and Chicago is 983 km. Dallas is 1815 km away from Boston. We put city no in range P3:P13 and cells in this range serve as By Changing Cells.
The city no for the first city that Jack needs to visit was put in cell P3 and city no for the second city that Jack needs to visit was entered into cell P4. Formula “=INDEX($D$3:$N$13,$P3,$P4)” in cell Q4 can return the distance that Jack will travel from the first city to the second city. By copying this formula into cells from Q5 through Q13, we can get distances that he needs to travel between other cities. Since he needs to travel back to his first city, formula “=INDEX($D$3:$N$13,$P13,$P3)” was entered into cell Q3 to calculate the distance between the last city and the first city. By sum values in range Q3:Q13, we can get the total distances that he travels. To minimize the total distance is our objective and cell Q14 is our target cell.
With the help of VLOOKUP function, we can retrieve the city name in the range R3:R13. For example, the formula in cell R3 is “=VLOOKUP($P3,$B$3:$C$13,2,FALSE)”. Formulas in other cells are copied from this formula.
2.2 Apply Excel Solver to solve the problem
Click on Solver in Analysis group to open Solver Parameters dialog box. Fill the Solver Parameters dialog box as shown in Figure 2.2. You can see that Evolutionary engine was used here.
Constraints “$P$3:$P$13 <= 11” and “$P$3:$P$13 >= 1” are used to ensure that values should be between 1 and 11. Other constraints are that city no should be an integer and they should be different from each other.
2.3 Results returned by Excel
Excel returns solution as shown in Figure 2.3 after we click on Solve. You can see that the minimized distance is 8995 km.Perhaps you’ve already noted that the first city in range Q3:Q13 is not Dallas. It seems that this does not meet the problem’s requirement – Jack lives in Dallas and has to return to Dallas finally. Never mind. What Excel returns is only an order and we can start at any cities. Replace range P2:P13 with data in Figure 2.4 and you will find that the total distance is still 8995 km.
3 Shop Scheduling Problem
A small job shop needs to schedule six jobs. The due date (days measured from today) and days needed to complete each job are given in the following table. There are two machines to work on those jobs. In what order should the jobs be scheduled to minimize the total number of days needed to complete all tasks?
|Job||Days needed||Due date|
3.1 Set up model
Days needed and the due date for jobs were entered into cells from C3 through D8. Cells in range G3:G8 are the By Changing Cells in this case and the job no will be entered into these cells.
By copying formula “=VLOOKUP($G3,$B$3:$C$8,2,FALSE)” from cells H3 into range H4:H8, we can get days needed for each job. Similarly, by copying the formula “=VLOOKUP($G3,$B$3:$D$8,3,FALSE)” into cells K4:K8, we can get days left for each job.
We cannot do the next job without finishing the current job. Therefore, we have to sum days needed for the current job and previous jobs (finished on the same one machine) to compute the total days. Per the problem, the total days should be less than the left days.
Those two machines can start work at the same time. But they may not stop working at the same time because different jobs require a different number of days. Therefore, we need to use the formula “=MAX(I5,I8) to get the total number of days needed to complete work. Cell G9 is our target cell and our objective is to minimize it.
3.2 Apply Excel Solver to solve the problem
Click on Solver in Analysis group to open Solver Parameters dialog box. Fill the Solver Parameters dialog box as shown in Figure 3.2. The evolutionary engine was used here.
The job no should be integers between 1(including 1) and 6(including 6). And they also should be different from each other. Another constraint is the jobs should be finished before the due date.
3.3 Results returned by Excel
From the returned solution shown in Figure 3.3, you can find that we need at least 36 days to finish those six jobs. Job 2, 3, and 6 are done on the same machine. The other 3 tasks are to be completed on another machine.
Download working file
Download the working file from the link below.