作业车间调度与遗传算法Python/Java实现及应用：BitMES，基于

作业车间调度问题描述

作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型，是最难的组合优化问题之一，应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等，因此对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用，还可缩短生产周期，降低生产成本。

作业车间调度问题描述：

一个加工系统有 M 台机器，要求加工 N 个作业，其中，作业 i 包含工序数为 $L_{i}$ 。令，则 L 为任务集的总工序数。其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。作业车间调度需要考虑如下约束:

每道工序在指定的机器上加工，且必须在前一道工序加工完成后才能开始加工。
某一时刻1台机器只能加工1个作业。
每个作业只能在1台机器上加工1次。
各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。

问题的数学模型：

令(i,j)表示作业i的第j个工序。 $S_{ij}$ 和 $T_{ij}$ 分别表示(i,j)的加工起始时刻和加工时间。 $Z_{ijk}$ 表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器上加工， $Z_{ijk} = 1$ ；否则， $Z_{ijk} = 0$ ， $C_{k}$ 为第k台机器的完工时间，则问题的数学模型如下：

公式(1)为目标函数，即优化目标，系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。

遗传算法

随着遗传算法（genetic algorithm (GA)）在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究。已有研究结果表明，遗传算法对求解作业车间调度问题具有较好的效果，因此系统采用遗传算法来解该问题，遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。系统通过模拟生物进化，包括遗传、突变、选择等，来不断地产生新个体，并在算法终止时求得最优个体，即最优解。

遗传算法解决作业车间调度问题基本步骤

初始化一定数量的种群（染色体编码）
计算个体适应度（染色体解码）
采用锦标赛法选择染色体并交叉产生新个体
个体（染色体）变异
达到遗传代数终止算法并从中选取适应度最优的个体作为作业车间调度问题的解

流程图如下

遗传算法所需参数

种群规模：种群中个体的数量，用 populationNumber 表示
染色体长度：个体的染色体的长度，用 chromosomeSize 表示
交叉概率：控制交叉算子的使用频率，用 crossProbability 表示，并且值为0.95
变异概率：控制变异算子的使用频率，用 mutationProbability 表示，并且值为0.05
遗传代数：种群的遗传代数，用于控制遗传算法的终止，用 times 来表示

遗传算法实现基本步骤及伪代码

1. 编码及初始化种群

采用工序实数编码来表示染色体，即M台机器，N个工件，每个工件的工序数为 $process_{i} (0 <= i < N)$ ，则染色体长度为 $chromosomeSize = \sum process_{i}$ ，对染色体编码如下： $chromosome = { ..., w_i, w_j, w_k, ... }$ 。其中代表第i个工件编号，而出现的次数代表该工件的第几道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的编号，第几次出现就代表第几道工序。然后将每一次随机生成的染色体个体加入到种群集合中。

算法伪代码：

2. 解码及计算适应度

将优化目标定义为总加工时间最短，因此适应度定义为最短加工时间的倒数，设fitness为对应个体的适应度，fulfillTime为最短加工时间，因此

其中fulfillTime的计算方法如下：

首先定义如下变量

然后从左到右遍历个体的染色体序列 ${..., w_i, w_j, w_k, ...}$ ，其中表示第i个工件的编号，则对应的当前工序为 $processIds_{w_i}$ ,设为p。当前工件当前工序所使用的机器编号为 $machine_{w_i, p}$ ，设为m。当前工件当前工序对应的加工时间为 $time_{w_i, p}$ ，设为t。则工件的第p道工序的最晚开始时间为

而第m台机器的加工时间为

工件的第p道工序的结束时间为

最后加工完所有工件的最短加工时间fulfillTime为

从而计算出适应度fitness。

伪代码如下：

3. 个体选择算子

个体的选择使用锦标赛法，其基本策略为从整个种群中随机抽取n个个体让它们竞争，选取其中最优的个体。该算子的选择过程如下

伪代码如下：

4. 染色体交叉算子

使用Order Crossover(OX)交叉算子，该算子的交叉步骤如下：

