求解带有阻塞限制的HFSP的 MILP模型与改进回溯搜索算法

孟磊磊 张超勇 任彩乐 李振国 任亚平 , ,430074 华中科技大学数字制造装备与技术国家重点实验室 武汉

China Mechanical Engineering - - CHINA MECHANICAL ENGINEERING -

: . ,

编者按 调度技术是生产过程智能化和供应链优化的核心技术 目前 工业制造过程计划调度决策主要、 、 . ,依赖管理者 调度员 工程师等知识型工作者人工进行 但是 仅依靠人工决策已无法适应智能制造的, . ,要求 必须向人工智能驱动的智能调度转变 为交流我国车间智能调度相关的最新研究成果 探讨车间, ,智能调度的发展方向和趋势 把握车间智能调度的研究前沿及应用重点 促进我国智能制造工程的发展,« » .和落地应用 中国机械工程 杂志社决定出版车间智能调度专辑

: , ,

摘要 针对带有阻塞限制的不相关并行机混合流水车间调度问题 以最小化最长完工时间为目标 依

, 4 (MILP) ;据不同的建模思想 建立了求解该问题的 个混合整数线性规划 模型 鉴于混合整数线性规划不

, , ,适合求解中大规模问题 提出了一种改进的回溯搜索算法以求解中大规模问题 在该算法中 引入了轮盘, . , MILP赌选择策略以及变邻域搜索算法 以提高算法的收敛速度以及局部搜索能力 最后 对所提 模型以, MILP .及算法进行了对比分析 通过对具体实例的求解验证了所提 模型以及算法的有效性及优越性: ;; ; ;

关键词 混合流水车间调度 阻塞 混合整数线性规划 回溯搜索算法 轮盘赌选择策;略 变邻域搜索 中图分类号:TP18 DOI:10.3969/j.issn.1004 132X.2018.22.001

MILP ModelsandanImprovedBSAforHybridFlowShop

SchedulingProblemswithBlocking

MENG Leilei ZHANG Chaoyong REN Caile LIZhenguo REN Yaping StateKeyLabofDigitalManufacturingEquipmentandTechnology,HuazhongUniversity

ofScienceandTechnology,Wuhan,430074 Abstract: Thehybridflowshopschedulingproblemswithblocking(HFSPGB)werestudied with theminimizationofmakespans.Firstly,fourMILP modelswereproposedbasedondifferentmodeling ideas.Secondly,duetotheinefficiencyofthe MILP modelto mediumGlargeproblems,animproved backtrackingsearchoptimizationalgorithm(IBSA)wasproposed.Inthisalgorithm,rouletteselection strategyandVNSwereintroducedtoimprovetheconvergencerateandlocalsearchability.Atlast, numericalexperimentswerecompletedonrealinstancesandtheresultsshowtheeffectivenessandsuG periorityoftheproposed MILP modelsandtheIBSA.

Keywords: hybridflowshopscheduling;blocking;mixedintegerlinearprogramming(MILP); backtrackingsearchoptimizationalgorithm(BSA);rouletteselectionstrategy;variableneighborhood search(VNS)

0 引言

混合流水车间调度问题 (hybridflow shop

收稿日期:2018 05 21

基金项目:国家自然科学基金资助项目(51575211,51705263); () (51561125002);国家自然科学基金国际 地区 合作与交流项目

(20180101058JC);吉林省自然科学基金资助项目 浙江省自然(LQ16G010002);科学基金资助项目 高等学校智能制造创新引

(B16019)

智计划资助项目 schedulingproblem,HFSP)

又称为柔性流水车间

(flexibleflowshopschedulingproblem,调度问题FFSP), , 、、、、

应用行业很广 如化工 冶金 纺织 机械

、、、半导体 物流 造纸 建筑等很多领域问题都可归结

HFSP.HFSP 3:为 按照并行机类型分为 类 相同并行机 HFSP、均匀并行机 HFSP以及不相关并行HFSP, , [ 1].机 其中 不相关并行机HFSP最为复杂

