需求背景
生產調度問題是典型的組合優(yōu)化問題（NP-hard），有別于經典的流水線車間調度，實際中的場景往往是存在并行設備，在某個流水線工序中存在兩個或以上可選擇的加工機器，這種情況解空間更大、復雜度更高。解決這類問題有多種方法，遺傳算法、粒子群算法、差分進化等，他們原理不同但也有相似之處，我們盡量一一探討。
柔性車間調度也叫混合流水車間調度問題（Hybrid Flow Shop Scheduling Problem, HFSSP）是經典流水車間調度的推廣。它綜合了經典流水車間和并行機兩種調度的特點。我們這里討論的是半柔性的調度，區(qū)別在哪呢，柔性車間調度中每個工件的加工時間是不同的，而我面對的問題是對于相同粒度的加工單位其在某臺設備上的加工時間是基本一致的，也就是說這個加工時間是跟著設備變化的，但同一個工序的不同設備加工時間可能相同也可能不同和設備自身情況有關。
問題描述
本文中考慮在一條流水線上進行生產。要解決的場景是給定數(shù)量的原材料，如何規(guī)劃給定粒度的材料（實際中可能是指載具）在每臺機器上的分配加工路線，使得整個流水線的加工效率最高、用時最短。
假設m個工件在包含n個階段（工序）的流水線上進行加工。每個工件都要依次通過每個階段。每個階段至少有一臺加工機器并且至少有一個階段包含多臺并行機器如下圖示。（若每階段有且僅有一臺加工機器，則稱為經典流水車間調度問題Flow Shop Scheduling Problem, FSSP）。
工序的并行設備
已知各設備的加工時間，優(yōu)化目標是如何確定工件的加工順序以及每階段工件在機器上的分配情況，使得最大完工時間極小化。
假設條件
- 工件可以在某工序的任意一臺機器上進行加工但有嚴格的加工順序
- 同一工序中所有機器功能相同，機器時間存在差別
- 任意時刻每個工件至多在一臺機器上加工
- 每臺機器某時刻只能加工一個工件
- 工件的加工過程不允許中斷
- 默認每條調度指令都被執(zhí)行成功
- 默認設備時間包含了設備加工所需時間、上下料時間、工件運送時間。
遺傳算法
基本原理
遺傳算法的原理網(wǎng)上資料很多，也比較容易理解，這里簡要說下。本文著重討論如何用它解決實際問題。
遺傳算法是一種基于自然選擇和群體遺傳機理的搜索算法,它模擬了自然選擇和自然遺傳過程中的繁殖、雜交和突變現(xiàn)象.再利用遺傳算法求解問題時,問題的每一個可能解都被編碼成一個“染色體”,即個體,若干個個體構成了群體(所有可能解).在遺傳算法開始時,總是隨機的產生一些個體(即初始解),根據(jù)預定的目標函數(shù)對每一個個體進行評估,給出一個適應度值,基于此適應度值,選擇一些個體用來產生下一代,選擇操作體現(xiàn)了“適者生存”的原理,“好”的個體被用來產生下一代,“壞”的個體則被淘汰,然后選擇出來的個體,經過交叉和變異算子進行再組合生成新的一代,這一代的個體由于繼承了上一代的一些優(yōu)良性狀,因而在性能上要優(yōu)于上一代,這樣逐步朝著最優(yōu)解的方向進化.因此,遺傳算法可以看成是一個由可行解組成的群體初步進化的過程。
基本流程如下：
GA基本流程
比較關鍵的步驟是編碼和適應度函數(shù)的定義，這直接決定了選擇、交叉、變異的方法以及解碼的方式。尤其是編碼方式需要慎重考量，這個在一定程度上決定了后續(xù)的操作方式及復雜度。
實現(xiàn)過程
編碼
編碼這塊網(wǎng)上博客、論文都有很多實現(xiàn)，不過沒找到易于理解的高效的編碼。根據(jù)自己的實際情況，我的編碼方案如下（下文中的追溯單位等同于工件等同于最小調度單位）：
[工序1-各個工件的設備號，工序2-各個工件的設備號，工序3-各個工件的設備號，...... ，工序n-各個工件的設備號]
上述編碼中是由等長的n段組成，每段是一個工序，按實際加工順序排列；每臺設備有唯一的整數(shù)編號，每個工件對應一個設備編號，工件數(shù)m就是每段工序的編碼長度，因此一條染色體的編碼長度就是工序數(shù)p*工件數(shù)m。編碼內容為設備編號。
假設我們有：
- 4個工件{0:'#W-1',1:'#W-2',2:'#W-3',3:'#W-4'}
- 5道工序{0:'#P-1',1:'#P-2',2:'#P-3',3:'#P-4',4:'#P-5'}
- 共計12臺設備{0:'#M-1-1a',1:'#M-2-2a',2:'#M-2-2b',3:'#M-3-3a',4:'#M-3-3b',5:'#M-3-3c',6:'#M-4-4a',7:'#M-4-4b',8:'#M-4-4c',9:'#M-4-4d',10:'#M-5-5a',11:'#M-5-5b'}，其中各個工序的機器數(shù)為1，2，3，4，2。
一條完整的染色體編碼形如：
[0.0, 0.0, 0.0, 0.0, 2.0, 2.0, 1.0, 2.0, 4.0, 3.0, 4.0, 5.0, 7.0, 7.0, 8.0, 9.0, 10.0, 11.0, 10.0, 10.0]
初始化
有了編碼方案，后面就逐步實現(xiàn)遺傳算法的各個環(huán)節(jié)即可，首先是初始化，這里采用隨機初始化?；趐ython的實現(xiàn)如下（文末會有完整代碼，如下代碼段假設各個變量都已定義）：
def init_population(self):
print(self.population_number)
for _ in range(self.population_number):#self.population_number為初始化種群數(shù)量
g = Gene()
chromosome = []
for j in range(self.process_number):#工序數(shù)
p_choice = copy.deepcopy(self.process_matrix[j])
for k in range(self.workpiece_number):#工件數(shù)
p = random.choice(p_choice)
chromosome.append(p)
# if len(p_choice)>1: #如果希望避免有的設備沒被選到加上如下代碼，種群數(shù)比較大的話不需要
# p_choice.remove(p)
# else:
# p_choice = copy.deepcopy(self.process_matrix[j])
g.chromosome = chromosome
# print("chromosome:", g.chromosome)
g.fitness = self.calculate_fitness(g)
if g in self.genes:
print(g)#重復的編碼
print('---------------')
self.genes.add(g)
選擇個體
從種群中隨機選擇一定數(shù)量的個體，然后選擇適應度最高的,代碼如下：
def select_gene(self, n: int = 100):
if len(self.genes) <= n:
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 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 = randint(0, len(index_list) - 1)
p2 = randint(0, len(index_list) - 1)
start = min(p1, p2)
end = max(p1, p2)
prototypef = father.chromosome[start: end + 1]
prototypem = mother.chromosome[start: end + 1]
father.chromosome[start: end + 1] = prototypem
mother.chromosome[start: end + 1] = prototypef
child1 = Gene()
child2 = Gene()
child1.chromosome = father.chromosome
child1.fitness = self.calculate_fitness(child1)#計算適應度，下文實現(xiàn)
child2.chromosome = mother.chromosome
child2.fitness = self.calculate_fitness(child2)
return child1,child2
return gene_generate(g1, g2)
變異
隨機選取一個位置，隨機選取該工序可選的設備號替代原設備號即可。實現(xiàn)如下：
def gene_mutation(self, g: Gene, n = 2) -> None:
chromosomes = [g.chromosome[i:i+self.workpiece_number] for i in range(0,len(g.chromosome),self.workpiece_number)]
for index,item in enumerate(chromosomes):
position = randint(0, len(item) - 1)
item[position] = random.choice(self.process_matrix[index])
g.chromosome = list(itertools.chain.from_iterable(chromosomes))
g.fitness = self.calculate_fitness(g)
適應度計算
適應度計算稍微有點復雜，需要計算每道工序每個工件的開始和結束時間，以最后一個工件最后一道工序的結束時間作為總時間。定義machine_td用于記錄每臺設備的加工結束時間。這部分不太好理解需要多想想。
def evaluate_gene(self, g: Gene) -> GeneEvaluation:
evaluation = GeneEvaluation()
machine_td = {};w_time_list = []
chro_list = [g.chromosome[i:i+(self.workpiece_number)] for i in range(0,len(g.chromosome),self.workpiece_number)]
ch_mat = np.array(chro_list).T
for w in range(ch_mat.shape[0]):#追溯單位數(shù)目
for p in range(ch_mat.shape[1]):#工序數(shù)
if ch_mat[w][p] in machine_td:
evaluation.start_time[w][p] = machine_td[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]])
evaluation.end_time[w][p] = machine_td[ch_mat[w][p]]+self.time_dict[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]]) +self.time_dict[ch_mat[w][p]]
machine_td[ch_mat[w][p]] = machine_td[ch_mat[w][p]] + self.time_dict[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]]) +self.time_dict[ch_mat[w][p]]
if not ch_mat[w][p] in machine_td:
evaluation.start_time[w][p] = 0 if p==0 else machine_td[ch_mat[w][p-1]]
evaluation.end_time[w][p] = self.time_dict[ch_mat[w][p]] if p==0 \
else machine_td[ch_mat[w][p-1]]+self.time_dict[ch_mat[w][p]]
machine_td[ch_mat[w][p]] = self.time_dict[ch_mat[w][p]] if p==0 \
else machine_td[ch_mat[w][p-1]]+self.time_dict[ch_mat[w][p]]
evaluation.machine[w][p] = ch_mat[w][p]
w_time_list.append(machine_td[ch_mat[w][p]])
evaluation.fulfill_time = max(w_time_list)
# 計算適應度
def calculate_fitness(self, g: Gene) -> float:
return 1 / self.evaluate_gene(g).fulfill_time
完整過程：
single_ga_new.py
# -*- coding: utf-8 -*-
"""
Created on 2019/9/18 4:00 PM
# 918 勿忘國恥
@author: xuanlei
"""
from random import (randint)
from typing import (List, Tuple, Set, Dict, Any)
from collections import namedtuple
import random
import numpy as np
import itertools
import copy
import pprint
from tqdm import tqdm
MATRIX_SIZE = 5000
# 個體對象，染色體和適應度
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)
# 存儲解碼結果
class GeneEvaluation:
def __init__(self):
self.fulfill_time = 0
self.machine = np.empty([MATRIX_SIZE,MATRIX_SIZE],dtype=float)#[[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.end_time = np.empty([MATRIX_SIZE,MATRIX_SIZE],dtype=float)#[[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.start_time = np.empty([MATRIX_SIZE,MATRIX_SIZE],dtype=float)#
# 遺傳算法實現(xiàn)
class GA:
def __init__(self, population_number = 1000000, times = 1000, cross_probability = 0.85,
mutation_probability = 0.05, workpiece_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.process_number: int = 0 # 工序數(shù)量
self.chromosome_size: int = 0 # 染色體長度
self.machine_matrix = np.empty([MATRIX_SIZE,MATRIX_SIZE],dtype=float)#[[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
self.time_dict = {}
self.process_matrix = {}#dict
self.genes: Set[Gene] = set()
# 評估染色體
def evaluate_gene(self, g: Gene) -> GeneEvaluation:
evaluation = GeneEvaluation()
machine_td = {};w_time_list = []
chro_list = [g.chromosome[i:i+(self.workpiece_number)] for i in range(0,len(g.chromosome),self.workpiece_number)]
ch_mat = np.array(chro_list).T
for w in range(ch_mat.shape[0]):#追溯單位數(shù)目
for p in range(ch_mat.shape[1]):#工序數(shù)
if ch_mat[w][p] in machine_td:
evaluation.start_time[w][p] = machine_td[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]])
evaluation.end_time[w][p] = machine_td[ch_mat[w][p]]+self.time_dict[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]]) +self.time_dict[ch_mat[w][p]]
machine_td[ch_mat[w][p]] = machine_td[ch_mat[w][p]] + self.time_dict[ch_mat[w][p]] if p==0 \
else max(machine_td[ch_mat[w][p-1]],machine_td[ch_mat[w][p]]) +self.time_dict[ch_mat[w][p]]
if not ch_mat[w][p] in machine_td:
evaluation.start_time[w][p] = 0 if p==0 else machine_td[ch_mat[w][p-1]]
evaluation.end_time[w][p] = self.time_dict[ch_mat[w][p]] if p==0 \
else machine_td[ch_mat[w][p-1]]+self.time_dict[ch_mat[w][p]]
machine_td[ch_mat[w][p]] = self.time_dict[ch_mat[w][p]] if p==0 \
else machine_td[ch_mat[w][p-1]]+self.time_dict[ch_mat[w][p]]
evaluation.machine[w][p] = ch_mat[w][p]
w_time_list.append(machine_td[ch_mat[w][p]])
evaluation.fulfill_time = max(w_time_list)
return evaluation
# 計算適應度
def calculate_fitness(self, g: Gene) -> float:
return 1 / self.evaluate_gene(g).fulfill_time
# 個體交叉
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 = randint(0, len(index_list) - 1)
p2 = randint(0, len(index_list) - 1)
start = min(p1, p2)
end = max(p1, p2)
prototypef = father.chromosome[start: end + 1]
prototypem = mother.chromosome[start: end + 1]
father.chromosome[start: end + 1] = prototypem
mother.chromosome[start: end + 1] = prototypef
child1 = Gene()
child2 = Gene()
child1.chromosome = father.chromosome
child1.fitness = self.calculate_fitness(child1)
child2.chromosome = mother.chromosome
child2.fitness = self.calculate_fitness(child2)
return child1,child2
return gene_generate(g1, g2)
# 突變
def gene_mutation(self, g: Gene, n = 2) -> None:
chromosomes = [g.chromosome[i:i+self.workpiece_number] for i in range(0,len(g.chromosome),self.workpiece_number)]
for index,item in enumerate(chromosomes):
position = randint(0, len(item) - 1)
item[position] = random.choice(self.process_matrix[index])
g.chromosome = list(itertools.chain.from_iterable(chromosomes))
# print(g.chromosome)
g.fitness = self.calculate_fitness(g)
def init_population(self):
print(self.population_number)
for _ in range(self.population_number):
g = Gene()
chromosome = []
for j in range(self.process_number):#工序
p_choice = copy.deepcopy(self.process_matrix[j])
for k in range(self.workpiece_number):
p = random.choice(p_choice)
chromosome.append(p)
# if len(p_choice)>1:
# p_choice.remove(p)
# else:
# p_choice = copy.deepcopy(self.process_matrix[j])
g.chromosome = chromosome
# print("chromosome:", g.chromosome)
g.fitness = self.calculate_fitness(g)
if g in self.genes:
print(g)
print('---------------')
self.genes.add(g)
# print(g)
# print(i)
print(len(self.genes))
# 選擇個體
def select_gene(self, n: int = 100):
if len(self.genes) <= n:
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:
workpiece_size = len(parameter)
self.process_number = len(parameter[0])
for i in range(len(parameter)):
self.time_dict.update(dict(parameter[i]))
for i in range(workpiece_size):
self.chromosome_size += len(parameter[i])#染色體長度=工件數(shù)*工序數(shù)
for j in range(self.process_number):
self.machine_matrix[i][j] = parameter[i][j][0]
# self.time_matrix[i][j] = parameter[i][j][1]
'''
4行5列 machine_matrix記錄每個追溯單位（行）每道工序（列）的機器編號
time_matrix記錄每個追溯單位（行）每道工序（列）對應機器完成該工序所需時間
'''
for i in range(workpiece_size):#工序和機器號的key value
for j in range(self.process_number):
if self.machine_matrix[i][j] != -1:
self.process_matrix.setdefault(j,[]).append(self.machine_matrix[i][j])
self.process_matrix[j] = list(set(self.process_matrix[j]))
self.init_population()
print(len(self.genes))
for _ in tqdm(range(self.times)):
probability = randint(1, 100) / 100
if probability < self.mutation_probability:
index = randint(0, len(self.genes))#22
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)
print('=====================...>>>')
print(len(self.genes))
print('=====================...<<<')
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"])
# 輸出結果
def schedule() -> ResultData:
# print(data)
# reshape = reshape_data(data)#ReshapeData(ans, workpieces, machines, process, reverse_machines, reverse_workpieces)
parameter = [[(0, 10), (1, 15), (3, 9), (6, 35), (10, 8)],
[(0, 10), (2, 18), (4, 4), (7, 47), (11, 5)],
[(0, 10), (2, 18), (5, 8), (8, 49), (10, 8)],
[(0, 10), (1, 15), (5, 8), (9, 40), (11, 5)]]#4個工件
'''
[[(2, 21), (4, 21)],
[(4, 10), (0, 21), (3, 12)],
[(1, 5)],
[(4, 10), (1, 11), (0, 5)]]
每個工件對應的加工設備編號和所需時間，并按照工序優(yōu)先級排序
'''
# print(parameter)
n = 4#工件數(shù)目
ga = GA(workpiece_number = n)
result = ga.exec(parameter)
p = ga.process_number
# print(n,p)
row_data = []
res_w = {0:'#W-1',1:'#W-2',2:'#W-3',3:'#W-4'}
res_m = {0:'#M-1-1a',1:'#M-2-2a',2:'#M-2-2b',3:'#M-3-3a',4:'#M-3-3b',5:'#M-3-3c',
6:'#M-4-4a',7:'#M-4-4b',8:'#M-4-4c',9:'#M-4-4d',10:'#M-5-5a',11:'#M-5-5b'}
res_p = {0:'#P-1',1:'#P-2',2:'#P-3',3:'#P-4',4:'#P-5'}
for i in range(n):
for j in range(p):
temp = {
"workpiece": res_w[i],
"process": res_p[j],
"machine": res_m[result.machine[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)
return ResultData(result.fulfill_time, row_data)
if __name__ == "__main__":
pprint.pprint(schedule().row_data)
運行結果如下，因為這里測試的參數(shù)比較小只有4個工件12臺設備，所以設置的初始種群和迭代次數(shù)非常大，目的是找出全局最優(yōu)解（運行多次結果基本一致，確實是全局最優(yōu)了），實際中的解空間往往非常大，需要折中選擇初始種群規(guī)模和迭代次數(shù)。
[{'endTime': 10.0,
'machine': '#M-1-1a',
'process': '#P-1',
'startTime': 0.0,
'workpiece': '#W-1'},
{'endTime': 28.0,
'machine': '#M-2-2b',
'process': '#P-2',
'startTime': 10.0,
'workpiece': '#W-1'},
{'endTime': 32.0,
'machine': '#M-3-3b',
'process': '#P-3',
'startTime': 28.0,
'workpiece': '#W-1'},
{'endTime': 81.0,
'machine': '#M-4-4c',
'process': '#P-4',
'startTime': 32.0,
'workpiece': '#W-1'},
{'endTime': 89.0,
'machine': '#M-5-5a',
'process': '#P-5',
'startTime': 81.0,
'workpiece': '#W-1'},
{'endTime': 20.0,
'machine': '#M-1-1a',
'process': '#P-1',
'startTime': 10.0,
'workpiece': '#W-2'},
{'endTime': 35.0,
'machine': '#M-2-2a',
'process': '#P-2',
'startTime': 20.0,
'workpiece': '#W-2'},
{'endTime': 43.0,
'machine': '#M-3-3c',
'process': '#P-3',
'startTime': 35.0,
'workpiece': '#W-2'},
{'endTime': 90.0,
'machine': '#M-4-4b',
'process': '#P-4',
'startTime': 43.0,
'workpiece': '#W-2'},
{'endTime': 95.0,
'machine': '#M-5-5b',
'process': '#P-5',
'startTime': 90.0,
'workpiece': '#W-2'},
{'endTime': 30.0,
'machine': '#M-1-1a',
'process': '#P-1',
'startTime': 20.0,
'workpiece': '#W-3'},
{'endTime': 48.0,
'machine': '#M-2-2b',
'process': '#P-2',
'startTime': 30.0,
'workpiece': '#W-3'},
{'endTime': 52.0,
'machine': '#M-3-3b',
'process': '#P-3',
'startTime': 48.0,
'workpiece': '#W-3'},
{'endTime': 92.0,
'machine': '#M-4-4d',
'process': '#P-4',
'startTime': 52.0,
'workpiece': '#W-3'},
{'endTime': 100.0,
'machine': '#M-5-5a',
'process': '#P-5',
'startTime': 92.0,
'workpiece': '#W-3'},
{'endTime': 40.0,
'machine': '#M-1-1a',
'process': '#P-1',
'startTime': 30.0,
'workpiece': '#W-4'},
{'endTime': 55.0,
'machine': '#M-2-2a',
'process': '#P-2',
'startTime': 40.0,
'workpiece': '#W-4'},
{'endTime': 59.0,
'machine': '#M-3-3b',
'process': '#P-3',
'startTime': 55.0,
'workpiece': '#W-4'},
{'endTime': 94.0,
'machine': '#M-4-4a',
'process': '#P-4',
'startTime': 59.0,
'workpiece': '#W-4'},
{'endTime': 100.0,
'machine': '#M-5-5b',
'process': '#P-5',
'startTime': 95.0,
'workpiece': '#W-4'}]
繪制甘特圖
上述結果不夠簡潔明了，可以繪制甘特圖更加形象地展示調度結果。代碼如下：
# -*- coding: utf-8 -*-
"""
Created on 2019/9/18 5:10 PM
# 918 勿忘國恥
@author: xuanlei
"""
import matplotlib.pyplot as plt
import numpy as np
from single_ga_new import schedule
plt.figure(figsize=(15,8))
ax=plt.gca()
[ax.spines[i].set_visible(False) for i in ["top","right"]]
from pylab import mpl
mpl.rcParams['font.sans-serif'] = ['FangSong']
mpl.rcParams['axes.unicode_minus'] = False
def gatt(m,t):
"""甘特圖
m機器集
t時間集
"""
tt = [x[1]-x[0] for x in t]
for j in range(len(m)):#工序j
i=num_machine[m[j][0]]#機器編號i
sn = '追溯單位-'+str(m[j][1][1:])
# if j==0:
# plt.barh(i,tt[j],height=1.2,align='center')
# plt.text(tt[j]/2,i,'%s\nT:%s'%((sn),tt[j]),color="white",verticalalignment="center",horizontalalignment="center",size=8)
# else:
plt.barh(i,tt[j],left=(t[j][0]),height=0.8,align='center')
plt.text(t[j][0]+tt[j]/2,i,'%s\nT-%s'%((sn),str(tt[j])+'('+str(t[j])+')'),color="black",verticalalignment="center",horizontalalignment="center",size=8)
def make_reverse_index(arr: list) -> dict:
result = {}
for i in range(len(arr)):
result[arr[i]] = i
return result
if __name__=="__main__":
"""測試代碼"""
# m=np.random.randint(1,7,35)#reshape.machine#
# t=np.random.randint(15,45,35)
tt = schedule().row_data
mms = ['#M-1-1a','#M-2-2a','#M-2-2b','#M-3-3a','#M-3-3b','#M-3-3c',
'#M-4-4a','#M-4-4b','#M-4-4c','#M-4-4d','#M-5-5a','#M-5-5b']
mm = dict(zip(range(len(mms)),mms))
plot_result = [[item['machine'],item['workpiece'],item['process'],item['startTime'],item['endTime']] for item in tt]
plot_result2 = [value for index, value in sorted(enumerate(plot_result), key=lambda plot_result:plot_result[1])]
# mm.sort(reverse=True)
num_machine = make_reverse_index(mm)
m = [[x[0],x[1]] for x in plot_result2]
t = [[x[-2],x[-1]] for x in plot_result2]
gatt(m,t)
# time =t
# plt.xticks(np.arange(len(time)), time)
plt.yticks(np.arange(len(num_machine)),list(num_machine))
#plt.grid()
plt.savefig("gant.png",dpi=250)
如下圖：
這個圖并非是上面結果的繪制，是上述參數(shù)下多次運行的結果之一，基本近似。
調度結果
由上圖可以看出，有個設備沒用上卻達到了最優(yōu)狀態(tài)，說明該工序下的設備是冗余的，可以考慮減除；另外工序1只有一臺設備顯然成為產能的瓶頸應該增加設備。
小結
上面就是用遺傳算法解決針對批量加工標準工件、設備時間相對固定且存在并行設備的半柔性生產調度問題的過程。通過調度算法運行模擬不僅對工件的生產加工進行合理規(guī)劃最大限度地接近理論產能，同時也可以推算出產能瓶頸從而優(yōu)化各個工序間的設備配比。對實際上產來說有很大意義。
參考
https://blog.csdn.net/daydream13580130043/article/details/95927841
