作業(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)度需要考慮如下約束:

1. 每道工序在指定的機(jī)器上加工，且必須在前一道工序加工完成后才能開始加工。
2. 某一時(shí)刻1臺機(jī)器只能加工1個(gè)作業(yè)。
3. 每個(gè)作業(yè)只能在1臺機(jī)器上加工1次。
4. 各作業(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)度問題基本步驟

1. 初始化一定數(shù)量的種群（染色體編碼）
2. 計(jì)算個(gè)體適應(yīng)度（染色體解碼）
3. 采用錦標(biāo)賽法選擇染色體并交叉產(chǎn)生新個(gè)體
4. 個(gè)體（染色體）變異
5. 達(dá)到遺傳代數(shù)終止算法并從中選取適應(yīng)度最優(yōu)的個(gè)體作為作業(yè)車間調(diào)度問題的解

流程圖如下

遺傳算法所需參數(shù)

1. 種群規(guī)模：種群中個(gè)體的數(shù)量，用 populationNumber 表示
2. 染色體長度：個(gè)體的染色體的長度，用 chromosomeSize 表示
3. 交叉概率：控制交叉算子的使用頻率，用 crossProbability 表示，并且值為0.95
4. 變異概率：控制變異算子的使用頻率，用 mutationProbability 表示，并且值為0.05
5. 遺傳代數(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é)果。

1. 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)用程序。

2. 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)。

3. 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)。

4. 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)贊哦