Samples of Optimization

Recipe

Planning

Machine Planning – Plan 1, 2 & 3

This application is typical of machine scheduling in manufacturing. A factory has four machines A, B, C and D. Their respective maximum available capacity in a week is 1000, 4720, 400 and 1000 minutes. The products manufactured involve three operations O1, O2 and O3. Some products require O1 and O2, others O2 and O3 and so on. The requirements for a week have been summed up as orders of 1400 units,

1200 units and 900 units for operations O1, O2 and O3 respectively. Machine A can handle all operations. Machine B can handle O2 and O3. Machine C can handle O1.

Machine D can handle O1 and O3. The times in minutes per operation and the cost per minute for each machine are shown in the table below:

Minutes per unit operation

The problem is, how many units of each operation should be manufactured in each machine in order to fulfil the requirements at a minimum cost, without exceeding the capacity of the four machines. There are a number of ways of representing the above problem for the purpose of optimization, illustrated in three separate tasks, Plan 1, Plan2 and Plan 3.

Plan 3: Using one Variables chromosome

The obvious way of solving the problem is to represent as genes the quantities of each operation on the various machines. Hence, we have genes for MA O1 (Machine A operation1), MA O2, MA O3, MB O2, MB O3, MC O1, MD O1 and MD O3.

Note that the operations that cannot be handled by certain machines have no corresponding genes. The problem is further simplified by imposing the constraint of 1400 , 1200 and 900 units as the total units for O1, O2, and O3 respectively. This removes the need for gene MD O1 since it can calculated as 1400 - (MA O1 + MC O1). Similarly there is no need for genes MB O2 and MD O3. This leaves a chromosome with five genes:

MA O1 MA O2 MA O3 MB O3 MC O1

Each of the above genes can be defined as ordinal (0 decimal places) with a minimum value of 0. The maximum value of genes MA O1 and MC O1 is 1400, of MA O2 is 1200, and of MA O3 and MB O3 is 900.

Task Plan3 of the Planning application is an implementation of the above genes structure. With Plan3_Opt in the Multiple Object Editor examine the genes of the non sequence chromosome. The genes are mapped onto (tied to) numeric array elements within Knowledge Builder. This data structure is used in order to streamline the calculations of the effectiveness of machine planning using different representations. Units[1..3,1..4] stores the numbers of units of each operation (1..3) on machines A to D (1..4). Illegal combinations of machine / operation are simply set to have 0 units. Examine the tied attributes (arrays) for each of the five genes.

The script commands of Plan3_Cost_PRC_VB contain all the calculations required to derive a value for Plan3_Cost. The data structure used by the commands is:

·Capacity_Available[1..4] – holds the available capacity (minutes) for machines 1..4 (A to D)

·Capacity_Used[1..4] – holds the used capacity (minutes) for machines 1..4 (A to D)

·Cost_Per_Minute[1..4] – holds the cost/minute for machines 1..4 (A to D)

·Minutes_Per_Operation[1..3,1..4] – holds the minutes per operation (1..3) for machines A to D (1..4)

The script commands of Plan3_Cost_PRC_VB calculate the cost of production (in $) given a set of genes values in Units[1..3,1..4]. This cost is assigned to the attribute Production_Cost. Furthermore, exceeding the capacity of any machine is penalised by adding a cost of $100 per overrun minute. This cost is assigned to Penalty_Cost. The value of Plan3_Cost is the sum of Production_Cost and Penalty_Cost. Finally, the report displays the best solution reached in terms of the cost of production and the utilisation of machine capacities.

In most cases, the 50 generations of evolution can reduce the cost to below 270,000 and give a good schedule.

In the Planning_Adaptation Knowledge Module an adaptation strategy is used for Plan3. Adaptation strategy involves the adjustment of the optimisation parameters dynamically during the optimisation process and this sample increases the mutation probability after a number of generations have failed to improve the cost. The logic being that if the system is failing to find a better result then adding more randomness may pop up a better individual and cause the system to start to explore in a new area of the search space.

In Planning _Adaptation the mutation probability is changed during the optimisation process so the original value is stored in the variable Start_Mutation_Level in event Optimisation Start. Also the variable prevCost is initialised to a number that is higher than any possible cost result. The Generation End event code is shown below:

Function ( genNo:N , bestCost:N , avgCost:N ) : B
@Return TRUE
@If bestCost < prevCost
  @Assign prevCost = bestCost
  @Assign CostCount = 0
  @Assign Plan3_Opt.mutation = Start_Mutation_Level
@Else
  @Assign CostCount = CostCount + 1
  @If CostCount = 10
     @Assign Plan3_Opt.mutation = Plan3_Opt.mutation + (Start_Mutation_Level / 4)
     @Assign CostCount = 0
  @EndIf
@EndIf

If the system fails to improve the cost for 10 generations the mutation probability is increased by Start_Mutation_Level / 4. If the cost has not improved after a further 10 generations then the mutation probability is increased again and so on. Every time the cost is improved the mutation probability is reset to its original pre-set value and the counter (CostCount) set to zero.

