文章目錄

• • 1.模糊作業(yè)車(chē)間
  • • 1.1 模糊數(shù)
    • 1.2 三角模糊數(shù)操作
    • 1.3 模糊甘特圖
  • 2.FJSP+模糊加工時(shí)間+GA
  • • 2.1 GA算法設(shè)置
    • 2.2 python代碼
    • 2.3 測(cè)試結(jié)果

創(chuàng)新互聯(lián)長(zhǎng)期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為菏澤企業(yè)提供專(zhuān)業(yè)的網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)，菏澤網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。1.模糊作業(yè)車(chē)間 1.1 模糊數(shù)

論域X上的模糊集合A由隸屬度函數(shù)u(x)表示，u(x)取值[0,1]。如果A為三角模糊數(shù)，A可以表示為(a1,aM,a2)。如果A為四角模糊數(shù)，A可以表示為(a1,a2,a4,a5)。各模糊數(shù)和隸屬度函數(shù)如下所示：


對(duì)于不確定條件下的工件加工時(shí)間和完工時(shí)間，采用三角模糊數(shù)來(lái)進(jìn)行描述。對(duì)于不確定條件下的交貨期，采用梯形模糊數(shù)來(lái)進(jìn)行描述。例如job1的第一個(gè)操作O11，其在機(jī)器1上的模糊加工時(shí)間用三角模糊數(shù)表示(4,7,12)，三個(gè)數(shù)分別表示最好的，最可能的，最壞的加工時(shí)間。一個(gè)帶有模糊加工時(shí)間的4job 和 2machine的柔性作業(yè)車(chē)間調(diào)度問(wèn)題數(shù)據(jù)案例如下：括號(hào)為實(shí)際加工時(shí)間，可不考慮

1.2 三角模糊數(shù)操作

【1】Sakawa, M., & Mori, T. (1999). An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate. Computers & Industrial Engineering, 36(2), 325-341. doi:https://doi.org/10.1016/S0360-8352(99)00135-7
【2】Sakawa, M., & Kubota, R. (2000). Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms. European Journal of Operational Research, 120(2), 393-407. doi:https://doi.org/10.1016/S0377-2217(99)00094-6

要求解車(chē)間調(diào)度問(wèn)題，會(huì)遇到加工時(shí)間的一些計(jì)算，比如求加工開(kāi)始時(shí)間，加工完成時(shí)間，和確定數(shù)操作一樣，模糊數(shù)的操作也非常重要，主要包括模糊數(shù)的求和和取大操作以及對(duì)模糊數(shù)的比較。

• 求和：計(jì)算每個(gè)操作的模糊完成時(shí)間[1]

• 取大：計(jì)算每個(gè)操作的模糊開(kāi)始時(shí)間[1]

• 比較：模糊完成時(shí)間是模糊加工時(shí)間的總和，因此也變成了三角模糊數(shù)，如果要最小化大的模糊完成時(shí)間，就要比較一些模糊完成時(shí)間的值[2]
  
• 舉例

假設(shè)有2??2的JSP問(wèn)題：
Job 1: Machine 1 (2, 5, 6), Machine 2 (5, 7, 8)
Job 2: Machine 2 (3, 4, 7), Machine 1 (1, 2, 3)
那么Job1的第二個(gè)操作模糊開(kāi)始時(shí)間為(2, 5, 6)V(3, 4, 7)，即(3, 5, 7)；模糊完成時(shí)間為(3, 5, 7)+(5, 7, 8)=(8, 12, 15)
假設(shè)有4個(gè)三角模糊數(shù)為A1=(2,5,8),A2=(3,4,9),A3=(3,5,7),A4=(4,5,8)，根據(jù)比較原則可得A4,A1,A3,A2

1.3 模糊甘特圖

由于每個(gè)操作的開(kāi)始時(shí)間和完成時(shí)間都是三角模糊數(shù)，因此其甘特圖也與正常甘特圖不同，如下圖，每個(gè)操作的模糊開(kāi)始時(shí)間在直線下面，模糊完成時(shí)間在直線上面，每個(gè)三角形就是前面提到的隸屬度函數(shù)圖像。如果是機(jī)器上第一個(gè)加工，用長(zhǎng)方形表示。如O41模糊開(kāi)始時(shí)間為(4,5,7)，接下來(lái)要在M1上加工，而M1最快的模糊結(jié)束時(shí)間為O31的(6,10,14)，因此O42模糊開(kāi)始時(shí)間為(6,10,14)。

2.FJSP+模糊加工時(shí)間+GA 2.1 GA算法設(shè)置

