未来智库 > 神经网络论文 > 基于人工神经网络的作业车间调度算法

基于人工神经网络的作业车间调度算法

发布时间:2018-07-21 01:06:41 文章来源:未来智库    
    关键词:作业车间;调度算法;禁忌搜索;人工神经网络
    中图分类号: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
    作�I车间调度问题(Job-shop scheduling Problem,JSP)[1],是一个NP 难问题[2]。在作业车间调度中,多个并行执行的任务需要在多个机器中调度执行,目标是得到一个可行的最优调度使得最大完工时间(makespan)最短。
    作业车间调度问题是一个很有名的优化问题,已有许多不同算法用于解 决这一问题。如禁忌搜索(Tabu Search)算法 [3],模拟退火(Simulated Annealing)算法 [4, 5],神经网络(Neural Network)算法 [6],遗传算法(Genetic Algorithm)[7],粒子群优化(Particle 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,MLP)[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节中可知,车间作业调度可化为一个析取图,一个调度的完工时间取决于其中的最长路径值。由于不在最长路径上的工序的顺序并不影响完工时间,因此对于一个给定的解决方案,可以通过改变其最长路径中工序的前后顺序来得到邻居集合。
    2.2.4 数据的转化
    从禁忌搜索算法中得到是一个工序调度序列,并不能直接作为神经网络的输入使用。神经网络最后将对输入的每个工序进行分类,因此需要计算出工序的4个属性值,同时将每个工序的在序列中的位置转化为优先级并作为目标输出,这样调度序列便转化为分类问题。
    2.3 人工神经网络的运行
    在得到了训练集并进行训练后,便可将新的作业车间调度问题实例转化为属性输入集,并将其输入训练完的神经网络中,从而分类得到相应的优先级。将工序先按照所要运行的机器分配至对应机器,并按照工作内的工序号和优先级升序排列,这样便能得到一个可行的调度,将此作为最终的调度结果。
    2.4 算法总结
    本文的目标是利用人工神经网络来实现作业车间问题的调度。因此,算法主要分训练与运行2大步骤:
    1) 训练:
    a) 获得最优调度
    b) 将最优调度转换为可供分类的输入数据集和分类输出数据集
    c) 将输入输出集分为训练集、验证集合测试集
    d) 使用数据集训练神经网络、得到调度器
         2) �\行
    a) 使用调度器调度之后所有的问题实例,得到对应的调度结果
    对于一个作业车间调度问题,首先利用禁忌搜索算法提供训练集,训练神经网络。之后,对于同一类型的问题便可以直接利用神经网络分类工序,从而得到调度。这样的好处是利用神经网络可以大大节省调度所需的时间,而且作为花费最多时间的训练步骤,只需要运行一次。下面的实验证明了本文的观点。
    3)实验
    实验均在Think Server RD430上完成,操作系统Red Hat Enterprise Linux Server release 6.3 (Santiago),CPU型号Intel(R) Xeon(R) CPU E5-2420,1.90GHz,个数2,内存16G。
    2.5 训练的结果
    对于转化后的作业车间调度问题的训练结果可以从表1中的混淆矩阵(confusion table)中看出,此表将Fisher和Thompson(1963)设计的ft06例子作为输入,ft06中有6个工作,6个机器。混淆矩阵显示了神经网络实际值与目标值的分布情况,对角线上的数据显示了正确分类的情况,底部的正确率反映了每个优先级各自的正确率以及总体的正确率。
    有两个主要的错误的来源。一是由于不唯一的最优解造成的。不同的最优解导致同一类型的工序可以被分为不同的优先级类别,将导致工序被错误的分类。另一个可能的原因是在将输入工序转化为分类属性时损失了部分的信息,从而导致分类不完善。
    2.6 调度的结果
    表 2与表 3中的结果,显示了使用禁忌算法和训练完成的人工神经网的比较。从表中可知,虽然使用禁忌搜索算法可以得到很好的结果,但是对于每个新的实例需要更多的运行时间。对更加复杂的实例,禁忌算法需要过多的时间。相比之下,神经网络可以在几乎一定的时间内给出一个有一定质量的调度,主要的时间花费是只有一次的训练过程。
    3 总结与展望
    本文使用禁忌算法生成训练集,通过训练一个人工神经网络的方法,对于作业车间调度算法给出了一个可行的调度器。从而使用一种人工智能的方式给出了一个NP难问题的解决方案。在保证调度结果质量的同时保证了较短的运行时间。当然仍有可以改进的空间,如可以通过对于网络的进一步改进,提高训练的速度与正确性,同时提升结果的调度质量。
    参考文献:
    [1]Bazewicz J, Al E. Scheduling Computer and Manufacturing Processes[J]. Journal of the Operational Research Society, 1997, 48(6):659-659.
    [2]A. S. Jain, S. Meeran. Job-Shop Scheduling Using Neural Networks[J]. International Journal of Production Research, 1998, 36(5):1249-1272.
    [3]Dauzere-Peres S, Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search[J]. Annals of Operations Research, 1997, 70(1):281-306.
    [4]K. Steinh?fel, Albrecht A, C.K. Wong. Two simulated annealing-based heuristics for the job shop scheduling problem[J]. European Journal of Operational Research, 1999, 118(3):524-548.
    [5]Matsuo H, Suh C J, Sullivan R S. A Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem[J]. 1988.
    [6]Geneste L, Garbot B. Implicit versus explicit knowledge representation in a job-shop scheduling decision support system[J]. International Journal of Expert Systems, 1997, 10(1):37-52.
    [7]Bierwirth C, Mattfeld D C. Production scheduling and rescheduling with genetic algorithms[J]. Evolutionary Computation, 1999, 7(1):1-17.
    [8]Lian Z, Gu X, Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Chaos Solitons & Fractals, 2006, 183(35):851-861.
    [9]Tahar D N, Yalaoui F, Amodeo L, et al. An ant colony system minimizing total tardiness for hybrid job shop scheduling problem with sequence dependent setup times and release dates[C] 2005.
    [10]Zurada B J M. Introduction to Aitifcial Neural Systems[J]. 2012.
    [11] Jacek Blazewicz, Erwin Pesch, Malgorzata Sterna. The disjunctive graph machine representation of the job shop scheduling problem[J]. European Journal of Operational Research, 2000, 127(2):317-331.
    [12]Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer Operations Research, 1986, 13(5):533-549.
    [13]Weckman G R, Ganduri C V, Koonce D A. A neural network job-shop scheduler[J]. Journal of Intelligent Manufacturing, 2008,19(2):191-201.
    [14]Rosenblatt F. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms[J]. Archives of General Psychiatry, 1962(3):218-219.
    [15]Rumelhart D E, Hinton G E, Williams R J. Learning representations by back-propagating errors[M]. Neurocomputing: foundations of research. MIT Press,1986:533-536.
转载请注明来源。原文地址:https://www.7428.cn/page/2018/0721/23161/
 与本篇相关的热门内容: