基于Python的CDS算法解析
- CDS算法步骤
-
- 总结一下下：
CDS算法步骤
第一步导入数据
| 工件数 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 第1道工序在M1上所用的时间 | 31 | 19 | 23 | 13 | 33 |
| 第2道工序在M2上所用的时间 | 41 | 55 | 42 | 22 | 5 |
| 第3道工序在M3上所用的时间 | 25 | 3 | 27 | 14 | 57 |
| 第4道工序在M4上所用的时间 | 30 | 34 | 6 | 13 | 19 |
代码NO.1导入数据
data = data[:, np.argsort(data[0])]
#将data的第一行进行排列得到是，第一行从小到大的位置索引
#解析np.argsort（）函数
import numpy as np
a = np.array([-1, 2, 5, 3, 9, -11, 0])
arg = np.argsort(a)
输出为：
#[5 0 6 1 3 2 4]
#可以知道np.argsort（）是对数组的的安从小到大排列的index
所以代码块1表示的含义：
| 2 | 5 | 4 |
|---|---|---|
| … | … | … |
变成
| 2 | 4 | 5 |
|---|---|---|
| … | … | … |
代码NO.2按顺序排列的数组
def group(self, data):data_group = np.zeros([data.shape[0] - 2, 3, data.shape[1]])#创建一个三维数组，3块，每块是3行5列for i in range(data_group.shape[0]):#对每一块进行循环，行进行遍历data_group[i, 0] = data[0]#data第一行的数据赋值给data_group第i页，第一行for j in range(data.shape[1]):#对data的列进行遍历data_group[i, 1, j] = np.sum(data[1:i + 2, j])#将data第1行到底i+2行相加，在第j列求和赋值给pagei的第1行j列data_group[i, 2, j] = np.sum(data[-i - 1:, j])#将data倒数第1行到倒数第i-2行相加，在第j列求和赋值给pagei的第2行j列return data_group
输出的data_group为：
page1：
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 31 | 19 | 23 | 13 | 33 |
| 30 | 34 | 6 | 13 | 19 |
page2：
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 72 | 74 | 65 | 35 | 38 |
| 55 | 37 | 33 | 27 | 76 |
page3：
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 97 | 77 | 92 | 49 | 95 |
| 96 | 92 | 75 | 49 | 81 |
代码NO.3按johnson算法
def johnson(self, data_group):data_johnson = np.zeros([data_group.shape[0], data_group.shape[2]])#创建3行5列的二维数组for i in range(data_group.shape[0]):data_johnson[i] = johnson(data_group[i])#让data_group的每一块数组都进行johnson算法，return data_johnsonjohnson主程序
def johnson(data, draw=0):""":param data:3行，工序编号，机器1加工时间，机器2加工时间:return:"""data = data[:, np.argsort(data[0])]#输入数据new = Johnson()P, Q = new.group(data)#将数据产生P/Q两组P, Q = new.sort(P, Q)#分类data_johnson = new.combine(P, Q)#在组合P、Q数据，形成新的数据
分组：
def group(self, data):P = data[:, np.where(data[1] < data[2])[0]]Q = data[:, np.where(data[1] >= data[2])[0]]return P, Q
分类：
def sort(self, P, Q):P = P[:, np.argsort(P[1])]Q = Q[:, np.argsort(-Q[2])]return P, Q
拼接：
def combine(self, P, Q):try:data = np.hstack([P, Q])except ValueError:data = Pdata_johnson = data[0]#得到零件的加工序列return data_johnson
代码NO.4根据johnson算法德到的序，在根据makespan选择一个最好的序
def select(self, data, data_johnson):data_johnson = np.array(data_johnson, dtype=int) - 1data_best = data_johnson[0]#先保存第一个序列，作为初始值for i in range(1, data_johnson.shape[0]):#对每个序进行遍历if makespan_value(data[:, data_best]) > makespan_value(data[:, data_johnson[i]]):#比较makespandata_best = data_johnson[i]#保存最小的makespandata_best += 1return data_best
总结一下下：
9.27日主要对CDS算法进行了代码解析，CDS算法简言之就是在进行赛选序，筛选的核心就是根据每道工序的完成时间的和进行的，用了多个列表进行保存，最好排序np.argsort这个函数