復(fù)現(xiàn)文章：【3】Lei, D. M. (2010). A genetic algorithm for flexible job shop scheduling with fuzzy processing time. International Journal of Production Research, 48(10), 2995-3013. doi:10.1080/00207540902814348

與前面介紹不同，[3]提出了新的max操作算子，即直接根據(jù)rank結(jié)果確定，兩個(gè)三角模糊數(shù)s,t中的較大值要么是s，要么是t

• 編碼和解碼（two-string）

用兩層編碼表示，一層為操作序列，一層為選擇機(jī)器，注意第二層的機(jī)器分配編碼對(duì)應(yīng)的是各個(gè)操作按順序排下來(lái)的機(jī)器，與第一層編碼無(wú)關(guān)。比如操作011最后加工，加工機(jī)器為1。

在部分其它文獻(xiàn)中的兩層編碼，第二層的機(jī)器編碼對(duì)應(yīng)的是第一層編碼下每個(gè)操作的加工機(jī)器，與此處不同。下面是另一種編碼方式，比如操作023最后加工，加工機(jī)器為M5。

適應(yīng)度值為目標(biāo)函數(shù)值（模糊完成時(shí)間）

• 選擇（tournament select）

使用精英策略，即保留每代種群里最優(yōu)的個(gè)體。由于模糊目標(biāo)值，輪盤(pán)賭選擇(roulette wheel)方式不適合，因此使用錦標(biāo)賽選擇(tournament select)。有放回的從種群中隨機(jī)選擇兩個(gè)個(gè)體，選擇適應(yīng)度值較小的個(gè)體進(jìn)入新種群

• 交叉（TPX；GPX/GPPX）

將種群分成兩個(gè)子種群A和B，分別代表作業(yè)序列和機(jī)器分配。對(duì)于機(jī)器分配部分，交叉使用兩點(diǎn)交叉(two point crossover TPX)。對(duì)于作業(yè)序列部分，使用兩種交叉：generalised position crossover (GPX)和generalisation of the precedence preservative crossover (GPPX)
GPX：從parent1中選擇子字符串S，如S=1231，找到S中每個(gè)元素在parent2中的位置并刪除對(duì)應(yīng)的元素，注意元素是有順序的，如S中的1在parent1中是第二次出現(xiàn)，因此要找到parent2中第二次出現(xiàn)的1，刪除S后parent2變成32414234，將S插入到parent2中，位置等于S在parent1中的位置，即pos=4

GPPX：設(shè)置一個(gè)取值[1,2]的string，分表代表從parent1(2)中相繼選擇基因，如果從parent1中選擇了一個(gè)基因，刪除其在parent2對(duì)應(yīng)的基因

• 變異（swap）

對(duì)于某個(gè)個(gè)體，隨機(jī)選擇兩個(gè)基因并交換

• 算法

隨機(jī)生成N個(gè)個(gè)體的初始種群P；
對(duì)P執(zhí)行tournament select；
將P分成兩個(gè)子種群A和B，分別代表作業(yè)序列和機(jī)器分配部分；
對(duì)種群A執(zhí)行GPPX或者GPX交叉和swap變異；
對(duì)種群B執(zhí)行TPX交叉和swap變異；
合并A和B生成新種群并計(jì)算適應(yīng)度值；
迭代直到結(jié)束

2.2 python代碼

操作序列用GPPX交叉算子，交叉率=0.8，變異率=0.1，種群數(shù)=100，迭代數(shù)=1000，編碼第二種方式，下面是GA部分，完整代碼https://github.com/bujibujibiuwang/solve-fuzzy-FJSP-with-GA

import random
from params import get_args
from Shop import Shop
from utils import *


