算法分析与设计课程的期末大作业,问题如下:

Problem 2: job scheduling problem.

The production line has 8 machines, and 28 jobs are ready to be processed. The process time of each job to the machine is given as follows, the number in the table is the process time of each job on each machine:

 

machine1

machine2

machine3

machine4

machine5

machine6

machine7

machine8

Job1

11

16

15

4

15

22

17

22

Job2

9

9

15

3

21

4

16

2

Job3

15

15

19

15

22

15

17

8

Job4

22

33

16

19

21

21

27

9

Job5

14

28

14

12

12

17

8

21

Job6

7

18

19

11

10

23

13

19

Job7

18

19

20

5

29

16

9

10

Job8

8

32

32

16

1

12

8

5

Job9

23

22

14

18

22

11

11

5

Job10

9

17

27

45

12

11

8

6

Job11

21

15

11

10

10

13

17

29

Job12

8

8

12

12

12

16

16

16

Job13

7

7

27

7

7

7

19

9

Job14

11

11

11

12

25

33

11

11

Job15

19

5

5

5

7

8

21

21

Job16

21

12

11

3

3

3

5

5

Job17

7

7

4

4

12

12

16

16

Job18

8

1

1

8

8

1

1

1

Job19

11

22

22

33

33

11

11

22

Job20

11

35

33

18

6

6

6

2

Job21

2

2

33

1

1

51

22

2

Job22

15

15

15

5

5

5

5

5

Job23

19

2

19

2

2

2

19

2

Job24

18

18

38

2

2

22

38

3

Job25

10

9

9

29

1

1

1

22

Job26

50

1

1

5

2

1

44

1

Job27

35

7

7

12

12

35

1

5

Job28

22

1

1

29

11

29

1

1

We suppose:

Each machine can process one job at one time.

The process of each job at each machine cannot be spitted.

Each job has to be processed along machines based on sequence 1,2,3,, ,8  (for example, any job cannot be processed on machine 2 before machine 1, it cannot be processed on machine 3 before machines 1 or 2).

For Jobs 3,5,7,9,11,14 you can choose only 3 job to process, and the others can be ignored.

You need give a process sequence of jobs, such that can minimize the final complete time (at last machine) of last job.

This process sequence cannot be changed along all the machines. For example, once the sequence is 1-2-3-…-27-28, then, for each machine, the job 1 is processed first, then job 2,…, and job28 is the last process job on each machine.

程序设计思路:

一、编码

28个job需要按照确定的时间依次在8台machine上完成8道工序,job间的加工顺序一旦确定在每台machine上都保持一致,同时需要满足job 3,5,7,9,11,14中只有3个被加工,这是一个带有约束的flow shop问题。在进行染色体编码时可以采用如下方式:

每条染色体由31个{1,2,…,28}间的整数排列而成,其中前28个数为head,可以理解为不考虑约束情况下包含28个job的flow shop的加工顺序,后3个数为tail,tail为{3,5,7,9,11,14}中的任意3个不重复的数。则把每条染色体tail部分包含的数从head部分去除将会对应一个原带有约束的flow shop问题的解,如:染色体[8,3,4,…,9,7,6,…,11,28,10,…,3,7,11]表示[8,4,…,9,6,…,28,10…]的加工顺序。

二、初始化种群(initial)

根据种群规模pop_size,将{1,2,…,28}随机打乱pop_size次以获得head,从{3,5,7,9,11,14}中任取3个数,重复操作pop_size次以获得tail,将head和tail拼接,获得初始种群每个个体的染色体。

三、交叉(cross over)

父代种群中的两条染色体(parent1,parent2),以p_cr的概率进行交叉产生子代(child1, child2)。为了保证子代的可行性,可以设计如下交叉方式:

对于head部分,采取单点交叉,即令两条父代染色体的head部分从某一任意索引后的基因片段互换,然后分别遍历两条父代染色体head部分的基因,将没有被包含进子代染色体中的基因依次加入,直到子代染色体的head长度也为28,形成两个子代染色体的head,如下图(以1到7的序列示意):

对于tail部分,任取1~3间的数i,若parent1的tail中没有parent2的tail部分第i位对应的基因(gene2),则将parent1 tail部分的第i个基因(gene1)替换位gene2,反之保持不变;同理,若parent2的tail部分没有gene1,则进行替换,反之不替换,如:

四、变异(mutate)

对每个交叉产生的子代染色体child,以p_mu的概率发生变异,变异规则为:对于head部分,任意生成两个1到28间的索引值,使索引值区间内的基因片段逆序排列,对于tail部分,使其内的任意一位基因替换为{3,5,7,9,11,14}中不被包含在原来的tail内的数,如(head以1到7的序列为例):

