Example File:  GHSAMPLE.XLS, Scheduler worksheet

Solution Type:  Enumerated Chromosomes

This example is located in a tab labeled Scheduler in the GHSAMPLE.XLS worksheet that was installed in the C:\GENEHUNTER\EXAMPLES\EXCEL subdirectory if you chose the default directory during GeneHunter installation. (If you install the entire AI Trilogy set of programs, the GeneHunter folder is a subfolder of the C:\AI Trilogy folder.)

One of the most important uses of genetic algorithms is their ability to create optimum schedules for just about any reasonably sized scheduling problem.  Gas have been used for transportation scheduling [Ref. 17 ], classroom schedules, and several types of job shop scheduling problems [Ref. 17].  In our example, called SCHEDULER, we will be building a job scheduler based upon the example described by Cleveland G., and Smith S.[Ref. 14 ].

Unfortunately, formulating a fitness function for a scheduling system is not always an easy task.  For this reason, there may be quite an opportunity for entrepreneurs to build GA applications using GALIB and Visual Basic for specific job scheduling environments.  In fact, few of these fitness functions will be able to be developed with formulas alone, but it was possible to use our Excel GeneHunter interface in our example since Excel contains Visual Basic for Applications (VBA).  It was not hard to write the fitness function in a VBA module.  A slightly different shop will no doubt require changes to the fitness function, and some could get quite complex.

In our example, we are the manager of a small circuit board assembly plant that assembles, wires, solders, and tests a number of circuit boards of different types each day.  There are a total of five workstations that each board must go through, but each workstation may have several specialists on duty (or machines in the case of a fully automated shop), each of which can independently fully perform the duties of that workstation.

There are several types of circuit boards manufactured at this shop, and each type requires a different amount of time at a particular workstation. Therefore, there is the potential that some specialists or machines will have no work to do at various times because boards at the previous stations require long job times.  If the boards could be scheduled in such a way as to minimize this type of delay, then the work could be completed earlier, and therefore at less cost since the plant employees are hourly workers.  In our example we will use the term machines, but a small shop is just as likely to have specialists or machinists.

Figure 5.13  View of main dialog for Scheduler problem

We will use GeneHunter to determine the exact sequence in which each board will be "fed into the system", so to speak.  Each board will have a unique number from 1 to the total number of boards to be manufactured (call it N).  We will use enumerated chromosomes, and since each board only goes through once, they will be unique chromosomes.  If there are five boards, for example, the GA will produce a sequence of five numbers (such as 3, 2, 5, 1, 4) just as it does in the Traveling Salesman Problem.  Each such sequence will then be run through the fitness function which measures the total amount of time it will take to process all boards through all stations in that specific order.  Obviously, we seek to minimize this total time.

The fitness function we have written in VBA is really a small simulator that demonstrates the movement of all boards through the workstations.  It maintains a small queue of work to be done for each station.  When a machine becomes available, the next board in the queue for that station goes onto the free machine.  The total time from the start of the first board in the sequence at the first station until the end of the last board at the last station is measured.  This is the fitness of the given sequence generated by the GA.

In our example, there are three arrays on the spreadsheet which can be changed by the user to represent various shops.  The first is the list of boards to be produced in the upper left hand corner.  Our example was designed to process 10 boards, so there are 10 boards listed.  If you want to change the number of boards to be produced, you can do so, but a constant in the VBA module ShopFit called NUM_OF_BOARDS must be changed as well.  Note that there are four distinct types of boards.

Figure 5.14  View of Scheduler worksheet

Just to the right of the first array is a column labeled "Board Order".  It is these cells that the GA will manipulate as enumerated genes.  At the bottom is the total production time (processing time) for the boards in this order (the fitness).

To the right of the Board Order column are the other two arrays that can be modified by the user:  the Workstation Times by Board Type matrix, and the Number of Machines at Each Workstation matrix.  You can experiment with the values in each of these self-explanatory arrays in order to create different shop situations.  In the Workstation Times array, there is a time for each of the five stations (insert, wire wrap, test 1, solder, test2) for each type of board.