HFSP

以前针对 的研究都假设各加工阶段

, ,之间的缓冲区无限大 可以存放任意数量的工件

, ,但在实际生产过程中 由于设备或空间的限制 相[ 2G3].邻阶段间缓冲区是有限的或者不存在缓冲区

,如果相邻阶段间缓冲区是有限的 则该问题为缓

HFSP(HFSP withlimitedbuffers,冲区有限的HFSPGLB).HFSPGLB :

可描述为 工件在某一阶

, ,段加工完成后 如果其下一个阶段有空闲的机器那么它可以直接被送到下一个阶段继续进行加

;工 如果下一阶段没有空闲机器且缓冲区仍有存, ,,储能力 则该工件进入缓冲区 否则 该工件阻塞[ 4].在该阶段所选加工机床上 如果相邻阶段间没

,有缓冲区 则该问题为带阻塞限制的混合流水车

(HFSP with blocking,HFSPGB).间调度问题HFSPGB ,

在 中 如果一个工件在一个阶段完成加

, ,工后 其下一阶段没有空闲机器 则该工件只能滞,留在该阶段所选机器上 直至下一阶段有空闲机

[ 4]. ,器 阻塞状态会增加工件的等待时间 导致总完, ,, HFSPGB工时间延长 影响生产效率 因此 研究

.具有重要的实践意义

HFSPGB ,WARDONO

关于 方面的研究[4] ,等 提出了一种禁忌搜索算法 并提出一种根据

.工件 序 列 构 造 出 完 整 调 度 方 案 的 算 法TAVAKKOLIGMOGHADDAM [5G6]

等 提出了一

Memetic HFSPGB.种有效的 算法来求解 列车调

HFSPGB , [7G8]度问题是典型的 问题 张其亮等 针对

,该问题 提出了一种混合迭代邻域的粒子群优化

,算法 并设计了释放 回推算法来求解最长完工时

. [9]间 张其亮等 又研究了同时考虑阻塞以及无等HFSP .ZHANG [10]待限制的 问题 等 将集装箱

HFSPGB码头的集卡调度问题抽象为基于属性的, eMGPlant问题 并提出了基于遗传算法以及 仿真

. [11] HFSPGB

软件的组合求解方法 茜彦辉 针对

,最小化最长完工时间问题 提出了改进的微粒群

. [12]优化算法 陈璐等 提出了一种禁忌搜索算法

HFSPGB和优先级规则相结合的方法来求解 最. ,小化最长完工时间问题 在重型机械加工车间, HFSPGB ,由于工件体积比较大 属于 问题 针对

, [13]该调度问题 陈超等 使用遗传算法对其进行求, DelmiaQUEST解 并使用物流仿真软件 验证了. [14]其有效性 陈飞跃等 提出了改进的布谷鸟搜HFSPGB ,索算法来求解 问题 求解结果优于文献

[8] .YUAN [15]

中粒子群算法求得的结果 等针

HFSP,对考虑阻塞限制的 提出了求解该问题的

(mixedintegerlinearproG混合整数线性规划gramming,MILP) 、模型 问题下界求解方法以及

.RASHIDI [16]类电磁机制算法 等 针对同时考虑

HFSPGB ,序列相关调整时间的 问题 以最小化最

长完工时间和最大拖期为目标,提出了基于遗传算法的多目标求解方法.THORNTON等提[17]

出了一种基于先到先服务(FCFS)规则的启发式算法来求解 HFSPGB问题.

综上,求解 HFSPGB主要有 MILP模型[15]、

启发式方法[17]以及元启发式方法[ 7G9,14]. MILP

模型为精确求解方法,针对小规模问题可以求得

, 、问题的最优解 可以通过使用分支定界 分支剪枝[ 18].以及动态搜索等方法来求解 但针对中大规模问题,MILP模型求解时间太长甚至无法得到. 、可行解 如粒子群算法 遗传算法等元启发式方, ,法虽然为近似求解方法 不可保证可求得最优解,但其求解效率高 高效的元启发式算法可以在较

