Deal with Sequencing Problems Using Excel Solver!

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.

Sequencing Problems with Excel Solver Image 1.1

Figure 1.1

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.

Sequencing Problems with Excel Solver Image 2.1

Figure 2.1 [click on the image to get a full view]

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.

Sequencing Problems with Excel Solver Image 2.2

Figure 2.2

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.

Sequencing Problems with Excel Solver Image 2.3

Figure 2.3 [click on the image to get a full view]

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.
Sequencing Problems with Excel Solver Image 2.4

Figure 2.4

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.

Sequencing Problems with Excel Solver Image 3.1

Figure 3.1

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.

Sequencing Problems with Excel Solver Image 3.2

Figure 3.2

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.

Sequencing Problems with Excel Solver Image 3.3

Figure 3.3

Download working file

Download the working file from the link below.

Zhiping Yan

I am from China and this photo was taken in a classical garden. There are many similar gardens in China, attracting a lot of visitors every year, especially in spring and summer. I was major in Biotechnology. But I took a job as a SAS programmer because I prefer programming. Besides SAS, I also learned Excel VBA in my spare time. It is fantastic to be able to manipulate data, files and even to interact with the internet via programming. This will save me a lot of time. I am keen to learn new things.

3 Comments
  1. 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?

  2. 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?

Leave a reply

ExcelDemy
Logo