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. |
Read More: How to Use Solver in Excel (Solving Linear Programming Problems)!
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?
City | Boston | Chicago | Dallas | Denver | LA | Miami | NY | Phoenix | Pittsburgh | SF |
Chicago | 983 | |||||||||
Dallas | 1815 | 1205 | ||||||||
Denver | 1991 | 1050 | 801 | |||||||
LA | 3036 | 2112 | 1425 | 1174 | ||||||
Miami | 1539 | 1390 | 1332 | 1332 | 2757 | |||||
NY | 213 | 840 | 1604 | 1780 | 2825 | 1258 | ||||
Phoenix | 2664 | 1729 | 1027 | 836 | 398 | 2359 | 2442 | |||
Pittsburgh | 792 | 457 | 1237 | 1411 | 2456 | 1250 | 386 | 2073 | ||
SF | 2385 | 2212 | 1765 | 1765 | 403 | 3097 | 3036 | 800 | 2653 | |
Seattle | 2612 | 2052 | 2404 | 1373 | 1909 | 3389 | 2900 | 1482 | 2517 | 817 |
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.
Read More: GRG Multistart and Evolutionary Excel Solver Engines [2 Case Studies]
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 |
1 | 9 | 32 |
2 | 7 | 29 |
3 | 8 | 22 |
4 | 18 | 21 |
5 | 9 | 37 |
6 | 6 | 28 |
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.
Read More: Solving Transportation or Distribution Problems using Excel Solver
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.
Read More: Sequencing problem using Johnson’s algorithm of scheduling n-jobs on 2-machines [Sol]
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.
Thank you Professor for the nice and useful illustration. I teach subjects like Operations Management ad Decision Science and use Excel for solving the problems. Your methods are very helpful. Can you kindly explain how to solve sequencing problem using Johnson’s algorithm of scheduling n-jobs on 2-machines?
I will pass your request to the author, Jagadeesh!
Glad to know it helped you!
Thank you for the very informative tutorial.
I would like some advice though to take the shop scheduling problem 1 step further.
How can I do this at a time/hour level – rather than day?
For example – if we have x amount of jobs in queue; varying in duration
We can only turn around jobs during standard work hours (7 AM and 4 PM).
We also need to meet delivery dates.
How do I arrange jobs in a way that maximizes machine utilization?
Nice model that can be simplified a bit because the help file for solver stats that:
“A constraint such as A1:A5 = alldifferent, where A1:A5 are decision variable cells, requires that these cells must be integers in the range 1 to N (N = 5 in this example), with each variable different from all the others at the solution.”
So constraints G3:G8=1 and G3:G8 = integer are not needed
Alf