.短时间内得到问题的满意解

回溯搜索算法(backtrackingsearchoptimiG zationalgorithm,BSA) CIVICIOGLU[ 19]

由 于2013 .年提出 作为一种新的基于种群迭代的进

,BSA化算法 在解决连续优化问题如函数优

[19]、 [20]、 [21]、化 神经网络权值 约束优化问题 切削

[22] .参数优化 等方面表现出良好效果 之后,LIN等及[23] LU等[24]通过对算法解空间以及进化操, .作进行重构 将其拓展到流水车间调度问题 与

,BSA ,其他算法相比 只有一个控制参数 操作简

; ,单 基于历史种群与当前种群两个种群 可以利用

;, ,先前种群的信息 同时 它在产生新种群时 不同

,于遗传算法中以较大概率选择较好个体 而是随,, .机选择 因此 该算法具有较强的全局搜索能力、但是,BSA存在收敛速度慢 局部搜索能力较弱的.问题 本文将锦标赛选择方法以及变邻域搜索引BSA, 、 .入 以加快其收敛速度 增强其局部搜索能力HFG目前笔者尚未查到研究不相关并行机SPGB MILP . ,问题的 模型 根据本文问题特性 首

3 ,4 MILP先基于 种不同的建模思想 建立 个 模

;,型 然后 设计了一种改进的回溯搜索算法以求解. , 4 MILP 、中大规模问题 最后 对 个 模型 改进回

,溯搜索算法以及已有文献中算法进行对比分析

.验证本文方法的有效性及优越性

问题描述

1.1

符号说明

, ,记i为工件序号n为工件总数I为工件集

1,2, , , ∈; ,合{ n}iIj且 为加工阶段序号 S为, 1,2, , ,

加工阶段总数 J为加工阶段集合{ S}

j ∈ J ; , m ,且k为机器编号 为机器总数 m 为加

j ,工阶段j的并行机数 K 为加工阶段j的并行机

j 1,2, , , {1,2, ,器集合{ mK }为总机器集合

j

mt }; 为机器位置序号, L 为机床k的位置集合

k { 1,2, , ; 为工件 在机器k上的加工时n}ti, i

k间, M为一个极大正数.

1.2 HFSPGB问题描述

HFSPGB : n S

问题可描述为 个工件在含有

,个加工阶段的流水线上进行加工 各个阶段至少存在一台机床且至少有一个阶段存在2台或多台

. ,机床 同时 同一阶段的多台机床加工同一零件,的加工时间是不同的 所有工件必须按顺序经过

. ,

S个阶段的加工 相邻阶段间没有缓冲区 工件,在上一阶段加工完后 如果下一阶段机床都被占,用 那么该工件将被阻塞在该阶段所选加工机床, .上 直至下一阶段存在可用机床: 0

该问题满足以下基本假设 机器与工件在

;时刻均处于可用状态 所有工件在所有机床上的;加工时间是已知的 同一机器上不同工件间的转

、换时间 以及同一工件不同阶段间的运输时间忽略; ;不计 工件可在每阶段的任意一台机器上加工 工; ,序一旦开始加工则不可中断 对于每台机床 在同

; ,一时刻最多只能加工一个工件 对于每个工件 在

;同一时刻最多只能被一台机床加工 所有工件后一.阶段的加工必须在前一阶段加工完工后方可开始

,HFSPGB 、

综上 需要解决机器选择 工件排序3 .HFSPGB及阻塞 个子问题 的目标就是合理解3 , .决这 个子问题 使最小化最长完工时间最小

2 MILP

模型的建立4 MILP . ,

本文总共建立 个 模型 其中 模型1 2及模型 基于不同工件间先后关系的建模思,3 ,4想 模型 基于机器位置的建模思想 模型 基于[ 18].相邻工件先后关系的建模思想 不同建模思、想的共同点都是通过引入工序的开始 结束以及

