The LA Fox Developer Newsletter

October 1999

Scheduling Concepts (Con’t from page 1)

This type of problem is also encountered when a carpenter

needs to cut pieces out of a sheet of plywood, or a tailor is

cuthng pieces of cloth from a bolt of cloth. The container would

be the plywood or bolt of cloth, respectively. Then instead of

putting items into the container, you are taking them out, as

parts of the container.

The “Traveling Salesman” routing problem

The next class of scheduling problem is a routing problem

called the “Traveling Salesman Problem”. It assumes that a

salesman must travel to a number of cities and return to the

starting point. The goal is to have the salesman travel the least

distance. This class of problem is called a “Network” problem.

It is represented diagrammatically as a series of points called

nodes, vertices, or points, joined by lines. This type of problem

is encountered when scheduling the routing of mail carriers,

freight carriers, etc. The lines do not have to represent physical

distance; in some cases the lines represent the cost of travel or

time of travel between the nodes.

In the above figure, point 1 is assumed to be home or the

starting and stopping place.

At first glance, there is a tendency to try to solve this problem

using total enumeration, by building a database table of all the

distances between the cities and then creating a database table

with all the possible combinations. The difficulty with this

approach, as you can see below, is that the possible combina-

tions can be very large.

The total combinations = T

Total number of cities = n

T=(n—1)!

Which means that in the above example with 7 cities there are

720 possible combinations. This is manageable with today’s

computers; in fact, I wrote a FoxPro program to solve this

through total enumeration just to serve as a check for other

approaches. The shortest distance to travel to all of the cities

was 28.533. But, this is a small problem; it doesn’t take too

many additional nodes or cities to overwhelm even the largest

computers.

The most common approach to solving this problem is to find

“local solutions” first, find the cities that are closest and connect

those cities. Then, proceed from the “local solutions” to a

general solution. There is a table of the distances between the

cities below to help you. The closest cities are 5 & 7, then 1 &

2. As it turns out, they are part of the optimal solution. The

next closest cities are 1 & 3; they are not part of the optimal

solution. So, one has to be careful not to assume too much with

this approach. My approach is to only use the closest 25% and

then test combinations that include those solutions. You can

assume that the shortest distance to travel would be a solution

where the salesman does not travel to a city past another city.

So, the solution above could be manageable, if a database table

of distances between cities were used and if it were indexed by

distance from the starting city each time you wanted to evaluate

the next node. This approach can greatly reduce the combina-

tions to be evaluated.

Below is a table of the distances between cities with the

optimum solution in bold type:

"Waiting Line or Queuing” Problems

Waiting line or queuing problems are encountered when we

need to schedule personnel for a shift at work or for the rotation

of duties in a club or to schedule a machine on the shop floor. I

have written a number of FoxPro programs to solve these types

of problems. The following are two examples:

A few years ago, I was a member of a Toastmasters speaking

club. All of the members would rotate through duties each week

with the primary assignment being the need for two speakers

each week. When I was assigned the duty of creating the

weekly schedules, I knew that I had to automate the task. It

took a several hours each week to create the schedules manu-

ally with a spread sheet.

(Con’t, page 8)

Page 7