对于一对染色体g1, g2，首先随机产生一个起始位置start和终止位置end，并由从g1的染色体序列从start到end的序列中产生一个子代原型

将g2中不包含在child prototype的其余编码加入到child prototype两侧

上述步骤将产生一个child，交换g1, g2即可产生另一个child

伪代码如下：

5. 染色体变异算子

变异的作用主要是使算法能跳出局部最优解，因此不同的变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子，即从染色体中随机产生两个位置并交换这两个位置的值

伪代码如下：

6. 算法整体伪代码如下：

遗传算法代码实现

根据上面的步骤及伪代码，很容易就能写出Python及Java对应的代码实现了，如下：

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


# 个体对象，染色体和适应度
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_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)]


# 遗传算法实现
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  # 种群数量
        self.times = times  # 遗传代数
        self.cross_probability = cross_probability  # 交叉概率
        self.mutation_probability = mutation_probability  # 突变概率

        self.workpiece_number = workpiece_number  # 工件数量
        self.machine_number = machine_number  # 机器数量
        self.process_number: int = 0  # 工序数量
        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

    # 计算适应度
    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 = 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)

    # 选择个体，锦标赛法
    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"])


# 输出结果
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__":
    # 测试数据
    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函数实现

            
              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也很容易实现：

            
              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;
    }
    
    // 计算适应度
    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;
    }

    // 选择个体
    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的作业车间调度系统实现

写了那么多的遗传算法解作业车间调度问题，当然还要有实际应用了，因此开发了一个作业车间调度系统，核心功能很简单就是对工件、机器、工序进行增删改查并使用遗传算法计算调度结果，前端用甘特图展示调度结果。(GitHub地址：https://github.com/sundial-dreams/BitMESClient，如果觉得项目不错，别忘了点赞哦)

系统总体技术路线：采用前后端分离模式开发，基于C/S模式，客户端使用JavaScript，Electron， React，Node.js等进行组件化开发，服务端使用express，nodejs，typescript，python，sanic，graphql等开发独立的graphql服务或http服务，数据库使用mysql来存储基本的信息，redis来实现id生成，mongodb来存储调度结果。

Client端： 使用JavaScript来开发PC端应用程序。基于Electron进行开发，在Electron基础上使用React、Redux、Antd、Echarts等前端技术和包，以模块化、组件化的方式构建一个独立的UI页面，对于页面的切换使用了前端路由React-router。除此之外，通过封装一个GraphQL类来做GraphQL查询，以此和后端进行数据交互。通过这种方式能快速的构建一个可维护性好，UI美观的PC端应用程序。
GrapgQL Service端： 使用Typescript开发的一个GraphQL服务，提供GraphQL查询。基于NodeJS、Express、GraphQL等来构建一个GraphQL服务器，由于Node.js的异步非阻塞特性，使得构建的服务器并发能力更强。除此之外，使用TypeORM来做数据库的对象关系映射，加快开发速度。通过这种方式能快速搭建起一个GraphQL服务端，使用GraphQL查询来替代传统的RESTful API能使提供的API服务可维护性、扩展性更强。
Schedule Service端： 使用Python开发，提供作业调度服务。基于Python异步Web框架Sanic，使得构建的服务器运行效率和并发能力都比较强，并且使用Python来实现作业车间调度算法（遗传算法）一方面是比较容易，另一方面是Python支持多线程编程，因此多线程来优化算法也能实现。
Data Storage端： 数据存储，使用MySQL来存储一些基本的数据，如机器信息、工件信息、工件工艺信息、员工信息等等。使用Redis来存储一些健值对信息以及Id生成，由于Redis的单线程异步非阻塞特性，使得生成的Id不存在重复。使用MongoDB来存储调度结果，由于调度结果完全是JSON格式数据，与使用MySQL存储相比，使用文档数据库MongoDB来存储比较容易，而且查询也比较方便。

项目运行：

首页

管理

作业调度

最后，如果觉得这篇文章有帮助，别忘了点赞哦

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

2元

5元

10元

20元

自定义