基于无等待约束的供应链在线调度问题

基于无等待约束的供应链在线调度问题 1 ,2 1常桂娟,张纪会 ()1 . 青岛大学 复杂性科学研究所 ,青岛 266071 ; 2 . 青岛农业大学 理学院 ,青岛 266109 摘 要 : 研究了供应链在线调度问题 . 给出了在不改变已有工件调度的情况下 ,最早完成临时订单的算法 ,该算 法在寻优过程中结合了微粒群算法的局部搜索能力 ,计算机仿真结果表明 ,在大规模订单的情况下 ,该算法同样 能很快找到最优加工方案. 关键词中图分类号 : 在线调度 : F 273 ; 供应链 ; 实时文献标识码 ; 微粒群优化算法 : A 供应链计划与调度在供应链管理中具有核心地位 . 在供应链在线调度问题中 ,顾客随时都可能给制造 商下达订单 ,制造商接到订单后 ,根据订单的紧急程度来安排加工生产 ,并将最终商品运送给顾客 . 关于要 () 加工工件 这些工件被称为临时工件的到达时间 、数量及加工时间等信息 ,在工件进入生产加工系统之 前 ,都是未知的 ,因为其信息的不确定性 ,使得车间调度任务的难度大大增加. 在在线调度问题中 ,需要作 出的决策为 :如何安排临时工件的加工顺序及加工区间 ,使得这些工件在已有工件已经安排调度的情况下 能尽早完成 . 在线环境反映了许多供应链的实际情况 :顾客的订单依赖于不可预测的市场需求和波动 ; 在 制造商和顾客之间的活动难以为未来的订单作出计划或预测. 目前国内外研究供应链在线调度的文章还 1 不算多. Averbakh 等从理论上研究了供应链的在线调度问题 ,其中顾客给制造商下达订单 ,加工完成后 2 23 运送给顾客 ,其生产目标是最小化总费用. Chen 等给出了一种带有时间窗的化工生产线调度问题的组 合启发式算法 . 文献 4 中 Chauvet 等提出了对实时加工系统中增加一个临时工件的在线调度问题. 本文研究了供应链在线调度问题中制造商临时接到一批产品订单的调度问题 ,各种工件具有不同的 加工时间 ,怎样合理安排这些临时工件的加工顺序 ,使得这些工件在允许调度窗口内的加工时间最短是本 文研究的目标 . 当临时加工工件数为 1 时 ,可以直接按文献 4 中提到的算法计算 ,但随着临时工件规模的 增大 ,直接计算已经显得力不从心 ,本文使用了微粒群算法对临时进入加工系统的工件的加工顺序进行了 迭代 ,通过计算机仿真 ,使得问题在较短的时间内都能得到最优解. 1 微粒群算法描述 5 ( ) 微粒群优化算法Particle Swar m Op timizatio n Algo rit hm , PSO是一种基于群体智能理论的优化算 法 ,该算法通过模拟鸟类群体调整自身飞行速度和飞行方向 ,将所有个体移动到适应度好的环境中 ,从而 抽象出一种可以求解具有复杂解空间性质问题的优化算法 . 它既保持传统进化算法深刻的群体智慧背景 , 同时又有自己许多良好的优化性能 . 同时 ,在进化过程中该算法保留位置与速度上的信息 ,由于其概念和 参数调整简单而且容易编程实现 . 因此 , PSO 算法一经提出 ,立刻引起进化计算领域学者们的广泛关注. 传统微粒群算法的早期应用是在连续函数优化问题上展开的 ,其优化性能通过大量的实验已得到证 实 . 在微粒群算法中 ,粒子的位置和速度均以连续参数形式表示 ,这种连续实数域中的位置2速度计算模型 限制了粒子群算法在离散组合优化问题领域的应用. 从查阅的国内外文献看 ,近两三年微粒群算法才开始 被应用于求解组合优化问题 ,由于组合优化问题求解的困难性 ,相关文献较少 ,主要涉及旅行商问题 、车辆 收稿日期 : 2007206221 () ( ) 基金项目 : 国家自然科学基金资助项目 70671057; 教育部博士点基金资助项目 20051065002; 山东省“泰山学者” 路径优化问题等. 近几年 ,国内一些用粒子群算法解决车间调度问题的文献也开始陆续出现. 其中有夏蔚 6 7 军等提出的微粒群算法与模拟退火算法结合的混合启发式算法. 彭传勇等利用遗传算法交叉变异操 作的思想 ,提出了将粒子群算法与禁忌搜索相结合的广义粒子群优化算法. 本文通过分析传统微粒群算法的优化机理 ,提出了一种基于粒子坐标值排列编码的改进微粒群优化 模型 ,并以此模型为基础构建了适合调度问题求解的改进微粒群优化算法 . ( ) 在 n 维空间中有 N 个粒子 , 每个粒子的坐标为 X = X , X , ?, X , 并具有与优化目标函数相关 i i1 i2 i n ( ) 的适应度 Fi t , 同时每个粒子具有各自的速度 V = V , V , ?, V . 对于粒子 i 所经历过的历史最好 i i i1 i2 i n ( ) ( 位置记为 P= P, P, ?, P, 也称为 p . 群体所有粒子经历过的最好位置表示为 P= P, P, ?, i i1 i2 i n best g g1 g2 ) P, 也称为 g. 粒子群算法描述如下 : g n best ( )( ( ( ( ( )) )) ) ( ( ( ) ) )V t + 1= W V t + crPt X t ,1 - - X t + crPt i d i d 1 1 i d i d i d 2 2 g d ( ) ( ) ( )= X t + V t + 1, ( )X t + 1 2 i d i d i d 利用上述两式计算第 t + 1 代第 i 维的速度和位置. 式中下标 d 表示粒子的维度 , i 指第 i 个粒子 , W 是惯 ( ) 性权值 , c, c都是正的常数 , 称为加速系数 acceleratio n coefficient , r, r是两个在 [ 0 , 1 ]范围内变化的 1 2 1 2 ( ) 随机数. 1式中 , 等式右侧第一部分为粒子上一代的速度 , 它使粒子在搜索空间中有扩张的趋势 , 从而使 算法具有全局搜索的能力 ; 第二部分为“认知”部分 , 是粒子吸取自身经验知识的过程 ; 第三部分为“社会” 部分 , 是粒子学习其它粒子经验的过程 , 表现了粒子间信息的共享与社会协作 . 微粒群算法流程如下 : ? 初始化一群粒子 ,随机产生每个粒子的位置和速度 ; ? 评价每个粒子的适应度 ; ? 对于每个粒子 ,将其适应度值与自身 p 比较 ,如果优于 p ,则将当前值设为该粒子的 p ; best best best ? 对于全体粒子 ,将当前最优适应度值与 g比较 ,如果优于 g,则将当前最优适应度值设为群体 best best g;best () () ? 由 1, 2两式计算每个粒子的新速度和位置 ; ? 如未达到终止条件 ,则返回第 ?步 . ( )2 改进微粒群算法 IPSO 2 . 1 编码 在传统的微粒群算法中 ,粒子的位置和速度均以连续参数形式表示 ,这种连续实数域中的位置2速度 计算模型限制了粒子群算法在离散组合优化问题领域的应用 . 针对这一问题 ,本文提出了一种新的编码方 法 ,即基于粒子坐标位置排列编码. 这种编码方法成功的将解决连续优化问题的粒子群算法应用到流水车 ( ) 间调度 FSP这种离散问题当中 ,操作简单 、易于实现. 例如 ,对于 9 个工件加工的排序问题 ,表 1 给出了 粒子的位置对应 FSP 问题解的表达形式 . 表中 ,粒子位置中最小的坐标值所在的粒子维数对应于工作排 列的位置 1 处 ,倒数第二的坐标值所在的粒子维数对应于工作排列的位置 2 处 ,依此类推 . 如表 1 ,根据粒 () 子位置 ,我们得到这样一组排列 X = 5 6 3 8 9 2 1 7 4,它就表示临时工件的加工顺序 . 这种解的表示方 , 使 PSO 算 线性地减小到相对较小的值 表 1 FSP 问题中的粒子表示 法使得粒子中每一位置坐标对应一个工件. 法在开始时具有很强的全局搜索能力而 Tab. 1 Particle p resentatio n of FSP p roblem 在算法接近结束时具有更好的局部搜索 2 . 2 惯性权重与加速系数 1 2 3 4 5 6 7 8 9 粒子维数 能 力 , 计 算 公 式 为 : W = - W - 0 . 89 3 . 10 - 2 . 34 - 1 . 20 2 . 45 max 2 . 40 1 . 71 0 . 26 1 . 20 粒子位置 在微粒群优化算法中 , 惯性权重 W 是关系到 PSO 算法搜索能力的重要参数 , 将 W 从相对较大的值 5 6 3 8 9 2 1 7 4 工件排列 W - W max minN . 其 中 , W , W 为 惯 max min N max 性权重的初始值和最终值 ; N 为最大迭代次数 ; N 为当前迭代次数 . 在本文的计算实例中 , W = 1 . 2 , maxmax W = 0 . 4 . 加速系数 c, c根据经验均选取为 2 . min 1 2 3 在线调度问题 本文研究实时调度问题 ,其特点就是工件在任意时刻都可能进入到加工系统中 ,而且还要尽可能早的 加工完. 当一个临时工件进入到加工系统时 ,其他已经作好调度的工件无需改变它们的调度时间 ,临时工 件只在资源可以调度的时间区间内加工. 因为 ,在有些生产加工系统中 ,重新调度并不现实 ,重调度成本非 常昂贵 ,如果变动也可能会影响到其他工件的交货期 ,从而受到惩罚 . 所以在这种情况下 ,生产的目标就是 在不打乱其他现存工件调度的前提下 ,充分利用可以使用的区间来加工这些临时工件 ,并且合理的安排它 们的加工顺序 ,使得它们能尽早完成 . 在实时调度系统中 ,资源可以使用的加工时间是一些时间区间值 . 是否能在这些区间值上加工取决于 ( ) 要加工的工件的加工时间及资源的空闲时间 . 而且 ,本文讨论的问题是无等待 no2wait 约束 ,即一个工件 的前道工序结束后立即转入下一道工序的加工 ,这里安装时间不加考虑 . θδθ本文中 ,临时工件的加工时间介于两个数值之间 ,分别用 ,+ 表示工件在资源 i 内可以加工的 i i i 时间下界和上界. 这种实时加工系统还要注意的是工件要在允许加工时间区间内加工 ,如果超过 ,则会导 致该资源上的其他工件无法正常加工 . 因此 ,合理安排临时工件的加工顺序和加工时间就显得至关重要 . 本文研究的这类实时系统是以金属表面的化学氧化工艺加工为背景 ,金属部件采用化学浸渍方法处 理 ,以形成氧化膜层 ,每种不同的化学药品使用不同的容器来盛放 ,这些部件需要依次经过不同的化学药 品进行相关的表面处理 . 本文讨论的问题与传统的车间调度问题区别在于 :第一 ,工序的加工时间介于一个区间 ;第二 ,工件可 能随时进入生产系统 ,控制系统必须实时反应 ,对进入系统的每个工件要迅速有效地进行调度 ;第三 ,无等 待约束 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 工件的一道工序加工完后必须立即转入下一道工序 ,除非是在工件转移过程中 ,可以忽略转移 时间. 由此可知 ,一旦一个工件由控制系统进行调度了 ,它就不允许重新调度. 因此 ,每个新到的工件的调 度不能影响到其他已经安排调度的工件的生产 . k k 用符号 a表示盛放化学药品 i 的容器 j 的第 k 个允许加工区间的开始时间 , b表示盛放化学药品 i ij ij 假设有 m 种不同的化学药品来处理金属零部件 , 每种化学药品分别有 n 个容器 , 这里 i = 1 , 2 , ?, i 的容器 j 的第 k 个允许加工区间的结束时间. 用 x 表示工件在化学药品 i 里开始浸泡的时间. i m . k 把盛放同一种化学药品的容器归为一类 , 把它们的可以加工区间按 a递增的顺序排列 , 如果有区间 i j k k (α 左端点 a相同 , 则按 b的递增顺序排列. 排列完毕 , 我们可以得到这样一个加工时间序列 S = { , i j ij i i r iβ) } , 其中 r= 1 , 2 , ?, q, q为盛放药品 i 的容器总数 . i r i i i i ( 这样 , 问题就可以描述为寻找 x , x , ?, x , x 其中 x 表示工件在第 i 种药品里浸泡的开始时 1 2 m m + 1 i ) 间 , x 表示最后一道工序的结束时间及加工时间区间 , 使得 x 最小 , 并且还要满足下列关系式 : m + 1m + 1 θδθi = 1 , 2 , ?, m , ? x - x ?+ ii +1 i i i αβx x ?, ?. i i r i r i +1i i 这个问题可以通过下面的两个算法解决. 算法 1 步骤 1 对临时工件 ,随机产生初始加工顺序 ,选出要进入加工系统的工件. (αβ) 对每种化学药品 ,我们给出如上所述的加工区间序列 S = { ,} , r= 1 , 2 , ?, q, i = 步骤 2 i i r i r i i i i 1 , 2 , ?, m . 对每一个 i = 1 , 2 , ?, m , 令 r= 1 . i 步骤 3 使用下面等式构造一个时间序列 X = { x , x , ?, x } : 1 2 m + 1 步骤 4 αt = , 1 1 r1 (αθ)t = max , t + i = 2 , 3 , ?, m , i i r i - 1 i - 1 i x θt = t +, m + 1 m m = t ,m + 1 m + 1 ( θδ)x = max t , x - - i = m , m - 1 , ?, 1 . i i i + 1 i i β步骤 5 如果对于所有的 i , 都有 x ?, 转入步骤 7 ; 否则转步骤 6 . i + 1 i r i β对于所有使得 x >的 i , 令 r= r+ 1 , 返回步骤 4 . 步骤 6 i + 1 i r i i i 更新加工区间序列 , 对容器剩余可用加工区间按文中方法重新排列 , 得到新的加工区间序 步骤 7 列 . 步骤 8 按工件的加工顺序 ,选出下一个进入加工系统的工件 ,转入步骤 3 . 注意 ,在调度完一个工件之后要更新加工区间 ,以充分利用设备的空闲时间 ,从而达到目标函数生产 ( ) 周期 makespan最短. 随着临时工件规模的增大 ,为尽早完成这些订单任务 ,就需要考虑订单的加工顺序 ,本文随机产生初 始加工顺序 ,将微粒群算法与上述算法结合 ,以求得最优调度. 算法 2 步骤 1 通过对问题及解的特性进行分析和了解 ,设定粒子群体规模及最大迭代次数 . 步骤 2 假设有 N 个临时工件 , 采用随机产生粒子的位置和速度的方法初始化粒子群. 初始粒子的 坐标值和速度值限制在 - 4 与 4 之间. 按初始加工顺序 , 选出要进入加工系统的工件. αβ) (步骤 3 对每种化学药品 , 给出如上所述的加工区间序列 S = { ,} , r= 1 , 2 , ?, q, i = 1 , 2 , i i r i r i i i i ?, m . 步骤 4 对每一个 i = 1 , 2 , ?, m , 令 r= 1 . i X = { x , x , ?, x } :步骤 5 使用下面等式构造一个时间序列 1 2 m + 1 α(αθ)θi = 2 , 3 , ?, m , t x = t ,t = , t = max , t + = t + , 11 ri i r i - 1 i - 1 m m m +1m +1 m +1 1 i ( θδ)i = m , m - 1 , ?, 1 . x = max t , x - - i i i +1 i i β步骤 6 如果对于所有的 i , 都有 x ?, 转入步骤 8 ; 否则转步骤 7 . i + 1 i r i β对于所有使得 x >的 i , 令 r= r+ 1 , 返回步骤 5 . 步骤 7 i + 1 i r i i i 更新加工区间序列 , 对容器剩余可用加工区间按文中方法重新排列 , 得到更新后的加工区间 步骤 8 (αβ) 序列 S = { ,} , r= 1 , 2 , ?, q, i = 1 , 2 , ?, m . i i r i r i i i i 9 步骤 按工件的加工顺序 , 选出下一个进入加工系统的工件 , 转入步骤 4 . 步骤 10 ( ) 得到每个工件 粒子的完工时间 , 计算目标函数值 , 并记录全局最优粒子 g及个体最优 best 粒子 p .best ( ) ( ) 对 N 个粒子利用微粒群优化公式 1, 2产生新一代粒子群的位置及速度 , 并对全局最优 步骤 11 粒子和个体最优粒子进行更新. 步骤 12 满足最大迭代次数则输出最优适应度函数值并终止 ; 否则 , 返回步骤 3 . 4 算 例 算例 1 我们考虑这样一个算例 ,临时工件需要在 3 种化学药品中浸泡 ,这 3 种化学药品分别盛放在 不同容器中 ,盛放第一种药品的容器有 4 个 ,盛放第二种药品的容器有 3 个 ,盛放第三种药品的容器有 3 个 . 这些容器可以使用的加工时间区间如下. ) 第一种化学药品 :容器 1 : 0 , 4 ; 6 , 9 ; 10 , 17 ; 29 , + ?; 容器 2 : 0 , 5 ; 7 , 12 ; 20 , 27 ; 40 , ) ) ) + ?;容器 3 : 3 ,6 ; 8 ,9 ; 15 ,19 ; 30 , + ?;容器 4 : 2 ,5 ; 7 ,9 ; 23 , + ?. ) ) 第二种化学药品 :容器 1 : 1 ,7 ; 9 ,18 ; 24 , + ?;容器 2 : 3 ,6 ; 9 ,12 ; 20 ,24 ; 30 , + ?;容器 ) ?. 3 : 2 ,5 ; 8 ,10 ; 35 , + ) ) ?; 容器 2 : 3 , 10 ; 12 , 17 ; 32 , + ?; 容器 3 : + 第三种化学药品 :容器 1 : 5 ,9 ; 11 ,15 ; 28 , ) ?. 4 ,8 ; 9 ,15 ; 18 ,29 ; 35 , + 对每种化学药品 , 我们将其可加工区间按递增的顺序排列得化学药品 ?: S = { 0 , 4 ; 0 , 5 ; 2 , 5 ; 1 ) ) ) 40 , [ 3 , 6 ; 6 , 9 ; 7 , 9 ; 7 , 12 ; 8 , 9 ; 10 , 17 ; 15 , 19 ; 20 , 27 ; 23 , + ?; 29 , + ?; 30 , + ?; ) ) 30 , + ?} ; 化学 药 品 ?: S = { 1 , 7 ; 9 , 12 ; 24 , + ?; 2 , 5 ; 3 , 6 ; 8 , 10 ; 9 , 18 ; 20 , 24 ; 2 ) ) 11 , 15 ; 12 , 17 ; 18 , 29 ; + ?; [ 35 , + ?} ; 化学药品 ?: S = { 3 , 10 ; 4 , 8 ; 5 , 9 ; 9 , 15 ; 28 , 3 ) ) ) + ?; [ 32 , + ?; 35 , + ?} . 3 个临时工件的 3 道工序加工时间区间为工件 1 : 4 , 5 ; 3 , 4 ; 4 , 6 ; 工件 2 : 2 , 4 ; 3 , 4 ; 6 , 7 ; 工件 3 : 3 , 4 ; 5 , 7 ; 2 , 4 . 使用本文所提算法 2 对该算例用 Matlab 进行计算机仿真 ,初始种群大小根据问题的规模来设定 ,当 临时工件规模较小时 ,可选取较少的粒子进行迭代. 对上例 ,种群规模设为 10 ,迭代次数也设为 10 . 仿真结 果显示最短加工时间为 32 . 通过仿真试验可以发现 ,10 个初始粒子在迭代 10 次之后 ,均得到生产周期为 32 的仿真结果 ,由此可见本文算法对在线调度问题表现出了良好的计算能力及收敛能力. 图 1 给出了 3 个工件的最优调度的甘特图. 图 1 3 个工件的最优调度 Fig. 1 The op timal scheduling of t hree jobs 算例 2 为验证本文所提算法的有效性 ,本例给出了较大规模的在线调度问题 ,临时加工工件数为 10 ,每个工件有 8 道工序 ,即有 8 种化学药品 . 每种化学药品可能有多个容器来盛放 ,下面直接给出盛放不 同药品的容器的可以加工时间区间 . 化学药品可加工区间分别为 : S = { 0 , 3 ;0 , 5 ; 2 , 5 ; 6 , 9 ; 7 , 13 ; 8 , 10 ; 10 , 16 ; 15 , 19 ; 17 , 25 ; 21 , 28 ; 30 , 37 ; 1 ) [ 40 , + ?} ; S = { 1 , 6 ; 2 , 5 ; 4 , 6 ; 7 , 10 ; 9 , 12 ; 9 , 18 ; 15 , 19 ; 20 , 26 ; 27 , 30 ; 32 , 37 ; 42 , 49 ; 2 ) [ 53 , + ?} ; ) S = { 4 , 10 ; 5 , 8 ; 5 , 11 ; 9 , 14 ; 11 , 16 ; 12 , 17 ; 18 , 26 ; 32 , + ?} ; 3 S = { 3 , 6 ; 4 , 7 ; 4 , 9 ; 7 , 11 ; 8 , 12 ; 9 , 18 ; 15 , 19 ; 20 , 26 ; 29 , 36 ; 32 , 39 ; 42 , 49 ; 4 ) [ 55 , + ?} ; S = { 2 , 4 ; 4 , 8 ; 4 , 9 ; 7 , 14 ; 9 , 12 ; 9 , 16 ; 13 , 19 ; 18 , 26 ; 21 , 32 ; 31 , 35 ; 40 , 47 ; 5 ) [ 49 , + ?} ; S = { 7 , 9 ; 7 , 13 ; 8 , 12 ; 9 , 15 ; 13 , 19 ; 15 , 19 ; 21 , 27 ; 24 , 30 ; 30 , 37 ; 32 , 40 ; 43 , 6 ) 67 ; 53 , + ?} ; S = { 9 , 16 ; 13 , 18 ; 15 , 18 ; 20 , 27 ; 28 , 35 ; 35 , 39 ; 42 , 49 ; 48 , 57 ; 59 , 65 ; 70 , 87 ; 7 ) [ 90 , + ?} ; S = { 10 , 16 ; 12 , 15 ; 14 , 18 ; 17 , 22 ; 19 , 28 ; 19 , 29 ; 24 , 31 ; 28 , 39 ; 37 , 50 ; 48 , 57 ; 8 ) [ 53 , 60 ; 68 , 76 ; 74 , 90 ; 83 , + ?} . 临时工件的加工时间区间分别为 : 工件 1 : 2 , 3 ; 3 , 5 ; 3 , 4 ; 2 , 4 ; 4 , 6 ; 3 , 5 ; 2 , 3 ; 3 , 4 ; 工件 2 : 1 , 2 ; 3 , 4 ; 2 , 4 ; 1 , 3 ; [ 3 , 5 ; 4 , 5 ; 3 , 4 ; 2 , 4 ; 工件 3 : 3 , 4 ; 3 , 5 ; 2 , 4 ; 1 , 3 ; 3 , 5 ; 2 , 3 ; 2 , 4 ; 1 , 2 ; 工件 4 : 4 , 5 ; 2 , 3 ; 1 , 2 ; 1 , 3 ; 2 , 4 ; 3 , 4 ; 2 , 4 ; 1 , 2 ; 工件 5 : 3 , 5 ; 2 , 3 ; 1 , 3 ; 2 , 3 ; 3 , 4 ; 2 , 4 ; [ 2 , 3 ; 2 , 4 ; 工件 6 : 2 , 3 ; 3 , 4 ; 3 , 4 ; 2 , 3 ; 5 , 6 ; 2 , 3 ; 2 , 4 ; 3 , 4 ; 工件 7 : 3 , 5 ; 3 , 4 ; 2 , 3 ; 1 , 2 ; 2 , 4 ; 2 , 3 ; 1 , 3 ; 1 , 2 ; 工件 8 : 2 , 4 ; 3 , 5 ; 2 , 3 ; 2 , 3 ; 3 , 4 ; 2 , 4 ; 2 , 3 ; 1 , 2 ; 工 件 9 : 3 , 4 ; 2 , 3 ; 1 , 3 ; 2 , 4 ; 3 , 4 ; 2 , 3 ; 4 , 5 ; 2 , 3 ; 工件 10 : 3 , 5 ; 2 , 4 ; 1 , 2 ; 3 , 4 ; 2 , 3 ; [ 3 , 5 ; 4 , 5 ; 2 , 3 . 对该算例 ,种群规模取为 20 ,迭代次数为 60 ,经 Matlab 实验仿真结果显示 ,最优解是 79 ,下列矩阵 6 9 12 15 18 23 25 27 30 0 3 5 6 8 11 13 15 17 0 3 5 7 9 12 14 18 20 10 14 18 20 23 25 28 32 34 40 42 45 47 49 52 54 56 57 A = 50 53 56 59 61 65 70 72 75 18 20 23 25 26 30 35 38 40 53 58 61 63 66 70 73 75 76 58 61 64 67 70 73 75 77 78 64 68 71 77 61 73 75 78 79 记录了取得最优解时 ,工件顺序为 6 的工件在每个容器中加工的起始时 7 5 9 10 8 1 2 4 3 表示工件 6 在第一个容器的 间和结束时间 ,如矩阵 A 第一行 6 ,9 加工区间 , 9 ,12 表示工件 6 在第二个容器的加工区间 ,依此类推 , 27 ,30 表示工件 6 在最后一个容器的加工区间 . 而且从仿真结果 中也可以得出 ,最优调度并不惟一. 在实际问题中 ,制造商可以根据 自己的实际情况选择合适的调度 . 图 2 给出了算例 2 中迭代次数为 60 的计算机仿真结果 ,从图 中容易看出 ,在第 17 代种群就迅速收敛到最优解 79 . 5 结 论 本文给出了在线调度问题中接到临时加工订单 ,而又不改变其 图 2 迭代 60 次仿真图 Simulatio n result wit h sixty iteratio ns Fig. 2他已有工件调度的算法 . 该算法结合了微粒群 算 法 的 局 部 搜 索 能 力 ,使得问题在较大规模的时候 ,使用较小规模的种群及进化代数 ,同样能在较短时间收敛到最优解 . 实验 仿真结果验证了本文算法的有效性和优越性 . 参考文献 : 1 Averbakh I , Xue Z H. On2line supply chain scheduling p roblems wit h p reemp tio n J . Eu ropean Jou r n al of O perat ion al Resea rch , 2007 ,181 : 5002504 . 2 Chen H X , Chu C , Prot h J M . Sequencing of part s in robotic cellsJ . I nter n at ion al Jou r n al of Flex ible M an u2 () f act u ri n g S ystems ,1997 , 9 1:812103 . 3 Chen H X , Chu C , Prot h J M . Cyclic scheduling of a hoist wit h time windows co nst raint sJ . I E E E T ransac2 () t ions on Robot ics an d A utom at ion , 1998 ,14 1: 1442152 . 4 Chauvet F , L evner E , Meyzin L K , et al . On2line scheduling in a surface t reat ment system J . Eu ropean Jou r n al of O perat ion al Resea rch , 2000 ,120 :3822392 . Kennedy J , Eber hart R. Particle swarm op timizatio n : I EEE Internatio nal Co nference o n Neural Net wor ks , 5 Pert h , Aust ralia , 1995 C . Pert h , Aust ralia : s. l . ,1995 :1942 21948 . 6 ( ) 夏蔚军 ,吴智铭 ,张 伟 ,等 . 微粒群优化在 Job2shop 调度中的应用 J . 上海交通大学学报 , 2005 ,39 3: 3812385 . 7 彭传勇 ,高 亮 ,邵新宇 ,等 . 求解作业车间调度问题的广义粒子群优化算法 J . 计算机集成制造系统 , () 2006 ,12 6: 9112917 . On2l ine Supply Cha in Schedul ing Problems Ba sed on No2wa it Constra int 1 ,2 1CHAN G Gui2jua n, ZHAN G J i2hui ( 1 . Com plex i ty S cience I nst i t ute , Q i ng d ao U ni versi t y , Q i ng d ao 266071 , Chi n a ; )2 . T he Col lege of S cience , Q i ng d ao A g ricul t u ral U ni versi t y , Q i ng d ao 266109 , Chi n a Abstract : On2line supply chain scheduling p roblems were considered when customers release jobs to a manufact urer t hat has to p rocess t he jobs. There is not any information about t he coming order such as t he order quantit y , release , and p ro2 cessing time , etc. The objective is to minimize t he makespan. An algorit hm combining wit h t he local search abilit y of par2 ( ) ticle swarm optimization algorit hm PSOduring searching optimal solution is p roposed. The simulation result s show t hat t he optimal solution can be obtained rapidly wit hout changing t he ot her jobs’schedule. Key words : on2line scheduling ; supply chain ; real2time ; particle swarm optimization algorit hm