车间生产调度岗位职责（精选5篇）
车间生产调度岗位职责 篇1
编号11-03
第一条：根据生产作业计划编制计划下达各班组。
第二条：了解图纸、工艺、原材料和毛坯落实情况，按照先急
后缓的原则，做好各项准备工作
第三条：深入班组，了解各工序进度，督促各班组按计划生产，做好工序衔接。
第四条：抓好外协，组织好产品外协件的购进工作。
第五条：负责生产过程中各项规章制度的监督执行职责，并对
相关人员实行考核。
第六条：负责本部安全文明生产，确保生产设备的完好。
第七条：负责本部发货，并及时提供发货资金计划。
车间生产调度岗位职责 篇2
过去,企业的设计和车间生产部门信息没有集成,基本上处于信息化的初级阶段,企业调度仅仅凭借调度员的经验,调度难度大且任务繁重,而工艺规划与车间生产调度计划的分离等都影响了企业的整体工作效率。作为企业信息化建设的两个重要内容,制造过程管理之间的信息交流与共享和车间生产调度系统的研究对于提高企业CIMS的整体水平至关重要[1]。
1制造过程管理的信息集成研究
1.1 调度工艺数据库的建立
工艺数据库存储了工艺设计所要求的全部工艺数据和算法规则。采用关系模型建立工艺数据库,能系统地对工艺数据进行管理和维护,减轻了工艺设计人员繁重、重复的劳动,缩短了生产准备周期,减少了工艺设计过程中的费用,提高了对市场应变的响应速度和竞争力,实现了企业内部的工艺信息共享[2]。
本系统采用Object-Relation图建立面向对象的数据概念模型,如图1所示。调度工艺数据库存储了生产调度过程中的动态调度信息,包括设备的动态信息和调度任务单的动态信息,管理员可以很方便地对工件的加工工艺及其先后顺序进行调度,提高了设备的利用率并缩短了加工时间。
1.2 信息集成的实现
本文主要研究江西省科技厅攻关项目“产品开发与制造过程管理集成研究”,在整个系统的开发过程中都采用了面向对象技术,提高了系统的开发效率并减轻了工作量,而且使系统有很好的稳定性和重用性。系统的开发环境采用三层模式的系统结构,开发工具采用Visual Studio.NET 2008,开发语言是C#,数据库采用SQL Server 2005。
图2所示的界面可以查询到所有零件的加工工艺信息,此外,系统还能对产品信息、零件信息、工艺信息、工步信息、设备信息、刀夹具信息等进行增删改操作,使管理员对企业的所有加工信息一目了然。
2车间生产调度研究
本文的调度系统主要针对加工零件的工艺规划信息进行调度,即对零件的工序信息、设备信息以及加工时间进行调度。通过制定调度任务单,查找出零件相应的工艺信息,输入算法参数值执行调度[3]。
2.1 调度算法目标函数
本系统采用多目标调度函数,其调度目标函数包括制造时间间隔、设备负荷均衡等[4,5]。
制造时间间隔:
undefined。 (1)
其中:Oij为第i个工件在第j台机床上的等待时间;m为工件个数;n为机床台数。
设备负荷均衡:
S2=W1+W2 。 (2)
其中:W1为机床负荷与平均机床负荷差之和;W2为相邻机床负荷差之和。
总的延误时间:
undefined。 (3)
其中:Pi为第i个工件的延误时间。
设备空闲时间:
undefined。 (4)
其中:Qj为第j台机床的空闲时间。
最大延误时间
undefined。 (5)
通过设置几个目标函数的权重得出调度的整体目标函数:
undefined。 (6)
其中:wk为各目标函数的权重值(wk=0,0.1,0.2,…,1.0);Sk为各调度目标函数(k=1,2,…,5)。
2.2 调度系统的实现
本生产调度系统主要包括4个模块:调度任务单制定与维护模块、离线调度模块、实时运行模块及结果输出模块。
(1)调度任务单制定与维护模块用于制定需要调度的工件信息及其工艺信息。工件信息包括工件的数量、调度的时间、完工时间;工艺信息包括工序号、工序名称、设备、加工时间等,并能对这些信息进行维护,即能进行添加、删除、修改等工作。
(2)离线调度模块的作用是根据调度任务单中制定的调度任务计划,通过调度算法,输入算法所需要的一些参数值来进行离线的调度。
(3)实时运行模块可以检测到各台加工设备的实时运行状态,包括设备的空闲、启动、忙、等待。
(4)由结果输出模块可以对调度结果进行查看,可以方便地观看到各工件的加工顺序以及设备的使用效率。如果感觉不是理想的调度顺序,可以通过改变调度算法的目标函数来改变加工的先后顺序。
图3为调度结果界面,它显示的是7台不同的机床加工7个不同的工件,每个工件的加工工艺在几台机床上加工完成所产生的调度结果。在执行调度时,调度运算所涉及的调度目标函数是制造时间间隔和设备负荷均衡,其权重均为0.5,其他的都为0。
3结束语
工艺设计和车间生产调度直接影响着资源的利用率并关系到整个生产过程的生产效率。本文将产品工艺设计信息与制造管理信息贯通集成,实现了信息共享集成和互动,并对产品的工艺信息实现生产调度,因此本项目具有很强的实际工程应用价值。
参考文献
[1]韩云彪.车间层信息集成系统开发[J].机械管理开发,2010,25(2):198-200.
[2]郝博,李俊峰.集成制造环境下C/S模式工艺数据库的设计[J].兵工自动化,2005,24(4):38-40.
[3]Gozzi A,Paolucci M.AMulti-agent approach to support dy-namic scheduling decisions[G]∥Proc of ISCC2002.[s.l.]:[s.n.],2002:983-989.
[4]田颖,江平宇,周光辉,等.基于遗传算法的工艺规划与调度集成方法[J].西安交通大学学报,2006,40(9):1041-1044.
车间生产调度岗位职责 篇3
关键词：不确定环境；再制造；加工车间；调度优化
中图分类号：TM391.9 文献标识码：A 文章编号：1006-8937（2016）27-0107-02
再制造加工作为现代工业领域发展的一种趋势，它是实现循环生产的有效途径。依据当前工业领域发展现状来看，本文结合现有的制造加工经验，技术人员在对其加工时间进行描述时采用的是模糊随机变量，这一变量是和再制造废旧件特性相一致的，并由此进一步强化了模糊随机机会约束规划的基础性作用，在此基础上建立了具体的调度模型，并采取了一种具有混合性质的智能算法，以促进再制造加工车间生产调度的优化和完善。
1 再制造加工车间的调度问题模型分析
对于调度问题模型的分析，需要先对模糊随机变量有所了解，在本文所分析的不确定环境之下，它对于制造加工时间的描述时以随机变量和模糊变量为主的，而在这两个变量中，需要对两个变量的分布函数予以确定，对于随机变量来说，它的分布函数确定需要立足于大量数据基础上对其进行科学统计来实现，保证函数的科学性和准确性，而在模糊变量的分布函数确定上则相对较为简单，它的隶属度函数可以由相关人员依据之前的经验来确定，但需要注意的是，在很多情况下，需要对两个变量结合并具体应用，相反，如果只是选择其中的一个如果以单一的随机变量或者是模糊变量进行描述的话，描述的准确性会降低。
1.1 生产调度中的问题分析
对于生产调度中的问题分析，可以设想在一个再制造加工车间中共有生产机器设备m台，待加工废旧零件n个，每一个加工工件中都包含有多个工序，对于这些工序的顺序排列需要在事前给予设定，在每个加工机器上进行一种加工工序，而且工序加工的时间也是依据损伤的程度来决定的。在确保了工序顺序的约束和交货期约束的基础上，生产调度的优化目标就可以归结为是在最小化的预定置信水平下的最大完工时间悲观值。那么这种模型需要具备有以下几方面假设条件：
第一，在多个工序加工作用下完成工件加工再制造，不同的工序加工也要在特定的机器设备上进行，第二， 在同一时间内只能对一个工件进行加工处理；第三，加工工序一旦开始就不能中途停止，需要持续不间断完成；第四，只要是初始时刻，工序加工都可以进行；第五，机器之间的相互运送时间是可以省去的。
1.2 参数描述
在再制造加工过程中，会不可避免的涉及到诸多不确定因素。通过对不同工件的加工时间的历史数据信息进行分析可知，对于工件加工时间在自身估计值上下波动特性的表示可以在对模糊数据的利用过程中实现，并且这一过程也是相当准确的。除此之外，以传统生产流程作为参考来进行对比分析，可以知道在再制造加工车间中，需要进行加工处理的废旧件的损伤程度主要是由具体加工时间的决定性条件，通常情况下，对于具体损伤的程度反映可以以损伤面积大小、损伤位置以及属性等来进行合理划分，进而区别出具体的损伤级别，等级越低损伤程度就越轻。基于此，就可以采用三角离散模糊随机变量PTkij（ω）来对再制造加工车间中待加工废旧零件加工时间进行表示，具体公式表示如下：
1.3 生产调度的模型
通过上述分析可知，每一个加工工件在加工过程中所需要的时间实质上是一种模糊随机变量，在这个变量下，我们可以知道加工工序的开始和技术时间具体指，而这个所确定的时间值也是模糊随机变量的一种，这就导致了调度模型和确定周的调度模型两者就会有较大的差异，在具体分析时就可以将其描述为是模糊随机机会约束规划模型。假设x为决策矢量，ξ是模糊随机矢量，f（x，ξ）就是目标函数，gj（x，ξ）就是约束函数j=1、2、……p。
2 调度模型求解方面的分析
2.1 模糊随机模拟
该模拟指的是以模糊随机系统作为中心，并按照要求从中抽取样本的计算机处理技术，样本抽取的具体依据是以模糊随机分布特征为准，严格按照随机分布特征来有目的性的进行抽取。需要注意的是，在该模型之中，它所涉及到的关于模糊随机变量的具体运算有很多，这种繁多性就需要实现模糊随机技术和仿真试验手段两者的有机结合。它的具体计算流程如下：
①按照概率分布Pr，从样本空间Ω中随机采取样本ω；
②采用模糊模拟计算，βk=Cr{f（ξ（ωk））≤0}，k取值为1、2、3……，N；
③N是aN的整数部分，N=ceil（aN）；
④返回序列{βk}中的第N个的最大元素。
给出了置信水平α和β，采用模糊随机模拟技术可以计算得到临界值f。它的计算流程是：
①按照概率分布Pr，从样本空间Ω中随机采取样本ω；
②通过模糊模拟计算，fk=inf{fk|Ct{f（ξ（ωn））≤fk}≥β}；
③N是αN的整数部分，也就是N=ceil（αN）。
2.2 对于神经网络的函数逼近分析
对于此内容的分析，按照本文所依据的万能逼近定理，本文就有针对性的选取一个三层RBF神经网络以逼近不确定函数，同时采用PSO算法来实现网络训练。
2.2.1 径向基函数神经网络
从本质上来讲，它可以归属为是前馈神经网络，这种网络在应用中具备有结构简单、逼近能力强等的特点，在实际应用中主要是用来解决对调度模式的准确识别以及自适应滤波等等问题中。此外，它在适用于函数逼近时，它的隐层节点基函数也具有一定的特殊性，它是以非线性激活函数为中心的，除了这方面分析外，RBF还具有很强的径向对称性，在神经元输入方面，如果它的输入和中心值距离越来越远，就表示它的实际激活程度越低，通过调查研究可知，这种神经网络输入层总共有■ni个神经元，而在输出层上则是有q+1个神经元。
2.2.2 基于PSO算法的神经网络训练分析
严格来说，PSO算法可以归属为智能搜索算法范畴中，它的基础是群体行为，主要运作是以个体直接协作为主。每一个优化问题的解答在算法中，都可以将其视为是一个粒子存在，它在n维空间中的位置表示为xi=（x1、x2，……xn，），飞行速度则表示为vi=（v1，v2，……，vn），并且每一个粒子都是具有一个直接由被优化目标函数所决定的适应值。这种算法在每一次的迭代过程中，粒子对于自身位置和速度的更新主要是通过跟踪个体和全局的最佳位置来实现的。
2.3 采用GA优化再制造加工调度
在采用PSO算法RBFNN进行训练，并在训练结束后，技术人员可以依据所获得的信息来对需要的最优参数值进行确定。同时还必须要把经过训练后的且训练好的网络直接嵌入到GA，在此过程中还要对染色体进行检查，检查的目的是确保其合理性达到要求。
首先，编码和译码。对于染色体的编码是立足于工序为基础的，与工序密不可分，对于N个废旧件和K个机器的再制造生产调度问题分析，可知它的染色体是由N×K个代表工序的基因构成，这其中所有的工件出现的次数至少是K次；而在解码环节，基因的个位数代表的是工件的自身序号，在得到准确解码之后就会生成活动调度解。
其次，初始化。对染色体种群进行初始化，并对其大小、交叉概率、变异概率等进行准确设置。
第三，适应度函数，技术人员把经过训练得到的RBFNN嵌入GA中，可以很方便的根据实际需要直接计算得到染色体的实际输出，输出结束之后根据输出的值来对染色体质量进行划分。
第四，选择。选择的依据是以适应度的值为准，同时在具体过程中还要遵循精英保护策略相结合的原则。
第五，交叉和变异。以POX为基础在父代染色体中随机选取一段位置，与被选中位置内的基因进行交换，并把剩下的基因依据顺序来逐一填入其与位置，这样可以提高染色体表示可行解的全面性。
2.4 混合式算法的基本流程
第一，参数的初始化。参数的初始化一般只需要考虑一下几种即可，即样本数T、模糊随机模拟次数、交货期机会约束以及模糊随机加工时间分布特征等，并由此形成一个仿真平台，发挥其作用。
第二，对PSO算法的参数信息初始化处理，处理内容包括惯性权重函数、最大迭代次数以及群体规模大小等。
第三，依据样本数据采用PSO算法来训练RBF网络，确定网络的函数中心、宽度、隐层节点数以及隐层和输出层之间的连接权重。
第四，对GA参数进行初始化，其中就包含有染色体种群大小、交叉概率、变异概率等等。
第五，在对染色体进行更新操作时，最常见的措施是借助交叉和变异行为实现，还可以在神经网络基础上对染色体可行性进行检测。
第六，通过对训练好的RBF网络的应用，可以得到所有的染色体的自身目标值信息，并在参考这个目标值作用下可以对染色体进行针对性排除和分布。
第七，重复上两个环节操作，直到染色体最优解的输出。
3 结 语
现阶段的工业发展正处于改造升级趋势中，实现工业生产的循环是当前的一个研究方向。再制造加工可以推动工业的循环生产，本文分析了不确定环境下再制造加工的生产调度优化问题，构建了模糊随机机会约束问题模型，提出了一种新的混合智能算法，而且也阐述了这种算法在不确定环境下再制造生产调度优化方面所具有的优势。
参考文献：
[1] 刘明周，张玺，刘从虎，等.不确定环境下再制造加工车间生产调度优化 方法[J].机械工程学报，2014，50（10）：206-212.
[2] 王超，刘阶萍，常伟涛等.不确定条件下的作业车间生产调度综述[J].装 备制造技术，2011，（4）：144-148，154.
[3] 张红宇，高阳.再制造生产计划与调度的研究进展[J].科研管理，2011，32 （5）：120-128.
[4] 张铭鑫，张玺，彭建刚，等.不确定环境下再制造加工车间多目标调度优 化方法[J].合肥工业大学学报（自然科学版），2016，39（4）：433-439，542.
车间生产调度岗位职责 篇4
1 模型建立
模具车间调度生产问题模型可以描述为:
(1)零件集:加工i个零件J={1,2,..,M},需要机器j台,每零件有k道加工序列,在一个时间段一台机器只能加工一个零件的某道工序,并有零件加工顺序约束,每道工序可以占有若干台机器;
(2)机器集:因生产调度时有机床约束而不会出现人员约束,所以只给出工序的机器分配,车间内可用机床x台,标号组成机床集D={1,2,..,F};
(3)机器使用时间:每个零件使用每台机器的时间用T矩阵表示,tijk表示第i个零件在j台机器上加工第k道所消耗的时间,可以由n台机器加工第k道工序,第k道工序在n台机器上的加工时间随操作人员、设备性能的不同使加工时间有所不同,要表示加工时间值上下波动的不确定因素常采用三角数,t=(tl,tn,tu)最少时间tl、最大时间tn、最小时间tu[1]。
则调度目标:零件i投入生产时间为(MPiL,MPiO,MPiP),完工期为di=(dil,diu),当i零件的在di=(dil,diu)内加工完成时用户满意度为1,反之为0;要用Rij表示,当j台机床在加工第i零件的第k道工序时Rij为1,反之Rij为0;当第i工件第k道工序设定完工时间是t=(tl,tn,tu),实际完成时间为di=(dil,diu),则满意度为设定完工时间的所属函数与完成期的所属函数交叉面积与完成期的所属函数面积的比[1],由满意度得到调度目标函数为:
工件的加工工序在机器上完工时间:min Tmax=max{Tijk}。
2 遗传算法求解车间调度经验
遗传算法在求解车间作业问题时,将搜索空间中的参数转换成遗传空间中的染色体,通过一定规则进行逐步迭代产生新个体,新个体经交叉、变异和复制操作又产生新的个体,遗传算法的操作简单,全局搜索能力强,缺点是控制参数如个体规模、适应度指标、变异率、交叉率等较多,参数组合不同,搜索过程可能会出现多方面的功效,影响遗传算法行为和性能的关键因素是如何选择交叉概率和变异概率,交叉概率过小,会降低搜索过程,新个体结构产生不易;而交叉概率过大,加快产生新个体,也越有可能破坏遗传模式[1]。
要求出制造车间生产调度问题中遗传算法各参数的合适值是一件难事,必须通过反复试验才能获取当前最优值,因而这些参数如果能进行自适应动态实时的变动对遗传算法在解决生产调度问题上有着积极的作用。
3 智能RL模式
Muller提出的智能增强学习(Reinforcement Learning)是一种基于行为方法的半监督学习,它包括负责智能体之间信息交换的通讯层、完成指定任务的协作求解的协作层和接收命令来感知环境变化及改变环境任务的控制层[5]。增强学习RL的目的是动态调整参数从而实现信号强化,当一个动作行为作用于环境,RL将产生动作评价奖惩值合反馈环境状态给智能体,根据相关策略智能体选择下一个行为去影响环境状况,并对新环境做出调整,修改后的新环境状态所给出的信息和奖惩值重新影响智能体,RL中智能体依靠自身经历进行学习获取知识,从而改进行动方案来适应环境。基本的RL模型包括离散的状态信号反馈集合、行为集合、动作评价奖惩值和环境状态集合,如下图:
遗传算法中变异和交叉概率值的选择直接影响算法的收敛性,针对制造车间的工件加工顺序、机床调配和加工时间等生产调度问题,最佳的变异和交叉概率值得获取需要通过反复实验,当加工状况一旦变化最优概率值又要重新寻找,因而单一的遗传算法是不能满足实时动态的车间作业调度的决策过程,而且在调度规模较大时很难保证获取最优值的收敛速度[2],智能RL能根据行为和评价的环境获取知识进而改变行动方案来适应环境的能力可以有效地完成随机搜索,遗传算法如能结合RL可以提高获取最佳变异概率和交叉概率的速度。
4 基于RL的遗传算法的设计
增强学习RL在一个环境下的行为产生一个奖惩值,奖惩值越大,则该行为被采用的可能性越大[3],通过不断重复的学习积累奖惩值找到一个最优的变异概率和交叉概率的行为策略,这与人为调整概率值有很大的差异[4],因而作为一种解决复杂的车间动态作业生产调度问题,提出了结合增强学习与遗传算法的智能体自适应模型。
(1)强化学习RL决策过程
基于增强学习的智能体在遗传算法中起协调作用,它在增强学习决策过程中应包含行为集A,环境状态集S,反馈的信号映射集R:S×A→R,状态转移函数α,Q值为:
独立的增强学习能感知其他智能体的行为,并从环境中得到反馈值Q,当智能体在S状态选择行为(r1,r2),强化学习智能体在t时刻的奖惩值更新为:
处于环境状态s时,增强学习RL对算法进行局部调整获取Qi值,经过一轮自学习获取一个环境反馈值r,算法在更新前的局部RL奖惩值Qi+1简化为:
在结束局部RL更新并保存该Qi+1,一轮算法结束获取全局奖惩值,保留该次学习所得值后对染色体的交叉变异率进行一次更新。
当增强学习协调作用于遗传算法中染色体交叉和变异时,RL能根据染色体的当前环境状态做出概率调整,在St状态下,RL的行为会就当前环境状态及先前的奖惩值去选择一个值,被选中的合适的交叉和变异率可能性越大,过小或过大概率值被选中的可能性也越小,获取合适的交叉和变异率并得到一个状态转移函数值,根据这个函数值得出奖惩值;感知一次学习后记下遗传算法的交叉和变异率,奖惩值大的交叉和变异率在下一次行为中更有可能被选中的。由于奖惩值对交叉和变异率有明显的优化作用,形成正向反馈后的奖罚值使遗传算法的交叉和变异率最后落实到较优值上,个体就更好的遗传了父串的染色体,在算法更新时对该染色体结构中交叉及变异的适应度函数奖惩值也会更大,明显提高遗传算法的收敛速度[5]。
RL要获取最佳行为必须不断探索环境状态,如何判断已最佳交叉变异率是决定重新探索还是利用已知的最佳值的关键点。智能增强学习体可参照行为预测设定值来减少学习过程中考虑的因素而缩短学习过程,避免陷入次优行为找不到全局最佳交叉变异率。在开始智能学习时,随机获取交叉变异率去探索第一轮新值,RL将奖惩值与历史记录比较,保存较优值淘汰较劣值,经过多次增强学习探索,最佳的概率值得以保留,已证明智能增强学习的收敛与行为选择策略无关,设定行为预测值不影响RL的过程。
(2)智能体RL实现的流程
为快速求取普通遗传算法染色体中交叉变异率的最优选择,结合普通遗传算法与智能体增强学习RL,智能体RL的自我学习能够就状态、行为、学习率等的情况做出决策,对遗传算法解决车间调度问题编码中的染色体进行个体种群初始化,求取个体适应度函数值并判断是否终止遗传算法,如果终止条件不符合,则根据适应度函数值对染色体进行局部遗传算子的交换和变异,奖惩初始值0,RL探索学习交叉变异率的进程中,当前奖惩值比较之前值并保留局部较优值,一次学习结束更新交叉变异率,记录全局奖惩值同时进行全局优化探索学习,通过反复学习获取经验,保留良好的奖惩值实现染色体的交叉变异概率的最佳选择,实现作业车间的智能调度的算法流程如图示:
交叉和变异率能随智能增强学习机制的奖惩值自动改变,奖惩值较大时交叉和变异概率增加,跳出局部最优,奖惩值较小时交叉和变异了降低,有利保留良好种群,由于RL是一种动态即时智能学习,随着智能体学习的推进,保留的交叉变异率值逐渐良好,染色体的种群逐渐优化,因此智能RL与遗传算法结合在保证染色体编码多样性的同时也保证了遗传算法的收敛特性,当适应度函数值不再有明显改进,智能增强学习结束,最优解求出算法终止。(下转第238页)
5 总结
模具制造车间生产调度问题在企业中普遍存在,如何优化对提高企业竞争力有积极的影响,本文结合智能RL与遗传算法,建立了车间作业调度模型的在线调度,帮助企业合理安排工作进程。仿真实验证明该算法能有效提高企业资源的优化分配,合理安排加工任务,在动态的生产状况下能快速智能的做调整。
参考文献
[1]王万良,吴启迪.生产调度智能算法及其机器应用[M].科学出版社,2007.
[2]宋毅.基于遗传算法的生产调度方法及其软件实现[D].杭州:浙江工业大学,2003.
[3]王雪辉,李世杰,张玉芝.Multi-Agent技术在车间调度中的应用[J].河北工业大学学报,2005,34(2):106-109.
[4]陈文,王时龙,黄河.基于多Agent的蚁群算法在车间动态调度中的应用研究[J].组合机床与自动化加工技术,2004.
[5]李琼,郭御风,蒋艳凰.基于强化学习的智能I/O调度算法[J].计算机工程与科学,2010,32(7).
车间生产调度岗位职责 篇5
摘要：针对车间调度问题的特点，为解决传统禁忌搜索算法容易陷入局部最优解的问题，提出一种求解车间调度问题改进的禁忌搜索算法一双禁忌表禁忌搜索算法，该算法通过建立双禁忌表避免在搜索最优解时出现循环的现象，通过该算法与TSAB算法进行比较可知，该算法具有较强的寻优能力。
关键词：车间调度；启发式算法；禁忌搜索；禁忌表；邻域
DOI：10.15938/j.jhust.2016.06.010
中图分类号：TP301
文献标志码：A
文章编号：1007-2683（2016）06-0050-05
0.引言
车间调度JSP（J0b Shop scheduling）问题是一种NP-hard问题，由于其本身问题比较复杂，加之要解决的问题规模比较大，有些问题不能求出一组最优解，只能求出次优解，或者近似最优解，启发式方法较适合求解这类问题，禁忌搜索算法是一种有效的求得全局最优解的启发式算法，其优点是有灵活记忆的功能，当搜索陷入局部最优解时能够跳出；其缺点是对初始解的依赖较强，一个好的初始解往往能够得出一个比较好的结果，当产生某一个最优解时，常常因为这个最优解产生循环，而此时我们要跳出循环，本文提出一种新的禁忌搜索算法一双禁忌表禁忌搜索算法，用以解决在产生最优解的同时容易出现循环的问题。
1.问题描述
JSP问题实际上是安排n个工件在m台机器上加工使工件的加工时间最短，而且每一个工件都有若干道工序，每道工序有指定的加工顺序，固定机器上工件的工序有各自的加工时问.每一个工件都是独立的，也就是说一个工件在某一时刻只能被一台机器加工，并且某一时刻每台机器只能加工一个一个工件，加工期间不允许被中断，每个工件不能在同一台机器上加工多次，最终的目标是使工件完工时间最小。更具体的，问题可以形式化描述成一种JSP调度模型，工件集：J={1，2，…，n}；机器集：M={1，2，…，m}；加工时间矩阵用T表示，机器j上工件i的加工时间用T表示；机器的加工顺序矩阵JM，加工工件i第j个操作的机器编号用jm（i，j）表示，jm（i，·）表示要工件i所有操作按优先级顺序加工的各机器号的排列；工件排列矩阵Mi，其中Mi（i，j）表示在机器i上加工的第，j个操作的工件号，Mi（i，·）表示在加工机器i上依次加工的各工件号的排列；工件i在机器，j上的完工时间C（i，j）
1）工件的加工时间矩阵T为常数矩阵，也就是说每个工件的各个操作加工时间Ttj是已知的，并且均为常数；
2）加工顺序矩阵JM是已知的，也就是说加工每个工件各个工序的加工，必须在指定的机器上；
3）同一台机器上每个工件只能加工一次，也就是说同一台机器上不允许出现循环加工某个工件的现象；
2.算法设计
2.1邻域设计
本算法基于禁忌搜索算法，并采用两个禁忌表.由于当邻域规模比较大时，只试走一步，在规定的时间内，很容易陷入局部最优解，要采取一种策略使搜素的范围更广一些，并且所用的时间并不是很大.那么在规定一个可行解的情况下，对每两个连续的移动用禁忌搜索得到一个可行解，然后从这些可行解当中选一个最好的解，当作下一次迭代过程的起点，重复以上过程直到不能得到更好的调度解则停止，更具体的描述如下：
JSP问题的完工时间取决于关键路径长短，在一个可行调度解中如果工序之间的时间间隔为0，最长的路径被称为关键路径，我们的工作就是如何减少关键路径的长度.如图1中关键路径为（1，1）（2，1）（1，3）（1，4）（2，2）（3，2）（1，6），图1中调度为单一关键路径，当然可能出现多个关键路径.在关键路径上，有块的定义，在图1中有3个块分别是B1.B2.B3。
移动的定义每个关键块在Nowicki和Smutnicki的定义的基础上，有以下几点有所不同：
1）若关键块B是关键路径上第一个关键快，那么要交换的是关键块B上的最后两个工序61和62；
2）若关键块B是关键路径上的尾块，则要交换关键块B的前两个工序和α1和α1
3）另外的关键块B，交换前两道工序α1和α1和最后两道工序b1和b1，具体的操作如图1所示.
这些移动构成了移动集合p（s），令g（s，p）来表示通过对s运用一次移动而获得的一个可行解，那么s的邻域N（s）={g（s，p）：p∈p（s）}.之所以这样定义邻域的原因是，每个关键块只增加了两个移动，并没有极大的增加计算量。
2.2禁忌表
在传统的Ts算法中，禁忌表T所记录的是移动.也就是说在满足定义的邻域前提下，从一个可行解到下一个可行解的移动是交换工序i和j，那么有序对（i，j）被记录在禁忌表T中，它的意思是在接下来的一次移动中，不能再进行工序i和j的交换，禁忌表并不能把每一个可行解都保存，鉴于此设置一个禁忌表长度，禁忌表长度是指接下来的迭代不能再回到禁忌元素的最大步數，每一个新的移动都会被加到禁忌表最后的位置，随之最前面的移动被删除，但这就会形成一个问题，当某个移动被删除的时候，此移动还可能在某次迭代时被使用，因为此时该移动已经不在禁忌表中了，为了解决这一问题，采用双禁忌表的策略，两个禁忌表分别为SHORT-T和LONG-T（如图2所示），其中T1，T1…Ti，…Tn=（（α1，α2），（α3，α4））…（（αi，αi），αm，αn））表示移动，SHORT-T用来存放当前搜索到并且需要禁忌的解（移动），当满足迭代次数的迭代之后，并不是将所有禁忌的解直接释放，而是将普通的解从SHORT-T中释放，而通过移动产生最优解的移动则放入LONG-T中.LONG-T存储的是历史最优解，在LONG-T更新时，若当前解，与LONG-T中的解相同时，则说明出现了循环，可以允许出现一定的循环，但是循环达到一定次数的话，就要重新产生初始解而跳出循环.这么做的原因是，当通过迭代产生循环时，最容易产生循环的是产生最优解的移动而导致的循环，而且在最优解上产生的循环是不能容忍的，特别要强调的一点，SHORT-T存放的是移动，LONG-T存放的是历史最优解。
2.3逆排时技术
给定一个排时问题实例E和它的开工顺序，把工件的开工顺序和加工顺序倒过来得到另外一个可行解，例如给定的加工顺序（o（1），o（2）…，o（n）），计算得到倒转后的实例得到的加工顺序为（o（n）….，o（2），o（1），计算倒转后的每项工作的开始时间和最大完工时间。
举个例子，给定加工时间矩阵Tij和加工顺序矩阵Rij其中：
3.实例验证
算法在linux环境下使用c语言进行实验，实验环境为，CPU i3处理器，内存lG.Benchmark算例是国际上通用的算例，能够反映一个算法的优劣，对于35个Benchmark问题，将本文算法与TSAB算法进行比较计算得到makespan。
在合理的时间内，应用本算法有23个相同，并且是最优解，说明本算法对于大部分的算例能够计算出最优解是可行的，有10个优于TSAB算法得到的解更接近最优解，有两个与TSAB算法相比得到的解较差，从总体来说大部分的解都优于或者与TSAB算法的解相同，只有两个解稍差，说明本算法有一定的优越性，结果不同的算例为FTl0，LAl6，LA22，LA24，LA25，LA27，LA29，LA36-LA40，其中与TSAB算法对比makespan表不同的实例如表1所示。
衡量车间调度问题算法的优劣的标准一般有两个，分别是计算机时间和得到的最优解，本算法在计算时间上和TSAB算法基本相同，但是在寻优能力上比TSAB算法更强，由表1可画出如图6的折线图，从图6中可直观看出本算法更接近最优解，表明本算法有一定的寻优能力，并且可有效提高解的质量。
4.结论
【车间生产调度岗位职责】推荐阅读：
生产的调度主任车间述职报告05-02
生产车间职责07-06
生产车间岗位职责05-25
生产车间的岗位职责06-24
石子生产车间岗位职责08-02
生产车间安全生产岗位责任制05-06
生产车间文员具体岗位职责07-02
生产车间班长的岗位职责08-23
车间各岗位安全生产职责08-28
生产车间主任岗位责任制09-04