class GA(object):
    def __init__(self, args, shop):
        self.shop = shop
        self.cross_rate = args.cross_rate
        self.mutate_rate = args.mutate_rate
        self.pop_size = args.pop_size
        self.elite_number = args.elite_number

        self.chrom_size = self.shop.job_nb * self.shop.op_nb
        self.pop = []

    def encode(self):
        init_pop = []
        for _ in range(self.pop_size):
            one_string = []
            for _ in range(self.shop.op_nb):
                one_string += list(np.random.permutation(self.shop.job_nb))
            random.shuffle(one_string)
            two_string = [random.randint(0, self.shop.machine_nb-1) for _ in range(self.chrom_size)]
            individual = np.vstack([one_string, two_string])
            init_pop.append(individual)
        return np.array(init_pop)

    def decode(self, pop1):
        fuzzy_fitness = []
        certain_fitness = []
        for individual in pop1:
            fuzzy_completion_time = self.shop.process_decode1(individual)
            fuzzy_fitness.append(fuzzy_completion_time)
            certain_fitness.append(value(fuzzy_completion_time))
        return fuzzy_fitness, certain_fitness

    def selection(self, pop2, fuzzy_fitness, certain_fitness):
        """
        tournament selection + elite_strategy
        """
        pop2 = pop2.tolist()
        sorted_pop = sorted(pop2, key=lambda x: certain_fitness[pop2.index(x)], reverse=False)
        new_pop = sorted_pop[:self.elite_number]
        while len(new_pop)< self.pop_size:
            index1, index2 = random.sample(list(range(10, self.pop_size)), 2)
            if rank(fuzzy_fitness[index1], fuzzy_fitness[index2]) == fuzzy_fitness[index1]:
                new_pop.append(pop[index2])
            else:
                new_pop.append(pop[index1])
        return np.array(new_pop)

    def crossover_machine(self, pop_machine):
        """
        two point crossover (TPX)
        """
        temp = pop_machine.copy().tolist()
        new_pop = []
        while len(temp) != 0:
            parent1, parent2 = random.sample(temp, 2)
            temp.remove(parent1)
            temp.remove(parent2)
            if random.random()< self.cross_rate:
                pos1, pos2 = sorted(random.sample(list(range(self.chrom_size)), 2))
                offspring1 = parent1[:pos1] + parent2[pos1:pos2] + parent1[pos2:]
                offspring2 = parent2[:pos1] + parent1[pos1:pos2] + parent2[pos2:]
            else:
                offspring1 = parent1
                offspring2 = parent2
            new_pop.append(offspring1)
            new_pop.append(offspring2)
        return np.array(new_pop)

    def crossover_job(self, pop_job):
        """
        generalisation of the precedence preservative crossover (PPX)
        """
        temp = pop_job.copy().tolist()
        new_pop = []
        for parent1 in temp:
            if random.random()< self.cross_rate:
                new_individual = []
                parent2 = pop_job[random.randint(0, self.pop_size-1)].tolist()
                string = random.choices([0, 1], k=self.chrom_size)
                for choose in string:
                    if int(choose) == 0:
                        new_individual.append(parent1[0])
                        parent2.remove(parent1[0])
                        parent1 = parent1[1:]
                    else:
                        new_individual.append(parent2[0])
                        parent1.remove(parent2[0])
                        parent2 = parent2[1:]
                new_pop.append(new_individual)
            else:
                new_pop.append(parent1)
        return np.array(new_pop)

    def mutation(self, part):
        """
        swap
        """
        for individual in part:
            if random.random()< self.mutate_rate:
                pos1, pos2 = random.sample(list(range(self.chrom_size)), 2)
                individual[pos1], individual[pos2] = individual[pos2], individual[pos1]
        return part

    @staticmethod
    def elite_strategy(pop3, fitness):
        best_fitness = [np.inf, np.inf, np.inf]
        best_individual = None
        for k, individual in enumerate(pop3):
            if rank(fitness[k], best_fitness) == best_fitness:
                best_fitness = fitness[k]
                best_individual = individual
        return best_individual, best_fitness

2.3 測(cè)試結(jié)果

用文獻(xiàn)[3]中instance1測(cè)試，文獻(xiàn)中instance1求出最優(yōu)解[20, 31, 40]，本人測(cè)試最優(yōu)解[20, 31, 41]

0:old best:[inf, inf, inf], now best:[47, 70, 89], now mean:99.9475
100:old best:[28, 41, 54], now best:[34, 42, 52], now mean:48.41
200:old best:[25, 38, 46], now best:[25, 38, 47], now mean:38.92
300:old best:[25, 36, 45], now best:[25, 36, 45], now mean:38.2425
400:old best:[21, 33, 44], now best:[21, 33, 44], now mean:35.2775
500:old best:[21, 31, 41], now best:[24, 31, 40], now mean:34.475
600:old best:[21, 31, 41], now best:[21, 31, 42], now mean:34.35
700:old best:[19, 31, 42], now best:[19, 31, 42], now mean:33.5275
800:old best:[20, 31, 41], now best:[19, 31, 42], now mean:32.6575
900:old best:[20, 31, 41], now best:[20, 31, 41], now mean:34.175

模糊甘特圖如下

迭代曲線如下

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：帶模糊加工時(shí)間的柔性作業(yè)車(chē)間調(diào)度理論和GA復(fù)現(xiàn)(python)-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/cecpps.html