PDF《求解不相关并行机混合流水线调度问题的人工蜂群算法》

Li等[18] 针对多目标柔性作业车间调度, 提出了一种有效的ABC算法. 本文针对不相关并行 机混合流水线调度问题(HFSP with unrelated parallel 收稿日期: 2012?06?01;

收修改稿日期: 2012?06?19. 基金项目: 国家自然科学基金资助项目(61174189, 60834004);

国家重点基础研究发展计划资助项目(2009CB320602).

1552 控制理论与应用第29 卷machines, HFSPCUPM)的特点, 设计一种基于排列的 编码和解码方法, 提出了3种有效的邻域搜索方法进 行引领蜂和跟随蜂阶段的操作, 并运用侦察蜂的随 机搜索增强种群多样性. 通过试验设计方法分析参 数对性能的影响并给出有效的参数组合. 最后通过 比较验证所提算法的有效性和鲁棒性.

2 不不不相 相 相关 关 关并 并 并行 行 行机 机 机混 混 混合 合 合流 流 流水 水 水线 线 线调 调 调度 度度(HFSPC UPM) 2.1 问问问题 题 题描 描 描述 述述(Problem statement) HFSPCUPM可描述为[5] : n个工件在流水线上进 行S个阶段的加工, 各阶段至少有一台机器且至少 有一个阶段存在并行机, 同一阶段上各机器加工同 一工件的加工时间有所不同, 在每一阶段各工件均 要完成一道工序, 但各工件的每道工序可在相应阶 段上的任意机器上加工, 已知工件各道工序在各机 器上的处理时间, 要求确定所有工间的排序以及每 一阶段上机器的分配情况, 使得某种调度指标最小, 如最大完工时间. 图1给出了问题的一个图例. 图1HFSPCUPM图例 Fig.

1 An example of HFSPCUPM 2.2 数数数学 学 学模 模 模型 型型(Mathematical formulation) 假设工件一旦开始加工便不可中断;

一台机器 同一时刻只能加工一个工件;

一个工件同一时刻只 能在一台机器上加工;

工件可在每阶段的任意一台 机器上加工[19] . 记Ji为工件序号, i = 1, 2,n;

mj为每一阶段的机器数, j = 1, 2,S;

ti,j,k为工 件Ji第j道工序在第k台机器上的加工时间;

si,j,k和ei,j,k分别为工件Ji第j道工序在第k台机器上开始加 工时间和加工完成时间;

Ci为工件Ji的加工完毕时 间;

Cmax = max{C1, C2,Cn}为最大完成时间;

L为足够大数. HFSPCUPM的数学模型如下: min Cmax (1) s.t. n i=1 xi,l = 1, l = 1, 2,n, (2) n l=1 xi,l = 1, i = 1, 2,n, (3) ? ? ? ? ? mj k=1 yi,j,k = 1, i = 1, 2,n, j = 1, 2,S, (4) ei,j,k = si,j,k + ti,j,k, i = 1, 2,n, j = 1, 2,S, k = 1, 2,mj, (5) ? ? ? ? ? ? ? ei,j,k si,j+1,k , i = 1, 2,n, j = 1, 2,S ? 1, k = 1, 2,mj, k = 1, 2,mj+1, (6) ? ? ? ? ? ? ? ? ? n i=1 xi,lsi,1,k n i=1 xi,l+1si,1,k, i = 1, 2,n, l = 1, 2,n ? 1, k = 1, 2,m1, (7) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? n i=1 xi,l1 yi,j,kei,j,k n i=1 xi,l2 yi,j,ksi,j,k +(1? n i=1 xi,l2 yi,j,k)L, l1, l2 = 1, 2,n, l1 l2, j = 1, 2,S, k, k = 1, 2,mj, (8) xi,l = 1, 若工件 i 被安排在第 l 个位置, 0, 否则, (9) yi,j,k = 1, 若工件 i 的工序 j 在机器 k 上, 0, 否则, (10) 其中: 式(1)为调度性能指标;

式(2)确保每个优先级 位置只能对应一个工件;

式(3)确保每个工件只有一 个优先级位置;

式(4)表示任一阶段每个工件只能在 一台机器上加工;

式(5)表示同一阶段上工序完成时 间和开始时间的关系;

式(6)则表示同一........