Plan 1: Using one sequence chromosome

Although the Plan 3 representation of the machine planning problem can arrive at a good solution, the evolution process is relatively slow (many generations) and the solution is not optimal. A more effective way of representing the problem is that of optimizing a sequence. In this representation, the total orders for O1, O2 and O3 are broken down into smaller orders. The 1400 O1 order is replaced by 5 orders of 280 units each. The 1200 O2 order is replaced by 4 orders of 300 units each. The 900 O3 order is replaced by 3 orders of 300 units each.

Hence, the total number of orders (or jobs) has been changed from 3 to 12. If the jobs are numbered 1 to 12, then jobs 1 to 5 are each for 280 units of O1, jobs 6 to 9 are each for 300 units of O2, and jobs 10 to 12 are each for 300 units of O3. Now if we develop a simple job scheduler, which works on a first come first scheduled basis, then the order in which we feed the jobs to the scheduler will influence the effectiveness of the resulting schedule. Hence, the problem is transformed to that of optimizing the sequence of presenting the 12 jobs to the scheduler. The large quantities of O1, O2 and O3 were broken down into smaller jobs to give the scheduler the chance to spread the production of each operations between different machines.

The task Plan1 represents the planning problem as a sequenced chromosome. View the optimization object Plan1_Opt in the Multiple Object editor and examine the chromosome structure. The 12 genes of the sequence chromosome are mapped onto (tied to ) the numeric array Sequence[1..12]. View the Decision Tree of Plan1. Two Procedures are used, namely Initialisation and Rank_Match. As with the previous representation, the @commands of Initialisation are used to initialise the data constants. The commands of Rank_Match assigns a ranking of machines 1..4 in terms of cost/minute for each of the three operations O1, O2 and O3. These ranking figures are stored in the array Rank[1..4,1..3], where 1..4 represent the machine number and 1..3 represent the operation number. Hence, for operation O1 the cheapest machines are in order Rank[1,1], Rank[2,1], Rank[3,1] and Rank[4,1].

The @commands of Plan1_Cost_PRC_VB calculate the effectiveness of the planning. The first step is to take the sequence of genes in a chromosome and convert it into a valid plan. To do this, each gene in the sequence is examined to determine which operation (O1, O2 or O3) it refers to and what is the unit quantity for that operation. The order is then assigned fully or partially to the first machine with available capacity. If an order cannot be scheduled on any machine then it is added to a list of unscheduled units.

The order by which machines are checked for available capacity is defined by the ranking of machines by cost for a certain operation.

Having produced a valid schedule from a sequence of genes, the commands of Plan1_Cost_PRC_VB again calculate the production cost Production_Cost and the overrun cost Penalty_Cost from which Plan1_Cost is calculated.

With the default evolution parameters set run Plan1. The optimization process will find the following optimal solution in only 1 generation (in most cases)!

Production_Cost = 258800 Penalty_Cost = 0 Plan1_Cost = 258800

The speed and accuracy may sound unbelievable but it illustrates the effect of the problem representation on the optimization process. The reasons for the effectiveness of the above solution are:

·The search space (possible values) for 12 sequenced genes is far smaller than that with 5 non-sequenced genes with maximum values 900 to 1400.

·The search space for sequenced chromosomes is further constrained by the need for a unique value for each gene.

·The sequenced chromosome structure allows the developer to impart a search strategy into the system in the form of the simple job scheduler.

Plan 2: Using multiple sequence chromosome

The Plan 1 problem representation used a simple job scheduler which processed machines in the order of their cost in carrying out an operation. In some real machine planning problems it may not be possible to rank machines in this way, furthermore the ranking of machines may not be static but may vary with the accumulative loading on each machine as jobs are scheduled. In such cases, we can define the ranking of machines for each operation as a sequence chromosome. Hence, in addition to the 12 gene sequence chromosome we need three further sequence chromosomes with four genes each. The genes of the first additional sequence chromosome will represent the sequence by which machines 1..4 should be considered when scheduling an O1 job in the 12 genes original sequence. Similarly for the other two additional chromosome.

Plan2 is an implementation of this new strategy. View the optimization object Plan2_Opt to examine the structure of the chromosomes. View Plan2 and note that there is one Procedures; Initialisation. As before Initialisation initialises constant data. The @commands of Plan2_Cost_PRC_VB again apply a simple scheduler, then calculate the effectiveness of the schedule. The only difference from the Plan1 task is that the machine ranking array Rank[1..4,1..3] obtains its values from the chromosomes.

With the default evolution parameters, Plan2 can reach the optimal solution (Plan2_Cost = 258800) in one or two generations. This illustrates the strength of the job sequencer/simple scheduler structure for machine planning applications.

PLANNING Script Commands:

You can examine the use of these specific Knowledge Builder procedural @commands used, by looking in these Procedure objects within the application.