五、适应度计算(fitness)利用动态规划的思想可以求解每个解对应的加工顺序的完工时间,令seq表示某染色体代表的加工顺序,dij,i=1,2…8, j=1,2,…,28表示第 个job在第 台machine上的加工时间,Tij,  i=1,2,…,8, j=1,2,…,25表示第i个machine完成seq中第j个job的时间,则有:

T8,25为最大完工时间,将最大完工时间的倒数作为染色体的适应度。

六、种群选择(selection)

采用精英保留法与轮盘赌结合的方式筛选种群,从每一代交叉变异后的种群中选出一定数量的适应度最高的个体直接进入下一代,接着采用轮盘赌的方式从未被选中的个体中选择,直到下一代种群规模达到预设值,适应度越高的个体被选中的几率越大。

七、进化(evolution)

进化过程如下:

八、求解

设定种群规模为80,交叉概率为0.8,变异概率0.01,保留精英解数目为20,进化500代,记录第一代中完工时间的最小值为546,最后一代中完工时间的最小值为473,缩短了13.4%,最优加工顺序为{21, 15, 6, 12, 17, 1, 19, 24, 5, 18, 2, 28, 23, 14, 13, 25, 3, 4, 26, 8, 27, 10, 16, 20, 22}

两种加工顺序的甘特图如下:

可以发现,优化后的甘特图排程明显更加紧密,空置时间较少。

python代码如下,水平有限大家多多交流哇:

from datetime import time
import pandas as pd
import numpy as np
import random
import heapq
import matplotlib.pyplot as plt

class GA_TSP(object):

    pop_size = 50    # 种群规模
    p_cr = 0.8       # 交换概率
    p_mu = 0.01      # 变异概率
    constraints=[3,5,7,9,11,14]    # 约束条件
    job_num=28                     # job数量
    machine_num=8                  # 机器数量
    elite_number=20                # 每一代中精英解的数量
    minimize_complete_time=[]      # 最小完工时间
    best_solve=[]                  # 最佳作业排序
    work_time = np.array(pd.read_csv('工作时间.csv', header=None, engine='python'))

    def __init__(self,popsize,p_cr,p_mu,iteration,elite_number):
        self.pop_size=popsize
        self.p_cr=p_cr
        self.p_mu=p_mu
        self.iteration=iteration
        self.elite_number=elite_number

    def initial(self):
        pop=[]

        for i in range(self.pop_size):
            gene1=np.arange(1,self.job_num+1)
            np.random.shuffle(gene1)
            gene1=gene1.tolist()
            gene2=random.sample(self.constraints,3)
            gene1.extend(gene2)
            pop.append(gene1)

        return np.array(pop)        #初始化种群

    def cross_over(self,parent1,parent2):
        child1=[]
        child2=[]

        if np.random.rand()>self.p_cr:
            return np.zeros(self.job_num+3),np.zeros(self.job_num+3)
        else:
            index1=np.random.randint(0,self.job_num)
            index2=np.random.randint(self.job_num,self.job_num+3)
            for i in range(index1,self.job_num):
                child1.append(parent2[i])
            for i in range(self.job_num):
                if parent1[i] not in child1:
                    child1.append(parent1[i])
            for i in range(self.job_num,self.job_num+3):
                child1.append(parent1[i])
            if parent2[index2] not in child1[-3:]:
                child1[index2]=parent2[index2]

            for i in range(index1,self.job_num):
                child2.append(parent1[i])
            for i in range(self.job_num):
                if parent2[i] not in child2:
                    child2.append(parent2[i])
            for i in range(self.job_num,self.job_num+3):
                child2.append(parent2[i])
            if parent1[index2] not in child2[-3:]:
                child2[index2]=parent1[index2]

            return np.array(child1),np.array(child2)    #交叉

    def mutate(self,gene):

        if np.random.rand()>self.p_mu:
            return gene
        else:
            index1=np.random.randint(0,self.job_num)
            index2=np.random.randint(index1,self.job_num)
            index3=np.random.randint(self.job_num,self.job_num+3)
            gene_slice=gene[index1:index2].copy()
            gene_slice_reverse=gene_slice[::-1]

            for i in range(len(gene_slice)):
                gene[index1+i]=gene_slice_reverse[i]
            constraints_rem=self.constraints.copy()

            for i in gene[-3:]:
                constraints_rem.remove(i)
            gene_insert=random.choice(constraints_rem)
            gene[index3]=gene_insert

            return gene                                #变异

    def fitness(self,pop):
        c_time=[]
        fitness_all=[]

        for i in range(pop.shape[0]):
            pop_cal=pop[i].copy().tolist()
            pop_cal_head=pop_cal[:self.job_num].copy()
            pop_cal_tail=pop_cal[-3:].copy()

            for j in pop_cal_tail:
                pop_cal_head.remove(j)
            ctime_dp=np.zeros((self.machine_num,self.job_num-3))

            for ii in range(self.job_num-3):
                for iii in range(ii+1):
                    ctime_dp[0][ii]=ctime_dp[0][ii]+self.work_time[pop_cal_head[iii]-1][0]
            for ii in range(1,self.machine_num):
                for iii in range(ii+1):
                    ctime_dp[ii][0]=ctime_dp[ii][0]+self.work_time[pop_cal_head[0]-1][iii]
            for ii in range(1,self.job_num-3):
                for iii in range(1,self.machine_num):
                    ctime_dp[iii][ii]=max(ctime_dp[iii-1][ii],ctime_dp[iii][ii-1])+\
                                      self.work_time[pop_cal_head[ii]-1][iii]

            c_time.append(ctime_dp[self.machine_num-1][self.job_num-4])
            fitness_all.append(1/ctime_dp[self.machine_num-1][self.job_num-4])
        index=c_time.index(min(c_time))
        best_solve_iter=pop[index].copy()

        return min(c_time),fitness_all,best_solve_iter      #动态规划求解最大完工时间,计算适应度

    def selection(self,pop,fitness):
        pop_after_select=[]
        pop_before_select=pop.copy().tolist()
        index1=list(map(fitness.index,heapq.nlargest(self.elite_number,fitness)))

        for i in index1:
            pop_after_select.append(pop_before_select[i])
        pop_before_select=[pop_before_select[i] for i in range(len(pop_before_select)) \
                           if i not in index1]
        fitness=[fitness[i] for i in range(len(fitness)) \
                           if i not in index1]
        probability=np.array(fitness)/np.array(fitness).sum()
        index2=np.random.choice(np.arange(len(fitness)),size=self.pop_size-self.elite_number,\
                                replace=False,p=probability)

        for i in index2:
            pop_after_select.append(pop_before_select[i])

        return np.array(pop_after_select)                  #筛选种群:精英保留法+轮盘赌

    def evolution(self):
        population=self.initial()

        for i in range(self.iteration):
            for ii in range(self.pop_size):
                iii=np.random.randint(0,self.pop_size-1)
                if ii != iii:
                    child1,child2=self.cross_over(population[ii],population[iii])
                    if child1[0] != 0:
                        mut_child1=self.mutate(child1)
                        mut_child2=self.mutate(child2)
                        population=np.vstack((population,mut_child1))
                        population=np.vstack((population,mut_child2))

            best_time_iter,fitness_iter,best_solve_iter=self.fitness(population)
            self.minimize_complete_time.append(best_time_iter)
            self.best_solve.append(best_solve_iter)
            population=self.selection(population,fitness_iter)

        return self.minimize_complete_time,self.best_solve   #进化

