基于时间项调度（精选6篇）
基于时间项调度 篇1
UC/OS-II是源码开放的实时嵌入式操作系统，其主要特点如下：小巧，源码开放有详细的注解，系统透明化，可移植性强;在内核中添加关于时间片调度算法的调度依据是“任务的运行时间”，基本方法是为每个任务分配一个时间片，当任务启动时，对任务进行计时，当任务时间片运行完后进行任务调度，即切换到下一个任务。
在本算法中，可以利用UC/OS-II现有的条件，可以对任务进行控制。对于时间片调度算法的计时，在内核中中的时钟中断处理函数OSTimeTick本身就有对任务的计时功能，此外，只需要添加任务的时间片参数，以及连接多个优先级相同任务的链表，即可实现相同优先级任务的切换。至于不同优先级任务的切换，则需要人延续内核调度算法中按照任务链表轮转切换，不需要加以改进。
1 算法设计
1.1 相关数据结构的更改
OS_TASK_TIMESLICE 10：在OS_Cfg.h中增加常量OS_TASK_TIMESLICE，其值表示任务运行的时间片。在本文讨论的时间片轮转调度算法中，所有任务的时间片都是相同的。
增加全局变量：OS_EXT INT8U SamePrioNum[OS_LOWEST_PRIO+1];//同优先级任务个数
为统计同优先级任务个数以及判断同优先级是否存在，增加全局数组SamePrioNum，此数组的大小等于系统配置的最大优先级值。创建任务时，通过修改SamePrioNum[prio]的值可以方便的得到同优先级任务个数。
OS_EXT INT8U SamePrioSche;//主动调度标志
为进行主动调度，引入全局标志SamePrioSche：表示是否有同优先级任务调度的需要。若SamePrioSche为1，表示当前优先级任务有多个，并且当前任务时间片已耗尽，需要切换到下一个同优先级任务。
TCB的修改：时间片轮转调度中一个优先级是可以对应多个任务的，OSTCBPrioTbl[]的元素应该由原来的指向单个TCB改进为指向多个TCB，采用双向循环TCB链表来连接同优先级下的多个TCB块。根据时间片轮转调度在同优先级任务中的应用，需要对任务的TCB进行修改，增加3个属性项：
通过改动，由就绪表 (OSRdyTbl[], OSRdyGrp) 就能得出进入就绪状态任务中最高优先级值, 再根据最高优先级值和OSTCBPrioTbl[确定需要进入运行态的任务TCB双向循环链表, 而后对链表中的任务进行时间片轮转调度。
1.2 时间片轮转调度算法设计
1.2.1 OS＿TCBInit
任务控制块初始化只需把新添加的变量赋值即可, 首先要的就是把记录优先级任务个数的值加1, 然后初始化OSTSCurLen SamePrioNum[prio]++;//记录本优先级的任务个数
这一处是进行相同优先级链表的连接, 在优先级没有被占用的时候, 这个链表的前后都链向自己, 这样在调度的时候, FIFO调度就算指向下个任务, 也指向的是自己, 不影响优先级调度。如果此优先级的任务被占用了, 就在相同优先级的双向链表中加这个新建的tcb, 用OSTCBPrioTbl[prio]来索引前一个具有相同优先级的任务。
1.2.2 OSTimeTick
时间片调度计时的工作就放在OSTimeTick中，每个时钟tick，任务的时间片做相应的调整。只需添加以上部分内容，如果当同优先级里面有多个task，并且在此次的调度中时间片结束，就把时间片重新赋值回去，以便下一次的调度。把主动调度标志设为1，把当前的tcb指针OSTCBCur该为下一个同优先级的任务。
1.2.3 OSIntExit退出中断函数
因为UC/OS-II的调度依据是优先级，而时间片任务的优先级相同，所以必须进行“主动”调度，即调用其任务切换函数OSIntC-txSw () 。同优先级任务切换的基本条件是：当系统存在多于1个的同优先级任务，且任务优先级是当前就绪任务中最高的，也就是主动调度标志SamePrioSche=1。
1.2.4 OSIntCtxSw () 任务调度函数
这是任务调度的关键之处，而原系统优先级抢占调度方式中，OSTCBHighRdy是通过查表自动得到的，在同优先级任务调度时，OSTCBHighRdy要指向相同优先级链表的下一个任务，在此需要进行手动设置，否则将不能进行任务的切换。
2 总结
在UC/OS-II的优先级抢占式调度基础上添加了同优先级的时间片轮转调度策略，本算法最大的优点就是最大程度上保持了新操作系统与就内核的上层接口一致性。用户可以在不了解任务的具体调度实现的基础上，原来的应用程序可以不做任何修改即能运行在新系统之上，并且可以在原系统上添加更多的同优先级任务，使得UC/OS-II系统不再受到64个任务的限制，在实际应用中也不必在为相同重要程度的任务安排优先级而困扰，从而减少因多任务制约而带来的低效率编程复杂度。
参考文献
[1]成后发, 杨春金.UC/OS2II操作系统内核的改进[J].通讯和计算机, 2006, 3 (6) :52-55.
[2]赵炯.Linux内核完全注释[M].北京:机械工业出版社, 2004.
[3]吴永忠, 程文娟, 郑淑丽, 徐海卫.嵌入式实时操作系统UCOS-II教程[M].西安:西安电子科技大学出版社, 2007.
基于时间项调度 篇2
关键词：炼钢-连铸,动态调度,动态事件,时间偏差,规则
规则2缩短工序的处理时间和相邻工序间的运输时间
为了加快生产节奏, 需要对炉次j在工序k之后所有工序 (不含连铸工序) 的处理时间和相邻工序间的运输时间进行调整, 同时也需要对延迟时间tdyn进行更新。在调整处理时间和运输时间之前, 首先要对炉次j在工序k的开始时刻进行延迟调整, 调整所依据的算法和顺序为:
式中, t'p (i, j, k) 和t't (i, j, k) 分别为时间压缩后炉次j在工序k的处理时间和相邻工序间的运输时间;tp (i, j, k) 和tt (i, j, k) 分别为时间压缩前炉次j在工序k的处理时间和相邻工序间的运输时间。
规则3延长紧前炉次的浇注时间
仅当炉次j非浇次中的首炉时, 该规则才起作用。通过将浇铸速度从典型拉速降为最小平稳拉速, 延长紧前炉次的浇注时间并更新tdyn, 按式 (9) 调整:
式中, t'p (i, j-1, K) 为延长后紧前炉次的浇注时间。对于炉次j非浇次中首炉的情况, 经过该规则调整后, 时间延迟动态事件将被完全缓冲处理, 即满足tdyn=0。
规则4推迟浇次或浇次中部分炉次的开浇时刻
若炉次j非浇次中的首炉, 则当其紧前炉次的浇注时间延长时, 紧前炉次的浇注结束时刻也会相应延迟, 为了维持浇次的连浇特性, 炉次j本身和与其安排在同一台铸机设备上的后续炉次的开浇时刻均需要进行相应的延迟, 按式 (10) 调整:
式中, x' (i, j, K) 和x (i, j, K) 分别为后续炉次延迟后和延迟前的开浇时刻。
若炉次j为浇次中的首炉, 则该浇次中所有炉次开浇时刻均需延迟, 并按式 (11) 更新tdyn:
对于炉次j为浇次中首炉的情况, 经过该规则调整后, 时间延迟动态事件将被完全缓冲处理, 即满足tdyn=0。
规则1~4为发生时间延迟动态事件时针对单个炉次的处理规则, 且该炉次为发生动态事件的炉次本身。实际上, 在规则1和规则2中对炉次j在工序k的开始时刻进行延迟时 (不含推迟炉次在连铸工序的开浇时刻的情况) , 其结束时刻也会相应延迟, 那么, 就可能与同一设备上的紧后炉次发生冲突, 是否发生冲突的判断依据为规则5, 相应的消解冲突的处理措施采用规则6。
规则5判定当前炉次是否与其紧后炉次发生冲突
若经前调整后, 炉次j在工序k的开始时刻、处理时间和辅助时间等与其紧后炉次的开始时刻之间满足下面的关系, 则可判断会发生冲突:
式中, ta (i, j, k) 和分别为炉次j在工序k的辅助时间和相应的缓冲值;为紧后炉次的开始时刻。
规则6对紧后炉次进行时间优化调整
若规则5中式 (12) 成立, 则炉次j与其紧后炉次在工序k发生设备冲突, 冲突时长
为了消解该冲突, 令:
即将炉次j在工序k的冲突时间等同于其紧后炉次开始时刻的延迟时间, 进而用处理单个炉次时间延迟事件的规则1~4进行缓冲。
对紧后炉次调整后, 需继续判断紧后炉次与其紧后炉次是否发生设备冲突, 若是, 则递归调用规则1~6处理, 直至不再发生设备冲突为止。
2.3算法流程
基于规则的时间调整方法流程如下:
Step1若某炉次在某工序的开始时刻或结束时刻出现延迟, 则依次计算该炉次在该工序之后所有工序的等待时间之和、处理时间和相邻工序间的运输时间缓冲值之和, 该炉次在连铸工序的紧前炉次的浇注时间可延长量, 以及后续所有炉次开浇时刻的最小延迟量。
Step2根据该炉次是否为浇次中的首炉, 分别比较延迟时间是否不大于首炉和非首炉情况下可用的缓冲时间之和, 若是, 则继续下一步, 否则不能应用基于规则的时间调整方法缓冲延迟时间, 跳转至Step11。
Step3应用规则1, 调整该炉次在后续各个工序的等待时间和开始时刻, 同时对延迟时间进行更新。
Step4判断更新后的延迟时间是否大于0, 是则应用规则2, 调整该炉次在后续各个工序 (连铸除外) 的开始时刻、处理时间和相邻工序间的运输时间, 并更新延迟时间, 否则跳转至Step8。
Step5判断更新后的延迟时间是否大于0, 是则继续下一步, 否则跳转至Step8。
Step6判断该炉次是否为非浇次中的首炉, 是则应用规则3, 降低该炉次的紧前炉次浇注速度, 延长其浇注时间, 否则直接跳转至下一步。
Step7应用规则4, 推迟该炉次及其后续所有炉次在连铸工序的开浇时刻。
Step8应用规则5, 判断前面在应用规则1和2延迟该炉次在后续工序的开始时刻时, 是否与相应工序上使用同一设备的紧后炉次发生冲突, 是则继续下一步, 否则跳转至Step11。
Step9应用规则6, 将该炉次在发生冲突的某工序上的冲突时间等同于紧后炉次开始时刻的延迟时间, 并跳转至Step1。
Step10将紧后炉次作为当前炉次, 判断是否与其紧后炉次发生冲突, 是则跳转至Step9, 否则继续下一步。
Step11结束。
3仿真示例
以武汉钢铁集团公司二炼钢2013年1月31日白班计划为例, 检验时间偏差扰动情况下本文方法的有效性。该班次计划中各钢种的工艺处理路径和处理时间如表1所示。
min
假设炉次1-4 (制造命令号PONO为13200005) 在转炉工序兑铁时刻延迟了11 min, 该炉次的计划兑铁时刻为9:24。该时间偏差扰动的示意图如图1所示。
Fig.1 Schematic diagram of time deviation
在炉次1-4的实际兑铁时刻9:35触发动态事件, 调用本文方法进行动态调整。由于延迟时间较长, 所以该偏差对原计划的扰动程序较大。具体的时间调整方案如图2所示。
在原计划中, 因为炉次1-4在连铸工序前设置了11 min的等待时间, 所以应用规则1对转炉工序兑铁时刻延迟进行消解即可, 不会对浇次连浇造成影响, 但是需要注意的是必须将该炉次在转炉LD和吹氩站AR工序的开始时刻作相应延迟。
因为炉次1-4在转炉工序延迟了兑铁时间, 其结束时刻也会相应延迟至10:13, 由于其紧后炉次1-5 (PONO为13200006) 的计划兑铁时刻为10:02, 因此应用规则5可知, 炉次1-4必定与炉次1-5发生冲突。为了有效消解转炉工序的冲突, 压缩炉次1-4的辅助时间, 将其由原来的10 min缩短至8 min, 这样该炉次的结束时刻将调整为10:11, 与炉次1-5还有9 min冲突, 此时调用规则6, 将这9 min的冲突时间等同于炉次1-5的开始时刻的延迟时间, 继续对炉次1-5应用规则1~4。
炉次1-5在连铸工序前也设置了5 min的等待时间, 但是这个时间并不足以消解9 min的兑铁时刻延迟, 还需要对该炉次在AR工序的处理时间和AR→CC之间的运输时间分别缩短2 min。
与炉次1-4相同, 炉次1-5在转炉工序的开始时刻和结束时刻的延迟, 也造成与其紧后炉次7-4 (PONO为13200027) 发生冲突。在对炉次7-4应用规则1~4之前, 也要压缩炉次1-5在转炉工序的辅助时间, 最终传递到炉次7-4上的时间延迟为7 min。
针对炉次7-4的调整包括:LD→RH之间的运输时间缩短2 min, RH的处理时间缩短4 min, RH→CC之间的运输时间缩短1 min。
在转炉工序, 炉次7-4与其紧后炉次3-1之间的空闲时间为5 min, 这样, 压缩炉次7-4的辅助时间2 min后, 正好紧接着开始炉次3-1的兑铁操作, 不再发生冲突, 动态调整完成。
调整前后的时刻表对比见表2。表中黑体标注的是经过调整改变了的时间值或开始/结束时刻。
4结论
基于时间项调度 篇3
关键词：网格计算,任务调度,MinMin算法
网格计算的出现掀起了继传统Internet技术、Web技术之后的第三次技术浪潮。网格将高速互联网、高性能计算机、大型数据库、远程设备等融为一体, 以实现资源共享、协同工作和联合计算, 为各种用户提供基于网络的各类综合性服务。由于网格资源具有地理分布性、动态性、多样性、自治性和管理多重性, 资源任务调度策略成为网格计算领域中的关键研究方向之一。
1. 概述
网格计算任务调度就是一个将用户提交的任务分配到可用的计算机系统资源上, 并协调任务在资源上的执行顺序的过程。在网格计算中, 任务管理、任务调度和资源管理是网格必须具备的三个基本功能。用户通过任务管理系统向网格提交任务、为任务指定所需资源、删除任务并监测任务的运行状态。用户提交的任务由任务调度系统按照任务的类型、所需资源、可用资源等情况安排运行日程和策略。而资源管理系统监测网格资源状况, 收集任务运行时的资源占用数据等。任务调度的目的是在包含大量不同计算机的网格环境中, 同时考虑各网格节点的计算性能、节点之间的通讯性能等参数, 把不同的任务以最合理的方式分配到相应的网格结点去完成。由于在网格环境中各处理器的运行速度、主机的负载、网络的通信状态等是动态变化的, 因此任务调度问题同时也是一个非常困难的NP完全问题。
2. 网格计算的任务调度
网格环境是异构的并且动态性很强。任何计算节点在任何时刻都不一定稳定, 所以必须随时对其性能变化进行预测, 及时收集各节点的参数信息, 并且需考虑任务调度算法的移植性和可扩展性。
(1) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总是不停地改变, 有的资源出现了故障, 有的新资源要加入到网格中, 有些资源重新开始工作等。
(2) 网格的任务调度必须以分布、并行方式进行任务的管理与调度。
(3) 任务调度是面向异构平台的。由于网格系统是由分布在Internet上的各类网络资源组成的, 包括各类主机、工作站和PC机, 它们是异构的, 可运行在Unix, Windows等各种操作系统下, 也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。
(4) 任务调度不干涉网格节点内部的调度策略。在网格系统中, 各网格节点的内部调度策略是自治的, 网格任务调度系统干预其内部的调度策略是没有必要的, 也是不可能的。
(5) 任务调度必须具有可扩展性。网格系统初期的计算规模较小, 随着超级计算机系统的不断加入, 系统的计算规模也必将随之扩大。
3. 基于最短完成时间的Min＿Min算法
Min＿Min是一个比较传统、经典的任务调度算法之一, 它的主要调度原则就是将具有最短完成时间的任务分配到对应的资源上, 保证以最短的时间执行完所有的任务。
(1) Min＿Min算法的描述
任务调度问题的本质是在一个由m个需要调度的任务、n个可用的任务执行单元 (主机或集群) 以及由k个数据存储单元构成的网格环境下, 把m个任务T={Tl, T2, …, Tm}以合理的方式调度到n个主机H={H1, H2, …, Hn}上去, 目的是得到尽可能小的总执行时间。m个任务在n个不同机器上的预测执行时间ETC (Expected Time to Compute) 是一个m×n的矩阵。ETC (i, j) 表示第i个任务在第j台机器上的预测执行时间, 矩阵中的每一行代表某一任务在n台机器上的不同执行时间, 每一列代表在同一台机器上m个任务的不同执行时间。
记第i个任务在第j台主机上的预测最小完成时间 (Minimum Completion Time) 为MCT (i, j) , 则m个任务在n个不同主机上的预测最小完成时间也是一个m×n的矩阵, MCT (i, j) 主要由以下几个元素来决定:
(1) 任务i在主机j上的预测执行时间ETC (i, j) ;
(2) 主机j的最早可用时间TaskStart (j) ;
(3) 任务i运行时所需数据在存储系统上的最早可取时间DataStart (i) ;
(4) 任务i运行时在文件系统下存取数据所需要的时间Fetch (i) ;
(5) 把任务i所需的数据从存储系统传输到机器j上的传输时间Trans (i, j) ;
通过网格中的NWS, MDS等服务来获取这些数据, MCT (I, j总的计算公式为:
在Min＿Min算法中, 选取的最小完成时间任务/计算节点匹配对为:
(2) Min＿Min调度算法步骤
当需要调度的任务集合U非空时, 重复执行如下操作直至任务集合U为空:
(1) 对于集合U中每个等待分配的任务Ti, 计算出把该任务分配到n台机器上n个不同最小完成时间。假设该任务在第k台机器上的完成时间为最小, 记为Min＿Time (i) =MCT (i, k) 。Min＿Time是由各个最小完成时间组成的集合 (含m个元素的一维数组) , 同时记录该任务对应的主机号;
(2) 选择Min＿Time数组中具有最小MCT的任务a, 并将其分配给相对应的机器;
(3) 从需要调度的非空任务集合U中把任务a删除, 同时更新MCT矩阵。
(3) Min＿Min算法的C++伪代码实现
//对每一个任务Ti, 算出该任务在每一个资源上的期望完成时间CT。
(1) for all tasks ti in meta-task T;
//对每一个任务Ti, 找到它的最短期望完成时间MCT。
//第k个任务分配到相应最短期望完成时间的资源上执行, 并从T中删除该任务, 更新该资源的开始运行时间dj和所有任务的期望完成时间CTij。
(10) end do。
(4) Min＿Min算法的优缺点
Min-Min算法优先选取最早完成时间最小的任务进行调度, 以最快的速度减少调度队列中的任务, 尽量缩短所有任务的完成时间。具有较好的性能, 一般用作为调度算法的评测基准。
但由于Min-Min算法总是优先调度短任务, 当机器空闲时一些执行时间较长的任务才能得以执行, 这样便导致了主机负载不均衡, 利用率降低;其次, 没有同时考虑任务的数据传输和计算在存储资源和计算资源上的综合性能;再次, 没有考虑用户对任务比如带宽等的要求。在考虑到带宽的情况下, 各个任务对带宽有不同的要求, 有的任务对带宽没有任何要求, 有的任务却需要比较好的带宽。因此, 可能出现普通任务占据着高带宽网格资源, 而对带宽要求比较高的任务却得不到高带宽的网格资源的情况。
4. 结束语
网格计算技术是个正在迅猛发展的新兴学科。通过高速网络连接起来, 共同完成计算问题, 是网格计算快速发展的源动力, 它将极人地改变我们的生活和工科。Min＿Min算法作为网格计算中任务调度算法已经得到广泛的应用, 当所有任务的规模较小时, 即完成任务的时间均不长, Min＿Min算法被证明是一种最有效的调度算法, 具有较好的性能。
参考文献
[1].都志辉, 陈渝, 刘鹏著《网格计算》[M].北京:清华大学出版社, 2002
[2].刘凯鹅, 张伟哲, 胡铭曾.基于多QoS约束的网格任务调度算法[J].计算机工程与应用, 2006, 29:107-110
[3].朱春玲, 唐小勇, 李肯立.成本时间限制下的网格分类调度算法研究[J].计算机应用研究, 2007, 1 (1) :31-33.
基于时间项调度 篇4
军车调度作为军事交通运输(以下简称军交运输)工作的核心内容,越来越为军交运输管理者所重视。随着军队的发展,任务多、任务点分散、批量小、时间要求苛刻成了军交运输工作的一大特点。时间窗在军交运输任务中几乎是必要条件,不按用户时间窗送货会给供需双方带来不必要的经济损失。早于时间窗过多则车辆等待时间长,不经济;晚于时间窗则用户不满意,甚至影响用户的工作。面对众多分散的有时间窗的运输任务,运输线路合理与否,对运输成本、运输效率影响很大。因此,通过科学的调度方法提高军交运输调度水平,对于节省运输费用,提高运输部门服务质量具有重要意义。
车辆调度问题是NP(Non-deterministic Polynomial)难题,随着客户数量的增加,可选的配送路径方案数量将以指数速度急剧增长,用传统的方法,很难得到全局最优解或满意解[1]。遗传算法是求解此类问题的有效方法之一。但遗传算法在解决复杂的有时间窗车辆调度问题时,交叉算子设计复杂,进化过程中会产生大量劣质染色体,且进化后期搜索效率低。单亲遗传算法是在遗传算法的基础上的一种改进[3]。单亲遗传算法是指遗传操作交叉和变异都是针对单独的一个个体进行操作的一种遗传算法。它与传统遗传算法最大的不同在于它的交叉算子是仅在一条染色体上操作的基因换位遗传算子,从而简化了遗传操作过程,并且不要求初始群体的多样性,不易出现早熟现象[4]。但单亲遗传算法也存在产生新个体速度慢,不易收敛等问题。本文以此为出发点,设计一种基于时间序列的单亲遗传算法来使问题的求解得到优化。
1 问题描述
有一个车辆指挥运输中心和n个用户点,第i个用户点需要的货物量为gi(i=1,2,…,n),由指挥运输中心派出载重量为q的m辆运输车来承运(设gi
2 模型建立
根据以上问题描述,将变量作以下定义:
1)指挥运输中心编号为0,用户点编号为1,2,…,n;车辆数为m。
2)Cij为从用户点i到用户点j的运输成本。
3)xijk=0或1,为“1”时表示车辆k由用户点i驶向用户点j。
4)yik=0或1,为“1”时表示用户点i的任务由车辆k完成。
5)rk为车辆k的固定费用。
根据以上参数和变量,可得基本运输费用模型:
6)运输任务需要在一定的时间范围内[ETi,LTi]内完成,其中ETi表示任务允许的最早时间,LTi表示任务的最迟时间,Si表示车辆实际到达用户点的时间,如果车辆到达时间早于ETi,要加乘单位时间等待成本因子P1,如果到达时间晚于LTi,则要加乘单位时间惩罚因子P2。
综合(1)(2)(3)式,得到有时间窗,非满载车辆调度问题数学模型:
约束条件如(5)-(9)式:
1)车辆容量约束
2)每个用户点的运输任务仅由一辆车来完成
3)m辆车从指挥运输中心出发
4)到达某一用户点的货车有且只有一辆
5)离开某一用户点的货车有且只有一辆
3 算法设计
单亲遗传算法以编码空间代替问题的参数空间,将每一个参数可能的解表示为个体,从而得到一个种群。运行时,算法以适应度函数为评价依据得到适应度值,以编码群体为进化基础,再利用选择、交叉、变异这3种遗传算子对这些个体进行遗传操作,建立起一个迭代过程[5~8]。在这一过程中,通过随机重组个体的基因,使得子代的个体优于父代,群体的个体不断进化,逐渐接近最优解,最终达到求解问题的目的。
但在实际应用时,单亲遗传算法收敛速度慢,搜索效率较低。为此,提出了一种基于时间序列的单亲遗传算法。其基本思想是:编码时,使用时间序列的编码方式。即对插0后染色体两0之间的子路径(单台车的运输任务)按ETi排序,这样可以有效减少种群中劣质染色体,提高收敛速度。其次,在选择和交叉操作时,使用两代竞争选择法和多点交叉算子,以提高产生新个体速度,且使优秀个体得以保留。
将基于时间序列的单亲遗传算法应用于车辆调度中,其具体的设计步骤如下:
1)产生初始种群:将用户点按自然码编码方式表示为1-n的序列,随机产生M个1-n的全排列。然后对每条染色体插0,使得每两个0之间的排列为一台车的运输任务。再将每台车的任务按ETi排序。具体操作是:第一位和最后一位先插入0,随后计算,,则在第s-1个需求点后插0,再从第s个需求点开始计算,再插入0直到到达染色体末尾。如果用d表示用户,n表示用户数量,t(t<=m)表示所用车辆数,dki表示第k台车送往第i个用户,则染色体可表示为:
到此,一条满足单亲遗传算法要求的染色体产生了。但是军事运输有它的特殊性,永远是军事目的大于经济要求,按时按量送货是军事运输的基本要求。当然也要力求减少费用,节约开支。为此,再对产生的染色体子路径按ETi进行重新编码,形成新的按时间序列编码的单亲遗传算法,用以求解问题。
操作方法是:将上面产生的染色体上所有两个0之间的用户点按ETi的时间先后排序。选取某条染色体上的一个子路径举例:
原路径:0,d1,d2,d3,0
若时间窗中ET2>ET3>ET1,则排序后的运输路径为:
新路径:0,d2,d3,d1,0
完成排序后的染色体就是新的按时间序列编码的染色体。依次反复,直到满足群体数。
这样形成的初始种群,既能满足时间窗,达到军事要求,又能在进化过程中有效减少劣质染色体,加快了单亲遗传算法的收敛速度。仿真结果也证实了此编码方式的正确性和有效性。由图2、图3对比可知,基于时间序列编码的单亲遗传算法收敛速度明显好于不按此法编码的单亲遗传算法。
2)两代竞争选择:取适应度f为f=1/Z(Z为运输费用,f越大,Z越小)。计算f值,将父个体与子个体f值进行比较,f值大的个体作为新群体的个体留下,f值小的淘汰。
3)多点交叉算子:单点交叉使得新个体产生速度较慢,因此采用多点交叉算子。即在一条父代染色体上随机产生多个交叉点,对各交叉点随机进行两两配对,交换两交叉点位置上的基因,形成子代染色体。
如:父代:4|3|16|5|7|8|9|2|
||之间的基因为待交叉基因(如基因3与8,5与2配对),交叉得到子代个体。
子代:481627395
4)变异:以一定的变异率随机选取发生变异的个体染色体,然后在该染色体上随机选取一个基因位,把这个位置上的基因随机插入另外两个基因之间,形成新的染色体。
如:父代:481|6|27395
将||之间基因插入到基因3、9之间,得到子代个体。
子代:481273695
该算法使用了遗传算法求解多目标优化问题的混合方法,选择算子的主体使用并列选择法,再通过引入保留最佳个体和共享函数的思想来弥补仅仅只使用并列选择法的不足。同时通过自适应交叉变异的方法,引入两代竞争、稳态遗传方式,既能使搜索更加快速有效,又能避免出现早熟现象[3]。
4 仿真结果及分析
以某基层部队军交运输工作情况为分析对象。该部一次运输任务相关参数如下:有10个用户点(指挥运输中心与各用户点之间的距离见图1),各点物资需求量g=[2,1.5,4,3,2.5,3,2.5,1,2,3.5](单位:吨),各点时间窗AB=[2.1,5;3,4;0.5,2;1,1.5;2.5,3;1.2,3;1.6,2;3.2,5;2.3,4;1.9,3](单位:小时),车辆数m=6台,车辆载重量q=5吨,车速v=60千米/小时,车辆固定费用r=6(已换算为公里)。求最低成本的运输线路。
根据上述算法原理,用Matlab6.5编写了仿真程序。选取算法的控制参数如下:原始种群规模30,进化20代,仿真10次。仿真结果如图2、图3所示。
单亲遗传算法所得最佳路径:057010090380620410;基于时间序列的单亲遗传算法所得最佳路径:07501020490380610。最终最少运输费用为:1365,最优线路为:0-7-5-0,0-10-2-0,0-4-9-0,0-3-8-0,0-6-1-0。由图2、图3可以看出:基于时间序列的单亲遗传算法能有效克服单亲遗传算法收敛速度慢、搜索效率低的不足,且鲁棒性较好。
5 结论
减少运输成本,提高服务质量,一直是基层军交运输部门长期追求的目标。本文设计了一种基于时间序列的单亲遗传算法来求解车辆调度问题中的最少费用和最优线路,算法能快速求得问题的最优解,加快了单亲遗传算法的收敛速度,提高了搜索效率,且具有较好的鲁棒性。该算法解决背景问题行之有效,对有时间窗车辆调度问题的研究提供了借鉴,在军交运输系统的研究方面具有普遍意义。
参考文献
[1]方跃建,杨春节,等.一种新的非满载车辆调度的遗传算法[J].江南大学学报(自然科学版),2007,4.
[2]杨利平,李宏伟,等.改进遗传算法求解有时间窗车辆路由问题[J].解放军理工大学学报(自然科学版),2007,2.
[3]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006:1.
[4]吴值民,吴凤丽,等.退火单亲遗传算法求解旅行商问题及MATLAB实现[J].解放军理工大学学报(自然科学版),2007.2.
[5]邓欣,朱征宇.一种多车场车辆路径问题的单亲遗传算法[J].交通与计算机,2007:1.
[6]尚华艳.物流配送中车辆路径问题研究[D].武汉:武汉理工大学,2005.
[7]张海刚,顾幸生,等.基于免疫算法的带软时间窗车辆调度问题[J].华东理工大学学报(自然科学版),2007-02.
基于时间项调度 篇5
在半导体制造中, 由于晶圆直径越来越大, 加工工艺复杂, 组合设备被广泛的用来加工晶圆。组合设备是一类集成制造设备。在这样的一台设备中, 有几个加工模块 (Processing Module, PM) , 一个机械手以及真空锁 (Loadlock) 。机械手分为单臂机械手和双臂机械手, 如图1所示为单臂机械手, 因此叫单臂组合设备。此系统的工作过程大致如下:一批装在一个卡盒中待加工的晶圆首先放入真空锁中, 然后由机械手从卡盒中抓取一枚晶圆放到AL中, 经AL的视觉系统进行校准后, 由机械手按照工艺要求将该枚晶圆依次放入相应的PM中加工, 晶圆在每一个加工模块内完成一道工序, 当完成最后一道工序后, 晶圆被送入CL中冷却, 避免热的晶圆影响到真空锁内其他的晶圆, 最后晶圆被送回到真空锁。整个过程由程序自动控制, 当该批晶圆加工完成后, 真空锁中卸载, 并装入下一批晶圆。两个真空锁通过轮流使用实现对晶圆的装卸作业, 以保证组合装置加工的连续性, 使得系统绝大部分时间都是处在稳定运行的状态。这样的组合设备可以为半导体制造提供一个灵活的、可重置的和有效的环境, 减小生产节拍, 提高空间的利用率, 降低成本。一个晶圆通过真空所进入系统, 然后按照已知的加工路径在加工模块中加工, 当所有的加工工序完成后, 由机械手送回真空所。
为了调度组合设备, 许多学者在建模和对系统执行评估做了很多工作[1,2]。基于这些研究发现, 在稳态下, 当机械手有空闲时间时, 加工模块的加工时间决定系统的生产周期, 当机械手一直忙的时候, 系统的生产节拍由机械手的活动时间决定。在一台组合设备中, 仅仅当一个晶圆载入到加工模块中, 加工模块才开始加工晶圆。因此, 加工模块的活动跟随着机械手的任务[3]。这样, 调度组合设备的关键在于调度机械手的任务。众所周知, 组合设备中机械手从一个加工模块移动到另一个加工模块的时间可以看作为常数, 并且比晶圆的加工时间短很多[4]。这样, 对于单臂组合设备拉式调度是最优的[5,6]。然而, 以上的研究结果都是基于假设晶圆加工完成后可以在加工模块中停留无限长的时间。
对于一些晶圆加工工艺, 例如低压化学沉积工艺, 它对晶圆在加工模块中的滞留时间有严格的约束。这种约束叫晶圆驻留时间约束 (residency time constraint, RTC) [4]。RTC指一个晶圆在加工模块中加工完成后, 必须在规定的有限的时间内卸载出来, 否则此晶圆将成为废品。由于在加工模块之间没有缓冲区, 使得很难调度组合设备去满足晶圆在每个加工模块中的驻留时间约束。这样, 为了能够调度带驻留时间约束的组合设备, 文献[4]提出了一些方法为双臂组合设备找到最优的周期性调度。之后, 为了提高计算有效性, 伍乃骐等人分别对于单臂和双臂组合设备提出了充分必要的可行性调度条件[2,7]。如果可调度, 可通过由解析表达式组成的调度算法找到最优的周期性调度。然而在以上的研究中, 并没有给出怎么样进入稳态调度更好。也就是说, 不同文献给出进入稳态的调度方法不一样。这就意味着, 不同进入稳态的调度方法导致不同的稳态调度方案。这样, 本文基于earliest调度策略, 通过对系统暂态过程的分析, 给出了系统进入稳态后, 机械手的等待时间分布。
接下来文章主要介绍Petri网建模。基于此Petri网模型, 第二部分分析了系统进入稳态后机械手的等待时间分布。第三部分给出了实例验证了本文得出的结论。第四部分对文章进行了总结。
1 Petri网建模
本文用Petri网 (Petri net, PN) 对系统进行建模。Petri网的概念来自于文献[8-9], 对于没有重入加工工艺的组合设备, 晶圆的加工模式可以定义为 (m1, m2, …, mn) , 其中n是晶圆加工步骤数目, mi是晶圆加工步骤i中所包含的加工模块数目。
本文展示的Petri网模型中, 用库所pi表示步骤i的加工模块并有K (pi) =mi, iϵ{1, 2, …, n}。将真空锁看作一个加工步骤并称之为步骤0, 用p0表示。由于真空锁可以容纳设备中的所有晶圆, 因而有K (p0) =∞。这样, 整个系统就有n+1步加工步骤。让Ω={0, 1, …, n}表示包含步骤0的步骤集, 让Nn={1, …, n}表示可加工晶圆的步骤集。机械手由库所r表示, K (r) =1意味着机械手只有一只手臂。当库所r中有令牌时表示机械手是空闲状态。
对于带驻留时间约束的单臂组合设备, 机械手的等待时间用来平衡加工步骤之间的工作负载。用库所qi2和qi1表示机械手在缷载或安装晶圆到加工步骤i之前的等待时间。模型中变迁, si1, iϵNn, 和s01分别表示机械手安装一个晶圆到加工模块pi和真空锁p0中。变迁si2, iϵNn-1, 表示机械手从加工模块pi卸载一个晶圆然后移动到加工模块pi+1。变迁s02表示机械手从真空锁p0下载一个晶圆然后移动到加工模块p1。变迁sn2表示机械手从加工模块pn中下载一个晶圆然后移动到真空锁。yi表示机械手从第 (i+2) 道工序旋转至第i道工序, yn-1表示机械手从真空所旋转至第 (n-1) 道工序, yn表示机械手从第1道工序旋转至第n道工序, y0表示机械手从第2道工序旋转至第0道工序。图2展示了单臂组合设备具有n个加工步骤的Petri网模型。
假设组合设备按照给定的晶圆加工流模式 (m1, m2, …, mn) 对晶圆进行加工, 稳态时系统达到最大产能时有∑i0=1mi个晶圆同时在系统中加工。所以, 让初始状态M0为M0 (pi) =mi, iϵNn, M0 (r) =1来表示机械手为空, 让M0 (p0) =n表示系统中总有晶圆可被载入到系统中。为了避免图2中的Petri网模型死锁, 给出让Petri网避免死锁的控制策略。
定义1[2]:在标识M下, 如果M (pi+1) =mi+1-1, 则变迁yi, iϵNn-1∪{0}, 是可触发的;如果M (pi) =mi, iϵNn, 则变迁yn是可触发的。
通过定义1, 强迫Petri基于拉式策略运行。下面我们展示采用拉式策略的单臂组合设备的运行过程。稳态时一定有状态为M (pi) =mi, iϵNn, M (r) =1, 接着系统的运行过程如:, 这样系统走完一个周期。基于拉式策略, 系统不断的周期性重复以上的运行过程。
为了解决该系统的调度问题, 需将系统的活动时间与系统的Petri网模型联系起来。令机械手每次的运动时间为μ, 机械手从ρ0卸载一枚晶圆的时间为λ0, 而在其他步骤中卸载或安装晶圆的时间均为λ。这样, 有激活变迁yi, iϵΩ, 需要μ个单位时间, 激活变迁si1, iϵΩ, 需要λ个单位时间, 激活si2, iϵNn, 需要λ+μ个单位时间, 激活s02需要λ0+μ个单位时间。用ai表示晶圆在加工模块中的加工时间。由于考虑驻留时间约束, 这样用δi表示这样的约束, 即:晶圆在第i步加工完后, 需要在δi个单位时间内移走, 否则将变为废品。用ωi1和ωi2分别表示机械手在库所qi1和qi2中的等待时间。这样就完成了对单臂组合设备的Petri网建模。
2 基于Earliest调度策略, 机械手等待时间的分布规律
Earliest调度策略是指: (1) 机械手到达加工模块卸载晶圆时, 如果加工模块中的晶圆已经加工好, 那么机械手立即将其卸载下来; (2) 机械手到达加工模块卸载晶圆时, 如果加工模块中的晶圆还没加工好, 那么机械手在此等待, 一旦晶圆加工好, 机械手立即将其卸载下来; (3) 机械手拿着待加工的晶圆来到加工模块时, 如果该加工模块是空的, 立即将其载入加工模块中。暂态是指组合设备所有加工模块中从没有加工晶圆开始, 机械手将晶圆一个个的载入到组合设备中, 到所有的加工模块都有加工晶圆并最终组合设备进入稳态运行的过程。
根据文献[7], 设τi表示第i道工序的晶圆在加工模块中的停留时间, 如果晶圆在第i道工序满足驻留时间约束, 那么τiϵ[ai, ai, +δi]。根据图2中的Petri网模型, 第i步完成一个晶圆需要经过以下过程:触发si2 (λ+μ) →触发si+1 (λ) →触发yi-1 (μ) →机械手在第i-1步等待 (ω (i-1) 2) →触发s (i-1) 2 (λ+μ) →触发sil (λ) →晶圆在第i步加工 (τi) →触发si2 (λ+μ) 。则该过程所需时间为ρi=τi+4λ+3μ+ω (i-1) 2。这样, 考虑并行模块, 第i道工序完成一个晶圆允许的最短的时间为:
第i道工序完成一个晶圆允许的最长时间为:
第一道工序完成一个晶圆允许的最短时间为:
第一道工序完成一个晶圆允许的最长时间为:
在图2的Petri网模型中, 分析机械手走过一个周期的活动路径及时间:触发yn (μ) →机械手在qn步等待 (ωn) →触发sn2 (λ+μ) →触发s01 (λ) →触发yn-1 (μ) →机械手在qn-1步等待 (ωn-1) →触发s (n-1) 2 (λ+μ) →触发sn1 (λ) →…→触发yi (μ) →机械手在qi步等待ωi→触发Si2 (λ+μ) →触发s (i+1) 1 (λ) →触发yi-1 (μ) →机械手在q (i-1) 2步等待 (ω (i-1) 2) 触发s (i-1) 2 (λ+μ) →触发si1 (λ) →…→触发y1 (μ) →机械手在q12步等待 (ω1) →触发s12 (λ+μ) →触发s21 (λ) →触发y0 (μ) →机械手在q02步等待 (ω02) →触发s02 (λ0+μ) →触发s11 (λ) →再次触发yn (μ) , 这样一个周期完成, 若令机械手的节拍为ψ, 可得到:
式 (5) 中可以发现2 (n+1) μ+ (2n+1) λ+λ0是一个常数, 可令其为ψ1, 而是不确定的, 可令其为ψ2, 所以
根据文献[7], 晶圆在加工模块的停留时间如下式:
令表示第i道工序的生产节拍, 根据文献[7], 当所有的加工模块都有晶圆在加工时, 有下面的结论。
引理1:对于带驻留时间约束的单臂组合设备, 当所有的加工模块都有晶圆在加工时, 有θi=ψ, iϵNn。
让Πi L和Πi U分别表示第i道工序允许生产节拍的上限和下限, 那么有:
文献[7]针对带驻留时间约束的单臂组合设备的调度问题, 提出了使系统可调度的充分必要条件。在此基础上, 给出稳态下机械手的等待时间分布规律。假设第k道工序为瓶颈工序, 1≤k≤n。那么有下面的定理。
定理1:对于带驻留时间约束的单臂组合设备, 基于earliest调度策略, 当系统到达稳态后, 等待时间ωi1=0, iϵΩ和ωi=0, i=0, 1, ……, k-1, 成立。
证明:根据拉式调度策略, 当机械手拿着待加工的晶圆来到第i步时, 第i步一定为空。这样根据earliest调度策略定义, 机械手可以立即将此晶圆载入第i步中, 即ωi1=0。因为真空锁总有待加工的晶圆, 这样当机械手来到真空锁可立即将其中的晶圆卸载出一个, 所以有ω02=0。根据拉式调度策略, 当机械手来到第一步时, 其一定已经在瓶颈工序第k步完成一系列的机械手活动, 这样此时该系统的周期由瓶颈工序决定, 即为Πk L。这样由引理1和式子 (8) 可得τ1=m1×Πk L- (3λ+λ0+3μ+ω0) =m1×Πk L- (3λ+λ0+3μ) ≥m1×Π1L- (3λ+λ0+3μ) =a1, 所以当机械手来到第1步卸载晶圆时, 第1步中的晶圆已经加工好了。因此机械手可以立刻将其中的晶圆卸载出来, 同时不需要等待, 即ω1=0。当机械手来到第2步时, 同理由引理1和式子 (7) τ2=m2×Πk L- (4λ+3μ+ω1) =m2×Πk L- (4λ+3μ≥m2×Π2L- (4λ+3μ) =a2, 所以当机械手来到第2步卸载晶圆时, 第2步中的晶圆已经加工好了。因此机械手可以立刻将其中的晶圆卸载出来, 同时不需要等待, 即ω2=0。相似的, 可推出ω3=ω4=…=ωk-1=0。因此定理1成立。
根据文献[10], 可知机械手在qi2中的等待时间是有上界的, 否则此等待时间将会影响系统的最优性。让γi表示可分配到库所qi2最大的等待时间, 这样有γi-1=mi×Πk L- (ai+4λ+3μ) , 1≤i≤n和ωnϵ[0, ∞]成立[10]。
证明:根据定理1可知, ωi1=0, iϵΩ和ωi2=0, i=0, 1, …, k-1, 成立。假设机械手在第k步的等待时间ωk2>γk2, 根据引理1和式子 (7) 有τk+1=mk+1×Πk L- (4λ+3μ+ωk)
到现在为止, 分析了基于earliest调度策略, 稳态时机械手等待时间的分布情况。同时, 机械手的等待时间分布可通过解析表达式计算出来, 因此非常有效。
3 实例验证
一台组合设备有四道加工工序, 其中第三道工序有两个并行加工模块, 而其他工序只有一个加工模块。每道工序的加工时间分别为:a1=92 s, a2=98 s, a3=210 s, a4=95 s。机械手的活动时间分别为:λ=10s, λ0=15s, μ=2s。
基于工艺参数可以求得:ψ1=125s, Π1L=143s, Π2L=144s, Π3L=128s和Π4L=141s, 其中第二道工序为瓶颈工序。基于定理1和定理2得出, 稳态时, 机械手的等待时间分布为:ω02=ω12=0, ω22=19和ω32=ω42=0。通过基于e M-plant仿真, 采用earliest调度策略, 系统稳态时机械手等待时间的分布为ω02=ω12=0, ω22=19和ω32=ω42=0。此仿真结果与基于定理1和定理2得出的结果一致, 因此验证了本文的结论。
4 结束语
半导体加工是极复杂的制造系统, 它的调度问题非常复杂。本文对基于earliest调度策略的带驻留时间约束的单臂组合设备的暂态过程进行了分析, 运用Petri网模型得出了系统达到稳态后机械手的等待时间分布情况, 并且此分布可通过解析表达式计算得出, 因此非常有效。基于以上成果, 今后将着重研究基于earliest调度策略多组合设备到达稳态时机械手的等待时间分布情况。
参考文献
[1]J.Yi, S.Ding, M.Zhang.Steady-state throughput and scheduling analysis of multi-cluster tools:A decomposi tion approach[J].IEEE Trans.Automation Sci.Eng., Apr, 2008, 5 (2) :321-336.
[2]N.Q.Wu, M.C.Zhou.A closed-form solution for schedu lability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis[J].IEEE Transactions on Automa tion Science and Engineering, 2010, 7 (2) :303-315.
[3]Y.-H.Shin, T.-E.Lee, J.-H.Kim, et al.Modeling and implementing a real-time scheduler for dual-armed cluster tools[J].Computers In Industry, 2001, 45 (1) :13-27.
[4]J.-H.Kim, T.-E.Lee, H.-Y.Lee, et al.Scheduling analysis of timed-constrained dual-armed cluster tools[J].IEEE Transactions on Semiconductor Manufactur ing, 2003, 16 (3) :521-534.
[5]T.-E.Lee, H.-Y.Lee, Y.-H.Shin.Workload balanc ing and scheduling of a single-armed cluster tool[A].Proceedings of the 5th APIEMS Conference[C], Gold Coast, Australia.2004:1-15.
[6]M.-J.Lopez, S.-C.Wood.Systems of multiple cluster tools-configuration, reliability, and performance[J].IEEE Transactions on Semiconductor Manufactur ing, 2003, 16 (2) :170-178.
[7]N.Q.Wu, C.B.Chu, F.Chu, et al.A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints[J].IEEE Transactions on Semiconductor Manufacturing, 2008, 21 (2) :224-237.
[8]M.C.Zhou, K.Venkatesh.Modeling, simulation and control of flexible manufacturing systems[A].Petri net approach, World Scientific, Singapore, 1998.
[9]T.Murata.Petri nets:Properties, analysis and applica tions[A].Proceedings of the IEEE[C].1989, 77 (4) :541-580.
基于时间项调度 篇6
Flow-shop生产调度问题是对流水线生产调度问题的模拟,因而Flow-shop调度的研究对于实际流水线调度问题的解决具有重要的借鉴与指导意义。现阶段对Flowshop问题的研究大致可分为三类:第一种是用新算法对标准Flow-shop问题进行求解[1,2];第二种是提出了一种特殊的Flow-shop调度模型,并对模型进行求解[3,4];第三种是对原有算法进行改进或提出一种新颖算法求解相应的Flow-shop调度模型[5,6]。本文对不确定加工时间环境下的Flow-shop调度问题进行了研究,提出了一种改进遗传算法,最后通过仿真比较分析了改进遗传算法在模型求解上的有效性。
1 六点模糊数Flow-Shop问题描述
1.1 六点模糊数基础
论域U上的模糊子集构成了模糊集ξ(U),即
由于模糊数隶属度函数难以精确定义的特点,本文采用Romme Lfanger[7]提出的隶属度函数获取方法,如下:
基于上述描述,六点模糊数可以表示为以下形式:
1.2 六点模糊数运算法则
1.3 Flow-Shop鲁棒调度问题
现有n个工件以相同的顺序依次经过机器集Ω(M)={M1,M2,…Mj…Mm}中的设备;工件同一时刻只能被一台设备加工;设备某一时刻只能加工一个工件;工件在机器之间的搬运时间可以忽略;机器加工是一种无延迟加工;加工过程不可中断;本文采用最大完工时间跨度和最大完工时间的组合目标作为鲁棒调度的鲁棒性测度RM。
目标函数:
决策变量:
zij为工件加工顺序决策变量。
2 算法设计
遗传算法(Genetic Algorithm,GA)是一种随机优化算法,算法依靠选择、交叉以及变异等操作完成种群的进化。遗传算法的交叉操作是通过对被选择的个体彼此间遵循一定的规则完成基因的交换,其子代个体的优劣充满随机性。本文采用改进遗传算法(Improved Genetic Algorithm,IGA),采用单染色体遍历方式替代染色体间的交叉操作,以增强子代个体的确定性。
2.1 编码
本文采用实数编码规则,如图1所示,数字表示工件的序号,数字编码顺序表示工件的加工顺序。
2.2 遍历操作
遍历操作具体步骤如下:
步骤一:确定当前染色体遍历的基因个数N,采用线性递减方式,N=(1-t/T)×M/2+1。
式中:t为当前迭代次数;T为最大迭代次数;M为工序加工顺序编码基因个数。
步骤二:依据遍历基因数,随机生成遍历基因位置,依次从左至右完成基因遍历,如在染色体编码中随机选择(1,4)号基因作为遍历基因遍位置,则首先从1基因位置开始遍历,保留1左边基因顺序不变,将1基因右侧基因依次与1对调,计算对调后的染色体的适应度值,保留最优染色体,若1号基因完成遍历后最优个体恰是与4号基因完成对调后的染色体,则4号基因不在进行遍历操作,反之,4号基因继续上述操作直至完成遍历。
2.3 变异操作
本文采用随机法在编码处确定两点基因变异位置,如(5,7)号基因,截取包括(5,7)号基因在内的基因片段,参照图1所示编码,此处基因片段为(5,6,1,4,7),采用倒序方式将基因片段插入到原基因中,最终变异后的基因为(3,7,4,1,6,5,9,2,8)。
2.4 改进遗传算法基本步骤
步骤一:令ite=0,随机初始化种群大小为N的种群Pop(0),选择率Pc、变异率Pm,概率P,相似度阈值Thr,最大迭代次数Ite。
步骤二:计算种群Pop(ite)中各个体的适应度值(fitness value)。
步骤三:判断算法终止条件是否满足。满足,则输出适应度值最高个体,否则,进入步骤三。
步骤四:采用轮盘赌法从种群群众选择出Pc×N个个体,复制进入选择临时种群Tem Pop中。
步骤五:对Tem Pop各个体赋予随机数ε,ε∈[0,1]。
步骤六:若Pm≥ε,对该个体进行变异操作;否则,对个体进行遍历操作。将完成操作的个体放入下代种群Pop(ite+1)中。
步骤七:从Pop(ite)选取适应度值高的个体补足种群大小。在选取个体时,若P≥θ,θ∈[0,1],则计算个体与Pop(ite+1)中个体的相似度Sim,若个体相似度Sim≥Thr,对个体进行重新排序后放入Pop(ite+1);反之,则直接放入Pop(ite+1)。
步骤八:ite=ite+1,返回步骤二。
3 实例验证
为了测试改进遗传算法(IGA)对求解Flow-shop调度问题的有效性,本文分别将IGA和GA用于Flow-shop调度问题的求解,在求解的过程中采用多个问题多次求解的方式,即针对不同的加工工件规模进行算法求解。在[1,10]之间随机生成6个数据并依照大小依次排序,从而构成工件模糊加工时间;Pc=0.2,Pm=0.1,N=50,P=0.8,Ite分别为500、1000、2000次。针对不同的加工规模以及不同的迭代次数进行试验比较,具体仿真数据如表1所示,其中Size表示加工规模,BV表示搜索最优值,RT表示算法搜索耗时。
对上述数据进行进一步分析可知,加工规模为10时,在500、1000以及2000次迭代试验下IGA算法相较于遗传算法最优值分别提升11%、11%、6%,搜索耗时分别降低了9%、8%、14%;在工件规模为20时,精度提升25%、25%、23%,耗时降低7%、12%、12%;工件规模为20时,精度提升18%、18%、18%,耗时降低6%、8%、9%;工件规模为25时,精度提升14%、9%、12%,耗时降低5%、7%、3%;工件规模为30时,精度提升17%、18%、20%,耗时降低15%、10%、9%。由此可知IGA在求解Flow-shop调度问题上是明显优于传统遗传算法的。
4 结语
本文的研究内容主要可以分为以下几点:
1)利用六点模糊数方式描述了加工时间不确定的Flowshop调度车间问题;2)构建了Flow-shop调度模型,并利用改进遗传算法对模型进行求解。
摘要：对不确定加工时间环境下的Flow-shop调度问题进行了研究,利用六点模糊数对不确定加工时间进行描述,以最大完工时间和最大完工时间跨度的权重和为鲁棒性测度构建模糊加工时间Flow-shop调度模型。提出了模型求解的改进遗传算法,算法采用单染色体遍历操作代替染色体交叉操作,用以增强种子代繁衍的确定性,最后仿真分析验证了算法的有效性。
关键词：Flow-shop调度,六点模糊数,改进遗传算法
参考文献
[1]陈雄,杨凤霞,吴启迪.Flow-shop调度问题的自适应模拟退火算法[J].控制理论与应用,2003,20(3):445-448.
[2]周宏根,戚雪峰,景旭文,等.基于遗传算法的作业车间调度研究与应用[J].现代制造工程,2006(8):5-8.
[3]锦钿,刘建军,陈庆新,等.两机flow-shop类型模具热处理车间批调度算法[J].计算机集成制造系统,2014,20(7):1665-1674.
[4]王莉,杜广宇,刘洪,等.带有交货期窗口模糊加工时间的Flow-shop调度问题[J].2005,14(6):532-536.
[5]李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管理,2015,24(1):157-163.
[6]桑红燕,潘全科.求解流水车间批量流集成调度的离散入侵杂草优化算法[J].控制理论与应用,2015,32(2):246-250.
[7]ROMMELFANGER H.Fulpal:An Interactive Method for Solving(multiobjective)Fuzzy Linear Programming Problem[M]//Slowinski R,Teghem J(eds.),Stochastic Versus Fuzzy Approaches to Multiobjective Mathematical Programming Under Uncertainty.Dordrecht:Kluwer,1990:279-299.