基于人工神经网络的作业车间调度算法
作者：曹琛祺　金伟祖
来源：《电脑知识与技术》2016年第30期
        摘要：提出了一种解决作业车间调度问题的算法。使用禁忌搜索算法作为生成训练集的工具，通过对调度序列进行处理，将调度问题转化为一个分类问题，从而使用人工神经网络构建分类器。对于新的调度实例，利用训练得到的分类器得出优先级，再利用优先级得到调度序列。并在最后对调度器的实际效果使用测试实例进行了验证。
        关键词：作业车间；调度算法；禁忌搜索；人工神经网络
        中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2016）30-0204-04
        Job-shop Scheduling using Artificial Neural Network
        CAO Chen-qi，JIN Wei-zu
        （Tongji University， School of Software Engineering， Shanghai 201804， China）
        Abstract：Present an algorithm to solve the job-shop scheduling problem. The tabu search algorithm is used as the tool to generate the training set. The scheduling problem is transformed into a classification problem by transforming the scheduling sequence. The artificial neural network is used to construct the classifier. For the new scheduling example， the trained classifier is used to derive the priority， and then the priority is used to obtain the scheduling sequence. Finally， the test results are verified by the test cases.
        Key words： job-shop； scheduling algorithm； tabu search； artificial neural network
        作业车间调度问题（Job-shop scheduling Problem，JSP）[1]，是一个NP 难问题[2]。在作业车间调度中，多个并行执行的任务需要在多个机器中调度执行，目标是得到一个可行的最优调度使得最大完工时间（makespan）最短。
        作业车间调度问题是一个很有名的优化问题，已有许多不同算法用于解 决这一问题。如禁忌搜索（Tabu Search）算法 [3]，模拟退火（Simulated Annealing）算法 [4， 5]，神经网络（Neural Network）算法 [6]，遗传算法（Genetic Algorithm）[7]，粒子优化（Particl
e Swarm Optimization）算 法 [8]，蚁优化（Ant Colony Optimization）算法 [9] 等。
        人工智能的目标是构造一种智能机械，使之能够学习、模仿和展现近乎 于人的智慧。人工神经网络（Artificial Neural Network）[10] 便是其中的一种，其作为机器学习的一种重要的工具已被广泛使用。一个神经网络由多层的节点组成，节点间用加权边相连。连接的权值代表了连接的强度，其符号则代表了激发或抑制作用。神经网络将学习的知识以网络内部结构、激活函数、权值与偏差值的形式记忆下来。
        本文将使用人工神经网络来解决作业车间调度问题。首先，设计一种人工神经网络，定义输入与输出，以及内部结构、激活函数等参数。其次，使用禁忌搜索算法作为一种工具，提供训练实例，从而进行训练。最后，利用训练完成的神经网络，便可对同种的车间调度问题实例进行快速调度。
        1 问题描述
        1.1 定义
        作业车间调度问题（JSP）的定义如下：
        有一个作业的集合{Ji}1≤i≤n，其中包括n个作业，另有一个机器的集合{Mj}1≤j≤m，其中包括m个机器。这n个作业将会在这m个机器上执行。将一个作业Ji在某个机器Mj上的运行过程定义为工序Oij。在JSP中，Oij对于给定的Ji，它们的顺序是固定的，即作业必须按照给定的顺序依次在相应的机器上执行。当一道工序Oij在机器Mj上执行时，在执行时间pij内，工序是不能够被打断的，因此JSP属于非抢占式调度问题。
        在这些定义的基础上一个对于JSP的调度可以定义为一个完工时间的集合{cij}1≤i≤n，1≤j≤m，集合中的元素满足上文中的所有约束。完成所有工序所需的时间称定义为最大完工时间L，即集合{cij}中的最大值。
        作业车间调度问题的目标是得到一个有效的调度，使得最L最小。
        1.2 JSP的图表示法
        对于JSP的调度可以化为一个析取图（disjunctive graph）[11]，如图 1中所示，每个节点代表一个作业，节点0代表所有工序的开始，节点*代表所有工序的结束。每条合取边代表同一工作中工序间的先后约束，每条析取边则连接同一机器上的不同工序。边的权值取决于
边所连接的工序所需的时间。对于JSP的一个调度，可以视作对于析取边连接的工序的先后顺序的确立。而该调度的完工时间则是析取图的从起始点到终点最大路径值。
        2 算法描述
        2.1 人工神经网络的设计
        2.1.1 输入属性的选取与转化
        考虑到作业车间调度问题的特点，参考[13]，工序的以下属性被提取出来作为神经网络输入：工序号、处理时间、剩余时间、机器负载。同时，每个属性的具体值转化为类别值：
        工序号：每个工序在所属工作内的序号，由于工序在工作内的顺序是一定的，所以这个序号也是一定的。工序号按照第一、前半、后半、最后被分为4类。
        处理时间：每个工序在机器上运行所需要的时间。按照运行时间的范围均匀分为低、中、高3类。
        剩余时间：假设所属工作剩余的工序都不会被打断的情况下，所有剩余的工序运行结束
