一、最终输出以下:
1三个目标函数值
计算的目标函数有三种:最小化延迟作业数目(即作业完工时间超过交期时间的作业数目);min makespan(makespan是指job中最大完工时间);min total tardiness(作业权重均为1,其中tardiness=延期的作业完工时间-交期时间,求每个延期的作业tardiness之和)。
2生成的优先级规则
3算法的计算时间
二、对于输入计算数据分三个(附件text1已做、text2和text3):
2 Text2数据含义
6 6
2 1 0 3 1 6 3 7 5 3 4 6
1 8 2 5 4 10 5 10 0 10 3 4
2 5 3 4 5 8 0 9 1 1 4 7
1 5 0 5 2 5 3 3 4 8 5 9
2 9 1 3 4 5 5 4 0 3 3 1
1 3 3 3 5 9 0 10 4 4 2 1
第一行为作业数量x机器数量
接下来每一行代表一个job,分别是每个op的所在加工机器和加工时间
3 Text3数据含义
Nb of jobs, Nb of Machines, Time seed, Machine seed, Upper bound, Lower bound
15 15 840612802 398197754 1231 1005
Times
94 66 10 53 26 15 65 82 10 27 93 92 96 70 83
74 31 88 51 57 78 8 7 91 79 18 51 18 99 33
4 82 40 86 50 54 21 6 54 68 82 20 39 35 68
73 23 30 30 53 94 58 93 32 91 30 56 27 92 9
78 23 21 60 36 29 95 99 79 76 93 42 52 42 96
29 61 88 70 16 31 65 83 78 26 50 87 62 14 30
18 75 20 4 91 68 19 54 85 73 43 24 37 87 66
32 52 9 49 61 35 99 62 6 62 7 80 3 57 7
85 30 96 91 13 87 82 83 78 56 85 8 66 88 15
5 59 30 60 41 17 66 89 78 88 69 45 82 6 13
90 27 1 8 91 80 89 49 32 28 90 93 6 35 73
47 43 75 8 51 3 84 34 28 60 69 45 67 58 87
65 62 97 20 31 33 33 77 50 80 48 90 75 96 44
28 21 51 75 17 89 59 56 63 18 17 30 16 7 35
57 16 42 34 37 26 68 73 5 8 12 87 83 20 97
Machines
7 13 5 8 4 3 11 12 9 15 10 14 6 1 2
5 6 8 15 14 9 12 10 7 11 1 4 13 2 3
2 9 10 13 7 12 14 6 1 3 8 11 5 4 15
6 3 10 7 11 1 14 5 8 15 12 9 13 2 4
8 9 7 11 5 10 3 15 13 6 2 14 12 1 4
6 4 13 14 12 5 15 8 3 2 11 1 10 7 9
13 4 8 9 15 7 2 12 5 6 3 11 1 14 10
12 6 1 8 13 14 15 2 3 9 5 4 10 7 11
11 12 7 15 1 2 3 6 13 5 9 8 10 14 4
7 12 10 3 9 1 14 4 11 8 2 13 15 5 6
5 8 14 1 6 13 7 9 15 11 4 2 12 10 3
3 15 1 13 7 11 8 6 9 10 14 2 4 12 5
6 9 11 3 4 7 10 1 14 5 2 12 13 8 15
9 15 5 14 6 7 10 2 13 8 12 11 4 3 1
11 9 13 7 5 2 14 15 12 1 8 4 3 10 6
第一行15 15有含义其余的不管,代表作业数目和机器数目
Times代表每个op加工时间
Machines代表所在加工机器。
注:其中text2和text3没有交期时间duedate数据需要自己生成,在paper1第三部分实验设计,B数据集合中有说明,按图中公式生成即可。
三、算法改进:
本章使用的摄动操作主要包含两种:
方法一:子树约束的变异(Restricted subtree mutation,简称RSM);
RSM操作过程中,对于决策树的变异,允许新生成的子树最大深度不超过2。该约束能够保证新生成的决策树相对于母体不会产生太大的差异,从而使局部搜索算法在搜索最优解时效率提升。
方法二:子树提取(Subtree extraction,简称SE)。
对于SE操作,随机选取每一次迭代中计算的最优优先级规则的节点,同时这些子树将会成为接下来迭代计算中的待选子树。不同于RSM操作,SE操作不产生新的子树或节点;相反,SE操作将这些节点或子树构造新的决策树。原文如下: