以下为《作业车间调度问题算法分析与设计大作业》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

《算法设计与分析》综合设计与实现

作业车间调度问题

学生姓名：佟某某

学生学号：***27

学生班级：软件18-4

学生专业：软件工程

指导老师：马某某

一、作业车间调度问题描述

作业车间调度问题（Job Shop Scheduling, JSP）是最经典的几个NP-hard问题之一。其应用领域极其广泛，涉及航母调度，机场飞机调度，XX码头货船调度，汽车加工流水线等。

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

作业车间调度需要考虑如下约束:

Cons1：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后才能开始加工；

Cons2：某一时刻1台机器只能加工1个作业；

Cons3：每个作业只能在1台机器上加工1次；

Cons4：各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。

作业车间调度问题的数学模型

在本课程的综合设计与实现环节中，我们将作业车间调度问题的优化目标设为最大完工时间最小：令(i,j)表示作业i的第j个工序。Sij和Tij分别表示(i,j)的加工起始时刻和加工时间。Zijk表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器上加工，Zijk=1；否则，Zijk=0。Ck为第k台机器的完工时间，则问题的数学模型如下：

（1）

（2）

（3）

（4）

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

三、问题实例

下面给出作业车间调度问题的一个实例，其中每个工序上标注有一对数值（m,p），其中，m表示当前工序必须在第m台机器上进行加工，p表示第m台机器加工当前工序所需要的加工时间。（注：机器和作业的编号从0开始）

jop0=[(0,3),(1,2),(2,2)]

jop1=[(0,2),(2,1),(1,4)]

jop2=[(1,4),(2,3)]

在这个例子中，作业jop0有3道工序：它的第1道工序上标注有(0,3)，其表示第1道工序必须在第0台机器上进行加工，且需要3个单位的加工时间；它的第2道工序上标注有(1,2)，其表示第2道工序必须在第1台机器上进行加工，且需要2个单位的加工时间；余下的同理。总的来说，这个实例中共有8道工序。

该问题的一个可行解是L=8道工序开始时间的一个排列，且满足问题的约束。下图给出了一个可行解（注：该解不是最优解）的示例：

在上图中，我们能看到每个作业的工序按照问题给定的顺序进行了加工，且相互之间没有时间区间重叠。这个可行解的结果是12，即三个作业均被加工完成的时间。

四、算法设计思想

遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的［7］。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程［8］。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。

基本思路：

1）首先确定问题的求解空间；

2）其次将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；

3）计算当前群体中每个个体的适应度函数值。运用选择、交叉、变异算子产生新一代群体；

4）对新一代群体中的个体进行评价，若找到满足问题的最优解，结束；否则，转步骤3。

遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。

通常，种群太小则不能提供足够的采样点，以致算法性能很差;种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。

选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。

交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉;概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。

变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。

遗传操作对收敛性的影响，可利用马尔可夫链对遗传算法进行分析，从而论证了遗传算法在收敛性方面的一些重要性质，有力地支持了遗传算法的理论基础。由马尔可夫链推导出来的一些结论:基本遗传算法收敛于最优解的概率为1,使用保留最优个体策略的遗传算法收敛于最优解的概率为1。

隐含并行性定理:遗传算法所处理的模式总数与其群体规模N的立方成正比，即: m=O(N3)

由该定理可知，虽然表面上每代处理的个体数目都是一定的，但是由于每个个体都隐含着多种不同的模式，所以每次参与遗传算子操作的个体却不仅仅是两个。从总体上来说，每代之间所处理的个体要远大于其表面的数目，这就是遗传算法独特的隐含并行性。由隐含并行性定理可知，虽然表面上每代仅对N个个体处理操作，而事实上处理了O(N3)个模式，且无需额外存储。隐含并行性为遗传算法的高效性提供了理论依据。

五、伪代码

//初始化

for i←0 to population number

do chromosome←[-1, ... -1]

forj←0 to N

for k←0 to M

index←ranndom (chromosome size)

if第j个工件在第k台机器上有待加工工序

then chromosome [index] = j

过滤掉chromosome的—1

gene←Gene对象

gene.chromosome←chromosome

gene. fitness←chromosome 的适应度

将gene加入到种群集合中

//适应度

fulfillTime ← 0

for i = 0 to chromosomeSize

do [wId] ←gene.chromosome [i]

pId ← processIds [wId] + +

mId ← machine [wId] [pId]

t← time[wId] [pId]

if pId=0

then startTime [wId] [pId] ← machineWorkTime [mId]

else startTime [wId] [pId] ←max (endTime [wId][pId - 1], machineWorkTime [mId])

machineWorkTime[mId]← startTime [wId] [pId] + +

endTime [wId][pId] ←machineWorkTime [mId]

fulfillTime←max(fulfillTime,machineWorkTime [mId])

fitness 1 / fulfillTime

返回fitness

//选择

indexList←随机生成n 个索引

bestGene←Gene对象

for i←0 to populationNumber

do if indexList包含i

then if bestGene. fitness ←geneSet [i]. fitness

then bestGene←geneSet [i]

返回bestGene

//交叉

start←random (chromosomeSize )

end←random,(chromosomeSize)

childProto←g1 .chromosome [star...end ]

temp←g2 .chromosome.length

for i←0 to childProto.length

do for j←0 to temp

do if childProto[i] = temp [j]

then删除temp的第i项

break .child←Gene对象

child.chromosome←将 temp [0...start]，childProto, temp [star...]拼接成一一个数组child.fitness←计算 child的适应度

交换g1, g2以此产生第二个child2

返回child, child2

//变异

for i←0 to n

do p1 ←random (chromosomeSize )

p2 ← random(chromosomeSize )

交换g.chromosome [p1], g.chromosome [p2]的值

六、程序代码及运行结果

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 Gen 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 itness;

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];

}

七、总结

通过遗传算法解决作业车间调度，典型NP难问题，了解了遗传算法的基本步骤，编码，初始化种群，适应度函数，选择，交叉，突变等。遗传算法对求解作业车间调度问题具有较好的效果，对作业车间调度和遗传算法都有了更好的了解，但平时练习时间较少，不是很熟练，今后要更加勤于练习。

[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《作业车间调度问题算法分析与设计大作业》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。