【摘要】生产调度,即对生产过程进行作业计划,作为一个关键模块,是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心,有效的调度方法和优化技术的研究与应用,是实现先进制造和提高生产效益的基础和关键。改善生产调度方案,可大大提高生产效益和资源利用率,进而增强企业的竞争能力。生产调度的研究主要可分为建模和调度算法设计两方面,它是一个交叉行研究领域,涉及运筹学、数学、计算机工程、控制工程、工业设计等多个学科。其中,建模主要研究调度模型、调度规划、目标函数等内容;算法主要研究算法设计、算法的复杂性、算法的收敛性和优化质量等内容。本文就求解作业调度问题优化算法做了相关的探索。
【关键词】作业调度 优化算法 遗传算法
一、调度问题
调度问题通常指对生产过程的作业计划,譬如工件在机器上的顺序,生产批量的划分等。就生产方式而言,调度问题可以分为开环车间型和闭环车间型。开环调度问题,也称加工排序问题,它本质上只研究工件的加工顺序,即定单所要求的产品在所有机器上的加工排序,其中定单均来源于顾客,不考虑库存的设立。闭环调度问题除研究工件的加工顺序外,还涉及各产品批量大小的设置,即在满足生产工艺约束条件下寻找一个调度策略,使得所有确定的生产批量和相应的加工顺序下的生产性能指标最优,其中顾客需求的产品均由库存提供,生产任务一般只由产品的存储策略来决定。
显然,闭环调度问题较开环调度问题要复杂。鉴于批量大小与排序间的偶合性,寻求批量大小和排序的有效同时处理方案很困难,目前处理闭环问题的常用近似方法是,首先确定批量大小,然后确定加工顺序。
对于m台机器对n个工件的加工过程,所谓调度就是分配各工件在各机器上的加工时间。
二、车间作业调度问题的分类和性能指标
车间作业调度问题常按生产方式的类型分为“开环车间型”和“闭环车间型”。前者可归结为工件的排序问题,即对订单所要求的产品在每台机器上的先后加工排列次序,面向顾客;后者既包括工件的加工顺序,也包括确定工件的批量大小,即要确定与库存补充相关联的批量大小,面向库存。
根据工件在机器上的加工顺序的不同,车间作业调度问题也可分为两种:非流水型和流水型。
根据加工系统的复杂程度,可分为单机、多台并行机、Flow Shop(FSP)和Job Shop(JSSP)。
根据作业的加工特点,可将调度问题分为静态调度和动态调度。车间作业调度中涉及的工厂资源包括:原料、设备(加工、存储、运输)、人力、资金、能源等。资源的详细分配受到产品的生产工艺限制。生产调度的性能指标可以使成本最低、库存费最少、生产周期最短、生产切换最少、设备利用率最高、三废最少等。实际车间作业调度的性能指标可以归结为三类:
最大能力指标,包括最大生产率、在最短的生产周期等,他们都可以归结为在固定或者无限的产品需求下,最大化生产能力以提高经济效益。在假定存在连续固定需求的前提下,工厂通过库存满足产品的需求。因此,车间作业调度问题的主要目标是提高生产设备的利用率、缩短产品的生产周期,使工厂生产能力最大。
成本指标,包括最大利润、最小的运行费用、最小投资、最大收益等。其中收益指产品销售收入,运行费用包括库存成本,生产成本和缺货损失。
客户满意度指标,包括最短的延迟,最小的提前或者拖期惩罚等。
三、目前车间作业调度研究方法普遍存在的问题
调度领域中的大部分问题都具有NP难问题,虽然对它的研究己有几十年的历史,但至今尚未形成一套系统的方法和理论,理论研究与实际应用之间还存在着很大差距。尤其随着JI"T (Just-In-Time)思想的广泛采用提前/拖期调度问题,即使得工件尽量按交货期完成,变得越来越突出。实际应用中的调度方法虽然能够响应系统的动态变化,但不能保证得到好的调度。
由于大多调度问题属于NP困难组合问题,因此寻找具有多项式复杂性的最优算法几乎是不可能的。各种近似启发式方法、诸如基于规则的算法等,由于能在合理的时间内产生比较满意的调度,因此广泛应用于实际调度中,但其往往对所得的调度解的次优性不能进行评估。在这方面有必要探索更好的近似最优调度算法,可以考虑增加合理的计算时间代价,提高解的次优性。各种基于统计优化的方法,诸如模拟退火法、遗传算法等,提供了一种解决调度优化问题的新途径,但同别的优化算法类似,其本身也存在着一定程度的枚举,一般来说要收敛到最优解会很慢,并且对于判断解的最优性也很困难。在这方面也需要做进一步的研究。另外,还有很多有待进一步研究的问题,比如实际车间调度的多目标性、动态随机性等。
四、设计一个基本遗传算法的基本组成部分
遗传算法(Genetic Algorithm,GA)是一类借鉴生物界的自然选择和自然遗传机制的随机搜索算法,适用于处理传统搜索方法难以解决的复杂优化问题。遗传算法是由J.Holland于1975年受生物进化论的启示而提出的,它将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的迭代进化,包括复制、交叉和变异等操作,最终收敛到“最适应环境”的个体。作为一种被广泛应用的随机搜索和优化方法,遗传算法是最常用的进化算法之一。在工业工程领域,遗传算法通常被应用来解决各种优化问题。
设计一个基本遗传算法要包含有以下的基本组成部分:
编码方案。遗传算法不直接作用于问题的解空间,而是利用解的某种编码表示来进行进化。选择合理的编码机制对于算法的质量和效率有很大影响。
适应度函数。遗传算法基于适应度值进行遗传操作,因此合理的适应度值能够将各个体的优劣程度表现出来,并适应算法的进化过程。
选择策略。通常包括种群数目、交叉概率、变异概率、进化代数等。
控制参数。
遗传算子。通常包括初始化、选择(Selection)、交叉(Crossover)、变异(Mutation)和替换等操作。
算法的终止准则。终止准则应根据所求解问题的性质,在优化质量和效率方面作合理的均衡或侧重。
六、作业调度问题优化算法
(一)对作业车间调度问题的进行数学建模
作业车间调度问题的本质是建立产品的工序在每个机器上的排列,使此排列可以满足指定的工艺约束条件。因此对作业车间调度问题的进行数学建模如下:
公式1
约束(公式2)保证每个工件的工序的加工顺序满足预先的要求,约束(公式3)保证每台机器每次只能加工一个工件。
(二)设计适应度函数
对于当前的作业车间调度问题,由已确定的目标函数直接转换为适应度函数。本文设定求最小值,遗传算法适应度函数以最大表示最优,取倒数做为适应度函数f=1/eval=1/T(JM)。
(三)基于遗传算法的优化调度设计
1、染色体编码
本文采用单一编码方式,将所有工件的总的工序统一编号。例如,对于n个工件m台机器,第i个工件的工序数为 ,这样的调度问题我们可以以如下方式表示:
其中表示第一个工件的第一个工序在机床上 加工,加工时间为;表示第n个工件的第k个工序在机床上加工,加工时间为,依次类推。其中小括号内的元素作为染色体的一个基因,它是一个整体,遗传运算过程中不可分割。采用此种编码策略具有如下优点:
(1)染色体编码直接代表作业车间调度的有效解。
(2)染色体编码是一个有序编码串,将染色体编码唯一映象为一个机器工序排列阵JM。
(3)染色体编码串包含零件加工过程中的所有特征(即哪一个工件的第几个工序在哪一台机器上加工)。
(4)编码简单,利于提高遗传进化操作的效率。
(5)解决了按机器加工工序排列阵JM和加工时间阵T分别作为染色体进行编码必须要处理矩阵T和矩阵JM的相互关联性而增加的运算难度问题。
2、初始种群的选取
按照染色体编码方式,各基因是相互独立的,所以随机产生N个位数为nk的染色体串作为初始种群即可。其中每个染色体串用以上方式表示。
3、选择策略
选择策略为“轮盘赌”选择法,在该方法中,各个个体的选择概率和其适应度成正比例。令P(k)为个体k的选择概率,则
k=1,2,…,N
4、交叉算子
随机将工件集合{1,2,…,N}分成两个互补子集,相应的将个体的基因分成两个部分,分别表示为partl和part2,将两个父母个体的part2位置用h代替,得到两个新串,将这两个新串向左或向右转动任意个位置,但必须保持part1部分的操作相对顺序和相互之间的距离不变,然后用第二个父母个体的part2按照原来的相对顺序逐个替换第一个父母个体的part1产生的新串中的h,同样用第一个父母个体的part2按照原来的相对顺序逐个替换第二个父母个体的part1产生的新串中的h,得到两个后代个体。
例如:对于一个4个个体4个机器问题,假如父母个体为:
parentl:1 3 4 2 4 2 3 3 1 4 3 2 1 4 2 1
parent2:3 2 4 1 1 2 3 4 4 2 3 1 2 4 1 3
假设随机选择工件1,2,则从parentl的part l得到的新串为:
partl:1 2 2 1 2 1 2 1
part2:3 4 4 3 3 4 3 4
newl:l h h 2 h 2 h h l h h 2 1 h 2 1
则从parent2的part l得到的新串为:
partl,2 1 1 2 2 1 2 1
part2:3 4 3 4 4 3 4 3
new2:h 2 h 1 1 2 h h h 2 h 1 2 h 1 h
newl在这种情况下不能移动,因为要保证相对顺序和距离不变所以用parent2的part2替换new l的h得到一个后代个体:
child l:1 3 4 2 2 3 2 4 4 1 3 4 2 1 3 2 1
new2左移一个位置得到:
new22:2 h 1 1 2 h h h 2 h 1 2 h 1 h h
用parentl的part2代替new22的h得到另一个后代个体:
child2:2 3 1 1 2 4 4 3 2 3 1 2 4 1 3 4
5、变异算子
变异算子对每个个体的每一位按一定的概率产生新的变化,产生了新的基因型。
(四)停止准则
以预先设定的最大繁殖代数 作为停止准则。
(五)输出结果。
(六)对输出结果分析
通过进行一些实验数据可以看出,遗传算法所得到的结果是令人满意的,基本上都可以得到最优解。至于运行时间,遗传算法比多数传统程序的计算时间要长。这是因为遗传算法是一个迭代算法,而其他算法则为一次性的决策过程。不过,遗传算法在本质上是并行的,可在并行处理情况下获得较高效率。
参考文献
【1】周辉仁,基于遗传算法的作业车间调度优化求解方法,计算机应用研究 2008/10
【2】黄少荣,运用遗传算法优化车间作业调度问题,电脑知识与技术 2008/18
【3】程蓉,作业车间调度优化算法参数效能研究,新技术新工艺 2007/11
【4】彭翔,关于车间作业调度的组合优化算法,现代计算机 2004/05
【5】王万良,生产调度智能算法及其应用,科学出版社,2007.07
【6】王凌,车间调度及其遗传算法,清华大学出版社,2003.05
【7】玄光南,遗传算法与工程优化,清华大学出版社,2004.01
【8】雷英杰,MATLAB遗传算法工具箱及应用,西安电子科技大学出版社,2005.04