Adapting a genetic algorithm to schedule variants of the manufacturing shop.
P. R. Drake* and I. A. Choudhry
Intelligent Systems Laboratory,
Systems Division, School of Engineering, University of Wales Cardiff,
Queen's Buildings, Cardiff, CF2 3TE.
Abstract
Whilst it is well documented how genetic algorithms (GA's) can be applied to scheduling jobs for simple manufacturing shop models, this paper shows how they can be used to schedule jobs for some of the more complex standard models. The simplicity of the methods presented, and the use of proprietary spreadsheet software and GA 'add-in' to implement them, support the conjecture that GA's can provide a highly flexible and user-friendly solution to the general shop scheduling problem.
1Introduction
Since the late 1980s there has been a growing interest in genetic algorithms (GA's) - optimisation algorithms based on the principles of natural (Darwinian) evolution. As they are based on evolutionary learning they come under the heading of Artificial Intelligence. They have been used widely for parameter optimisation, classification and learning in a wide range of applications. More recently, production scheduling has emerged as an application. In particular, such applications have started to appear in this journal (Jain and Elmaraghy 1997) (Lee, Piramuthu and Tsai 1997). Whilst it is well documented how GA's can be applied to simple job sequencing problems, this paper shows how they can be implemented to sequence jobs/operations for manufacturing shops with precedence constraints among manufacturing tasks, alternative routeings (machines), sequence dependent set-up times and scheduled machine downtime. The methods presented are very simple and easy to implement and therefore support the conjecture that GA's can provide a highly flexible and user-friendly solution to the general shop scheduling problem.
The work presented here is carried out using standard spreadsheet software and an 'add-in' to provide the basic GA. The use of this proprietary software demonstrates how simple it is to implement the GA approach to schedule optimisation - very little software skill is required. Spreadsheets are used widely in manufacturing industry and they are particularly suitable for production scheduling because they store and manipulate data in tables.
2The Sequence Optimisation GA
Detailed introductions to GA's are given by Goldberg (1989) and Davis (1991). The flowchart for the particular GA used here is given in Figure 1. First, an initial population of randomly generated sequences of the tasks in the schedule is created. These individual schedules form 'chromosomes' which are to be subjected to a form of Darwinian evolution. The size of the population is user-defined and the fitness of each individual schedule in the population is calculated according to a user-defined fitness function such as: total makespan; mean tardiness; maximum tardiness; number of tardy jobs. The schedules are then ranked according to the value of their fitness function.
Once an initial population has been formed, 'selection', 'crossover' and 'mutation' operations are repeatedly performed until the fittest member of the evolving population converges to an optimal fitness value. Alternatively, the GA may run for a user defined number of iterations.
The 'selection' process consists of selecting a pair of parents from the current population using a rank-based mechanism to control the probability of selection. These parents then mate to produce a child by applying (in this particular implementation) the 'uniform order-based' crossover operator (Davis 1991). This is based on using a randomly generated bit string (zero-one) template to determine for each parent which genes are carried forward into their child. The operator is explained by the example in Figure 2. Here, the bit string template contains a one at positions {2, 3, 5, 6}. The genes (jobs) in these positions in parent-1 are carried straight across into the child. The template contains zeros at positions {1, 4, 7, 8}. In these positions parent-1 has genes {1, 4, 7, 8}. These genes are copied into the child in the same order as they appear in parent-2 {8, 4, 7, 1}. The proportion of the jobs in the child coming from the first parent is defined by the crossover rate which has a value between 0 and 1.
Following crossover, the resultant child may be mutated. The particular mutation operation used here is 'order-based' mutation. In this operation two jobs change positions in the chromosome. The probability that a job is mutated is defined by the user defined mutation rate which lies in the range 0 to 1. The purpose of mutation is to ensure that diversity is maintained within the population. It gives random movement about the search space thus preventing the GA becoming trapped in 'blind corners' or 'local optima'. Finally, the new 'child' schedule replaces the weakest (least fit) schedule in the current pool or 'population' of schedules.
A population size of 50, a crossover rate of 0.65 and a mutation rate of 0.006 are used in the experiments presented here.
3Why use GA's for Shop Scheduling ?
It is a characteristic of the schedule optimisation process that once fairly good solutions have been formed their features will be carried forward into better solutions, and lead ultimately to optimal solutions. It is in the nature of the GA that new solutions are formed from the features of known good solutions. Therefore, it follows that GA's are particularly attractive for scheduling.
Compared with other optimisation methods, GA's are suitable for traversing large search spaces since they can do this relatively rapidly and because the mutation operator diverts the method away from local minima, which will tend to become more common as the search space increases in size. Being suitable for large search spaces is a useful advantage when dealing with schedules of increasing size since the solution space will grow very rapidly, especially when this is compounded by such features as alternative machines/routes. It is important that these large search spaces are traversed as rapidly as possible to enable the practical and useful implementation of automated schedule optimisation. If the optimisation is done quickly then production managers can try out 'what-if' scenarios and detailed sensitivity analysis as well as being able to react to 'crises' as soon as possible.
For a simple n jobs and m machines schedule the upper bound on the number of solutions is (n!)m. Without n and m being very large this value soon becomes massive, e.g. for 20 jobs and 5 machines the value is 8.52x1091. Traditional approaches to schedule optimisation such as mathematical programming and 'branch and bound' are computationally very slow in such a massive search space.
4Example 1: A Flow Shop
Table 1 gives the job data for this example and the objective is to minimise the makespan for the schedule. When the GA is applied to this example the best sequence is 3-6-4-7-2-8-1-5 which yields a makespan of 584 units of time. The result of applying the 'network scheduling technique' to this example was recently reported and the best sequence found was 3-6-4-7-8-2-1-5 which produces a makespan of 595 units of time (Akpan 1996). This was also the best result reported when using a heuristic method (Campbell, Smith and Dudek 1970).
5Precedence Constraints
The normal sequence optimising GA will rearrange freely the jobs in a schedule. However, in most production scheduling situations there will be precedence constraints on the order of operations within a particular job. For example, holes must be drilled before they are tapped. To implement such constraints, a precedence table is introduced as in Table 2 for the example considered in the next section. This table shows that, for example, task 5 must be done before tasks 6 and 7. When the GA creates a child the precedence table is checked. If any precedence constraints are broken then tasks which must be performed earlier in the sequence are moved up the schedule.
6Example 2: Alternative Machines
There may be a choice of machines that can be used for a particular operation as illustrated in Table 3. In this example operation 2 for job A can be performed on machine 1 or 3, operation 2 for job B on machine 1 or 2, and so on. Table 4 presents the same information in the form of a 20 job-operation sequence. Note, five of these operations {tasks 3,7,13,15,19} will not in fact be performed. They are present in the table solely for the purpose of making the alternatives available to future generations. The first occurrence of a duplicated operation is taken to be an 'actual' occurrence that must be included in the calculation of the fitness function while subsequent occurrences are ignored. However, all occurrences are included in the crossover and mutation operations.
Using integer programming, Jiang and Hsiao (1994) produce two optimised schedules for this example - one to minimise the total absolute deviation from the due dates and one to minimise the total finishing times of the individual jobs. They show that the minimum total absolute deviation is four time units and the minimum total finishing time is ten time units. The GA produced the same results. Figures 3 and 4 show the schedules generated to optimise the two fitness functions. Table 5 illustrates how the GA presents the optimal solution for the minimum total finishing times schedule. As explained before, this is a sequence of 20 operations including 5 duplicated operations that are to be ignored.
7. Example 3: Sequence Dependent Set-up Times
Inter-operation set-up times may depend on the type of operation that has just been completed, as well as on the type of operation to be performed. In such situations it is not valid to absorb the set-up time for a job into its processing time. To accommodate sequence dependent set-up times, look-up tables containing the times are introduced. Then, fitness functions such as total makespan (lead-time) can be calculated for a schedule by combining process times with the appropriate set-up times in the look-up table.
Table 6 presents an example schedule with the corresponding sequence dependent set-up times being given in Tables 7 to 9. The smallest total makespan found by the GA is 45 time units with the task sequence {1,7,8,9,4,5,10,11,12,2,3,6}. Again, it is a relatively simple matter to implement the fitness function required to enable the GA to optimise this schedule.
8. Example 4: Scheduled Machine Downtime
Scheduled machine downtime may be requested for preventive or reactive maintenance. In the model considered here, the downtime must be inserted into the production schedule according to the following two rules.
i.If there is no production scheduled for a machine at the start of a requested downtime, then the downtime is allocated as requested. Any production scheduled to start during the downtime is moved to the end of the downtime.
ii.If production is already scheduled at the start time of the requested downtime, then the downtime is moved to the end of this operation.
Other rules may be used as desired. The important principle being demonstrated here is how these rules are applied with the GA.
Consider, the 3-job, 4-machine job shop example in Table 10 taken from Pinedo (1995). The precedence constraints for this example are defined in Table 11. The best makespan found by Pinedo for this example is 28. He uses disjunctive graphs and proves that this solution is optimal. The GA finds the same solution but with a different sequence of operations. The Gantt charts for the two solutions are given in Figure 5.
Now consider that before the execution of the schedule the maintenance department request machines 1, 2 and 4 for the times given in Table 12. This machine downtime is inserted into the schedule according to the above two rules to give the schedule in Figure 6. This increases the makespan to 55 time units. Rerunning the GA to optimise this schedule, the makespan is reduced to 51 as shown in Figure 7.
9Conclusion
The adaptation of a GA to schedule jobs in manufacturing shops with precedence constraints among tasks, alternative routeings, sequence dependent set-up times and scheduled machine downtime has been demonstrated. The simplicity of the methods used supports the conjecture that GA's can provide a highly flexible and user-friendly solution to the general shop scheduling problem. The use of proprietary spreadsheet software and a proprietary 'add-in' to implement the GA has shown how simple it is to implement this approach to scheduling.
References
Akpan, E. O. P., 1996, Job-shop sequencing problems via network scheduling technique, International Journal of Operations and Production Management, 16, 76-86.
Campbell, H. G., Smith, M. L., Dudek, R. A., 1970, A heuristic algorithm for the N jobs, machine sequencing problem, Management Science, 16, B630-B637.
Davis L, 1991, Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold.
Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimisation and Machine Learning, Reading, MA: Addison-Wesley.
Jain A. K., Elmaraghy H.A., 1997, Production scheduling/rescheduling in flexible manufacturing, International Journal of Production Research, 35, 281-309.
Jiang J. and Hsiao W., 1994, Mathematical Programming for the Scheduling Problem with Alternative Process Plans in FMS, Computers & Industrial. Engineering, 27, 15-18.
Lee C.-Y., Piramuthu S. and Tsai Y. -K., 1997, Job shop scheduling with a genetic algorithm and machine learning, International Journal of Production Research, 35, 1171-1191.
Pinedo, M., 1995, Scheduling: Theory, Algorithms and Systems, Prentice Hall, New Jersey.
Acknowledgements
The authors would like to thank the Pakistan Government for their assistance in this research.
Figure 1: The Genetic Algorithm (GA) for Schedule Optimisation
Position in Chromosome1 2 3 4 5 6 7 8
Parent-1
Binary Template
Parent-2
Child / 1 2 3 4 5 6 7 8
0 1 1 0 1 1 0 0
8 6 4 2 7 5 3 1
8 2 3 4 5 6 7 1
Figure 2: Schedule Chromosomes and the Crossover Operator
Figure 3 : Schedule to minimise absolute
deviation from due dates.
Figure 4 : Schedule to minimise total finishing times.
Figure 5 : Gantt Chart for Pinedo’s Solution and the GA Solution
Figure 6 : Modified schedule with machine downtime inserted
Figure 7 : Modified schedule after rerunning the GA
Table 1: Job Data for 8-job, 7-machine flow line example.
Job List / Processing Times for Machine1 / 2 / 3 / 4 / 5 / 6 / 7
1 / 13 / 79 / 23 / 71 / 60 / 27 / 2
2 / 31 / 13 / 14 / 94 / 60 / 61 / 57
3 / 17 / 1 / - / 23 / 36 / 8 / 86
4 / 19 / 28 / 10 / 4 / 58 / 73 / 40
5 / 94 / 75 / - / 58 / - / 68 / 46
6 / 8 / 24 / 3 / 32 / 4 / 94 / 89
7 / 10 / 57 / 13 / 1 / 92 / 75 / 29
8 / 80 / 17 / 38 / 40 / 66 / 25 / 88
Table 2: Precedence Constraints for Tasks
Task Number / Must / follow1
2 / 1
3 / 1
4 / 2 / 3
5
6 / 5
7 / 5
8 / 6 / 7
9
10 / 9
11 / 10
12
13
14 / 12 / 13
15 / 12 / 13
16 / 14 / 15
17
18 / 17
19 / 17
20 / 18 / 19
Table 3: The Alternative Machines Schedule
Job-Operation / Processing timefor machine / Due
Date
1 / 2 / 3 / 4
A-1 / 2
A-2 / 1 / 2
A-3 / 1 / 6
B-1 / 1
B-2 / 1 / 2
B-3 / 1 / 3
C-1 / 2
C-2 / 2
C-3 / 1 / 6
D-1 / 1 / 2
D-2 / 2 / 1
D-3 / 1 / 6
E-1 / 1
E-2 / 2 / 1
E-3 / 2 / 6
Table 4: GA Representation of the Example Alternative Machines Schedule
Job Number / Operation / Machine / Process Time / Contribution to Fitness Function / Task Number*A / 1 / 1 / 2 / 2 / 1
A / 2 / 1 / 1 / 1 / 2
A / 2 / 3 / 2 / - / 3
A / 3 / 4 / 1 / 1 / 4
B / 1 / 2 / 1 / 1 / 5
B / 2 / 1 / 1 / 1 / 6
B / 2 / 2 / 2 / - / 7
B / 1 / 1 / 1 / 1 / 8
C / 1 / 3 / 2 / 2 / 9
C / 2 / 4 / 2 / 2 / 10
C / 3 / 1 / 1 / 1 / 11
D / 1 / 3 / 1 / 1 / 12
D / 1 / 4 / 2 / - / 13
D / 2 / 2 / 2 / 2 / 14
D / 2 / 3 / 1 / - / 15
D / 3 / 2 / 1 / 1 / 16
E / 1 / 2 / 1 / 1 / 17
E / 2 / 2 / 2 / 2 / 18
E / 2 / 4 / 1 / - / 19
E / 3 / 3 / 2 / 2 / 20
* This column represents the chromosome used in the crossover and mutation operations.
Table 5: GA Optimised Schedule to Minimise Total Finishing Time
Job Number / Operation / Machine / Process Time / Contribution to Fitness Function / Task Number*D / 1 / 3 / 1 / 1 / 12
A / 1 / 1 / 2 / 2 / 1
A / 2 / 1 / 1 / 1 / 2
D / 1 / 4 / 2 / - / 13
A / 2 / 3 / 2 / - / 3
D / 2 / 3 / 1 / 1 / 14
E / 1 / 2 / 1 / 1 / 17
E / 2 / 4 / 1 / 1 / 19
B / 1 / 2 / 1 / 1 / 5
B / 2 / 1 / 1 / 1 / 6
D / 2 / 3 / 1 / - / 14
D / 3 / 2 / 1 / 1 / 16
E / 2 / 2 / 2 / - / 18
E / 3 / 3 / 2 / 2 / 20
B / 2 / 2 / 2 / - / 7
A / 3 / 4 / 1 / 1 / 4
C / 1 / 3 / 2 / 2 / 9
C / 2 / 4 / 2 / 2 / 10
B / 3 / 1 / 1 / 1 / 8
C / 3 / 1 / 1 / 1 / 11
* This column represents the chromosome used in the crossover and mutation operations.
Table 6: Schedule Data for the Sequence Dependent Set-up Times Example.
Job / Operation / Machine / Part Type / Process Time / Task Number*1 / 1 / B / 1 / 4 / 1
1 / 2 / A / 1 / 7 / 2
1 / 3 / C / 1 / 6 / 3
2 / 1 / B / 2 / 9 / 4
2 / 2 / C / 2 / 5 / 5
2 / 3 / A / 2 / 4 / 6
3 / 1 / A / 3 / 1 / 7
3 / 2 / B / 3 / 2 / 8
3 / 3 / C / 3 / 10 / 9
4 / 1 / A / 4 / 8 / 10
4 / 2 / C / 4 / 4 / 11
4 / 3 / B / 4 / 5 / 12
* This column represents the chromosome used in the crossover and mutation operations.
Table 7: Sequence Dependent Set-up Times for Machine 1
To Part TypeFrom Part Type / 1 / 2 / 3 / 4
None / 2 / 3 / 2 / 4
1 / 0 / 3 / 1 / 5
2 / 1 / 0 / 3 / 2
3 / 2 / 4 / 0 / 1
4 / 2 / 4 / 2 / 0
Table 8: Sequence Dependent Set-up Times for Machine 2
To Part TypeFrom Part Type / 1 / 2 / 3 / 4
None / 2 / 1 / 3 / 1
1 / 0 / 2 / 3 / 5
2 / 5 / 0 / 1 / 3
3 / 4 / 2 / 0 / 1
4 / 3 / 3 / 4 / 0
Table 9: Sequence Dependent Set-up Times for Machine 3
To Part TypeFrom Part Type / 1 / 2 / 3 / 4
None / 1 / 3 / 2 / 2
1 / 0 / 3 / 2 / 5
2 / 3 / 0 / 4 / 3
3 / 2 / 2 / 0 / 4
4 / 2 / 5 / 3 / 0
Table 10: Processing times and machine sequences for 3-job, 4-machine example
Operation Processing Times / Machine SequenceJob / 1st / 2nd / 3rd / 4th / 1st / 2nd / 3rd / 4th
1 / 10 / 8 / 4 / - / 1 / 2 / 3 / -
2 / 8 / 3 / 5 / 6 / 2 / 1 / 4 / 3
3 / 4 / 7 / 3 / - / 1 / 2 / 4 / -
Table 11: Precedence Constraint Table
Job-operation / Must followjob-operation
1-1
1-2 / 1-1
1-3 / 1-2
2-1
2-2 / 2-1
2-3 / 2-2
2-4 / 2-3
3-1
3-2 / 3-1
3-3 / 3-2
Table 12 : Requested Machine Downtimes
Requested DowntimesMachine / Start / Finish / Duration
1 / 10 / 20 / 10
2 / 15 / 30 / 15
4 / 10 / 40 / 30
1