ga=GA_TSP(80,0.8,0.01,500,20)
solution_time,solution_schedule=ga.evolution()

worst_schedule=list(solution_schedule[0].copy())
worst_schedule_head=worst_schedule[:28]
worst_schedule_tail=worst_schedule[-3:]
for i in worst_schedule_tail:
    worst_schedule_head.remove(i)                           #第一代的排班方案

best_schedule=list(solution_schedule[-1].copy())
best_schedule_head=best_schedule[:28]
best_schedule_tail=best_schedule[-3:]
for i in best_schedule_tail:
    best_schedule_head.remove(i)                            #最后一代的排班方案


def gantt(n,m,seq,wt):

    t = np.zeros(n)
    for i in range(m):
        for j in range(n):
            if j == 0:
                t[j]=t[j]+wt[seq[j]-1][i]
                plt.barh(y=i+1,left=t[j]-wt[seq[j]-1][i],height=1,width=wt[seq[j]-1][i])
            else:
                t[j]=max(t[j],t[j-1])+wt[seq[j]-1][i]
                plt.barh(y=i+1,left=t[j]-wt[seq[j]-1][i],height=1,width=wt[seq[j]-1][i])
            if (wt[seq[j]-1][i] != 0):
                pass

    plt.plot([t[-1], t[-1]], [-0.5, m + 1], color=(0, 0, 0))
    x_tickss = [i for i in range(0, int(t[-1]), int((t[-1] / 4) // 10) * 10)]

    if (t[-1] - x_tickss[-1] < (int((t[-1] / 4) // 10) * 10) / 4):
        x_tickss.pop()
    x_tickss.append(t[-1])
    plt.title('n=%d,m=%d,need_time=%.3f' % (n, m, t[-1]))
    plt.xticks(x_tickss)
    plt.show()

    return (t)                                             #绘制甘特图

gantt(ga.job_num-3,ga.machine_num,worst_schedule_head,ga.work_time)
gantt(ga.job_num-3,ga.machine_num,best_schedule_head,ga.work_time)

 

Logo

华为开发者空间,是为全球开发者打造的专属开发空间,汇聚了华为优质开发资源及工具,致力于让每一位开发者拥有一台云主机,基于华为根生态开发、创新。

更多推荐