所需的时间。即该工作未执行的（不包括当前工序的）所有工序的运行时间的和。按照剩余时间的范围均匀分为低、中、高3类。
        机器负载：机器上所有预定执行工序的处理时间的总和。按照机器负载的范围均匀分为低和高2类。
        2.1.2 目标输出的选取与转化
        假设一共有N道工序，那么工序在调度序列中的序号范围便是[1；N]。直接将此序号作为输出会导致输出范围过于庞大，且对于不同问题也会导致输出的范围不同。另外对于作业车间调度问题来说，最优调度并不唯一，这意味着对于一个工序来说，它的序号并不确定。直接使用序号作为输出会大大增加学习的难度。因此，可将序号的范围均匀分为多个类别，将类别作为输出可以很好地解决以上的问题。在本文中，将范围[1；N]均匀的分为6类，序号的值越小，优先级的值也越小，对应优先级则越高，分别为优先级0，1，2，3，4，5。
        2.1.3 神经网络的结构
        在本文中使用的人工神经网络的类型是多层感知器（Multilayer Perceptron，MLPjsp定义）[14]。
MLP的结构如图 2所示，由多层的节点组成，每层节点与下一层的所有节点相连，每个连接对应一个权值。输入层对应着作为分类依据输入的工序属性。由于输入包括4个属性，因此输入层有4个节点。隐层连接着输入与输出层，2隐层分别有4个和3个节点。输出层设置1个节点代表序列的优先级。
        2.1.4 实现细节
        使用交叉验证可以有效地防止过度训练（over training）的发生。使用交叉验证时，将训练数据分为训练集（training set），验证集（validation set）和测试集（test set）。在训练的过程中，只使用训练集作为神经网络的输入，同时使用无关的验证集来验证网络的正确性。如果训练的网络在训练集中连续多个世代（epoch）的代价都没有降低，则停止训练。这样，得到的模型变不会是对于特定训练集特化的模型，而是可以用来判断所有输入的泛用模型。禁忌搜索算法每次的输出的调度结果是不同的，因此通过多次运行可以得到足够多的训练集，训练集、验证集和测试集分别分配70%、15%和15%的数据。
        在人工神经网络中，训练算法用于判断何时停止训练可以使输入与输出的关系更好的记忆在神经网络中。本文选用误差反向传播（back propagation）算法[15]作为训练算法。该算
法的思想是通过输出与目标的误差得到隐层到输出层以及输入层到隐层新的权值，从而更新网络。通过不断更新来使代价函数的返回值变得最小。学习率决定了神经网络在调整权值时的幅度，使用动量记录上个世代的调整幅度，可以进一步加快训练的速度。
        2.2 人工神经网络的训练
        在定义了以上的神经网络后，面对实际的作业车间调度问题，还需要为其提供训练集，训练后便可用来解决今后的作业车间问题的实例。因此本文采用的禁忌搜索作为提供训练集的工具。
        2.2.1 禁忌搜索算法
        禁忌搜索算法[12]是一种局部搜索算法。局部搜索算法的搜索过程从一个可能的解决方案开始，得到其邻居集合，并从中搜索得到一个更好的解决方案，并迭代地执行这一步骤，直至达到停止的条件，搜索完成。局部搜索算法的一个缺点是很容易停留在局部最优解而无法搜索到全局最优解。为了解决这一问题，禁忌搜索引入了禁忌列表（Tabu List）这一结构。禁忌列表中存储了最近迭代中的局部最优解，通过将这些解设为禁忌的方式，避免搜索再次访问局部最优解。
        2.2.2 停止条件
        禁忌搜索在满足以下任意停止条件后便结束搜索，返回目前搜索到的最优解。
        · 总迭代次数达到阈值
        · 结果未改进的迭代次数达到阈值
        · 到最优解
        在本文中禁忌搜索只是作为生成最优解的工具，因此由于超过阈值而没有得到最优解的情况只要简单忽略此次结果便可。
        2.2.3 邻居集合
        从2.2节中可知，车间作业调度可化为一个析取图，一个调度的完工时间取决于其中的最长路径值。由于不在最长路径上的工序的顺序并不影响完工时间，因此对于一个给定的解决方案，可以通过改变其最长路径中工序的前后顺序来得到邻居集合。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。