车间作业调度范文
车间作业调度范文（精选10篇）
车间作业调度 第1篇
1. 遗传算法
遗传算法 (GA, Genetic Algorithm) 于20世纪60年代由美国Michigan大学J.Holland教授首先提出, 是模拟生物的遗传和进化过程而发展起来的一种搜索和优化方法, 其搜索过程始终是在群体中进行的, 它可广泛应用于人工智能、机器学习、函数的优化、自动控制等领域。而且遗传算法是一种逐次迭代方法, 具有全局性、并行性、快速性和自适应性, 是求解复杂问题最优解的有效方法。
GA的突出特点是将问题的解空间通过编码转换为GA的搜索空间, 把问题的解转换为生物的个体, 并借助生物的遗传和进化理论, 对多个个体同时进行选择、交叉和变异操作。可以较快地搜索到最优解。但是, 遗传算法易陷入局部最优, 搜索效率还不是很高。
2. 车间作业调度问题
(1) 问题描述
Job Shop调度问题描述为:在m台机器上安排n个加工作业。由于工件加工工艺的要求, 给定每个工件使用机器的顺序以及每道工序所花费的时间, 且满足如下假设:
1) 每个机器在同一时刻只能加工一个工件;
2) 不同工件的工序之间没有顺序约束;
3) 操作一旦开始就不能中途停止。调度的目的是在满足约束条件下安排每台机器上的工件加工顺序, 使得调度系统性能指标达到最大限度地优化。
(2) 数学模型
式中:h, k为机器类型;i, j为要加工的零件类型;Cjk为工件j在机器k上的完工时间;T jk为工件j在机器k上的加工时间;M是一个充分大的正数;
Aihk=1, 若机器h先于机器k加工工件i0, 非上述情况;
X ijk=1, 若工件i先于工件j在机器k上加工0, 非上述情况;
式 (2) 为工艺约束条件决定的各工件各操作的先后加工顺序;
式 (3) 为加工各工件的各机器先后顺序。
(二) 相关研究现状
车间作业调度 (JSS) , 是CIMS领域中研究的重要课题。它的研究不仅具有重大的现实意义, 而且具有深远的理论意义。长期以来, JSS研究的方法始终以启发式算法为主导, 绝大部分的JSS研究工作也都围绕着启发式算法进行, 如基于启发式算法的JSS仿真系统、并行JSS系统及专家系统等, 尽管这些研究取得了一定的应用效果, 但是却存在着难以克服的弱点, 如计算规模不可能较大, 寻优结果不具备全局特性等。
遗传算法经过20余年的发展, 取得了丰硕的应用成果和理论研究的进展, 特别是近年来世界范围形成的进化计算热潮, 计算智能已作为人工智能研究的一个重要方向, 以及后来的人工生命研究兴起, 使遗传算法受到广泛的关注。
(三) 算法
1. 基本算法步骤及过程描述
STEP0初始化参数
种群60, 循环500次, 交叉0.8, 变异0.6, 代沟0.9;STEP1初始化群
采用两层次遗传编码, 第一层次用来描述工件每道加工工序的作业单元选择问题, 其实质是形成工件的作业单元路径。一旦每个工件的作业单元路径确定下来了, 那么就可以产生第二层次的遗传编码, 用来表征工件在每个特定作业单元的并行机选择问题。
按调度优先级编码, 比如3个零件, 每个零件3个工序, 初始化:
STEP2计算适应值
解码成工序序列, 计算时间;
STEP3选择
在原种群中, 按轮盘法选择出60*0.9 (代沟) =54个个体组成新种群;
STEP4交叉
对选择出来的新种群进行交叉, 在新种群中, 随机选择2个个体 (选择过的个体将不在选择, 保证所有个体都选择) , 随机生成有一个数, 如果大于交叉概率, 就进行2点交叉。2点交叉位置每次都是随机的
如果交叉位置在2和5, 先生成0、2、3、5、6、0、0、0
然后按下面的数据删除2、3、5、6后写入即1、2、3、5、6、4、9、7、8;
STEP5变异
对交叉出来的新种群进行变异, 在新种群中, 对每个个体, 随机生成有一个数, 如果大于变异概率, 随机生成2个位置数据, 将2个位置的数据进行交换;
STEP6替换
新的种群个体是54个, 原来的种群为60, 保留6个适应值好的, 其他代替54个。
2. 程序流程图
(四) 实验
1. 编码方法与防止死锁
遗传编码的第一步实现的是OSP调度, 而第二步则是实现了HFSP调度, 本文两个层次的遗传编码构成了每个工件的调度路径, 其实质是给定作业单元的并行机分配问题, 即一个满足资源约束的调度方案。
由于Job shop调度问题要考虑其存在死锁的可能性。死锁 (Deadlock) 是互相竞争资源的事务间相互等待、各事务资源请求在现行的并发控制机制下永远得不到满足的一种停滞状态。这里可能导致死锁产生的资源约束可以分为两类:机器加工顺序约束和工件加工工序约束。
在用Matlab 6.5编写的程序中, 本文引进了两个分别表达机器加工顺序和工件工序的矩阵来记录各道工序的完工时间, 以此来判断调度中是否存在死锁。
2. 计算结果效果图
(五) 小结
本文就遗传算法在车间调度中的应用问题进行了探讨, 主要研究的问题是寻求用遗传算法解决更加适合生产实践的调度对象。在探讨过程中有以下结论:
1. 二层次编码方法不仅适合于JSP问题而且适用于解决通用作业计划问题。
2. 对于含有Job Shop调度的问题, 必须考虑其出现死锁的可能性。在编程的过程中, 应用两个辅助矩阵解决了死锁判断问题, 但是对于复杂的调度问题, 死锁的修复可能无法有效的实现。
3. 资源抢占中优先权的分配方式对解的质量有很大的影响。例如, 对于某个工件的某道工序, 如果出现两台及以上抢占加工时, 传统的优先权的分配仅考虑该工序的就绪时间, 谁短谁先加工, 是属于完全“顾后性”。本文通过许多算例发现, 在优先权的分配中以该工序的完工时间 (“瞻顾后性”) 作为参考指标的调度方案优于仅考虑该工序就绪时间产生调度方案。
参考文献
[1]衣杨, 汪定伟.GA求解并行多机成组调度[J].系统仿真学报, 2001, 5:554-558.
[2]衣杨, 常会友.成组调度研究综述[J].计算机应用研究, 2003, 18-24.
[3]王凌.车间调度及其遗传算法[M].清华大学出版社, 2003.
4S店车间调度管理 第2篇
1．车间调度管理就是以维修作业的《派工单》为依据，合理组织企业的日常生产活动，定期检查维修作业的完成情况，及时而有效地调整和处理维修过程中的异常情况，保证全面完成维修任务。
2．每日上班前，车间主管应检查维修准备情况，包括班组人员到位情况、设备工具准备情况、配件供应或修复待装情况等，督促和协助有关部门、班组按时作好各项准备工作。
3．根据当日的《派工单》及时、合理、均衡地安排班组进行维修作业。员工必须绝对服从调度指令。如班组或员工对调度指令有意见，必须先执行，下班后再提出各自的意见，必要时向部门经理报告。
4．上班期间，车间主管要在车间内进行周期性巡视，检查各个作业工位的工作情况。如果发现异常，应及时协调和处理。一般情况下，每小时巡查1次，每次不少于20分钟。
5．车间主管要根据维修需要，合理组织和调剂维修作业安排，以确保各工位之间的有效配合。当班组作业完成时，应及时通知技术检验员迅速到工位检验。
6．车间主管要经常与配件部门联系，了解配件供应情况，督促配件部门及时把配件供应到车间班组。
7．出现维修增加项目情况时，车间主管应立即通知业务部门，以便与客户取得联系。在接到业务部门的增项处理意见后，应及时通知班组进行增项作业。
8．车间主管要检查督促维修班组和一线员工合理使用和维护设备，禁止设备带病运行。一方面要检查、督促操作者按章操作，另一方面要检查、督促设备工具的日常维护、保养和维修。
9．车间主管要认真做好维修作业的调度记录、维修情况的统计和分析，以及总结维修过程中的问题与经验。10．车间主管要负责维修区域内的文明环境建设，应经常引导教育员工文明施工，爱护环境、爱护设备、爱护车辆，遵守安全生产规定，保持车间整洁卫生。
11．车间主管要组织好维修工作调度会，对维修过程中的突出问题或典型情况，要及时告诉员工，以引起大家的广泛重视；对表现优良的员工，要及时予以表扬，以树立榜样，鼓励员工积极向上。
车间作业调度 第3篇
【关键词】置换流水车间调度；分布估计算法；遗传算法；模糊逻辑控制
0.前言
置换流水车间调度问题（PFSP）是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组装和信息设备服务上[1]。该问题一般可以描述为，n个待加工工件需要在m台机器上进行加工。问题的目标是求出这n个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间（makespan）最短。
PFSP最早由Johnson于1954年进行研究[2]，具有NP难性质[3]。求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法[4]。数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。
遗传算法（GA）是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法[5]（EDA）。EDA是一种运用统计学习的新型优化算法。相比GA，EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优[6][7]。以混合优化为思路，本文将设计一种EDA与GA结合的混合算法来求解PFSP问题，混合算法通过EDA的概率模型和GA的交叉变异操作两种方式来生成个体，并引入模糊控制理论[8]来自适应调节两种算法生成个体的比例。
1.置换流水车间调度问题
PFSP问题通常假设：
（1）n台工件在m台机器上加工。
（2）每个工件以相同的顺序在m台机器上加工。
（3）每个工件在每台机器上的加工时间是预先确定的。
（4）每台机器只能同时加工一个工件。
2.混合算法设计
2.1种群初始化
初始种群含有PS个个体，利用经典的启发式方法NEH[9]算法产生1个个体，其余PS-1个个体采用随机初始化的方法生成。
2.2选择
根据PFSP问题所给的加工时间表计算出种群中所有个体的总完工时间Cmax，显然Cmax越小，个体的质量就越好，据此可将评价个体好坏的适应度函数设为1/Cmax。本文选择的是轮盘赌法，加工时间越小，适应度值越高，个体被选择的概率也就越大
2.3概率模型
2.4局部搜索
对概率模型采样即可得到新一代的个体，对个体进行局部搜索可以提高EDA的性能[11]，本文将对较好的个体进行局部搜索，分别有如下三种搜索方法：
插入：选择一个工件并随机插入到某一位置。
交换：随机选择两个工件并交换其所在位置。
倒置：随机选择两个工件，将这两个工件之间的序列反转。
2.5交叉算子
本文采用的交叉算子为次序保留交叉。例如，亲代个体为{2，3，5，1，4，9，8，6，7，10}和{1，2，4，5，6，7，8，3，9，10}，在交叉过程中保留的片段为{4，9，8，6}，则生成的子代个体为{1，2，5，7，4，9，8，6，3，10}和{2，3，4，5，6，1，8， 7，9，10}，图示如下：
2.6变异算子
本文选取的变异算子为移码变异，例如，变异前的个体为{6，8，9，10，7，4，3，1，2，5}，选择7，8这两个位点进行变异，变异后个体为{6， 9，10，7，8，4，3，1，2，5}，如下图所示：
2.7模糊逻辑控制
混合优化策略中，不同算法的比例是影响算法性能的关键，传统的算法比例混合方法主要包括固定比例和动态比例两种。使用固定比例时，比例值将在整个算法搜索过程中保持不变。这种方法需要进行试验来确定合适的比例值，其缺点在于为寻找到最佳比例值所需进行的试验多，耗时久。而动态比例调节则只需预先确定一个比例的初始值，而在运行过程中会根据搜索情况调节比例。调节方式又可以分为两种：一种是应用传统的启发式规则控制算法生成个体的比例，这些规则可以用确定的数学公式表示；而另一种是用人工智能技术自适应调整生成个体的比例，最常见的是将模糊逻辑应用于比例调节，能根据算法性能的变化来实现比例控制[12]。为了使混合算法具有优良的适应性，本文采用模糊逻辑控制来进行比例调节：在EDA表现良好时提高EDA生成个体的比例发挥其全局搜索的优势，在EDA求得解的质量下降时提高GA生成个体的比例，以避免出现局部最优。
3.EDA-GA混合算法
通过以上设计，EDA-GA混合算法的步骤如下：
3.1种群和概率模型的初始化
产生初始种群，迭代次数t=1，概率模型P中pij=1/n
3.2对种群个体进行评价并选择出优势个体
以轮盘赌法选择出用以更新EDA概率模型的优势个体和待进行交叉变异操作的父代个体。
3.3更新概率模型并对概率模型取样生成个体
对优势个体进行统计学习完成概率模型的更新，然后对概率模型抽样产生PS个个体，局部搜索后，把最好的rate（t）*PS个个体加入到下一代种群，rate（t）为当前EDA所生成个体的比例。
3.4交叉操作和变异操作
对父代分别进行交叉操作和变异操作，共产生（1-rate（t））*PS个个体，将这些个体加入到下一代种群中。
3.5模糊逻辑控制调节比例
新一代种群生成后，将种群平均完工时间与上一代进行比较，得到模糊输入量，根据模糊判断规则确定下一次迭代时EDA所生成个体的比例rate（t+1）。
3.6终止条件判断
若满足终止条件，输出此时得到的最优解；否则，t=t+1，进入步骤2）。
4.实验结果
4.1参数设置
将EDA-GA混合算法的参数设为种群大小PS=200，迭代次数iteration_times=300，优势个体所占比例为superior_rate=0.2，GA变异比例mutation_rate=0.1，EDA初始生成个体的比例rate=1，概率模型学习速率α=0.2。
4.2结果分析
PFSP问题的基准算例有很多，其中Car和Rec类算例运行时间段短，计算快捷，因此选用这两种算例來验证本文所设计混合算法的有效性。每个算例用matlab独立运行10次，并与GA，EDA的结果进行比较。测试结果如表3所示。其中，BRE=×100、ARE=×100为每种算法求得的最优解C与三种算法测试所得的最好解C*的相对偏差百分比的最小值和平均值。
从表3的实验结果可以看出，对测试问题Car1～Car8和Rec01～Rec37，本文设计的EDA-GA混合算法ARE与BRE均优于EDA和GA，说明GA的引入使得EDA的优化性能有了很大的改进。对于Rec39、Rec41，混合算法BRE不如GA，说明优化性能稍弱于GA，但相比EDA解的质量有显著提高。因此总体而言，EDA-GA混合算法的性能是要强于GA和EDA。
5.结论
针对EDA和GA各自在全局搜索和局部搜索的不同侧重，本文设计了一种EDA-GA混合算法对以最小化总完工时间为优化目标的PFSP问题进行了求解。在混合算法中， EDA和GA各自生成一定比例的个体进行混合，在两种算法比例的调节上使用了模糊逻辑控制的方法，其中模糊输入量为每一代种群个体总加工时间的平均值的变化，而模糊输出量为EDA在下一次迭代中所生成个体的比例。由此，混合算法综合了EDA和GA的优点，运用Car和Rec类进行算例仿真，实验结果证明上述EDA-GA混合算法是有效的。 [科]
【参考文献】
[1]Pan Q-K，Suganhan PN，Tasgetiren MF，Chua TJ.A discrete artificial bee colony algorithm for thelot-streaming flow shop scheduling problem. Information Sciences，2011，181（12）：2455-68.
[2]JohnsonS M.Optimal two-and three-stage production schedules with setup times included[J].Naval research logistics quarterly，1954，1（1）：61-68.
[3]Zhang Y，Li X.Estimation of distribution algorithm for permutation flow shops with total flow time minimization[J].Computers & Industrial Engineering，2011，60（4）：706-718.
[4]周驰，高亮，高海兵.基于 PSO 的置换流水车间调度算法[J].电子学报，2006，34（11）：2008-2011.
[5]LarranagaP，LozanoJA.Estimationofdistributionalgorithms：Anewtoolforevolutionary
computation[M].Springer，2002.
[6]叶宝林，高慧敏，王筱萍，等.基于分布估计算法的二阶段置换流水车间调度算法[J].计算机应用研究，2011，28（10）：3702-3706.
[7]ChenSH，ChenMC，Chang P C，et al.Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems[J].Expert Systems with Applications，2010，37（9）：6441-6451.
[8]Chan F T S，Prakash A，Mishra N.Priority-based scheduling in flexible system using AISwithFLCapproach[J].International Journal of Production Research，2013，51（16）：4880-4895.
[9]Nawaz M，Enscore Jr E E，Ham I.A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J].Omega，1983，11（1）：91-95.
[10]王圣尧，王凌，许烨，等.求解混合流水车间调度问题的分布估计算法[J].自动化学报，2012，38（3）：437-443.
[11]Wang S，Wang L，Liu M，et al.An effective estimation of distribution algorithm for solving the distributedpermutationflow-shopscheduling problem [J]. International Journal of Production Economics，2013，145（1）：387-396.
[12]何宏，钱锋.遗传算法参数自适应控制的新方法[J].华东理工大学学报：自然科学版，2006，32（5）：601-606.
[13]Kim K W，Gen M，Yamazaki G.Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling[J].Applied Soft Computing， 2003，2（3）：174-188.
车间作业调度 第4篇
离散制造业车间调度问题目前已从相对简单的经典车间调度问题逐渐转化为柔性作业车间调度问题(Flexible Job-shop Scheduling ,FJSP),打破了经典车间调度对某一产品的每个加工工序只能由一台设备加工的约束,FJSP不仅要确定各产品加工工序的顺序,而且要将各工序分配给不同的设备,从而保证所有产品的最大加工时间最短,属于NP-hard难题。谢皓等[1]以最大完工时间最短为目标,采用遗传算法对一个8×8(8台加工设备,8种工件)的问题进行计算,并没有考虑在实际生产中调度问题是典型的多目标优化问题。王硕、曹岩等[2,3]采用了一种改进的蚁群算法对机器编码,控制冗余解的数量,提高算法的计算速度,计算模型则是经典的车间调度模型与实际生产有一定的差距。此外,有部分学者考虑了实际生产中车间调度问题属于多目标优化问题,如刘烽等[4]针对混合流水车间多目标调度问题,以最大流程时间和生产中所消耗的总能量最小为目标函数,建立了混合整数规划模型,采用NSGA2算法计算了12×8的调度问题。魏巍等[5,6]分别以加工成本、加工质量、制造工期最短、设备利用率最大为目建立多目标优化模型,采用智能算法求解小规模的调度问题。曾强等[7,8]针对柔性作业车间调度问题中加工路径的不确定性,以最长完工时间最小和加工费用最少以及设备利用率最高为目标,建立多目标调度问题模型。
综合上述研究发现,现有的文献主要存在两点不足之处,一是在建立车间调度模型时没有考虑足够的约束和目标,大多数研究目标没有考虑到在实际生产中应当尽量减少产品的搬运距离/次数;二是在解决车间调度问题的同时并没有考虑车间加工设备位置布局,造成车间内的物料无效搬运距离/次数增加。
针对上述不足,本文首先建立了以最大完工时间最小、总延期时间最小、总提前期时间最小、设备总负荷最小、单台设备的最大负荷最小、总生产成本最低以及工件搬运次数最少的多目标车间生产优化调度模型。然后,对于优化的pareto解集采用AHP确定其最优调度方案。再次,根据车间调度问题确定的产品加工工艺线路,以加工产品搬运距离最少为目标,对现有的车间设备布局进行优化,使车间无效的搬运量最小。最后,以大连某空调生产车间为例,通过对一个10×10的车间调度进行计算,验证了本文算法和模型的可行性。
1离散车间多目标调度数学模型
1.1问题描述
多目标FJSP是指在m台设备(M={mk|1,2,…,m,k=1,2,…,m})上加工n个工件(J={ji|j1,j2,…,jn,i=1,2,…,n),每个工件包含Ni个事先确定加工顺序的工序,每个工序可以在多台设备上加工,mij表示工件ji的第j道工序可使用的加工设备集合。Sijk为工件ji的第j道工序在设备k上开始加工时间,Eijk为工件ji的第j道工序在设备k上结束加工的时间,工件ji的第j道工序在设备k上的加工时间为tijk,Ti表示工件ji的最后一道工序的完工时间,Di表示工件ji的交货时间,α表示单位时间延期交货费用为。工件ji的原材料费用为Ci,不同设备单位时间的加工费用用pk表示,单位时间的调整费用为sk,用wijk表示工件ji的第j道工序在设备k上的调整时间。Xijk为决策变量,当工件ji的第j道工序在设备k上加工时,取值为1,否则为0;Yikk为决策变量,当工件ji的第j道工序与第j-1道工序都在设备k上加工时,取值1,否则为0;车间调度的目的是在有限的资源条件下,将各个工序分配到相匹配的设备上,从而达到车间生产的多个目标组合最优。
根据上述描述,本文作如下假设:1)一台设备同一时刻只能加工一个工件;2)若某一工件加工的上一道工序加工完毕后,对应的设备处于空闲状态,则立即开始加工下一道工序;3)工件在每台设备上的加工时间、装卸时间都确定,并都作为加工时间计算;4)工序在每台设备上的调整时间已知;5)工件加工一旦开始,就不能中断,除非设备出现故障;6)所有设备一开始均处于正常状态,即最初不存在故障设备;7)设备的故障率是通过长时间对设备的观测和维护所到的统计值,数据真实可靠;8)同一个工件,只有在上一道加工工序结束后才能进行下一道工序;9)工件的加工顺序不能改变。
1.2目标函数
1)最大完工时间最小:
2)总延期时间最小:
3)总提前期时间最小:
4)总生产成本最低:
5)设备总负荷最小:
6)单台设备的最大负荷最小:
7)工件搬运次数最少:
约束条件如下:
其中,式(8)表示:在同一时刻任意工件的某一工序只能由一台设备加工;式(9)表示:同一工件的下一道工序的开工时间必须大于或等于该工件上一道工序的结束时间;式(10)表示:任意工件的结束时间大于等于该工件的开始时间、加工时间以及调整时间之和;式(11)表示:任意设备上新任务的开始必须在上一任务结束之后;式(12)工件的最后完工时间的;式(13)同一工件前后加工工序在同一设备的约束。
2算法设计
由于车间调度问题属于NP-hard难题,每个目标之间存在复杂的关系,而且属于非线性优化模型,传统优化方法计算难度较大,因此本文采用一种基于双层(加工工序和加工设备)编码的改进遗传算法求解该问题。与传统遗传算法相比,确保染色体包含信息的全面性和完整性,同时采用最优保存策略、锦标赛选择、序值以及拥挤距离选择的方法,选择种群个体中适应度较高的遗传给下一代。交叉和变异操作均采用随机的两点交叉和变异。为了保证下一代种群中个体的多样性和防止搜索解陷入局部最优解的循环中,本文将适应度函数通过线性尺度转换方法。
2.1染色体编码
本文采用基于加工工序和加工设备的两层编码的方式对染色体进行编,确保染色体包含信息的全面性和完整性。染色体编码采用整数编码,每个染色体长度为(n表示加工工件数,Ni表示第i个工件的工序数)。染色体分为两部,前半部分表示工件的加工工序,后半部分表示加工工件的加工工序所对应的加工设备顺序。
2.2适应度函数
本文把适应度函数与目标函数的转化关系式定义如下:
在传统遗传算法的实际操作中会出现某一代中有一部分个体的适应度值很高,是到目前为止所有种群中适应度最高的个体,但是这些个体未必就是待优化问题的最优解或者近似最优解,而可能是解空间中的局部最优解。当出现这种情况时,如果仍然按照原种群中个体适应度函数来确定个体是否遗传到下一代中,就会出现从下一代开始,以后各代的个体几乎都不会改变。因为从上一代开始,在进行选择操作时,由于种群中适应度较高的个体会排斥适应度较低的个体,所以,以后每一代种群中适应度较高的那些个体占据种群的绝大部分。根据个体进化规则和选择操作中最优保存策略,这些适应度较高的个体直接遗传给下一代。所以,这种个体进化会使种群基因的多样性减小,甚至会出现上一代和下一代个体完全重合,这样就会使搜索解停留在某一局部最优点上。本文对某些适应度较高的个体进行人为的修订,降低其适应度,减小与其他个体适应度的差异,限制这些个体的遗传代数,增加适应度较小的个体被选择遗传的概率,从而增加种群基因的多样性,来避免这一现象的发生,达到使搜索解跳出局部最优点的约束。
本文对适应度函数采用线性尺度转换方法,转换公式如下:
其中,F为原适应度函数,F'为转换后的适应度函数,a,b为转换系数,一般c的取值范围是1.2~2,本文取1.15,F为所有个体适应度的平均值,Fmax为所有个体中适应度最高个体的适应度值。
2.3选择操作
本文采用MATLAB工具箱中的锦标赛选择函数(Selection tournament),采用最优保存策略,通过计算个体的序值和拥挤距离,选择种群中序值较小的个体遗传给下一代,当种群中两个个体的序值相同时,为了保持种群个体基因的多样性,选择拥挤距离大的个体遗传给下一代。当种群中个体的序值和拥挤距离都相等时,选择子目标中权系数较大的个体。通过多层次的比较、分析逐步对个体进行适应度排序,淘汰适应度小的个体,选择种群个体中适应度较高的遗传给下一代。
2.4交叉操作
种群中的个体通过按一定的交叉概率,将染色体上的基因随机的交叉,得到新的个体,增加了种群基因的多样性。随机从种群中选择两个染色体,根据染色体编码的方法,先取出染色体的前半部分,其长度为∑Ni,采用双点交叉的方法,随机的设定两个交叉点进行交叉操作。交叉后会出现某些工件的工序多余,某些工件的工序缺失,因此,需要按照原有基因将交叉后的基因对应的设备顺序进行调整。
2.5变异操作
根据种群个体前半部分染色体的长度随机的产生两个之间的整数i和j,将前半部分的i,j基因互换。在互换后的个体中按一定的变异概率随机的选择个体进行变异操作,并将对应的设备编码做相应的调整,产生新的个体,从而淘汰适应度较小的个体,达到进化种群的目的。
2.6解码操作以及终止代数的确定
本文采用的染色体解码方法是全自动动解码方法。对于给定的一个染色体S而言,先计算其基因个数,然后取其基因的前半部分,根据解码公式进行解码。例如染色体S[3 2 1 4 1 3 2 4 2 3 4 3 1 2 2 4],共有16个基因,因为采用的是基于加工工序和加工设备的两层编码方式,所以取其基因的前半部分,共有8个基因分别为[3 21 4 1 3 2 4]。从上述基因中可以看出有4种工件,工序总数为8,分别根据下面程序进行解码。
关于终止代数T的确定,本文采用综合评价指标相对偏差值确定。令表示遗传算法运算第t代后第j种调度方案的综合评价指标,则终止代数T可由下式确定:
2.7改进遗传算法
传统的遗传算法采用的是隐性精英解保留策略,虽然保证了种群个体基因的完整性,但是在求解多目标问题的时候,可能会使Pareto解集出现过早收敛的现象。本文对Pareto解集采用改进的是三层评判标准的选择策略,首先通过计算序值,其次计算拥挤距离,最后根据各目标的模糊评价决策得到的综合评价指标进行排序,选择最优的Pareto解集。改进的遗传算法流程图如图1所示。
3实例分析
本文以大连市某企业空调制造车间为例,该车间某一时刻的10个工件需要在10台设备上加工,每个工件都要经过6道加工工序,具体数据如表1~表5所示:
本文的遗传算法参数为:种群中个体数目500,种群进化代数500,种群代沟0.8,交叉概率0.6,变异概率0.1。
经计算所得,传统遗传算法得到的pareto解集中最优解对应的最小加工时间为60分钟。
采用基于最优保存策略、序值排序、拥挤距离计算、综合指标排序、适应度函数转化以及工件加工工序和设备的两层编码方式的改进遗传算法的实例测试如图2和图3所示。
由于篇幅有限,本文只摘取6组比较优越的pareto解,如表6所示,然后通过AHP综合评价选择最佳的调度方案。各子目标的权重为:ω=(0.358, 0.2003,0.0872,0.2396,0.0461,0.0257,0.0431)T,最终选择调度方案3。
经计算所得的,改进遗传算法得到的pareto解集中最优解对应的最小加工时间为53分钟。根据计算结果可知,改进后的遗传算法的综合评价指标比改进前的优越。所以本文的调度方案更加适应解决离散车间多目标调度问题。
本文对车间的设备进行环形布局优化,建立如下数学优化模型。
s.t.
其中,wij为设备i到设备j的当量物流量,是根据工件加工工艺线路转化的,例如,工件1的加工工艺路线为3-1-2-7-8-5,则w31=w12=w27=w78=w85=1 。xij为0,1变量,如果设备i在生产线上的位置排在设备j前,取值为1,否则为0。目标函数(19)在保证所有工件加工完的前提下,使整个车间的逆向搬运物流量最小;约束(20)设备相对位置的约束,约束(21)确保设备位置在传递过程中不出现矛盾。
经计算得到图4加工设备环形布局图,其中(1)和(2)两个方案工件总的逆向搬运物流量都为17,总的无效搬运量都为237。与优化前的车间布局(设备摆放位置为1-2-3-4-5-6-7-8-9-10)相比,总的无效搬运量从270减为237。
4结束语
本文首先采用传统的遗传算法对空调制造车间10×10的案例进行求解,然后采用本文所提出的改进的遗传算法对上述给定的案例进行求解,通过对比两个方案的综合评价指标,可以证明本文提出的改进的遗传算法在求解同一车间调度问题中的优越性。最后根据车间调度确定的工件加工工艺路线,实现了对现有车间制造设备进行环形布局优化。
摘要：针对车间生产调度人员需要进行多目标的调度决策,以大连市某企业空调制造车间为例,首先建立了以最大完工时间最小、总延期时间最小、总提前期时间最小、设备总负荷最小、单台设备的最大负荷最小、总生产成本最低、工件搬运次数最少的多目标车间调度模型。然后提出了基于工件加工工序和加工设备的两层编码的改进遗传算法,再次通过层次分析法确定各个子目标的权重,对不同量纲的子目标进行模糊无量纲化处理,并通过综合评价指标确定pareto解集的最优调度方案。最后根据工件加工工艺线路对车间设备进行环形布局优化,建立了环形布局优化模型,并通过实例分析验证了该算法的可行性。
车间作业调度 第5篇
本标准规定了检修分公司检修分公司修配车间调度的岗位职责、岗位技能、工作目标、工作内容、检查与考核规则。
本标准适用于检修分公司检修分公司修配车间调度岗位的工作。规范性引用文件
下列文件中的条款通过本标准的引用而成为本标准的条款。凡是注日期的引用文件，其随后所有的修改单或修订版均不适用于本标准，然而，鼓励根据本标准达成协议的各方研究是否可使用这些文件的最新版本。凡是不注日期的引用文件，其最新版本适用于本标准。
全面实行劳动合同制劳动合同管理办法。岗位职责
3.1岗位关系
3.1.1 本岗位主要对检修分公司修配车间副主任负责。3.2 责任
3.2.1
负责完成属于机械制造专业范围内生产任务的调度、技术指导工作。3.2.2 对公司下达的各项任务的完成情况、工程质量、进度负责。3.2.3 承担因本人工作失误所造成的直接责任。3.3 权限
3.3.1 在主任、副主任授权的范围内和本岗位职责范围内有指挥决策权。
3.3.2 有权根据工作需要对车间内部的班组设置及班长、技术员的任免提出调整建议。
3.3.3 有权制止任何违反《电业安全工作规程》和《电气设备检修工艺规程》规定的施工作业。3.3.4 有权根据公司的有关规章制度对员工提出奖惩建议。
3.3.5 有权在管理评审中根据车间的质量体系要素及上次管理评审中确定的纠正或预防措施完成情况进行报告。
3.3.6 有权了解与本部门有关的数据和资料及参加本厂各种与本专业有关的会议。3.3.7 有权决定和处理职责范围内的各种日常事务。岗位技能
4.1 基本条件
4.1.1 爱岗敬业、遵纪守法、廉洁奉公、作风正派。
4.1.2、具有大专及以上文化程度或取得本专业中高级职称（或具有相当大专及以上的文化程度、取得岗位合格证书）
4.1.3 身体健康，能适应本岗位工作。4.1.4 从事本专业工作五年及以上。
4.1.5具有较强的组织能力和决策能力，4.1.6 有较好的群众基础。4.2 专业知识
4.2.1 有较丰富的检修分公司修配车间工作实践经验和管理经验。4.2.2 熟悉发电厂的生产过程，了解发电厂主要设备的工作原理。4.2.3 熟悉本车间设备的工作原理、构造、规范、性能。
4.2.4 掌握机械制图、机械制造、金属材料及焊接技术等理论知识。
4.2.5 熟悉《电业安全工作规程》、《电力生产事故调查规程》以及《机械加工操作规程》和消防规程中与本专业有关的条文规定。
4.2.6 掌握企业管理、ISO 9001标准的一般知识。
4.2.7 掌握人事管理和财务管理知识。
4.2.8 了解新技术、新工艺、新材料和新设备的应用知识。
4.2.9 了解《安全生产法》、《环境保护法》、《劳动法》《电力法》、《 合同法》、《企业法》等有关的法律、法规。4.3 实际技能
4.3.1 能看懂本车间设备的系统图和机械装配图。4.3.2 能组织实施较大项目的加工制作任务。
4.3.3 能编制本车间加工机件的安全、质量、进度要求。4.3.4 能掌握各班组机加工的工时定额。4.3.5 能组织技术革新，解决疑难加工问题。
4.3.6 能合理安排生产任务，制定加工工艺要求，提高工作效率。4.3.7 能合理组织协调各班组工作。
4.3.8 能正确判断和处理本专业设备异常问题。
4.3.9 具有较强的协调沟通能力和语言文字表达能力。4.3.10 能够熟练应用计算机进行本专业的工作。工作目标
5.1 管理目标
5.1.1 协助车间完成所管辖范围内的文明施工。5.1.2 完成机组维护和检修机加工任务。
5.1.3完成检修分公司的外创检修及维护任务。
5.1.4 完成××厂、检修分公司各部门及队部下达的各项任务。5.2 安全生产目标
5.2.1 不发生机组重要机件的废次品。
5.2.2 不发生个人和班组责任的二类障碍及以上不安全事件。5.2.3 本人实现三不伤害，控制异常和人身未遂事件的发生。工作内容
6.1 周期性工作
6.1.1 开工前布置各班组生产及其它工作任务。
6.1.2 布置生产的同时布置安全注意事项，坚持“五同时”。
6.1.3 定期对车间重点工作现场进行巡视检查，了解重要工作的进度、质量、安全及文明生产状况，发现疑难问题现场协调、指导。
6.1.4 每天将各班组重要的生产及劳动管理的信息汇报相关领导。6.1.5 定期参加本车间组织的各种会议。
6.1.6 定期参加安全活动、政治学习、民主生活会等。
6.1.7 编制机件加工制作工艺卡，检修工艺和质量达到标准要求。指导班组积极开展技术革新活动。6.1.8 每周参加班长会议，协调车间工作，研究解决生产上的主要问题。6.1.9 协助车间技术员加强各班组技术管理，开展一专多能培训。6.1.10 选择正确的工艺路线和加工设备，指导机加工班组安全生产。6.1.11 组织机件检验，质量检验记录准确齐全及时，保证机组安全。6.1.12 每年按上级要求做好春季、秋季安全大检查。6.2 非周期性工作
6.2.1 负责其它单位配合工作和临时工作的安排与组织。6.2.2 指导班组积极开展技术革新活动。
6.2.3 车间技术员外出或休假期间代理完成技术员工作。6.2.4 其它各种行政事务性工作。6.2.5
完成领导交办的临时性工作。检查与考核
7.1 按本《工作标准》和公司有关规章制度进行检查与考核。 7.2 按公司《经济责任制具体方案》进行检查与考核。 7.3 接受主管领导和有关部门的检查与考核。
车间作业调度 第6篇
作业车间调度问题 (jobshopproblem, JSP) 可描述为:加工系统中有n个工件和m台机床, 各工件均不重复的经历所有机床加工, 问题是如何安排生产, 使得生产周期最短[1]。JSP是许多时间调度问题的简化模型, 是一个著名的NP调度问题, 因此对其研究具有重要的理论意义和工程价值。
本文利用蚂蚁算法来求解JSP问题, 针对蚂蚁算法执行效率较慢这一问题, 提出了利用启发式信息来生成一些初始解, 利用初始解来初始化蚂蚁经过路径上的信息数, 这样就把一些好的信息事先放在了蚂蚁要经过的路径上, 有助于引导蚂蚁较快找到最优解, 提高算法效率。
1作业车间调度问题形式化定义
加工设备集M, 用来加工每个工件。加工工件集N, 其中工件又由多个加工工序组成, 对加工工序从1开始编号, 对应于同一工件的工序号按照约束关系由小到大编号。规定:
(1) 每一工序由特定机器完成;
(2) 每台机器不能同时加工不同的工序;
(3) 同一时刻, 同一工件的不同工序不能同时加工;
(4) 求出从第一个工序的加工开始到最后一个工序完成的最下完成时间 (makespan) 。
为了便于用蚂蚁算法来解决JSP问题, 根据工序之间的约束关系将问题描述为满足一定条件的有向无环图 (Directed Acyclic Graphs, DAG) , 以G= (V, E) 表示。结点集V={V1, V2, , Vn} (n≥1) 中的结点与工序对应;有向弧E代表了工序间的先后约束关系, 即若任意<Vi, Vj>∈E, 则称Vi为Vj的前驱, Vi应该先与Vj生产, 只有等Vi加工结束后Vj才可开始加工。对没有工序约束的两工序节点之间增加一条无向边, 表明这两个工序的加工顺序不受限制。
2初始解的求解方法
首先根据图论理论, 对每个工序i都有一个深度值, 记作D (i) , 定义为:
其中Pi为工序i的前驱工序, max{D (Pi) }返回工序i的前驱工序的最大深度。根据各个工序的深度值, 和工序与加工设备之间的对应关系, 把相应的工序分配到对应的设备上去, 具体的步骤为:
第一步:不考虑工序间的约束关系, 根据工序与设备之间的对应关系把工序分配到相应的设备上去。
第二步:对每台加工设备, 根据每个工序的深度值大小由小到大对工序的加工顺序进行排序。在排序过程中, 如果两个互不相关的工序的深度值相同, 且在同一个设备上进行加工, 则他们的排序可依据两条原则:即:基于父节点优先原则和短任务优先原则。
基于父节点优先原则按照是父节点的工序优先加工的原则排序工序, 这样就可保证其后的孩子节点也能较早的加工。而基于短工序优先加工则按照占用设备加工时间最短的任务优先加工的原则排序工序, 这样就可能尽早的完成尽可能多的加工任务。在两个原则都满足的情况下, 优先考虑基于父节点优先原则。这样就形成了初始解。同时还可依据一些其他的启发式信息生成一些初始解。
3蚂蚁算法的描述
蚂蚁算法 (Ant Colony Optimization ACO) [2,2,3]是意大利Dorigo等人于1991年创立的, 是继神经网络、遗传算法、免疫算法之后的又一种新兴的启发式优化算法。蚂蚁算法最初是从研究旅行商问题提出的[4], 目前被用作求解QAP[5]、JOB shop[6]等离散系统的组合优化问题。
试验证明, 由于较优解信息的匮乏, 蚂蚁算法在起始阶段很长一段时间处于盲目状态, 算法执行效率较慢。为了提高算法效率, 本文根据一些启发式信息生成一些初始解, 利用这些初始解初始化所经过路径上的信息素数量, 它们的初值比其他路径上的信息素初值要大, 这样蚂蚁就在一种启发式信息的引导下较快的找到最优解, 提高了算法效率。
3.1初始化参数
设NC=循环次数;AN=蚁群数目;ρ=挥发系数;τij 代表从节点工序i转到节点工序j的信息素, 初始时, 首先设所有的τij=C (C是一个常量且大于0) , 对于初始解中存在的路径上的信息素, 都按公式τij=τij+b (b>0) 来初始化, 这样, 初始解的良好性能将在蚂蚁寻找最优解的过程中从一开始就发挥了作用, 避免一些劣质解影响了蚂蚁的判断, 从而提高算法效率。
3.2算法运行步骤
步骤1: 首先放出AN只蚂蚁, 为了保证操作符和工序调度顺序, 每只蚂蚁在寻找路径过程中, 首先判断目的节点的前驱节点是否已经过, 在前驱节点已完成且本身尚未完成的节点中利用信息素浓度作为概率选择下一节点, 蚂蚁选择下一节点的概率按公式 (1) 来计算。
(1) 式中, τij (t) 为从节点i调目的节点j的信息素。
重复进行, 直到蚂蚁走完所有的节点, 一个解就形成了, 重复AN次, 这样形成了AN个解。
步骤2:解码算法对每解径求makespan。
具体算法如下:
步骤3:判断算法是否应该结束, 如果已经收敛于最优解或达到最大蚂蚁代数, 则退出循环并返回算法结果;否则, 按照公式 (2) 的规则修改蚂蚁经过的所有路径上的信息素数量
(2) 式中
(3) 式中
Q为常量且大于0, f (k) 是第k条蚂蚁经过的路径的makespan值, 如此路径经过了从节点i到节点j的路径段, 则将路径i到j上的信息素数量增加
4仿真结果及分析
对上述算法, 构造了仿真环境, 用实例来验证算法的可行性和有效性, 仿真实验在PIV2.93G/516M内存的计算机上进行, 用C++编写程序, 以基准问题Muth&thompson的66基准问题为例, 表1将实验结果与传统ACO算法, 文中的算法在较少代数中得到了问题的最优解, 算法效率得到大幅度提高。
经过反复的运行得出结论, ACO算法在起始阶段不能迅速找到最优解, 原因在于初始阶段受不确定信息影响较大, 因此需要花很长时间才能确定较优解的寻优方向, 因此这降低了算法的效率, 本文根据启发式规则给出一些初始解, 利用他们来初始化路径上的信息素, 相当于在一开始就将优质解的一些信息通过信息素体现了出来, 从而使得蚂蚁在好的信息的影响下一开始就朝着较优解的方向前进, 从而提高了算法的效率。
摘要：讨论了蚂蚁算法在车间作业调度问题中的应用, 针对传统蚂蚁算法执行效率较低的特点, 首先分析了影响因素, 然后针对这些因素提出了改进方法, 通过运行实例仿真说明本算法的有效性和可行性。
关键词：蚂蚁算法,有向无环图,生产调度
参考文献
[1]Cheng R W, Gen M, Tsujimura Y.A tutorial survey of job shop scheduling problems using genetic algorithms, part II:hybrid genetic search strategies.Computers&Industrial Engineering, 1999;32 (2) :343—364
[2]Dorigo M, Maniezzo V, Colorni A.The ant system:optimization by a colony of cooperating agents.IEEE Transactions on Syetem, Man and Cybernetics-Part B, 1996;26 (1) :29—41
[2]段海滨.蚁群算法原理及其应用.北京:科学出版社, 2005
[3]汪镭, 吴启迪.职能蚁群算法及应用.上海:上海科学技术出版社, 2004
[4]Dorigo M, Gambardella LM.Ant colonied for the travelling salesman problem.Biosystems (S0303-2647) , 1997;43 (2) :73—82
[5]Stiitzie T, Dorigo M.ACO algorithms for the quadratic assignment problem.NewMethod in Optimization.London:McGraw-Hill.1999:3—50
一种改进的车间调度问题算法 第7篇
遗传算法是一种模仿生物进化过程的随机方法,具有较强的问题求解能力,能够解决非线性优化问题。车间调度是指根据产品制造的合理需求分配加工车间顺序,从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题一般描述为:n个工件在m台机器上加工,给定各工序的加工时间、加工次序约束和可供选择的机器约束,在满足各项约束的条件下,确定每台机器上所有工件的加工次序及加工开始时间和结束时间,以达到最优加工性能指标。该问题是典型的生产调度问题,属于NP完全问题[1]。
目前,解决该问题的方法[2,3,4,5,6,7,8,9,10,11,12]有启发式算法、回溯法、分支限界法、智能计算方法等。这些方法中遗传算法的研究成果比较多,依据车间调度问题的特点,提出一种基于两层编码遗传算法的车间调度算法,旨在提高车间调度的性能。
2 数学模型
建立数学模型之前,做以下假设:(1)每个工件的各工序在某台机器上加工时间确定,并且工序不能分割。也就是说某工序在某台机器上一旦开始,将不能中断,直到该工序结束为止;(2)一个工件的各工序不能并行处理,只能串行;(3)各工序在某台机器上互斥处理,即一台机器可处理多个工序,但同一时间只能处理一个工序;(4)在机器忙时,允许工件等待;在工件未到达时,允许机器空闲。为此,选用集合建立车间调度的数学模型,具体如下:
(1)机器的集合M={mj|mj为机器序号,j=1,2,,m};
(2)工件集合J={Ji|Ji为工件序号,i=1,2,,n};
(3)工件的工序集合,OP={opi|opi为工件i的工序序号集合,i=1,2,,n },opi={ opij|opij为工件i的第j工序,j=1,2,k};
(4)opij={opijr|opijr为第i工件的第j工序可以选择的加工机器序号,r=1,2,3,,s,其中sm};
(5)用tij表示第i工件的第j工序在可供选择机器上加工所需相应时间的集合,机器加工工件的时间用时间矩阵T表示,T=(tij)nm。
3 两层编码遗传算法
3.1两层编码格式
根据车间调度的目标,采用自然数编码方法,每个染色体表示问题的一个可行解,即全部工件的加工顺序及其对应的机器。染色体包括两层编码,第一层为所有工件工序的加工顺序,第二层为工件的每道工序被处理的机器序号。假设待加工的工件数为n,每个工件包含k道工序,则染色体的编码长度为包含2nk个自然数的串。如个体X=[1,2,3]1 2 2,2 1 2, 1 1 2,2 2 1, 1 1 1,2 1 2]表达了3个工件,每个工件6道工序,2台机器上的加工顺序,其中“|”之前为第一层编码,“|”之后为第二层编码。第一层编码描述的加工顺序为:工件1工件3工件2工件1工件2工件3工件2工件1工件3工件2工件3工件1工件3工件1工件2工件3工件2工件1,同一工件的多次出现依次代表该工件的不同工序;第二层编码表示加工机器,依次为:机器1机器2机器2机器2机器1机器2机器1机器1机器2机器2机器2机器1机器1机器1机器1机器2机器1机器2。
3.2适应度度量
车间调度要求全部工件完成时所需要的加工时间最短,故选用全部工件的完成时间作为衡量染色体优劣的标准。设工件总数为n,每个工件有k道工序,m台机器,X[1:2nk]表示单个染色体,T[i][j]表示第i工件的第j道工序在可供选择的加工机器上加工所需相应时间,适应度值的计算公式为fi=1/T,其中T指全部工件完成的时间,T越小,fitness越大,染色体越优。
3.3选择算子
选择算子采用轮盘赌法选择适应度较好的染色体,个体的选择概率为
其中,p(i)表示染色体i在每次选择中被选中的概率,NIND为种群规模。
3.4交叉算子
采用两点交叉获得新染色体,首先从种群中随机选取两个染色体X和Y,产生1～nk之间的两个随机数pos1,pos2;不妨设pos1< pos2,个体X[pos1:pos2]与个体Y[pos1:pos2]进行交叉,交叉后可能出现一些工件的工序多余,而有些工件的工序缺失,此时需要将缺失的工件工序代替多余的工件工序。如:
X=[13112322323131|12121211222112];
Y=[13321321323121|12211211212121]。
pos1=3,pos2=6,则“1123”和“3213”为交叉区域的基因,交叉后形成的新个体X1和Y1为:
X1=[13321322323131|12121211222112];
Y1=[13112321323121|12211211212121]。
个体X1中多余的工序为工件3的工序,缺失的工序为工件1的工序。个体Y1中多余的工序为工件1的工序,缺失的工序为工件3的工序,用缺失的工件工序代替多余的工件工序,得到X2和Y2:
X2=[13321122323131|12121211222112];
Y2=[13132321323121|12211211211211]。
这样调整得到的染色体X2和Y2中,“|”之前的第一层编码为正常编码,“|”之后的第二层编码所表示的机器序号与第一层编码所表示的工件工序已不再一一对应,这将导致某些工序所对应的机器序号不是可供选择的机器序号,进而也无对应的该工序在机器上的处理时间,导致适应度计算时出错。因此,需要将交叉区域的工件工序对应的机器序号进行调整,X2中pos1和pos2之间的基因对应在它的第二层编码的机器序号调整为X中pos1和pos2之间的相同基因对应在X的第二层编码的机器序号。即X2中的3、2、1、1对应的机器1、2、1、2分别器调整为X中的2、1、2、1机器,Y2中的1、3、2、3对应的机器2、1、1、2分别器调整为X中的1、2、1、2机器,调整后的染色体X3和Y3为:
X3=[13321122323131|12212111222112];
Y3=[13132321323121|12121211212121]。
3.5变异算子
采用单点变异,从种群中随机取一个个体Z作为待变异的个体,产生1～nk之间的两个随机数pos1,pos2,然后将个体Z第一层中pos1和pos2指示的自然数基因交换,同时调整与pos1和pos2指示的自然数基因相同的所有基因对应的第二层编码中的机器号。如
Z=[13112322323131|12211212112112]
pos1=5,pos2=14,则变异后的新个体Z1为:
Z1 = [13111322323132|12211212112112];
在Z1中,由于第一层编码的两个基因进行了交换,导致第二层编码中与被调整基因相同的基因对应的机器序号不再一一对应。故要调整这些机器序号,即用Z的第一层编码中基因1依次对应的机器序号1、2、1、1、2替换Z1的第一层编码中基因1依次对应的机器号1、2、1、1、1;用Z的第一层编码中基因2依次对应的机器序号1、1、2、1替换Z1的第一层编码中基因2依次对应的机器号1、2、1、2,调整后的染色体Z2为:
Z2= [13111322323132|12211211122211]。
4 算法步骤
步骤1:生成初始种群,种群规模为NIND;交叉概率pc、变异概率pm,迭代次数为MAXGEN,置i=1。
步骤2:按照适应度度量,计算每个个体的适应度。
步骤3:采用轮盘赌法选择适应度较好的染色体。
步骤4:根据交叉概率pc选择父代个体进行交叉操作。
步骤5:根据变异概率pm选择父代个体进行变异操作。
步骤6:i++;如果iMAXGEN,则转步骤2;否则,输出最优解,算法结束。
5 仿真实验
为了验证算法的有效性,采用文献[13,14]中的实例和一个自选实例,每个实例数据中,表内各工件对应的第一行是机器序号,第二行是加工时间,实例具体数据如下:
[实例1] 文献[13]中的实例,设工件数n=6,每个工件有6道工序,机器数M=6,每个工序可选择的机器/工序加工时间如表1所示。
设定种群规模NIND=40,交叉概率pc=0.8,变异概率pm=0.1,最大迭代次数30代。本文算法搜索过程如图1所示。
[实例2] 文献[14]中的实例,设工件数n=8,每个工件有5道工序,机器数M=5,每个工序可选择的机器/工序的加工时间如表2所示。
种群规模、交叉概率、变异概率的设定同实例1的设定值,最大迭代次数60。算法的搜索过程如图2所示。
运行结果与文献[13,14]的结果对照如表3所示。
由表3可知,本文提出的算法与文献[13]和文献[14]相比,求解质量和求解速度均有提高,并且提高的程度在实例2的结果中表现更为突出。分析实例1和实例2的数据可以发现,这两个实例给出的每道工序可供选择的机器只有1台,而事实上,每道工序可供选择的机器可能有多台。针对这种情况,文献[13]和文献[14]均没有给出实例验证算法的有效性,因此,也不明确这两篇文献的算法在该情况下的有效性,而本文提出的算法却是十分有效的,实例3的仿真结果可以说明这一点。
[实例3] 设工件数n=6,每个工件有6道工序,机器数M=10,每个工序可选择的机器/工序的加工时间如表4所示。
各参数设定同实例2。该算法的搜索过程如图3所示,最好解的工件加工甘特图如图4所示。
6 结束语
由仿真实验结果可以看出:(1)提出的编码方案能够清楚的反映调度方案;(2)算法不仅适用于每道工序有1台可供选择机器的情况,也适用于每道工序有多台可供选择机器的情况;(3)全部工件的完成时间和平均完成时间随迭代次数的增加不断优化;(4)收敛速度快,求解质量高。通过比较,该算法的求解速度和求解质量是比较满意的,有广泛的实际应用前景。
车间作业调度 第8篇
混流加工车间生产调度问题 (Mix Flow WorkShop Scheduling Problem) 是具有一定难度的生产调度问题, 它的研究目的是对生产资源进行优化配置, 根据已知各个生产工序的加工时间及加工设备的情况, 在满足约束条件的限制下, 使生产资源得到优化配置, 使得订单产品的某项指标 (机器的完工时间、批量响应时间、延迟时间及生产成本等) 达到最优。针对现阶段客户对批量响应时间越来越短的要求, 将生产物流过程的瓶颈与响应时间联系起来, 可知影响客户订单响应时间延长的环节为生产物流时间瓶颈, 时间瓶颈已成为影响订单准时交货的严重阻碍, 基于时间瓶颈的加工车间调度问题的研究成为必然。
目前关于生产物流过程的时间瓶颈研究较少, 且研究重点主要放在加工单元的瓶颈辨识, 相关研究文献有:陈杰、赵伟等[1,2]提出基于约束理论的混流生产调度研究, 通过建立仿真模型来辨识瓶颈资源;李修琳、鲁建厦等[3]基于混流混合车间展开了协同调度研究, 建立了以在制品成本为最小目标的混流混合车间调度问题模型, 分别对零件加工、部件装配和产品总装3个加工单元进行详细分析;叶明[4]展开了对混合流水线生产计划与调度问题的研究, 构建了基于产品控制和在制品动态调整的混流装配生产计划与调度体系结构;上述关于混流生产模式的调度研究, 主要集中在串行生产线或组装生产线的加工单元上, 通过生产线中的相关性建立模型[5], 而很少考虑到运输单元, 虽然有的文献提出将运输单元看成是广义的制造单元, 并与其他制造单元进行比较, 但是在建模中将运输单元的物流能力假设为无限能力[6], 而没有考虑到运输单元的实际生产状况。
由于生产物流过程中的各种不确定性, 导致时间瓶颈呈现动态性, 在这种情况下, 要基于时间瓶颈来做好生产系统的调度工作, 提高生产系统的性能, 因此需要建立基于时间瓶颈的加工车间调度模型。本研究拟开展对加工单元中批量响应时间组成的研究的同时, 也对运输单元中批量响应时间组成进行研究。
1 加工车间调度模型建立
本研究将运输单元和加工单元分别单独进行讨论;运输单元主要考虑的是产品以批量运输方式到达加工单元前所选择运输路径对应的运输时间问题, 若在所有的运输路径中, 选择的运输路径并非最短, 那么运输单元的运输时间有可能成为时间瓶颈环节, 因此需要对运输路径进行调度, 尽量选取最短路径进行运输, 从而降低批量响应时间;加工单元采用混流生产方式进行生产, 当订单产品以批量运输形式到达之后, 随机进行生产排序, 且产品加工采用单件流的形式向下一道工序传送, 每个产品都经过m道工序 (也包括只流经而不加工的工序) , 当所有产品批量加工完后, 对订单的响应时间影响最大的产品为时间瓶颈环节, 再细分到产品加工的某道工序对订单的批量响应时间影响最大的为时间瓶颈工序环节;找到时间瓶颈环节之后, 对产品加工排序进行重新调度, 可得到更优的生产计划;现给出一条混流加工生产线如图1所示。
图1需要到达的目的地为加工单元Z, 设定运输单元的运输时间定义为产品从上一加工单元Z-1运送到下一加工单元Z所经过的最短路径时间, 且混流加工单元为流线型生产线 (即直线型或U型线) , 工序于工序之间传递时间 (单件流动) 忽略不计。综上由运输单元和混流加工单元构成的生产物流过程, 分别对运输单元和加工单元的时间瓶颈进行辨识, 并最终建立以最大批量响应时间最小化为优化目标的加工车间调度模型。
1.1 加工车间的时间瓶颈确定
1.1.1 加工单元时间瓶颈确定
假设有一个包含n个产品品种的订单和一个m道工序的混流生产线:Mj为第j个品种的加工批量, j=1, 2, , n;stji为第j品种单位产品在i工序上的加工时间, i=1, 2, ⋯, m;Tj为第j品种单位产品在生产线上各工序中的最大加工时间, ;LTj为第j个品种的生产提前期;Qwip为在制品。本研究设定提前期为加工周期, 而且假定单个的产品品种将以一个批量进行加工和传送。因此, 可以得到第j个品种在单独进行工序j加工时的提前期和在制品表示为:
那么第j个品种完成所有工序的提前期和在制品表示为:
为了使问题不至于太复杂并遵循JIT的思想, 现本研究作如下假设:①以加工批量1进行加工, 也就是单件流的JIT加工模式;②生产方式为离散式;③设订单的n个品种以流水加工的模式都经过m道工序 (包括仅经过但并不加工的工序) ;④初始加工顺序按照既定的方案来加工。
参数说明如下:Si, j为第j个品种第i道工序的开工时间;Fij为第j个品种第i道工序的完工时间;grli, k为第i道工序上品种l转换成品种k时的准备时间;GRl, k为整个加工过程中品种l转换成品种k的准备时间最大值, 即GRl, k=miax{grli, k}。
因此, 产品每个品种的开始和完工时间分别表示如下:
第1个品种开工时间:S1, 1=0。
第1个品种的完成时间为:
第2个品种开始时间为:
第2个品种的完工时间为:
以此类推, 可得到第j个品种的开始和完工时间为:
最后, 第n个品种的完工时间 (此时订单已完成) 为:
因此得到加工单元订单产品最大响应时间CTM为:
即为时间瓶颈环节, 也就是TBN=max Tl;st1i和Ml均为常量。
1.1.2 运输单元时间瓶颈确定
运输时间按照单元间的批量运输时间来计算, 一次性运输下一个加工单元所需的产品品种数和数量。现假设从出发点I需要经过a个加工单元才能到达输出点O (即目标加工单元) ;为了简化模型, 对于每一个加工单元规定:I点和O点分别位于单元矩形每条边的1/2处, 且两点均为对边位置, 那么进出口位置只有两种情况;引入一组决策变量 (Iv, Ov) 来简化表达, 即:
单个加工单元的布局只有两种位置, 横放和竖放两种方式。
参数设计如下:
设有a个单元数, v=1, 2, , a;v, w均表示单元号;lvw表示单元v到下一个单元w的物流量的大小;dvw表示从单元v到单元w的物流运输距离; (xvu, yvu) 和 (xvd, yvd) 分别表示每个单元的左上角和右下角在空间的坐标;设矩形布局平面的长、宽分别为W和H;那么对应的单元长、宽分别为wv和hv;最后设定rvu和rvd分别为单元v长宽比的最大值和最小值, 且rv=max (wv, hv) /min (wv, hv) ;假定运送到混流加工单元的n (i=1, 2, , n) 个订单品种每个品种单独进行批量运输, 因为同为一个系列的产品, 因此相似性很高, 所以考虑用同样的运输工具进行运输, 运输路径也是一样的, 设运输速度为常量vp, 每个品种的运输批量为[Qi] (i=1, 2, ⋯, n) 。那么总的运输距离表示为:
而运输量lvw的大小可以计算为 , 那么式 (11) 改写为:
物流距离dvw根据无向图路径表示为:
那么订单的n种品种一次批量经由出发单元到达加工单元所用的运输时间的数学表达式为:
对于每两个单元v到w的运输距离dvw可以根据无向图的方法求得, 假设起点和终点分别为距离进出口最近的加工单元。一般情况下运输批量和加工批量的大小成倍数关系, 特别是在时间瓶颈环节, 它的加工批量比较大, 为了不产生过多的在制品, 因此对应的运输批量比较小。一般批量也是固定的值, 因此批量运输的响应时间跟单元路径dvw的选择有很大的关系。即运输单元的时间瓶颈可表示为TBN=max dvw/vp。
1.2 基于生产物流时间瓶颈的调度模型建立
1.2.1 目标函数的建立
响应时间由运输单元和加工单元两部分组成, 根据统计和分析得知[7,8,9], 产品运输或停滞时间占总时间的90%~95%, 而处于加工的纯工艺时间仅占生产周期的5%~10%。因此, 将运输时间和加工时间的权重值ω1和ω2分别赋予为0.9和0.1;那么批量响应时间公式为:
1.2.2 约束条件
(1) 运输时间约束条件为:
式 (16, 17) 表示任意两个加工单元不重叠;式 (18, 19) 表示每个单元不会超出车间平面范围;式 (20) 表示单元的长宽比在合理范围内;式 (21) 表示决策变量的范围。
(2) 加工时间条件约束为:
式 (22, 23) 分别表示每台机器同时只能加工一种品种, 且产品品种加工有先后顺序制约。
2 基于生产物流时间瓶颈的加工车间调度模型求解
根据加工车间调度模型解空间大和复杂性更高的特点[10], 传统的加权系数法不能很好地解决交货期瓶颈的作业车间调度问题, 因此需要寻求一种优秀的算法对模型求解。混合粒子群算法 (Hybrid Particle Swarm Optimization) 是近年来求解独立优化问题的优秀算法, 具有良好的全局搜索能力和收敛速度, 针对作业车间调度解空间大的特征, 具有良好的优化效果。
2.1 混合粒子群算法设计
2.1.1 编码和解码设计
编码的设计是非常关键的步骤, 设计的好坏影响着算法性能和搜索效率;考虑到本研究模型为加权目标和, 因此采用分段编码法, 分别对运输单元和加工单元进行分段编码, 之后再整合。
(1) 运输单元编码和解码。
运输单元的编码比较复杂, 之前对于最短路径研究多数采用Dijstra解决此类问题;近年来随着对于Dijstra算法研究的深入, 发现随着节点数的增多, 计算量也非常大, 因此本研究弃用;运输单元时间模型相对较复杂, 为了保证编码的直观性, 该部分采用分段整数编码法, 即把染色体分成两部分:第1部分表示最短路径的顺序选择, 第2部分表示订单的n种品种的加工批量;两基因位置之间没有一一对应的关系;染色体编码结构如图2所示。
运输单元染色体的结构组成如图2所示, 其中第1部分路径选择染色体描述了从出发节点v1到目的地节点va的最短路径选择的问题, 该部分可采用0、1编码的方式, 1表示最小路径经过节点v和w之间的路径rvw, 不经过就为0;第2部分为n个产品品种所要运输的加工批量的大小, 加工批量也采用整数编码方式, 跟路径不同之处在于其基因值的含义, 由于n个产品品种为同一订单, 因此它们具有很大的相似性, 其染色体的基因值可以设置为相同。那么得到运输单元的一条完整染色体为0_1_10_20_8_10__16。
该部分的解码相对比较简单, 若得到路径的最终染色体为1_0_11, 中间省略号部分均为0, 那么最短路径即为R12+R14+Ra-1, a;加工批量的基因值代表的就是产品批量实数, 因此不需要赘述。
(2) 加工单元编码与解码。
该模型讨论的前提为在混流流水线上产品以加工批量1不间断传送到下个工序且每个产品的加工路线一致 (也包括流经而不需要加工的工序) , 而订单的n个产品品种的投产加工顺序是随机的。为方便编码和解码的说明, 在此设n个产品品种和m道工序分别为4和4, 该部分采用随机生成产品品种投产顺序的编码方式, 如图3所示。
随机染色体顺序如图3所示, 每种产品有4道工序, 第1个2表示产品2的第1道工序开始加工, 以此类推, 第4个2表示产品2的第4道工序加工完成;产品1、3、4同样的道理。
因此一条完整染色体表示为0_1_10_20_8_10__16_2_24_4_1_3_3。
解码过程是根据产品染色体的顺序来分配产品投产加工的优先顺序。首先通过基础数据, 得到四种产品的加工优先调度表, 每种产品的某个工序加工时间最长者为时间瓶颈, 解码方法比较普遍, 在此不再赘述。
2.1.2 种群初始化
在生成初始解时, 从整个搜索空间中获取初始解, 从而保证初始解的多样性;之后根据初始种群计算适应值均值和方差, 根据均值和方差的区域将初始粒子种群分类进化, 如此便克服了PSO算法单一的进化方式, 更加确保了粒子群的高质量。假设nm维粒子表示为:
初始位置为图1染色体位置, 初始速度设为0, 种群数为40。
2.1.3 适应度函数
本研究的目标函数为求解最大批量响应时间最小, 在此不做改动, 直接将其作为适应度函数, 即:
2.1.4 适应度值的计算及粒子更新
适应度值的计算直接根据公式 (24) 计算即可。
混合粒子群算法在粒子群算法更新部分采用将粒子分类进化的设计方法;在PSO算法得出全局最优之后, 由于PSO算法搜索解的单一性, 容易陷入局部最优, 因此SA算法在它的基础上继续进行粒子搜索全局最优解的迭代, 以一定的概率接受不良解, 才能保证粒子快速且多样性的收敛于最优解。
2.1.5 退温操作
根据经验设定初始温度和退火系数分别为:T0=100°C, λ=0.98;退火操作公式为:
2.1.6 终止条件
若最后达到最大迭代次数200或者降到了最低温度T1为10°C, 则结束迭代;输出最优解。其他参数为:c1=2, c2=2, c=c1+c2=4, w=0.9, rand () 为属于[0, 1]区间变化的随机数。
2.2 加工车间调度模型求解流程
本研究根据上文算法步骤分析和设计, 对基于时间瓶颈的最大批量响应时间最小的加工车间调度模型进行求解, 采用混合粒子群算法的求解流程如图4所示。
3 算例验证及算法性能评价
由于本研究以最大批量响应时间最小为优化目标, 而基于生产物流时间瓶颈的加工车间调度模型的研究却较少。因而直接采用本研究设定的目标函数和约束条件, 以Matlab7.0.1为算法的软件编程平台, 分别采用混合粒子群算法 (HPSO) , 标准粒子群算法 (PSO) 对提出的基于时间瓶颈的混流生产模式下加工车间调度模型进行求解, 以验证建立的模型和提出的算法的有效性。最后, 本研究选取生产电器装置的某公司某加工车间为研究对象, 以验证调度模型的有效性。
3.1 参数的确定
3.1.1 加工车间
将订单的零件加工车间的一部分环节抽象成混流生产方式下的加工车间, 其中需要调度的生产产品资源共6种, 分别为N1、N2、N3、N4、N5、N6。该订单主要生产插座, 6种产品的工艺流程大致相同, 每个产品的生产均采用单件流的传递方式。6个产品最多需要生产13道工序;具体为:放金工件、上铜螺钉、入袋封口。各产品的加工批量为80件, 每道工序的加工顺序和加工时间如表1所示。
注:逗号前为工序加工顺序;逗号后为工序加工时间, s。
由该车间2011年下半年度的实际加工情况可知:6种产品N1、N2、N3、N4、N5、N6每天的平均产量为8 000件、8 000件、7 200件、8 000件、7 200件、8 000件, 因此6个品种的生产数量比例大致为1∶1∶1∶1∶1∶1, 因此这里设定N1、N2、N3、N4、N5、N6的生产任务均为8 000件, 6种产品需要加工的批次均为100批。因此, 以其最小生产循环作为调度研究的对象, 产品1到6均1批, 共6批产品。
3.1.2 运输单元
现假设加工单元的上一运输环节需要经过5个加工单元才能到达, 且每任意两个进出口采用运输网络的无向图路段节点表示方法, 表示为v1, v2, v3, v4, v5, 同一批订单的产品运输批量和路径应该是一样的, 因此按照每小时运输一次, 设定运输批量为1 000件。首先给出各加工单元间的物流量, 如表2所示。
可得到任意两个I/O点之间的最短路径 (即最短距离) 如表3所示。
注:表中 (v6) 表示从I到O需要经过v6点, 没有则表示直达。
由表3和公式 (13) 可得到任意两进出口所对应的运输距离, 如表4所示。
随机生成一条路径为运输路径, 假设选择从v3到v5的这条路径。得到6种产品对应的总的运输距离为12 000 m, 加工单元运输速度按照车间内最高叉车运输速度来设定, 为20 km/h;那么运输单元的最短批量运输时间可以由公式 (14) 求得为0.6 h;当第1个产品到达混流加工车间时, 开始对需要生产的产品进行调度。
3.2 模型仿真及结果分析
在没有干扰的情况下, 随机得到初始调度。假设从产品1到产品6顺次投产, 每个产品均生产80件, 得到当前最优调度甘特图, 各实例甘特图中时间单位均为秒, 如图5所示。
图5得到了6种产品按1∶1∶1∶1生产下的甘特图, 总的生产周期为63.2 s;由甘特图可以看出, 产品3的工序M3, 8、M3, 9和M3, 10成为阻碍批量响应时间最小的时间瓶颈环节;因此在辨识出时间瓶颈的基础上, 需要对其进行优化, 对计划进行重新调度, 得到的最优调度, 如图6所示。
由图6可知:总的批量生产周期时间为63.1 s, 虽然总的响应周期优化幅度不是很大, 但产品3所产生的时间瓶颈得到了优化, 整个生产线的流程相对于初始调度更加平衡, 人员和设备避免了由不准确调度而产生的浪费。而流程总的响应时间得不到大幅度压缩的原因是由于产品3的流程跟同类型的其他产品流程出入比较大, 因此可以考虑在成本不是很大的情况下优化该产品流程或者重新设置专门的加工单元, 这样更有利于其他产品的流线型生产。由此可以看出基于时间瓶颈环节的辨识, 该调度模型不仅能够在辨识出时间瓶颈环节的同时, 也能够很好的对最优生产计划进行调度。因此验证了该模型的有效性。
3.3 算法运行结果及性能评价
通过已设计的混合粒子群算法和Matlab仿真运行平台, 得到的仿真收敛图如图7所示。
由图7分析可知:HPSO算法在前期的收敛速度比PSO算法收敛速度来的快;且PSO算法一直在最优值附近搜索, 也就是陷入了局部最优;随着优化过程的进行, HPSO算法粒子更新方式和模拟退火算法的Metropolis准则越来越体现优越性, 不仅提供了更广泛的粒子更新空间, 而且提高了粒子群体质量, 优化了算法的调度结果。当HPSO迭代到第20代时, 优化计算的数值变化幅度逐渐变小趋于稳定, 最终收敛得到全局最优解;运输单元和加工单元对应的最优目标为2 160 s和63.1 s, 订单产品的最大批量响应时间最小值为2 223.1 s。
4 结束语
针对加工车间最大批量响应时间最小化为优化目标, 本研究采用混合粒子群算法, 展开了具有生产物流时间瓶颈的加工车间调度问题的研究。给出了加工单元和运输单元的生产物流时间瓶颈确定方法, 建立了基于时间瓶颈的加工车间调度模型;根据基于时间瓶颈的车间调度模型解空间大的特点, 建立了基于SA算法的混合PSO算法, 该算法不仅具有跳出局部最优的特点而且收敛速度快;应用仿真对车间进行调度模拟, 分别采用PSO和PSO-SA对提出的加工车间调度模型求解, 研究结果表明, PSO-SA算法求解效率高且算法的稳定性好, 验证了PSO-SA算法的广泛性。
参考文献
[1]陈杰, 陈栋, 马义中.基于约束理论的混流生产调度研究[J].中国机械工程, 2007, 18 (20) :2433-2438.
[2]赵伟, 韩文秀, 罗永泰.准时生产方式下混流装配线的调度问题[J].管理科学学报, 2000, 3 (4) :23-28.
[3]李修琳, 鲁建厦, 柴国钟, 等.基于混合遗传算法的混流混合车间协同调度问题[J].中国机械工程, 2012, 23 (8) :935-940.
[4]叶明.多级混流生产线动态调度系统关键技术研究与应用[D].南京:南京航空航天大学机电学院, 2007.
[5]ROSER C, NAKANO M, TANAKA M.A Practical Bottle neck Detection Method[C].Proceedings of the 2001 Win ter Simulation Conference, Arlington, 2001:949-953.
[6]左燕, 谷寒雨, 席裕庚.大规模流水线调度的瓶颈分解算法研究[J].控制与决策, 2006, 21 (4) :425-429.
[7]郑永前, 张锦, 王伟有.自适应粒子群算法的制造单元集成布局方法[J].工业工程与管理, 2010, 15 (6) :58-67.
[8]郜庆路, 罗欣, 杨叔子.基于蚂蚁算法的混流车间动态调度研究[J].计算机集成制造系统, 2003, 9 (6) :456-457.
[9]林献坤, 李爱平, 陈炳森.混合粒子群算法在混流装配线优化调度中的应用[J].工业工程与管理, 2006, 1 (4) :53-57.
基于并行蚁群优化的车间调度研究 第9篇
车间调度问题(job shop scheduling problems,JSSP)也称为工序调度问题,目的是安排每台机器上的工件加工顺序,并满足约束条件,使制造系统某些性能指标得到最大限度地优化。JSSP是最有名的组合优化问题之一,属于NP(Non-deterministic Polynomial-time)难题。许多实际工程问题均可以与之相转化。具有建模、计算复杂性,而且具有动态随机性、多约束性、多目标性,一直是学者研究的热点。
近年来,计算智能技术因具有普遍适用性和较低的经验复杂性等优点而被应用来求解JSSP。其中,蚁群算法在作业车间调度问题等方面获得了成功的应用。文献[1]给出了解决车间作业调度问题的蚂蚁优化算法的一般步骤和模型。文献[2~4]在原有标准蚁群算法的基础上采用了新的状态转移规则。还有研究者将Palmer启发式算法、NEH启发式算法、双向调度算法等与蚁群算法结合[5~7],取得了较好的效果。但是这些研究都是借鉴蚁群算法在求解TSP问题[8]中的方法,将蚂蚁随机或均匀分布到各个城市,基于单个蚂蚁的搜索路径活动,进而再寻求全局最优解,缺乏对蚁群算法中的并行性的利用。
蚁群算法中各个体的运动是随机的,但是整个群体寻优过程中所体现出的并行性、协同性、自组织性、动态性等特点。这与JSSP的许多特点是相似的。本文借鉴蚁群活动的规律,通过蚁群中的并行、多样化寻优活动,在加速解的收敛的同时扩大解的搜索空间,以保证JSSP的更优解的突现。
1 蚁群信息素分布多样性
蚁群最优解的搜索过程可分为初期,中期和后期三个阶段,需要在“探索”(exploration)、“利用”(exploitation)、“再探索”之间建立一个平衡点[9]。
在搜索初期,小生境中可利用的经验信息还不多,这时蚂蚁运用初始启发信息,以“探索”为主;随着搜索的演进,小生境中经验信息增多,这时蚂蚁的搜索则以“利用”经验信息为主,加速解的收敛;而到了搜索的后期,要避免算法早熟、停滞的现象,就要在已有解的基础上“再探索”,以扩大解的搜索空间,使更优解得以突现。
所以,蚁群算法对经验信息和启发信息的利用是随着搜索演化进程而变化的。蚂蚁既考虑下一段路的长度,也考虑其信息素的分布强度,在相邻结点中以一定的概率选择下一到达结点。
位于结点i的蚂蚁k,按以下选择策略选择下一结点j:
其中,allowedk(k=1,2,,m)表示当前允许蚂蚁k通过的结点。τij表示散播在结点i与结点j之间的路段(i,j)上的信息素,是搜索解空间的一种趋向信息,是蚂蚁从结点i向结点j移动的动力;ηij为从结点i向结点j移动的启发函数,是评价蚂蚁个体在结点i结点j之间的路段(i,j)上的搜索代价,ηij=1/dij;α(t)用于描述经验信息的重要性,β(t)用于描述启发函数的重要性,均为正实数。
为了保证蚂蚁构造的解是相对较优的,在搜索初期,需要更多的利用启发信息,这是缩小搜索空间的需要;而在算法后期,为了保证更优解的突现,需要更多的“利用”经验信息,而淡化局部特征的影响。因此,设置,
其中α0和β0为初始设置的参数数值,取值范围同于基本蚂蚁算法,0α05,1β05。kα,kβ为两个正常数(0
为了扩展解的搜索空间,MPACO在这三阶段对不同的寻优群体设置不同的控制参数值,进行相对独立的寻优,使得各子蚁群具有不同的信息素分布模式。
2 蚁群更新信息素策略
在每一次搜索周期结束时(即所有寻优群体都搜索结束时),更新全部路径的信息素,即全局更新。全局更新考虑了每一次寻优的结果,隐含了信息反馈,将上一步得到的局部最优结果反作用于问题空间,使得算法更容易趋优。
设信息素挥发率为(1-ρ),每次寻优循环结束时路段(i,j)上的信息素强度τij(t+n)为:
Visitedij为该次循环中经过路段(i,j)的蚂蚁集合,
Lk为第k只蚂蚁在该循环中的局部最优目标函数值。
因为经验信息和启发信息的利用是随着搜索演化进程而变化的,所以信息素强度采用时变函数Q(t)。Q(t)随着搜索逐渐变大,更新量也逐渐变大。根据局部最优解计算全局信息增量。
kQ的取值依据经验。一般取为和kα、kβ同一个数量级,使得Q(t)的变化不太大。
全局更新后,继续迭代直到满足停止条件。停止条件为最大迭代次数或解处于停滞状态。
3 车间调度问题
典型规模的静态JSSP可以描述为:有n项加工任务T={T1,T2,,Tn}要在m台机器M={M1,M2,Mm}上加工,每项任务都有若干项有序的加工工序,每台设备分别完成不同的工序。每项任务在每台机器上不间断地加工一段时间,一台机器任何时刻都只能最多加工一个任务。在满足约束条件的前提下,将每一个工序分配到对应机器的某个工作时间段,使得调度目标趋于优化。
JSSP具有两类固有的约束特点。一类是体现为逻辑上串行的任务自身的工序约束,第二类是通过对任务的并行选择而得到对机器的独占性约束。串行的工序约束体现了同一任务的工序之间的串行时序关系。独占性约束体现加工队列中不同任务之间的并行时序关系。
JSSP可用非连接图表示[10]。非连接图G=(N,A,E)的形式如图1所示。其中,N包含代表所有工序的节点,A包含连接同一工件的邻接工序的有向边,E包含连接同一设备上加工工序的非连接边。非连接边有两个可能方向。
A所包含的有向边,体现了JSSP逻辑上对任务的工序串行约束。调度将确定E所包含的非连接边的优先方向,这体现了JSSP工序对机器的独占性约束。
调度目的在于找出每台设备上的工序加工顺序,也就是确定非连接边的方向,使得其结果是非循环的(工序间无先后冲突),并且起点到终点的最大权路径的长度(最大流程时间)最小。在调度过程中,JSSP满足以下约束。
设rijk表示在机床Mi上加工任务j的第k道工序,ftijk、stijk、etijk分别表示rijk的加工所需时间、加工开始时间、加工完成时间。
任何一道工序的完工时间减去开始时间不能小于其加工时间,即,
若rimn为正在机床Mi上加工的工序,则stijk=max(stij(k-1)+ftij(k-1),stimn+ftimn)。
对于具有确定工艺路径的JSSP问题,同一任务的不同工序在逻辑上是串行的,它们之间的时序关系是确定的。工序约束表现为后一工序需在前一工序完成后才能开始,即:
若机器M={M1,M2,Mm}可加工的任务集合为MT={MT1,MT2,MTk}(0
式中,t为机器Mk的工作时间。独占性约束则要求不同任务在同一设备上的加工时间不能重叠,即一台机器任何时刻都只能最多加工一个任务。不同任务之间的时序关系具有不确定性。生产过程中,可能出现不同任务同时需要在同一设备上进行加工,形成机器的并行待加工队列。从待加工队列中选择适当的任务作为当前任务,就是一个并行选择过程。同时,整个车间的设备运行和任务分配也处于并行工作状态。
JSSP一般采用下列调度策略对车间作业进行调度求解。1)完成该批零件的加工时间最短。该调度策略的目标函数为该批零件加工完成时间最小。2)使该批零件占用加工设备的时间最短。该调度策略的目标函数为该批零件的工件流通时间最小。3)保证该批零件的交货期延时最小该调度策略的目标函数为该批零件交货延迟时间最小。4)基于准时制造思想的调度策略,保证工件在需要的时候完成加工。该调度策目标函数为该批零件的交货延迟时间与提前完成时间之和最小。
不同的实际情况要求采用相应的调度策略。通常情况下考虑尽早完成零件的加工任务,采用第一种调度策略。本文在求解动态车间调度问题时以该批零件最小加工完成时间为目标函数f,
其中,etj为任务Tj的完工时间。
4 调度算法步骤
在JSSP中存在着顺序约束,并不是每个节点都允许在初始化的时候放置蚂蚁的。并且因为JSSP的并行性,在同一时刻,可能有多个任务在加工或者选择设备。这就造成任务的工序之间和设备之间存在耦合关系。TSP中的单只蚂蚁遍历搜索方式,则较难体现这种耦合。
本文将每个任务设置一个蚂蚁。n项任务构成一个寻优蚁群,其蚂蚁数目为n。JSSP中的n项任务对设备的选择过程就转化为n只蚂蚁从起点向终点并行前进的过程。寻优蚁群中的蚂蚁全部完成路径的搜索,就构成一个调度解。设置acnum个寻优蚁群,就可得到acnum个调度解。基于并行蚁群优化的JSSP调度能够简捷地模拟刻多个蚂蚁和设备的并行活动,调度步骤如下:
步骤1,根据具体的JSSP建立非连接图G。初始化非连接图中各节点所关联的边的信息素强度。
步骤2,初始化。根据任务数量n设置寻优蚁群的蚂蚁数目n。设置总的寻优蚁群数目acnum,最大循环数目Cyclemax。寻优蚁群蚂蚁的初始出发点置于虚拟节点Nstart上。
步骤3,蚂蚁并行移动。设置寻优蚁群相应的控制参数kα、kβ、kQ。扫描当前已经搜索结束的寻优蚁群数目,如果该数目小于acnum,转步骤4。如果该数目等于acnum,转步骤5。
步骤4,扫描寻优蚁群的工序。
如果有工序未结束,则将未处于加工状态的蚂蚁加入可移动蚂蚁集AM。根据信息素分布多样性公式(1)计算AM中的蚂蚁当前各可行节点与蚂蚁所在节点之间的信息素τijα(t)和启发函数ηijβ(t),以及选择概率Pij。根据各蚂蚁的选择概率大小,采用轮盘方法(roulette wheel),对AM中的蚂蚁进行排序,得到调度顺序集AMO。根据AMO蚂蚁移动次序,确定当前可以移动的蚂蚁前往工序节点。如果该工序节点的设备空闲,则蚂蚁占用该设备。该蚂蚁标志从可移动转为工作,该设备标志从空闲转为工作,该设备加工的工序集EP记录该蚂蚁号和相应的工序号。扫描设备状态,正在加工的设备上的工序时间减1。调度时间加1。
如果工序已经全部结束,记录该次搜索结果的最小流通时间(Makespan),转步骤3。
步骤5,对acnum个寻优蚁群的搜索结果进行路径“再探索”。按照交流信息多样性策略,对这acnum个解采用遗传操作(遗传交叉,遗传变异),求出局部最优解。
步骤6,按更新信息素策略公式(5),根据设备加工的工序集EP记录该蚂蚁号和工序号,更新非连接图G中相应的路径的信息素。
步骤7,如果达到最大搜索次数,所建立的所有局部最优解中,最小值的解作为当前迭代次数的全局最优解,即最短路径的距离值。否则转向步骤3。
通过信息素分布多样性,蚁群更新信息素策略,以及寻优结果通过信息交流,实现并行蚁群优化。
5 仿真计算和分析
本文对JSP Benchmark中的基准算例[11]分别进行用本文算法、基本蚁群算法和基本遗传算法进行了计算。算法采用MATLAB7语言编写,运行环境为WindowsXP,1G RAM。对每个算例,分别独立进行20次运算,其平均结果见表1。
由表1可知,对于不同规模的JSSP,本文算法的结果比基本蚁群算法和基本遗传算法的结果更优,可以得到最优解。
6 结论
模拟蚁群的并行活动,对不同时段出发的寻优群体赋以不同的控制参数,各寻优群体分别进行相互独立的蚁群寻优,体现寻优活动多样性和并行性。各寻优群体的寻优结果通过信息交流,实现蚁群之间的寻优信息交换。整个寻优过程结束后,得到待求解问题的最优规划方案及若干次优方案。最优解的获取是多个蚁群协同进化的综合结果。在JSP Benchmark问题上的仿真结果表明,这种方法求解Job-Shop问题的结果令人满意。仿真结果说明,利用蚁群寻优的并行性能比基本蚁群算法的集中式方法有效。
参考文献
[1]赵虎,李睿.蚂蚁算法在车间作业调度问题中的应用[J].计算机工程与应用,2003,22:6-8.
[2]刘志刚,李言,等.基于蚁群算法的Job-Shop多资源约束车间作业调度[J].系统仿真学报,2007,19(1):216-220.
[3]陈知美,顾幸生.改进型蚁群算法在Job Shop问题中的应用[J].华东理工大学学报(自然科学版),2006,32(4);466-470.
[4]王万良,赵澄,等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报,2008,20(16):4326-4328,
[5]Ying Kuoching,Liao Chingjong.An ant colony system for permutation flow-shop sequencing[J].Computers&Opera-tion Research,2004,31:791-801.
[6]刘延风,刘三阳.基于蚁群优化的置换流水车间调度算法[J].系统工程与电子技术,2008,30(9):1690-1692.
[7]李燕,陈华平,等.自适应蚁群算法在双向生产车间调度中的应用[J].运筹与管理,2008,17(3):160-163,159.
[8]Marco Dorigo,Thomas Stutzle.蚁群优化[M].北京:清华大学出版社.2007.
[9]甘屹,齐从谦,等.基于蚁群算法的动态联盟伙伴选择研究[J].系统仿真学报,2006,18(2):517-520,525.
[10]玄光南,程润伟.遗传算法与工程优化[M].北京:清华大学出版社.2004.
车间作业调度 第10篇
流水车间调度(FSP)已成为一个非常活跃的研究领域。在流水车间调度中,设为N的n个无关作业被设为M的m个机器处理。这些机器按串联的顺序排序,每个作业以相同的顺序依次访问这些机器。这个顺序设为1,…,m,因此,每个作业j,j∈N由m个任务组成。作业在机器上的加工时间是确定的和非负的,被表示为Pj,i,j∈N,i∈M。FSP细节如下:
(1)所有作业是独立的,在时间为零时都可以加工处理。
(2)机器可以持续工作(无故障)。
(3)每个机器同一时间仅可以加工处理一个作业。
(4)机器一旦开始加工给定的作业,就不可以被中断,持续到加工完成。
(5)准备时间是与加工序列无关的,它包括在加工时间内或者忽略不计。
(6)作业等待缓冲区容量足够大,不会出现堵塞等问题。
FSP的目标是获得N个作业在M个机器上的加工序列,使得给定的判定是最优的。一个加工序列通常明确到每个机器,因此每个机器有n!个可能的作业加工序列,总共的可能序列有(n!)m个。一个简化的问题是假设一个相同的作业加工序列在所有机器上都保持不变,其有效防止了作业加工序列在每个机器上都重新排序一次,所以总共的可能序列为n!。这个简化的问题被称为为置换流水车间调度问题。调度判断标准使用作业在机器上的完成时间,被标记为Cj,i,j∈N,i∈M。一旦作业加工序列被确定(π(j),序列为π,作业的位置为j),完成时间就可以很容易地计算出来:
PFSP研究的仅仅是一个工厂中的调度问题,所有的作业都在这一个工厂中加工。之后提出了分布式置换流水车间调度问题,作业首先被分配到工厂,然后工厂中再进行调度。在PFSP中,问题是安排作业在一组机器上的加工顺序,DPFSP添加了一个重要的决策———作业首先要分配到合适的工厂。因此,DPFSP的两个决策是作业分配到合适的工厂和工厂中的作业调度。
分布式置换流水车间调度被称为DPFSP,其定义如下:
在之前的计算中,我们计算了工厂可能没有被分配作业的情况,在现实情景中也不可能排除这种情况,但是关于Cmax优化判断,不可能存在空着的工厂。因为如果n≤F,每个作业分配到一个工厂,这就不需要去优化。所以在DPFSP中,我们设n>F。
通过计算,我们知道DPFSP的解集数量接近普通的PFSP。当n=1时,DPFSP变为普通的PFSP,因为PFSP是一个NP—完全问题,所以DPFSP也是一个NP—完全问题。
2 分布式置换流水车间调度问题模型描述[2]
数学模型能很自然地描述问题的详细特征。描述模型以前,我们列出了模型中所需要的参数如表1所示,模型中所需要的索引如表2所示。
目标函数是使最大加工时间最小化:
模型是基于位置的分布式置换流水车间调度。对于DPFSP中的两个决策,我们定义两个不同的二进制变量集合,分别处理作业在工厂间的分配和作业在工厂内的加工序列的排序。模型中的变量如下:
Xj,k:设为1,如果作业j在位置k,否则为0。
Yk,f:设为1,如果在位置k的作业在工厂f加工处理,否则为0。
Ck,i:表示位置k的作业在机器i上的完成时间。
具体模型如下:
目标函数:
服从:
3 总结与展望[3]
一般的置换流水车间调度问题都是单工厂的模式,而现实情况是复杂的,很少有单工厂模式,所以很有必要研究多个工厂的分布式置换流水车间调度问题。但是由于现实情况过于复杂,为了化简问题的难度,我们进行了很多的假设。随着问题的不断深入研究,我们所做的假设也将渐渐减少,越来越靠近真实环境中的复杂情况。
摘要：研究一个新的置换流水车间调度(PFSP)问题,被称为分布式置换流水车间调度(DPFSP)问题。一般情况下,假设有F个完全相同的工厂,每个工厂有M个机器。N个作业分配到这F个工厂加工处理,处理顺序由每个作业分配到每个工厂时决定。最优化准则是最小化最大完成时间,现描述DPFSP的特征和模型,以便进行相应算法的求解。
关键词：分布式置换流水车间调度(DPFSP),作业调度,工厂分配
参考文献
[1]Naderi B,Ruiz R.The distributed permutation flowshop scheduling problem[J].Computers&Operations Research,2010,37(4):754-768.
[2]Naderi B,Azab A.Modeling and heuristics for scheduling of distributed job shops[J].Expert Systems with Applications,2014,41(17):7754-7763.
车间作业调度范文
声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