,离开时间来确定阻塞子问题 不同点在于通过引入不同含义的决策变量来确定机器选择以及工件

.排序子问题

2.1 1

模型1 0 G 1

模型 引入 与 两个 决策变量来

Xi, k Yi, ii, k分别确定机器选择以及工件在机床上的排序两个子. , ,问题 其中 Xi,用来确定机床选择子问题Yi, 用k ii, k .来确定不同工件在同一机床上的排序子问题

(1) .6 、决策变量 个决策变量分别为Xi, k、、、、 . ,

Ei,

Yi, ii, Bi, Ei, Di, C 其中 表示工序k j j j max j Oi, j ; ;的完工时间 表示工序 的开始时间 表示Bi, Oi, Di,

j j j

; .工序Oi,的释放时间C 表示最长完工时间 有

j max

{ 1 i k工件 安排在机器 上加工Xi, =

k 0 其他 { 1 在机器k上,工件i先于工件i加工, ii < Yi, = i i ii, k

0 其他(2)

目标函数为

minCmax (1) (3)

约束条件为Σ 1∀∈ ∈ (2)

= Xi, ,j

iI J

k

k ∈ Kj

Σ ( )∀∈ ∈ (3) = + X

Ei, Bi, ti, i, i I ,j

J

j j kk k ∈Kj ∀∈ ∈ {1,2, , 1} (4) = - Di, Bi, ,j

iI S

j j+ 1 ≤ (3- )

+ - -

Di, Bii, M Yi, ii, Xi, Xii, j j k k k

∀∈ , ∈ , < , ∈ ∈ (5) i Ii Ii i j J ,

kK i i j

(2+ ) ≤

+ - - Dii, Bi, M Yi, ii, Xi, Xii, j j k k k

∀∈ , ∈ , < , ∈ ∈ (6) i Ii Ii i j J ,

kK i i j ≤ ∀∈ ∈ (7) Ei, Di, i I ,j

J

j j

≤ ∀∈ (8) Di, Cmax i I

S ≥0 ∀ ∈ ∈ (9) Bi, ,j

iI J

j

, (2)其中 约束 表示任一工件在任一阶段只能选择. (3)在一台机床上加工 约束 表示工序开始时间,与结束时间之间的关系 即结束时间等于开始时. (4)~ (6)间与加工时间之和 约束 约束 表示阻塞, (4)约束 其中约束 保证同一工件任一阶段的释放.时间等于其下一阶段的开始加工时间 成对约束(5) (6) ,

与 用来保证同一机床上加工的非重叠性 即,保证在同一机床上 后加工工件的开始时间不少于

. (7)先加工工件的释放时间 约束 表示工序只有在. (8)加工完之后方可释放 约束 表示最长完工时间

. (9) .约束 约束 表示开始时间决策变量约束

2.2 2

模型2 1 ,01 G

模型 是对模型 的简化 决策变量数

. 1 ,

Yi,减少 对模型 中 进行分析 是为了确定ii,

k ,不同工件在同一机床上的排序 因为机床是与加,工阶段对应的 只需要确定不同工件在同一加工

,阶段的先后顺序以及机床选择 则可确定不同工

.

Yi,件在同一机床上的先后顺序子问题 将 降ii,

k

, , 0 1 Yi, G维到 从而大幅减少 决策变量个数 这ii,j ,

m是因为由于并行机的存在 机床数 大于或者远

. S大于阶段数(1) .6 、

决策变量 个决策变量分别为Xi,

k、、、、 . 0 1 G

新引入的 决策Yi, ii,j Bi, Ei, Di, C

j j j max变量 与 共同确定不同工件在同一机床Yi, ii,j Xi,

k

.上的排序子问题 有

{ 1 , , <在阶段j上 工件i先于工件i加工ii = i i

Yi,

ii,j

0 其他(2) . 1.目标函数 同模型(3) . (5) (6) 1

约束条件 模型 的成对约束 与:替换为如下约束

)

≤ + (3- - -

Di, Bii, M Yi, ii,j Xi, Xii,

j j k k

∀ i ∈, Ii i ∈ Ii ,< i i , j ∈ Jk ,∈ K j (10) Dii, j ≤ Bi, j + M (2+ Yi, ii,j - Xi, k - Xii, k ) ∀ i ∈, Ii i ∈ Ii ,< i i , j ∈ Jk ,∈ K j (11)

则得到模型2的约束.成对约束(10)与(11)表示只有工件i与工件i i在阶段j被安排在一台机床上加工时,才存在先后加工顺序.

2.3 模型3

不同于模型1与模型2,模型3基于机器位置的建模思想.引入机床位置占用决策变量Zi, , ,

kt , 通过确定不同工件在机床上的位置关系可同时确定机床选择以及不同工件在机床上的先

. Zi, Xi,后顺序两个子问题 决策变量 ,与上文 k kt ,,有关 因此 本模型不需要单独的机床选择决策变

Xi, , .量 从而减少决策变量个数 即

k

Σ = ∀∈ ∈ (12) Zi, , Xi, i I , kK kt k t ∈ Lk (1) .6 Zi, 、决策变量 个决策变量分别为 , kt、、、、 ,其中, Sk, 表示机器k Bi, j Ei, j Di, j Sk, t C max t

.上第t个位置的开始时间 有

{ 1 工件i安排在机器kt的第 个位置上加工

Zi, =

kt , 0 其他(2) . 1.目标函数 同模型(3)约束条件为ΣΣ

Zi, = 1∀∈ iI ∈ J (13)

,j

kt ,

k ∈Kj t ∈Lk Σ ≤1 ∀ k ∈ Kt , ∈ L (14)

Zi, kt , k iI ∈

Σ Σ Zi, ≥ ∀ k ∈ Kt , ∈ {1,2, , n - 1} kt , Zii, kt+ , 1 iI ∈ ii∈ I

(15)

Σ = + Z ∀ ∈ ,∈ (16) Fk, Sk, ti, i, , k Kt L

t t k kt k iI ∈ ≤ ∀ ∈ , ∈ {1,2, , 1}(17) Fk, Sk, k Kt n -

t t+ 1 ≤ (1- )

+ Sk, Bi, M Zi, , t j kt

∀∈ ,j ∈ , ∈ ,∈ (18) i I Jk K t L

j k

≥ (1- )

- Sk, Bi, M Zi, , t j kt

∀∈ ,j ∈ , ∈ ,∈ (19) i I Jk K t L

j k

≥ (2- 1)

- - Bii, Di, M Zi, , Zii, , j j kt kt+

(20)

∀∈ , ∈ , ≠ , ∈ ∈ i Ii Ii i j J ,

kK i i j t ∈ {1,2, , n - 1}

≥0 ∀ ∈ , ∈ (21) Sk, k Kt L

t k

ΣΣ

( Z ) ∀∈ ∈

= + Ei, Bi, ti, i, , ,j

iI J j j k kt

k ∈Kj t ∈Lk

(22)

, (13)其中 约束 表示任一工件只能选择在一个机

. (14)床的一个位置上加工 约束 表示任一机床

. (15)的任一位置最多只能安排一个工件 约束,表示工件在机床上加工时 先安排机床前面位置

. (16)后安排机床后面位置 约束 表示机床位置

. (17)开始时间与结束时间之间的关系 约束 表

示任一位置的开始时间不小于其紧前位置的结束时间.成对约束(18)与(19)表示如果工件在阶段开始时间等于机床该位置的开始时间j中安排在机床机床kt的第 位置,那么工件的.约束(20)表示安排在同一机床上两相邻位置的工件,后一位置工件只有等前一位置工件释放后方可开始加工,与约束(4)共同构成了阻塞约束.约束(21)为机床位置开始时间约束.约束(22)同约束(3)含义,表示工序结束时间等于开始时间与加工时间之和.

2.4 模型4 0 G 1决策变量Ui, ii, k用来确定机床选择以及不同工件在同一机床上的排序两个子问题,它与模型1中的决策变量Xi, k存在关系,表示如果某一工件在某一机床上加工,那么该工件在该机床上一定有一个紧前工件.因此,本模型不需要单独的机床选择变量 Xi, k ,从而减少决策变量个数即.

Σ Ui, ii, k = Xii, k ∀∈ i I , kK ∈ (23) i ∈ {0∪ Ii },≠ii i

该模型需要引入虚拟工件0,它在所有机床上的加工时间为0,为任一机床上的第一个工件,以便构造约束方程.

(1)决策变量.5个决策变量分别为Ui, 、ii, k

Bi,、、、Ei, Di, C ,有

j j j max

{ 1 在机器k上,工件i在工件i紧后加工,≠ ii Ui, = i i ii, k 0 其他(2) . 1.目标函数 同模型(3)约束条件为

ΣΣ Ui, = 1∀ ∈ ∈ (24)

iI ,j J ii, k i

i ∈ {0∪ Ii },≠ii k ∈Kj Σ Σ

Ui, ≥ Uii, ∀∈ i I , kK ∈ ii, k ik , i

i ∈ {0∪ Ii },≠ii i ∈ 0∪ Ii },≠ii (25)

Σ ≤1 kK ∈ (26)

U0, ik , iI ∈

Σ

≤ + (1- ) Di, j Bii, j M Ui, ii, k k ∈Kj

∀∈ , ∈ , ≠ , ∈ (27) i Ii Ii i j J

i i B0, = E0, = D0, = 0∀∈ jJ (28)

j j j

ΣΣ ( = + U )∀∈ ∈ Ei, j Bi, j ti, k ii, ik , ,j

iI J

k ∈Kjii∈ I

(29)

, (24)其中 约束 表示任一工件在任一阶段只能选择

, 0在一台机床上加工 因为虚拟工件 必须为每台使

,用机床上的第一个工件 所以不能约束虚拟工件

0. (25) ,

约束 表示任一工件在任一机床上加工时,一定存在紧前工件但不一定有紧后工件 机床上加. (26)工的最后一个工件没有紧后工件 约束 表示

虚拟工件0在任一机床上最多只能有一个紧后工件.约束(27)表示同一机器上相邻工件的先后关系,即工件的开始时间不少于其紧前工件的释放时间,与约束(4)共同实现了阻塞约束.约束(28)表示虚拟工件0时间变量约束.约束(29)同约束

(3),表示工序开始时间与结束时间之间的关系.

3 回溯搜索算法(BSA)

BSA由种群初始化、选择Ⅰ、变异、交叉及选择Ⅱ五部分组成[ 19]. (1)种群初始化.包括对历史种群Po 以及当前种群PC 进行初始化.即

P i o , j ~ Ul ( , u ) }

jj P C ~ Ul ( , u )

i ,j jj其中, i = 1,2, , s p , j = 1,2, , Ds , 表示种群

p规模, D表示个体长度,、lu 分别表示第j维分jj

量的最小值和最大值, U ( )表示均匀分布.

(2) I. ,选择 目的在于确定历史种群 当前种群有50%的可能性成为历史种群.即if a < b then Po = PC

其中, ab、 是(0,1)上服从均匀分布的随机数. (3) . Po ,变异 历史种群 确定后 对其中的个

, (: Po ′ )体进行随机排序 生成中间种群

M = PC + F (( Po ′ ) - PC )其中, F表示变异尺度系数,用来控制变异的程度.

(4) . 0 G 1 m ,

交叉 通过 矩阵 综合利用历史种

T :群与当前种群的信息产生子代种群

{ )= 0 ab < mi, = mi, um (r 1: rD

j )= 0 ab ≥ mi, randiD (

{ =1

= Mi, j mi, j Ti, j P C mi, =0

i ,j j , m N × DG 0 1 ,其中 为 的 矩阵 初始值所有元素

1; ( ) [0, ] ;为 randiD 为 D 中的随机整数 m 为混

r

,合比例参数 且为该算法中唯一需要人为设置的

. [0,1] ;参数 r为 区间的随机数u为随机排序后

, u ∈[ 1,2, , D ].BSA的整数向量 算法通过使() ( )用m rD 取整 和randiD 控制了交叉的程r

, < , 0; ,度当ab时 m 为多个元素置为 反之 m

i

0.为仅有一个元素置为(5) Ⅱ.

选择 目的在于更新当前种群以及保

.存当前最优解 用T中所有适应度比PC 较好的

, .个体代替PC 的对应位置个体 完成PC 的更新

.同时记录当前最优解和对应的解向量, (

遗传算法中 交叉操作前对个体进行选择 轮

),盘赌或者锦标赛选择 较好个体被选择的概率较

. BSA , ,大 然而在 中 变异操作在交叉操作之前

进行交叉的个体随机选择、解的质量较差,从而导

致BSA收敛速度较慢.同时,由变异过程可以看

出,BSA对所有个体进行变异,虽然保证了种群

,的多样性但也导致算法的局部搜索能力不[ 25]. BSA ,足 本文针对 这两方面的不足 通过引,入轮盘赌选择策略 以较大可能选择质量较好的

, . ,解进行交叉 从而加快算法的收敛速度 同时 对其部分较好个体进行变邻域搜索,以增强BSA的

.局部搜索能力

4 改进回溯搜索算法求解 HFSPGB问题BSA ,

原始算法为求解连续优化问题 本文将

, 、其用来求解车间调度问题 需要对其的编码 变异[ 21G24].以及交叉操作进行重构

4.1 编码及解码

.

编码采用最为常用的工件排序的编码方法WARDONO [4] .解码采用 等 提出的解码方法 文

[4] ,献 中解码方法是针对相同并行机问题设计的

,没有考虑不同并行机加工能力的差异 本文将其(进行改进以考虑不同并行机的不同加工能力 机

).器选择 该解码方案根据工件在编码中的先后,“”顺序 按照 先进先加工 的规则来确定同一阶段

. ,的机器选择问题 当下一阶段没有空闲机器时该工件阻塞在当前机器上直至下一阶段出现空闲

.机器 该解码方法模拟了按照编码序列先后顺, .序 工件通过所有加工阶段的加工过程 其具体[ 4,26].的解码过程如下

, ,

首先 在第一加工阶段 将编码序列中前m

(个工件分配到该阶段的m 台机床上 选择加工

),时间最短的机床 得到该m 个工件在该阶段的

.完工时间 该m 个工件以及其完工时间分别构

1 .成初始事件集合E和初始事件完工时间集合T . ,按照完工时间升序对ET和 进行排序 接下来.程序总是针对集合E中的第一个工件进行操作

(当某一个事件完成后 对应工件i在阶段完成后

j), 3 .分以下 种情况进行操作(1) ,

如果阶段j为最后加工阶段 则完成工件

, ,加工 放入已完成工件集合R 并将其所在的机ii

“”, :床状态设置为 空闲 该事件触发以下操作

① 2 ,

从第j阶段起至第 阶段 按如下步骤进

: - 1行操作 如果在阶段j 中存在被阻塞的工件( “”)所在机器处于 阻塞 状态 且阶段j存在处于“” ,空闲 状态的机床 则将该工件安排到该空闲机

, ,床进行加工 得到其在该阶段的完工时间 并将其按照完工时间升序的排序放入事件集合E和完

. - 1工时间集合T中 将其所在阶段j 的机器设 2651

( ) ( OSID): 开放科学 资源服务 标识码

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.