研究改进遗传算法的车间调度问题
来源：UC论文网2015-11-30 20:30
摘要：
导读:：作业车间调度是一类求解困难的组合优化问题，本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性，最终使算法能够趋于全局最优。在次基础上
导读:：作业车间调度是一类求解困难的组合优化问题，本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性，最终使算法能够趋于全局最优。在次基础上，将遗传算法和模拟退火算法相结合，提出了一种基于遗传和模拟退火的混合算法，并用实例对该算法进行了仿真研究。结果表明，该算法有教好的收敛精度，是可行的，与传统的算法相比较，有明显的优越性。
论文关键词：遗传算法，车间调度，模拟退火
1. 引言
作业车间调度（Job Shop SchedulingProblem，JSSP）通常指车间生产过程的作业计划，解决如何合理地分配车间有限的资源，使资源利用率最高，成本最小等问题[1]。随着制造型企业之间竞争的加剧，调度决策水平的高低己经成为现代企业决定生产经营过程能否实现降低成本，对市场实现快速响应，从而实现稳定高效地运转的决定性因素之一。为提高调度水平，新的生产调度策略和优化算法不断被提出并被研究，以提高资源的利用率及操作管理的水平，生产出更具有竞争性的产品。因车间调度优化问题在提高生产效率，降低生产成本等方面至关重要，所以车间的调度优化工作成为现代企业制造中的重要研究课题之一。
2. JSSP问题的数学描述
JSSP问题可以描述为如下：
1）一个工件不能两次被同一机器加工；
2）不同工件的加工工序之间没有先后约束；
3）工序一旦进行不能中断；
4）每台机器一次只能加工一个工件；
5）下达时间和交货期都不是确定的。
问题的数学描述为：
（1）
：机器
先于机器
加工工件
，
，
（2）
工件先于工件
在机床上加工
模拟退火，
，
（3）
式中
，
， （4）
其中，式(1)表示目标函数，式(2)(3)(4)表示工艺约束条件决定的各工件的各操作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中，符号
和
分别为工件在机器上的完成时间和加工时间。
3．用改进遗传算法(MGA)求解
3.1编码方式
如何将所研究问题的解转换为由编码形式表达的染色体是遗传算法的关键问题[2]。对JSSP问题，遗传算法的编码常见的有以下几种：基于工序(或操作)的编码、基于工件的编码、基于先后表的编码、基于工件对关系的编码、基于优先规则的编码、基于机器的编码、基于完成时间的编码、随机键编码、基于析取图的编码[3]。这些编码方法都存在这样或者那样的不足，鉴于以上车间调度问题编码方法所存在的问题，提出一个既能保证后代的合法性，又能表征全部解空间，解码又相对简单的编码方法很有必要。本文考虑一个基于工序(或操作)的编码[4,5]方法用来保证搜索空间是一个完整的解空间，并且任何操作者的所有交换可对应于合适调度，对于每个基因对应一道工序，代表该工序在进行调度操作时的处理优先级，对于n个工件m台机器的调度问题，一个染色体由
个基因组成。
考虑3个工件和2台机器问题的机器加工次序矩阵：
以及加工的时间矩阵：
假设一个任意基于操作的解分别为s = (1，3，2，2，1，3)， 其中1，2和3分别代表工件1，2和范例。通过一个半活动解码过程[4,5]，工件的加工次序对于机器1对应3-2-1，对于机器2对应1-2-3。它们对应的makespan(工件完工时间)为7的甘特图如图１所示：
Figure 1. Halfactivities scheduling correspond to tmakespan
图1 半活动调度对应的makespan
我们认为，活动调度编码是半自主调度编码的一个子集，因此，最优调度方案必须是一个活动调度编码对应的工件完工时间[4]。活动调度编码的应用可以在下一个操作之前检查可能的空白的间隔时间所在最后位置模拟退火，并且在最后操作之前填补前一个空白间隔时间直到最后一个操作转化为半活动调度，导致makespan的长度可以变得更短。 因此，Gantt图(图1)被改变为如下图2所示，同时，对应的makespan 为6 (最优值)。
Figure 2. Activitiesscheduling correspond to tmakespan
图2 活动码调度对应的makespan
3.2解码算法
染色体只包含数字编码。在解码时首先要把基因与工序对应起来，即把优先级赋给对应的工序。
设：
——包含t个已调度工序的部分调度；
——阶段t可调度工序的集合对应给定的。
解码步骤如下：
步骤1：令t=0，开始
为空的部分调度。初始的包括无紧前工序的所有工序。
步骤2：比较中所有工序的调度优先级，把具有最大优先级的工序(假设为
，其上道工序的结束时刻为
)尽可能早的加入到中，即从
时刻开始对该工序所对应机器上各加工空闲依次判断能否将此工件插入加工。若能，则在空闲中插入加工，并修改该机器上的加工队列；否则，把该工序加入到该机器加工队列的末尾，构造一个新的部分调度
。
论文关键词：遗传算法，车间调度，模拟退火
1. 引言
作业车间调度（Job Shop SchedulingProblem，JSSP）通常指车间生产过程的作业计划，解决如何合理地分配车间有限的资源，使资源利用率最高，成本最小等问题[1]。随着制造型企业之间竞争的加剧，调度决策水平的高低己经成为现代企业决定生产经营过程能否实现降低成本，对市场实现快速响应，从而实现稳定高效地运转的决定性因素之一。为提高调度水平，新的生产调度策略和优化算法不断被提出并被研究，以提高资源的利用率及操作管理的水平，生产出更具有竞争性的产品。因车间调度优化问题在提高生产效率，降低生产成本等方面至关重要，所以车间的调度优化工作成为现代企业制造中的重要研究课题之一。
2. JSSP问题的数学描述
JSSP问题可以描述为如下：
1）一个工件不能两次被同一机器加工；
2）不同工件的加工工序之间没有先后约束；
3）工序一旦进行不能中断；
4）每台机器一次只能加工一个工件；
5）下达时间和交货期都不是确定的。
问题的数学描述为：
（1） ：机器先于机器加工工件，， （2）工件
先于工件在机床上加工模拟退火，， （3）式中
，， （4）其中，式(1)表示目标函数，式(2)(3)(4)表示工艺约束条件决定的各工件的各操作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中，符号
和分别为工件在机器上的完成时间和加工时间。3．用改进遗传算法(MGA)求解
3.1编码方式
如何将所研究问题的解转换为由编码形式表达的染色体是遗传算法的关键问题[2]。对JSSP问题，遗传算法的编码常见的有以下几种：基于工序(或操作)的编码、基于工件的编码、基于先后表的编码、基于工件对关系的编码、基于优先规则的编码、基于机器的编码、基于完成时间的编码、随机键编码、基于析取图的编码[3]。这些编码方法都存在这样或者那样的不足，鉴于以上车间调度问题编码方法所存在的问题，提出一个既能保证后代的合法性，又能表征全部解空间，解码又相对简单的编码方法很有必要。本文考虑一个基于工序(或操作)的编码[4,5]方法用来保证搜索空间是一个完整的解空间，并且任何操作者的所有交换可对应于合适调度，对于每个基因对应一道工序，代表该工序在进行调度操作时的处理优先级，对于n个工件m台机器的调度问题，一个染色体由
个基因组成。考虑3个工件和2台机器问题的机器加工次序矩阵：
以及加工的时间矩阵：
假设一个任意基于操作的解分别为s = (1，3，2，2，1，3)， 其中1，2和3分别代表工件1，2和范例。通过一个半活动解码过程[4,5]，工件的加工次序对于机器1对应3-2-1，对于机器2对应1-2-3。它们对应的makespan(工件完工时间)为7的甘特图如图１所示：
Figure 1. Halfactivities scheduling correspond to tmakespan
图1 半活动调度对应的makespan
我们认为，活动调度编码是半自主调度编码的一个子集，因此，最优调度方案必须是一个活动调度编码对应的工件完工时间[4]。活动调度编码的应用可以在下一个操作之前检查可能的空白的间隔时间所在最后位置模拟退火，并且在最后操作之前填补前一个空白间隔时间直到最后一个操作转化为半活动调度，导致makespan的长度可以变得更短。 因此，Gantt图(图1)被改变为如下图2所示，同时，对应的makespan 为6 (最优值)。
Figure 2. Activitiesscheduling correspond to tmakespan
图2 活动码调度对应的makespan
3.2解码算法
染色体只包含数字编码。在解码时首先要把基因与工序对应起来，即把优先级赋给对应的工序。
设：
——包含t个已调度工序的部分调度；——阶段t可调度工序的集合对应给定的。解码步骤如下：
步骤1：令t=0，开始
为空的部分调度。初始的包括无紧前工序的所有工序。步骤2：比较
中所有工序的调度优先级，把具有最大优先级的工序(假设为，其上道工序的结束时刻为)尽可能早的加入到中，即从时刻开始对该工序所对应机器上各加工空闲依次判断能否将此工件插入加工。若能，则在空闲中插入加工，并修改该机器上的加工队列；否则，把该工序加入到该机器加工队列的末尾，构造一个新的部分调度。
