作業(yè)車間調(diào)度問題描述
? ? ? ?作業(yè)車間調(diào)度(Job shop scheduling problem, JSP) 是車間調(diào)度中最常見的調(diào)度類型，是最難的組合優(yōu)化問題之一，應(yīng)用領(lǐng)域極其廣泛，涉及航母調(diào)度，機(jī)場飛機(jī)調(diào)度，港口碼頭貨船調(diào)度，汽車加工流水線等，因此對其研究具有重大的現(xiàn)實(shí)意義。科學(xué)有效的生產(chǎn)調(diào)度不但可以提高生產(chǎn)加工過程中工人、設(shè)備資源的高效利用，還可縮短生產(chǎn)周期，降低生產(chǎn)成本。
作業(yè)車間調(diào)度問題描述：
一個(gè)加工系統(tǒng)有
M
臺機(jī)器，要求加工
N
個(gè)作業(yè)，其中，作業(yè)
i
包含工序數(shù)為
。令，則
L
為任務(wù)集的總工序數(shù)。其中，各工序的加工時(shí)間已確定，并且每個(gè)作業(yè)必須按照工序的先后順序加工。調(diào)度的任務(wù)是安排所有作業(yè)的加工調(diào)度排序，約束條件被滿足的同時(shí)，使性能指標(biāo)得到優(yōu)化。作業(yè)車間調(diào)度需要考慮如下約束:
- 每道工序在指定的機(jī)器上加工，且必須在前一道工序加工完成后才能開始加工。
- 某一時(shí)刻1臺機(jī)器只能加工1個(gè)作業(yè)。
- 每個(gè)作業(yè)只能在1臺機(jī)器上加工1次。
- 各作業(yè)的工序順序和加工時(shí)間已知，不隨加工排序的改變而改變。
問題的數(shù)學(xué)模型：
? ? ? 令(i,j)表示作業(yè)i的第j個(gè)工序。
和
分別表示(i,j)的加工起始時(shí)刻和加工時(shí)間。
表示(i,j)是否在第k臺機(jī)器上加工：如果(i,j)在第k臺機(jī)器上加工，
；否則，
，
為第k臺機(jī)器的完工時(shí)間，則問題的數(shù)學(xué)模型如下：
? ? ?公式(1)為目標(biāo)函數(shù)，即優(yōu)化目標(biāo)，系統(tǒng)中使用總加工時(shí)間最短為優(yōu)化目標(biāo)。公式(2)表示1個(gè)作業(yè)只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1個(gè)作業(yè)的第1道工序的起始加工時(shí)刻大于或等于0。公式(4)表示在1臺機(jī)床上不會同時(shí)加工1個(gè)以上的作業(yè)。
遺傳算法
? ? ? ?隨著遺傳算法（genetic algorithm (GA)）在組合優(yōu)化問題的廣泛應(yīng)用，許多人開始對遺傳算法進(jìn)行深度研究。已有研究結(jié)果表明，遺傳算法對求解作業(yè)車間調(diào)度問題具有較好的效果，因此系統(tǒng)采用遺傳算法來解該問題，遺傳算法是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。系統(tǒng)通過模擬生物進(jìn)化，包括遺傳、突變、選擇等，來不斷地產(chǎn)生新個(gè)體，并在算法終止時(shí)求得最優(yōu)個(gè)體，即最優(yōu)解。
遺傳算法解決作業(yè)車間調(diào)度問題基本步驟
- 初始化一定數(shù)量的種群（染色體編碼）
- 計(jì)算個(gè)體適應(yīng)度（染色體解碼）
- 采用錦標(biāo)賽法選擇染色體并交叉產(chǎn)生新個(gè)體
- 個(gè)體（染色體）變異
- 達(dá)到遺傳代數(shù)終止算法并從中選取適應(yīng)度最優(yōu)的個(gè)體作為作業(yè)車間調(diào)度問題的解
流程圖如下
遺傳算法所需參數(shù)
- 種群規(guī)模：種群中個(gè)體的數(shù)量，用 populationNumber 表示
- 染色體長度：個(gè)體的染色體的長度，用 chromosomeSize 表示
- 交叉概率：控制交叉算子的使用頻率，用 crossProbability 表示，并且值為0.95
- 變異概率：控制變異算子的使用頻率，用 mutationProbability 表示，并且值為0.05
- 遺傳代數(shù)：種群的遺傳代數(shù)，用于控制遺傳算法的終止，用 times 來表示
遺傳算法實(shí)現(xiàn)基本步驟及偽代碼
1. 編碼及初始化種群
? ? ? ?采用工序?qū)崝?shù)編碼來表示染色體，即M臺機(jī)器，N個(gè)工件，每個(gè)工件的工序數(shù)為
，則染色體長度為
，對染色體編碼如下：
。其中
代表第i個(gè)工件編號，而出現(xiàn)的次數(shù)代表該工件的第幾道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的編號，第幾次出現(xiàn)就代表第幾道工序。然后將每一次隨機(jī)生成的染色體個(gè)體加入到種群集合中。
算法偽代碼：
2. 解碼及計(jì)算適應(yīng)度
? ? ? ?將優(yōu)化目標(biāo)定義為總加工時(shí)間最短，因此適應(yīng)度定義為最短加工時(shí)間的倒數(shù)，設(shè)fitness為對應(yīng)個(gè)體的適應(yīng)度，fulfillTime為最短加工時(shí)間，因此? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
其中fulfillTime的計(jì)算方法如下：
首先定義如下變量
然后從左到右遍歷個(gè)體的染色體序列
，其中
表示第i個(gè)工件的編號，則
對應(yīng)的當(dāng)前工序?yàn)?
,設(shè)為p。當(dāng)前工件當(dāng)前工序所使用的機(jī)器編號為
，設(shè)為m。當(dāng)前工件當(dāng)前工序?qū)?yīng)的加工時(shí)間為
，設(shè)為t。則工件的第p道工序的最晚開始時(shí)間為??????????
而第m臺機(jī)器的加工時(shí)間為???????????????????????????????????
工件
的第p道工序的結(jié)束時(shí)間為
最后加工完所有工件的最短加工時(shí)間fulfillTime為
從而計(jì)算出適應(yīng)度fitness。
偽代碼如下：
3.?個(gè)體選擇算子
個(gè)體的選擇使用錦標(biāo)賽法，其基本策略為從整個(gè)種群中隨機(jī)抽取n個(gè)個(gè)體讓它們競爭，選取其中最優(yōu)的個(gè)體。該算子的選擇過程如下
偽代碼如下：
4. 染色體交叉算子
使用Order Crossover(OX)交叉算子，該算子的交叉步驟如下：
對于一對染色體g1, g2，首先隨機(jī)產(chǎn)生一個(gè)起始位置start和終止位置end，并由從g1的染色體序列從start到end的序列中產(chǎn)生一個(gè)子代原型
?
?將g2中不包含在child prototype的其余編碼加入到child prototype兩側(cè)
上述步驟將產(chǎn)生一個(gè)child，交換g1, g2即可產(chǎn)生另一個(gè)child
偽代碼如下：
5. 染色體變異算子
變異的作用主要是使算法能跳出局部最優(yōu)解，因此不同的變異方式對算法能否求得全局最優(yōu)解有很大的影響。使用位置變異法作為變異算子，即從染色體中隨機(jī)產(chǎn)生兩個(gè)位置并交換這兩個(gè)位置的值
偽代碼如下：
6. 算法整體偽代碼如下：
遺傳算法代碼實(shí)現(xiàn)
根據(jù)上面的步驟及偽代碼，很容易就能寫出Python及Java對應(yīng)的代碼實(shí)現(xiàn)了，如下：
Python代碼：
from random import (randint)
from typing import (List, Tuple, Set, Dict, Any)
from utils.utils import reshape_data
from collections import namedtuple
MATRIX_SIZE = 500
# 個(gè)體對象，染色體和適應(yīng)度
class Gene(object):
def __init__(self, fitness: float = 0, chromosome = None):
self.fitness = fitness
self.chromosome: list = chromosome
def __eq__(self, other):
if isinstance(other, Gene):
return other.fitness == self.fitness and other.chromosome == self.chromosome
return False
def __hash__(self):
return hash("".join(map(lambda x: str(x), self.chromosome)))
def __str__(self):
return "{} => {}".format(self.chromosome, self.fitness)
# 存儲解碼結(jié)果
class GeneEvaluation:
def __init__(self):
self.fulfill_time = 0
self.machine_work_time = [0 for _ in range(MATRIX_SIZE)]
self.process_ids = [0 for _ in range(MATRIX_SIZE)]
self.end_time = [[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.start_time = [[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
# 遺傳算法實(shí)現(xiàn)
class GA:
def __init__(self, population_number = 50, times = 10, cross_probability = 0.95,
mutation_probability = 0.05, workpiece_number = 0, machine_number = 0):
self.population_number = population_number # 種群數(shù)量
self.times = times # 遺傳代數(shù)
self.cross_probability = cross_probability # 交叉概率
self.mutation_probability = mutation_probability # 突變概率
self.workpiece_number = workpiece_number # 工件數(shù)量
self.machine_number = machine_number # 機(jī)器數(shù)量
self.process_number: int = 0 # 工序數(shù)量
self.chromosome_size: int = 0 # 染色體長度
self.machine_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.time_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.process_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.genes: Set[Gene] = set()
# 評估染色體
def evaluate_gene(self, g: Gene) -> GeneEvaluation:
evaluation = GeneEvaluation()
# print(g.chromosome)
for workpiece_id in g.chromosome:
process_id = evaluation.process_ids[workpiece_id]
machine_id = self.machine_matrix[workpiece_id][process_id]
time = self.time_matrix[workpiece_id][process_id]
evaluation.process_ids[workpiece_id] += 1
evaluation.start_time[workpiece_id][process_id] = evaluation.machine_work_time[machine_id] \
if process_id == 0 else max(evaluation.end_time[workpiece_id][process_id - 1],
evaluation.machine_work_time[machine_id])
evaluation.machine_work_time[machine_id] = evaluation.start_time[workpiece_id][process_id] + time
evaluation.end_time[workpiece_id][process_id] = evaluation.machine_work_time[machine_id]
evaluation.fulfill_time = max(evaluation.fulfill_time, evaluation.machine_work_time[machine_id])
return evaluation
# 計(jì)算適應(yīng)度
def calculate_fitness(self, g: Gene) -> float:
return 1 / self.evaluate_gene(g).fulfill_time
# 個(gè)體交叉
def gene_cross(self, g1: Gene, g2: Gene) -> tuple:
chromosome_size = self.chromosome_size
def gene_generate(father: Gene, mother: Gene) -> Gene:
index_list = list(range(chromosome_size))
p1 = index_list.pop(randint(0, len(index_list) - 1))
p2 = index_list.pop(randint(0, len(index_list) - 1))
start = min(p1, p2)
end = max(p1, p2)
prototype = father.chromosome[start: end + 1]
t = mother.chromosome[0:]
for v1 in prototype:
for i in range(len(t)):
if v1 == t[i]:
t.pop(i)
break
child = Gene()
child.chromosome = t[0: start] + prototype + t[start:]
child.fitness = self.calculate_fitness(child)
return child
return gene_generate(g1, g2), gene_generate(g2, g1)
# 突變
def gene_mutation(self, g: Gene, n = 2) -> None:
index_list = [i for i in range(self.chromosome_size)]
for i in range(n):
a = index_list.pop(randint(0, len(index_list) - 1))
b = index_list.pop(randint(0, len(index_list) - 1))
g.chromosome[a], g.chromosome[b] = g.chromosome[b], g.chromosome[a]
g.fitness = self.calculate_fitness(g)
# 初始化種群 [0, 1, 2, 1, 2, 0, 0, 1] => 12
def init_population(self):
for _ in range(self.population_number):
g = Gene()
size = self.workpiece_number * self.machine_number
# print(self.workpiece_number, self.machine_number)
index_list = list(range(size))
chromosome = [-1 for _ in range(size)]
for j in range(self.workpiece_number):
for k in range(self.machine_number):
index = randint(0, len(index_list) - 1)
val = index_list.pop(index)
if self.process_matrix[j][k] != -1:
chromosome[val] = j
g.chromosome = list(filter(lambda x: x != -1, chromosome))
# print("chromosome:", g.chromosome)
g.fitness = self.calculate_fitness(g)
self.genes.add(g)
# 選擇個(gè)體，錦標(biāo)賽法
def select_gene(self, n: int = 3):
if len(self.genes) <= 3:
best_gene = Gene(0)
for g in self.genes:
if g.fitness > best_gene.fitness:
best_gene = g
return best_gene
index_list = list(range(len(self.genes)))
index_set = {index_list.pop(randint(0, len(index_list) - 1)) for _ in range(n)}
best_gene = Gene(0)
i = 0
for gene in self.genes:
if i in index_set:
if best_gene.fitness < gene.fitness:
best_gene = gene
i += 1
return best_gene
# 遺傳算法
def exec(self, parameter: List[List[Tuple]]) -> GeneEvaluation:
# print(parameter)
workpiece_size = len(parameter)
for i in range(workpiece_size):
self.chromosome_size += len(parameter[i])
self.process_number = max(self.process_number, len(parameter[i]))
for j in range(len(parameter[i])):
self.machine_matrix[i][j] = parameter[i][j][0]
self.time_matrix[i][j] = parameter[i][j][1]
for i in range(workpiece_size):
for j in range(self.process_number):
if self.machine_matrix[i][j] != -1:
self.process_matrix[i][self.machine_matrix[i][j]] = j
self.init_population()
for _ in range(self.times):
probability = randint(1, 100) / 100
if probability < self.mutation_probability:
index = randint(0, len(self.genes))
i = 0
for gene in self.genes:
if i == index:
self.gene_mutation(gene)
break
i += 1
else:
g1, g2 = self.select_gene(), self.select_gene()
children = self.gene_cross(g1, g2)
self.genes.update({*children})
best_gene = Gene(0)
for gene in self.genes:
if best_gene.fitness < gene.fitness:
best_gene = gene
return self.evaluate_gene(best_gene)
ResultData = namedtuple("ResultData", ["fulfill_time", "row_data", "json_data"])
# 輸出結(jié)果
def schedule(data) -> ResultData:
print(data)
reshape = reshape_data(data)
parameter = reshape.result
print(parameter)
n = len(reshape.workpiece)
m = len(reshape.machine) # number from 0
print(m)
ga = GA(workpiece_number = n, machine_number = m)
result = ga.exec(parameter)
p = ga.process_number
machine_matrix = ga.machine_matrix
row_data = []
for i in range(n):
for j in range(p):
if machine_matrix[i][j] != -1:
temp = {
"workpiece": reshape.workpiece[i],
"process": reshape.process[i][j],
"machine": reshape.machine[machine_matrix[i][j]],
"startTime": result.start_time[i][j],
"endTime": result.end_time[i][j]
}
# print(i, j, machine_matrix[i][j], result.start_time[i][j], result.end_time[i][j])
row_data.append(temp)
json_data = {}
for i in range(n):
for j in range(p):
if machine_matrix[i][j] != -1:
temp = {
"workpiece": reshape.workpiece[i],
"process": reshape.process[i][j],
"startTime": result.start_time[i][j],
"endTime": result.end_time[i][j]
}
m = reshape.machine[machine_matrix[i][j]]
if m not in json_data:
json_data[m] = [temp]
else:
json_data[m].append(temp)
return ResultData(result.fulfill_time, row_data, json_data)
if __name__ == "__main__":
# 測試數(shù)據(jù)
d = [{'workpiece': '#W-89-10', 'process': '#P-1349-31', 'machine': '#M-8763-12', 'time': 10, 'order': 0},
{'workpiece': '#W-89-10', 'process': '#P-6261-32', 'machine': '#M-2304-14', 'time': 21, 'order': 1},
{'workpiece': '#W-89-10', 'process': '#P-6917-33', 'machine': '#M-6360-16', 'time': 12, 'order': 2},
{'workpiece': '#W-5863-13', 'process': '#P-2772-34', 'machine': '#M-6557-17', 'time': 21, 'order': 0},
{'workpiece': '#W-5863-13', 'process': '#P-468-35', 'machine': '#M-8763-12', 'time': 21, 'order': 1},
{'workpiece': '#W-5829-8', 'process': '#P-3959-28', 'machine': '#M-2304-14', 'time': 5, 'order': 2},
{'workpiece': '#W-5829-8', 'process': '#P-5852-27', 'machine': '#M-671-13', 'time': 11, 'order': 1},
{'workpiece': '#W-5829-8', 'process': '#P-7792-26', 'machine': '#M-8763-12', 'time': 10, 'order': 0},
{'workpiece': '#W-554-9', 'process': '#P-6810-29', 'machine': '#M-671-13', 'time': 5, 'order': 0}]
print(schedule(d).row_data)
工具reshape_data函數(shù)實(shí)現(xiàn)?
from typing import (List, Dict)
from collections import namedtuple
test_data = [{"workpiece": '#W-5829-8',
"process": '#P-3959-28',
"machine": '#M-2304-14',
"time": 5,
"order": 2},
{"workpiece": '#W-5829-8',
"process": '#P-5852-27',
"machine": '#M-671-13',
"time": 11,
"order": 1},
{"workpiece": '#W-5829-8',
"process": '#P-7792-26',
"machine": '#M-8763-12',
"time": 10,
"order": 0},
{"workpiece": '#W-554-9',
"process": '#P-6810-29',
"machine": '#M-671-13',
"time": 5,
"order": 0},
{"workpiece": '#W-554-9',
"process": '#P-8883-30',
"machine": '#M-3836-15',
"time": 10,
"order": 1}]
ReshapeData = namedtuple("ReshapeData",
["result", "workpiece", "machine", "process", "reverse_workpiece", "reverse_machine"])
def make_reverse_index(arr: list) -> dict:
result = {}
for i in range(len(arr)):
result[arr[i]] = i
return result
def filter_value(origin: list, except_value: int) -> list:
return list(filter(lambda v: v != except_value, origin))
def reshape_data(data: List[Dict]) -> ReshapeData:
def make_array(r: dict) -> ReshapeData:
workpieces = list(set(map(lambda v: v["workpiece"], data)))
machines = list(set(map(lambda v: v["machine"], data)))
process = [-1 for _ in workpieces]
reverse_workpieces = make_reverse_index(workpieces)
reverse_machines = make_reverse_index(machines)
ans = [-1 for _ in r.keys()]
for key, val in r.items():
# print(val, type(val))
m = max(*map(lambda v: v["order"], val)) + 1 if len(val) > 1 else val[0]["order"]
t = [-1 for _ in range(m + 1)]
x = [-1 for _ in range(m + 1)]
for p in val:
t[p["order"]] = (reverse_machines[p["machine"]], p["time"])
x[p["order"]] = p["process"]
x = filter_value(x, -1)
t = filter_value(t, -1)
if ans[reverse_workpieces[key]] == -1:
ans[reverse_workpieces[key]] = t
else:
ans[reverse_workpieces[key]].append(t)
process[reverse_workpieces[key]] = x
process = filter_value(process, -1)
ans = filter_value(ans, -1)
return ReshapeData(ans, workpieces, machines, process, reverse_machines, reverse_workpieces)
result = {}
for value in data:
w = value["workpiece"]
if w in result:
result[w].append(value)
else:
result[w] = [value]
# print(result)
return make_array(result)
if __name__ == "__main__":
print(reshape_data(test_data).result)
print(reshape_data(test_data).machine)
?同理Java也很容易實(shí)現(xiàn)：
import java.util.*;
class GeneticAlgorithm {
private final int populationNumber = 60;
private final double crossProbability = 0.95;
private final double mutationProbability = 0.05;
private int jobNumber;
private int machineNumber;
private int processNumber;
private int chromosomeSize;
private int[][] machineMatrix = new int[1024][1024];
private int[][] timeMatrix = new int[1024][1024];
private int[][] processMatrix = new int[1024][1024];
private Set
geneSet = new HashSet<>();
private Random random = new Random();
public GeneticAlgorithm(int jobNumber, int machineNumber) {
this.jobNumber = jobNumber;
this.machineNumber = machineNumber;
for (int[] matrix : this.machineMatrix) Arrays.fill(matrix, -1);
for (int[] process : this.processMatrix) Arrays.fill(process, -1);
}
private List
makeList(int n) {
List
result = new ArrayList<>();
for (int i = 0; i < n; i++) result.add(i);
return result;
}
private Integer[] filterArray(Integer[] arr, int filterVal) {
List
result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] != filterVal) {
result.add(arr[i]);
}
}
return result.toArray(new Integer[0]);
}
// 初始化種群
public void initialPopulation() {
for (int i = 0; i < populationNumber; i ++) {
Gene g = new Gene();
int size = jobNumber * machineNumber;
List
indexList = makeList(size);
Integer[] chromosome = new Integer[size];
Arrays.fill(chromosome, -1);
for (int j = 0; j < jobNumber; j++) {
for (int k = 0; k < machineNumber; k ++) {
int index = random.nextInt(indexList.size());
int val = indexList.remove(index);
if (processMatrix[j][k] != -1) {
chromosome[val] = j;
}
}
}
g.chromosome = filterArray(chromosome, -1);
g.fitness = calculateFitness(g).fulfillTime;
geneSet.add(g);
}
}
public List
subArray(Integer[] arr, int start, int end) {
List
list = new ArrayList<>();
for (int i = start; i < end; i++) list.add(arr[i]);
return list;
}
// 計(jì)算適應(yīng)度
public Result calculateFitness(Gene g) {
Result result = new Result();
for (int i = 0; i < g.chromosome.length; i ++) {
int jobId = g.chromosome[i];
int processId = result.processIds[jobId];
int machineId = machineMatrix[jobId][processId];
int time = timeMatrix[jobId][processId];
result.processIds[jobId] += 1;
result.startTime[jobId][processId] = processId ==0 ? result.machineWorkTime[machineId] :
Math.max(result.endTime[jobId][processId - 1], result.machineWorkTime[machineId]);
result.machineWorkTime[machineId] = result.startTime[jobId][processId] + time;
result.endTime[jobId][processId] = result.machineWorkTime[machineId];
result.fulfillTime = Math.max(result.fulfillTime, result.machineWorkTime[machineId]);
}
return result;
}
// 交叉算子
private Gene crossGene(Gene g1, Gene g2) {
List
indexList = makeList(chromosomeSize);
int p1 = indexList.remove(random.nextInt(indexList.size()));
int p2 = indexList.remove(random.nextInt(indexList.size()));
int start = Math.min(p1, p2);
int end = Math.max(p1, p2);
List
proto = subArray(g1.chromosome, start, end + 1);
List
t = new ArrayList<>();
for (Integer c : g2.chromosome) t.add(c);
for (Integer val : proto) {
for (int i = 0; i < t.size(); i++) {
if (val.equals(t.get(i))) {
t.remove(i);
break;
}
}
}
Gene child = new Gene();
proto.addAll(t.subList(start, t.size()));
List
temp = t.subList(0, start);
temp.addAll(proto);
child.chromosome = temp.toArray(new Integer[0]);
child.fitness = (double) calculateFitness(child).fulfillTime;
return child;
}
// 突變算子
public Gene mutationGene(Gene gene, int n) {
List
indexList = makeList(chromosomeSize);
for (int i = 0; i < n; i++) {
int a = indexList.remove(random.nextInt(indexList.size()));
int b = indexList.remove(random.nextInt(indexList.size()));
int t = gene.chromosome[a];
gene.chromosome[a] = gene.chromosome[b];
gene.chromosome[b] = t;
}
gene.fitness = calculateFitness(gene).fulfillTime;
return gene;
}
// 選擇個(gè)體
public Gene selectGene(int n) {
List
indexList = makeList(geneSet.size());
Map
map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(indexList.remove(random.nextInt(indexList.size())), true);
}
Gene bestGene = new Gene(0xfffff);
int i = 0;
for (Gene gene : geneSet) {
if (map.containsKey(i)) {
if (bestGene.fitness > gene.fitness) {
bestGene = gene;
}
}
i ++;
}
return bestGene;
}
public Result run(List
> job) {
int jobSize = job.size();
for (int i = 0; i < jobSize; i ++) {
chromosomeSize += job.get(i).size();
processNumber = Math.max(processNumber, job.get(i).size());
for (int j = 0; j < job.get(i).size(); j ++) {
machineMatrix[i][j] = job.get(i).get(j)[0];
timeMatrix[i][j] = job.get(i).get(j)[1];
}
}
for (int i = 0; i < jobSize; i++) {
for (int j = 0;j < processNumber; j++){
if (machineMatrix[i][j] != -1) {
processMatrix[i][machineMatrix[i][j]] = j;
}
}
}
initialPopulation();
for (int i = 0; i < populationNumber; i++) {
double p = (double) random.nextInt(100) / 100.0;
if (p < mutationProbability) {
int index = random.nextInt(geneSet.size());
int k = 0;
for (Gene gene : geneSet) {
if (k == index) {
mutationGene(gene);
break;
}
k ++;
}
} else {
Gene g1 = selectGene(), g2 = selectGene();
Gene child1 = crossGene(g1, g2), child2 = crossGene(g2, g1);
geneSet.add(child1);
geneSet.add(child2);
}
}
Gene bestGene = new Gene(0xffffff);
for (Gene gene : geneSet) {
if (bestGene.fitness > gene.fitness) {
bestGene = gene;
}
}
return calculateFitness(bestGene);
}
public Gene selectGene() {
return selectGene(3);
}
public Gene mutationGene(Gene gene) {
return mutationGene(gene, 2);
}
static public void main(String[] args) {
List
> job = Arrays.asList(
Arrays.asList(new Integer[]{0, 3}, new Integer[]{1, 2}, new Integer[]{2, 2}),
Arrays.asList(new Integer[]{0, 2}, new Integer[]{2, 1}, new Integer[]{1, 4}),
Arrays.asList(new Integer[]{1, 4}, new Integer[]{2, 3})
);
int n = 3, m = 3;
GeneticAlgorithm ga = new GeneticAlgorithm(n, m);
Result result = ga.run(job);
int processNumber = ga.processNumber;
int[][] machineMatrix = ga.machineMatrix;
System.out.println(result.fulfillTime);
for (int i = 0; i < n; i++) {
for (int j = 0 ; j < processNumber; j++) {
if (machineMatrix[i][j] != -1) {
System.out.println(String.format("job: %d, process: %d, machine: %d, startTime: %d, endTime: %d",
i, j, machineMatrix[i][j], result.startTime[i][j], result.endTime[i][j]));
}
}
}
}
}
class Gene {
public double fitness;
public Integer[] chromosome;
public Gene() {
fitness = 0;
}
public Gene(double fitness) {this.fitness = fitness;}
}
class Result {
public int fulfillTime = 0;
public int[] machineWorkTime = new int[1024];
public int[] processIds = new int[1024];
public int[][] endTime = new int[1024][1024];
public int[][] startTime = new int[1024][1024];
}
基于Electron的作業(yè)車間調(diào)度系統(tǒng)實(shí)現(xiàn)
寫了那么多的遺傳算法解作業(yè)車間調(diào)度問題，當(dāng)然還要有實(shí)際應(yīng)用了，因此開發(fā)了一個(gè)作業(yè)車間調(diào)度系統(tǒng)，核心功能很簡單就是對工件、機(jī)器、工序進(jìn)行增刪改查并使用遺傳算法計(jì)算調(diào)度結(jié)果，前端用甘特圖展示調(diào)度結(jié)果。(GitHub地址：https://github.com/sundial-dreams/BitMESClient，如果覺得項(xiàng)目不錯(cuò)，別忘了點(diǎn)贊哦)
系統(tǒng)總體技術(shù)路線：采用前后端分離模式開發(fā)，基于C/S模式，客戶端使用JavaScript，Electron， React，Node.js等進(jìn)行組件化開發(fā)，服務(wù)端使用express，nodejs，typescript，python，sanic，graphql等開發(fā)獨(dú)立的graphql服務(wù)或http服務(wù)，數(shù)據(jù)庫使用mysql來存儲基本的信息，redis來實(shí)現(xiàn)id生成，mongodb來存儲調(diào)度結(jié)果。
-
Client端： 使用JavaScript來開發(fā)PC端應(yīng)用程序。基于Electron進(jìn)行開發(fā)，在Electron基礎(chǔ)上使用React、Redux、Antd、Echarts等前端技術(shù)和包，以模塊化、組件化的方式構(gòu)建一個(gè)獨(dú)立的UI頁面，對于頁面的切換使用了前端路由React-router。除此之外，通過封裝一個(gè)GraphQL類來做GraphQL查詢，以此和后端進(jìn)行數(shù)據(jù)交互。通過這種方式能快速的構(gòu)建一個(gè)可維護(hù)性好，UI美觀的PC端應(yīng)用程序。
-
GrapgQL Service端： 使用Typescript開發(fā)的一個(gè)GraphQL服務(wù)，提供GraphQL查詢。基于NodeJS、Express、GraphQL等來構(gòu)建一個(gè)GraphQL服務(wù)器，由于Node.js的異步非阻塞特性，使得構(gòu)建的服務(wù)器并發(fā)能力更強(qiáng)。除此之外，使用TypeORM來做數(shù)據(jù)庫的對象關(guān)系映射，加快開發(fā)速度。通過這種方式能快速搭建起一個(gè)GraphQL服務(wù)端，使用GraphQL查詢來替代傳統(tǒng)的RESTful API能使提供的API服務(wù)可維護(hù)性、擴(kuò)展性更強(qiáng)。
-
Schedule Service端： 使用Python開發(fā)，提供作業(yè)調(diào)度服務(wù)。基于Python異步Web框架Sanic，使得構(gòu)建的服務(wù)器運(yùn)行效率和并發(fā)能力都比較強(qiáng)，并且使用Python來實(shí)現(xiàn)作業(yè)車間調(diào)度算法（遺傳算法）一方面是比較容易，另一方面是Python支持多線程編程，因此多線程來優(yōu)化算法也能實(shí)現(xiàn)。
-
Data Storage端： 數(shù)據(jù)存儲，使用MySQL來存儲一些基本的數(shù)據(jù)，如機(jī)器信息、工件信息、工件工藝信息、員工信息等等。使用Redis來存儲一些健值對信息以及Id生成，由于Redis的單線程異步非阻塞特性，使得生成的Id不存在重復(fù)。使用MongoDB來存儲調(diào)度結(jié)果，由于調(diào)度結(jié)果完全是JSON格式數(shù)據(jù)，與使用MySQL存儲相比，使用文檔數(shù)據(jù)庫MongoDB來存儲比較容易，而且查詢也比較方便。
項(xiàng)目運(yùn)行：
首頁
管理
作業(yè)調(diào)度?
最后，如果覺得這篇文章有幫助，別忘了點(diǎn)贊哦
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
