clsp

Size: px

Start display at page:

Download "clsp"

孝些姬
5 years ago
Views:

1 能力受限的批量问题的数学模型与算法新进展 * 谢金星姜启源邢文训谭泽光 ( 清华大学应用数学系北京 ) 摘要古典库存问题和能力无限的单层批量问题的研究已经有几十年的历史了, 但由于实际生产中产品结构往往是复杂的, 生产能力总是有限的, 因此能力受限的批量问题 ( 尤其是多层批量问题 ) 成为了近年来运筹学管理科学和工业工程等领域的研究热点之一. 本文在综合大量国内外有关文献的基础上, 对一般批量问题的数学模型作了比较系统全面的介绍, 重点讨论能力受限的单层批量问题和多层批量问题的一些新算法, 并指出一些值得深入研究和努力实践的新方向. 关键词数学模型, 算法, 生产计划, 批量, 库存, 排序 1 引言批量问题 (Lot-sizing Problem) 是成批生产中生产计划的重要问题之一 [1], 其早期研究一般是以库存问题的形式出现的年, Harris 发表了著名的经济订货量 (EOQ--- -Economic Order Quantity) 公式, 可以认为是这方面的最早文献 [2]. 但直到五十年代中期, 主要研究定常需求条件下资源 ( 能力 ) 无限的批量问题. 五十年代中后期, 动态批量问题 ( 即需求随离散的时间段而变化的批量问题 ) 和资源 ( 能力 ) 有限的批量问题开始受到重视年, Wagner 和 Whitin 提出了动态批量问题的动态规划算法 ( 简称 WW 算法 ) [3]; 同时, Manne 提出了整体生产计划 (APP----Aggregate Production Planning) 问题的混合整数规划 (MIP----Mixed Integer Programming) 模型和启发式算法 [4]. 但这些研究仍限于讨论单层批量问题年, Schussel 首次讨论了串联生产系统的批量问题 [5]; 同时, 物料需求计划 (MRP----Material Requirements Planning) 系统在生产企业中被广泛接受, 大大地促进了多层批量问题的研究. 随后, 对批量问题的研究不断深入, 从不同的角度出发, 建立了不同的批量模型 [6]: CLSP --- Capacitated Lotsizing Problem ( 能力受限的批量问题 ) ELSP --- Econoimic Lotsizing Problem ( 经济批量问题 ) DLSP --- Discrete Lotsizing Problem ( 离散批量问题 ) CSLP --- Continuous Setup Lotsizing Problem ( 连续批量问题 ) JSP --- Job Scheduling Problem ( 作业排序问题 ) 本文在综合大量国内外有关文献的基础上, 较全面地介绍 CLSP 的数学模型及算法, 并指出一些值得深入研究和努力实践的新方向. 由于目前的研究一般不考虑随机性, 所以本文只讨论确定性问题. 2 能力受限的批量问题的一般模型 CLSP 考虑的是在有限的计划期内, 给定产品结构生产能力和相关费用及生产项目在离散的时间段上的外部需求之后, 确定每一生产项目在每一时间段上的生产量 ( 即批量 ), 使总费用最小. 由于每一生产项目在每一时间段上生产时必须经过生产准备 (Setup), 占用时间 ( 能力 ), 所以通常的讨论中总费用至少应考虑生产准备费用和库存费用. 如果把库 * 国家高技术计划 (863)CIMS 主题资助项目本文已发表于运筹学杂志第 15 卷第 1 期 (1996 年 )1-12 页

2 存限制和能力调整也考虑进来, 可提出更一般的 CLSP 模型, 用混合整数规划 (MIP----Mixed Integer Programming) 描述如下 : N T MinCOST = { s Y + c X + h I δ( I ) b I δ( I )} + { uc u + oc o it, it, it, it, it, it, it, it, it, it, kt, kt, kt, kt, i= 1 t = 1 k = 1 t = 1 st.. I + X I = d + r X i= 1, L, N, t= 1, L, T, (. 3 2) it, 1 it, it, it, i, j jt, j S() i N i= 1 kit,, it, kit,, i, t k, t k, t k, t it, it, it, it, it, it, kt, kt, kt, K T ( a X + A Y ) = C u + o k = 1, L, K, t = 1, L, T, ) ( 31. ) 0 X BY i = 1, L, N, t = 1, L, T, ( 3. 4) LI I UI i = 1, L, N, t = 1, L, T, ( 35. ) Y {,} 01 i = 1, L, N, t = 1, L, T, (.) 36 0 u U k = 1, L, K, t = 1, L, T, ( 3. 7) 0 o ( 3. 3) Okt, k = 1, L, K, t = 1, L, T, ( 38. ) 其中 COST 为总费用函数 ( 目标函数 ); X it,,i it,,y it,,u kt,,o kt, 为变量 ; 其余为已知量. 具体意义如下 : N 生产项目总数 ; T 计划期长度 ; K 资源种类数 ; B 充分大正数 ; d it, 攭项目 i 在 t 时段的外部需求 ; X it, 项目 i 在 t 时段的生产批量 ; I it, 项目 i 在 t 时段的库存量 ; Y it, 项目 i 在 t 时段是否生产的标志 (0 不生产, 1 生产 ); S(i) 产品结构中项目 i 的直接后继项目集合 ; r i, j 产品结构中项目 j 对项目 i 的消耗系数 ; s it, 项目 i 在 t 时段生产时的生产准备费用 ; c it, 项目 i 在 t 时段生产时的生产费用 ; h it, 项目 i 在 t 时段的单件库存费用 ; b it, 项目 i 在 t 时段的单件欠量费用 ; LI it, 项目 i 在 t 时段的最小允许库存量 ( 此量为负时即表示最大允许欠量 ); UI it, 项目 i 在 t 时段的最大允许库存量 ; C kt, 资源 k 在 t 时段的正常可供能力 ; a kit,, --- 项目 i 在 t 时段生产时, 生产单个产品占用资源 k 的能力 ; A kit,, --- 项目 i 在 t 时段生产时, 生产准备占用资源 k 的能力 ; uc kt, ---- 资源 k 在 t 时段的单位能力闲置费用 ; oc kt, ---- 资源 k 在 t 时段的单位能力加班费用 ; u kt, 资源 k 在 t 时段的闲置能力 ; o kt, 资源 k 在 t 时段的加班能力 ; U kt, 资源 k 在 t 时段的最大允许闲置能力 ; Okt, 资源 k 在 t 时段的最大允许加班能力 ; δ(x)---- 表示当且仅当 x>0 时取值 1, 否则取值 0.

3 目标函数 (3.1) 表示总费用包括生产准备费用, 生产费用, 库存费用, 缺货费用, 资源能力闲置费用, 能力加班费用等. 约束 (3.2) 表示的是物流守恒方程, 约束 (3.3) 表示的是资源能力限制, 约束 (3.4) 和 (3.6) 表示每时段生产某项目前必须经过生产准备. 约束 (3.5) 和 (3.7),(3.8) 分别表示的是项目的最小最大允许库存量, 资源能力的最大允许闲置能力及最大允许加班能力等限制条件. 本模型中生产提前期 (Leadtime) 未予考虑, 或不失一般性地假定为常数. 上述 CLSP 模型非常一般, 表 1 给出了一种按照有无资源能力限制和产品结构的复杂程度的简单分类方案 [7]. 能力无限看作能力受限的一种特殊情况. 多层产品结构又可分成串联, 组装, 和一般等复杂程度不同的三大类 ( 此外, 有些研究者把具有多个最终产品的串联生产系统称为并联生产系统, 也有些研究者在一般生产系统中划出一类与组装生产系统相对的分支生产系统 ). 除单层能力无限 (SLUR) 情形有多项式算法外, 其它几类问题一般来说都是 NP 完全的, 甚至有时其可行性问题也是 NP 完全的 [8]. 表 1 能力受限的批量问题(CLSP) 的分类产品资源资源有限结构无限单资源多资源单层单层能力无限的批量问题 (SLUR) 单层能力受限的批量问题 (SLCR) 串联并联组装多层能力无限的批量问题 (MLUR) 多层能力受限的批量问题 (MLCR) 分枝一般 SLUR --- Single-Level ( 或 Stage) Unconstrained-Resources ( 或 Uncapacitated) SLCR --- Single-Level ( 或 Stage) Constrained-Resources ( 或 Capacitated) MLUR --- Multi-Level ( 或 Stage) Unconstrained-Resources ( 或 Uncapacitated) MLCR --- Multi-Level ( 或 Stage) Constrained-Resources ( 或 Capacitated) 3 能力无限的批量问题单层能力无限的批量问题 (Single-Level Uncapacitated Lotsizing) 的研究是 CLSP 研究的基础, 已经比较成熟并在生产实践中 ( 如 MRP 中 ) 被广泛采用, 国内目前对批量问题的介绍也主要仅限于此. 一般来说, 此时只需考虑单项目问题, 因为多项目问题可看成多个独立的子问题. 但由于其解法经常作为求解其它复杂问题的子算法, 所以其最优算法的计算复杂度有重要意义年 Wagner 和 Whitin 最早提出的动态规划算法 ( 简称 WW 算法 ) 是最优算法 [3], 依据的是如下基本性质 ( 简称 WW 性质 ): 存在满足条件 Iit, 1X it, = 0 的最优解. WW 算法的计算复杂度为 OT ( 2 ), 而计算复杂度为 O( T log T) 的最优算法则是最近才被不同的研究者先后独立地发现的 [9]. 此外有大量的近似或启发式算法 [10][11], 一般是容易理解的. 有关单层能力无限的 CLSP 批量问题的主要研究情况参见表 2 表 2 CLSP-SLUR 批量问题的主要研究文献研究者算法简要评述 [3] Wagner 等 (1958) W-W 最早提出的动态规划最优算法 [10] LFL 直接批量方法 (Lot-for-Lot) [2] Harris (1913) EOQ 最早研究的批量方法

4 [11] MEOQ 修正的 EOQ ( 又称 EOQ-MRP) [11] POQ 基于 EOQ 计算生产周期的启发式方法 [11] LUC 基于最小单件费用的启发式方法 [10] LTC 基于最小总费用的启发式方法 [11] DeMatteins (1968) PPB " 前瞻后顾 " 的 LTC 启发式方法 ( 又称 PPA) [11] Karni (1981) MPG 获最大费用改善的 PPB 启发式方法 [11] Silver 等 (1973) SM 基于最小单位时段费用的启发式方法 [11] Silver 等 (1984) MSM " 前瞻后顾 " 的修正 SM 启发式方法 [11] Groff (1979) MCA 基于边际费用分析的启发式方法 ( 又称 GR) [11] Freeland 等 (1981) ICA 基于增量费用分析的启发式方法 ( 又称 FC) [11] Gaither (1981) GA " 前瞻后顾 " 的 ICA 方法 [10] Boe 等 (1983) IPPA 基于增量费用分析的 PPA 启发式方法 [10] Coleman 等 (1990) TOPS 最近提出的一种基于 IPPA 的迭代方法多层能力无限的批量问题 (Multi-Level Uncapacitated Lotsizing) 中, 中间项目除独立需求 ( 即外部需求 ) 外, 还有相关需求 ( 即内部需求 ), 因此求解方法与产品结构的复杂程度关系密切. 主要求解方法有 [11]: 动态规划最优算法 1968 年, Schussel 首次提出单最终产品定常需求串联生产系统的批量模型, 并基于如下原则用动态规划方法求解 : 前趋的生产批量是其后继的生产批量的整数倍 [5] 年, Crownston 和 Wagner 将这一原则用于求解单最终产品非定常需求的组装生产系统年, Zangwill 将凹费用网络分析方法从单层批量问题推广到串联生产系统的批量问题, 基于最优解一定是极流 (Extreme Flow) 这一性质构造了动态规划最优算法年, Love 分析了 Nested 性质 ( 即前趋项目的生产时段一定是其后继项目的生产时段 ), 简化了计算年, Lambrecht 等对串联生产系统的批量问题进行了较全面的综述 [12]. 分枝定界最优算法 1984 年, Afentakis 等对组装系统情形采用 Lagrange 松弛确定下界, 然后分枝定界求最优解 [13] 年, 该方法被推广到一般生产系统 [14] 年,Rosling 对组装系统情形采用设备布置问题 (FLP----Facility Location Problem) 建模, 基于线性规划松弛确定下界, 然后分枝定界求最优解 [15]. 基于费用修正的启发式算法 1981 年,Graves 提出了一种称为 Multi-pass 的启发式算法 [16], 从某种单层能力无限的批量问题的求解算法 ( 如 WW 算法 ) 出发, 在层与层之间通过修正费用参数进行反馈, 迭代求解.1982 年,Blankburn 和 Millen 直接根据项目之间的相互关系对费用参数进行修正 [17]. 平行启发式算法通常的启发式算法一般是逐层 (Level by Level) 确定生产批量, 在滚动式生产计划环境中容易产生不稳定性年, Afentakis 提出了一种称之为平行启发式的算法, 逐个时段 (Period by Period) 确定生产批量 [18]. 他考虑的是组装结构, 假定只有最终产品有外部需求 (d t ), 费用参数不随时间变化, 消耗系数全为 1, 即数学模型为 :

5 MinCOST = { siyi, t + hii i, t} st.. I + X I = d t= 1, L, T, I + X I = d + X i = 2, L, N, t = 1, L, T, 0 X BY i = 1, L, N, t = 1, L, T, Y N T i= 1 t = 1 1, t 1 1, t 1, t 1 it, 1 it, it, it, it, it, 0 I i = 1, L, N, t = 1, L, T, it, it, S(), i t { 01, } i = 1, L, N, t = 1, L, T, 可以通过将库存 I it, 1 变换成阶梯 (Echelon) 库存 E it, 1, 将库存费用 h i变换成阶梯库存费用 e i, 即令 Eit, = ( X i, d ), ei = hh h k, 这里 P(i) 表示的是项目 i 的直接前趋集合. 目标函数等价地变成 t τ τ λ= 1 k P() i N T MinCOST = ( siyit, + eieit, ). i= 1 t = 1 平行启发式过程对时段 t=1,2,,t 分成如下两个步骤处理 : (1) 生成候选计划集合, 即假定项目 i 在 1,2,,t-1 时段的计划已经确定, 生成项目 i 在 t 时段的候选计划集合. 启发之处在于, 此时并不是把所有可行计划都选入, 而是从 1,2,,t-1 时段的已有计划中的最后一个实际生产时段开始考虑, 根据 WW 性质生成候选计划集合. (2) 从候选计划集合中选择费用最小者. 当所有项目的候选计划集合都生成后, 根据 Nested 性质剔除一些计划的组合方式, 对剩余的组合方式求最小费用. 由于此时问题规模已大大减小, 可用 0-1 规划来计算最优的计划组合方式. 有关多层能力无限的 CLSP 批量问题的主要研究情况参见表 3 表 3 CLSP-MLUR 批量问题的主要研究文献研究者类型简要评述 [5] Schussel (1968) 串联前趋批量为后继的整数倍, 逐层启发式方法 [11] Zangwill (1969) 串联基于凹费用网络分析的动态规划 ( 最优解 ) [11] Love (1972) 串联同上, 引入 "Nested" 概念 [11] Crowston 等 (1972) 组装比较启发式算法的性能 ( 定常需求 ) [11] Crowston 等 (1973) 组装动态规划 ( 最优解 ) [16] Graves (1981) 一般 Multi-pass 启发式方法 [17] Blackburn 等 (1982) 组装费用修正的启发式方法 [13] Afentakis 等 (1984) 组装 Lagrange 松弛, 分枝定界 ( 最优解 ) [14] Afentakis 等 (1986) 一般同上 [15] Rosling (1986) 组装 LP 松弛, 分枝定界 ( 最优解 ) [18] Afentakis 等 (1987) 组装平行启发式方法 4 单层能力受限的批量问题单层能力受限的批量问题 (Single-Level Capacitated Lotsizing) 可以看作通常所说的整体生产计划问题 (APP). 由于问题的难度, 一般只考虑单个资源的能力限制, 即整体约束 (Aggregate Constraint) 或瓶颈 (Bottleneck). 这类问题只对个别单项目的特殊情形存在多项式时间的最优算法, 且这种最优算法一般都采用动态规划求解年, Florian 和 Klein 把单产品定常能力的批量问题等价地变化成最小费用流问题求最优解 ;

6 1973 年, Love 将此方法推广到能力限制表现为库存限制时的情形 ; 1978 年, Lambrecht 和 VanderEechen 又将此方法推广到非定常能力的情形 [19] 年, Maes 和 Van Wassenhove 对该问题进行了综述, 大致可分为两大类算法 [20]: 基于常识的启发式算法基于常识的启发式算法很多, 一般都分成三个步骤 [20]: (1) 成批, 即将某些时段的需求合并成一定的批量, 目的在于降低总费用 ; (2) 可行化, 保证可行性 ( 即按时满足需求, 且不超出能力限制 ); (3) 改进, 采用一定的规则以求进一步获得总费用的改善年, Eisenhut 给每个项目定义了一个优先级 ( 基于单层能力无限的批量问题的 SM----Silver & Meal 算法 ), 按项目的优先级由大到小逐个时段增加批量, 直至能力饱和或优先级小于 0. 但这一算法不一定能得到可行解, 所以, 1979 年, Lambrecht 和 Vanderveken 提出了通过反馈保证可行性的启发式算法年, Dogramaci 等在每一时段都预测到后续时段的不可行性, 保证只需一次单向扫描就得到可行解. 同年, Dixon 和 Silver 提出的算法也与此类似年, Karni 和 Roll 先用 WW 算法求得初始解, 然后对能力冲突的时段分析批量移动 (Shifting) 引起的费用变化, 以最小的费用增加得到可行解年, Maes 和 Van Wassenhove 对这些算法进行了实际计算比较, 并提出了简化的算法, 即对所有时段采用同样的优先级 [21] 年, Gunther 基于单层能力无限的批量问题的 Groff 算法来定义优先级 [22], 即项目 i 在 t 时段的优先级定义为 Ui() t = ( 2si hi di, t t ( t 1 ))( di, t ai). 表 4 CLSP-SLCR 批量问题的主要研究文献研究者简要评述 [4] Manne (1958) 最早提出的 MIP 建模及启发式算法 [7] Dzielinski 等 (1965) 用 Dantzig-Wolfe 分解解 Manne 模型 [7] Lasdon 等 (1971) 用列生成法解 Manne 模型 [7] Florian 等 (1971) 单产品, 定常能力时解最小费用流问题求最优解 [7] Love (1973) 单产品, 库存受限制时解最小费用流问题求最优解 [7] Newson (1975) 基于 W-W 算法和解最小费用流问题的启发式方法 [19] Lambrecht 等 (1978) 单产品, 非定常能力时用动态规划方法求最优解 [23] Bahl (1983) 用列生成法解 Manne 模型的启发式方法 [7] Bahl 等 (1984) 求 Manne 模型的周期解 [24] Barany 等 (1984) 建立割平面, 分枝定界求最优解 [26] Thizy (1985) 用 Lagrange 松弛解 Manne 模型的启发式方法 [27] Gelders 等 (1986) 与上类似, 但松弛定界后再分枝定界求最优解 [28] Trigeiro (1987) 与上类似, 用对偶费用解 Manne 模型的启发式方法 [28] Trigeiro (1989) 与上类似, 但考虑生产准备费用 [25] Eppen 等 (1987) 变量重定义, 求最优解 [20] Eisenhut (1975) 基于 SM 优先级的启发式方法, 但可能不可行 [20] Lambrecht (1979) 同上, 但采用反馈保证可行 [20] Dogramaci 等 (1981) 同上, 但提前确定上下界, 单向保证可行 [20] Dixon 等 (1981) 与上类似 [21] Maes 等 (1986) 与上类似, 但基于固定优先级的启发式方法 [22] Guenther (1987) 与上类似, 但基于 MCA 优先级的启发式方法

7 [7] [7] [7] [7] Karni (1981) 单产品问题的 Shifting 方法 Karni 等 (1982) 多产品问题的 Shifting 方法 Aras (1982) 与底层排序结合考虑 ( 单资源 ) Daniels (1983) 与底层排序结合考虑 ( 多资源, 串联 ) 基于混合整数规划 (MIP) 的最优算法或启发式算法 1958 年, Manne 最早提出此问题的 MIP 模型并将求解范围限定在批量满足 WW 性质的解集中, 对 0-1 变量线性松弛启发式求解并讨论了解的性质 [4]. 为便于求解较大规模的问题, 1965 年, Dzielinski 和 Gomory 提出了 Dantzig-Wolfe 分解算法 ; 1971 年,Lasdon 和 Terjung 提出了列生成算法 ;1975 年, Newson 提出了基于 WW 算法和最小费用流问题的启发式算法 ; 1983 年, Bahl 提出了基于列生成技术的启发式计算方法 [23]; 1984 年, Barany 等提出了割平面法 [24]; 1987 年, Eppen 和 Martin 提出变量重定义法 [25]. 后这两种算法最终都基于分枝定界隐式枚举求最优解, 由于计算量过大, 实用于求解大规模问题的可能性不大年, Thizy 和 Van Wassenhove 开始采用 Lagrange 松弛方法定界, 然后启发式求可行解 [26]; 1986 年, Gelders 等则在定界后再分枝定界求最优解 [27]. 下面简要介绍 1989 年 Trigeiro 等对带生产准备时间的批量问题提出的启发式 Lagrange 松弛算法 [28]. 此时的批量问题的数学模型为 : N T MinCOST = { s Y + c X + h I } i= 1 t= 1 it, it, it, it, it, it, st.. I + X I = d i= 1, L, N, t= 1, L, T, ( 4. 2) N i= 1 it, 1 it, it, it, ( ax + AY ) C t= 1, L, T, ( 4. 3) i i, t i i, t t 0 X BY i = 1, L, N, t = 1, L, T, ( 4. 4) it, it, 0 I i = 1, L, N, t = 1, L, T, ( 45. ) it, ( 41. ) Yit, {,} 01 i = 1, L, N, t = 1, L, T, (.) 46 对能力约束 (4.3) 进行松弛, 设 u 攬 i,t 攭为 Lagrange 乘子, 则对偶问题为 : ' ' ' Min COST = { sit, Yit, + cit, + hit, Iit, } i= 1 t = 1 st.. ( 42. ),( 44. ),( 45. ),( 46. ). ' ' ' 其中 s = s + u A, c = c + ua, h = h. it, it, t i it, it, t i it, it, N T 这一问题可分解为 N 个单层能力无限的批量问题, 易求最优解 ( 如 WW 算法 ). 于是算法可描述如下 : (1) 初始化 Lagrange 乘子 ; (2) 求解问题 (PL); (3) 检验能力是否可行, 若不可行, 则启发式地左右移动或分解批量计划, 使之可行, 并希望导致的费用增加尽量地少 ; (4) 判停, 若不满足判停条件, 则由次梯度优化得到新的 Lagrange 乘子, 继续 (2). 单层能力受限的批量问题的研究情况参见表 4 5 多层能力受限的批量问题多层能力受限的批量问题 (Multi-Level Capacitated Lotsizing) 更接近于实际生产计划, 是研究的重点和难点. 如果说多层能力无限的批量问题是古典 MRP 的数学模型, 那么多层能力受限的批量问题将是新一代 MRP 的数学模型. 由于一般不存在多项式时间的最优算法, 所以有实用价值的主要是启发式算法. 基于网络分析的动态规划最优算法和启发式算法

8 1978 年, Lambrech 和 VanderEechen 研究了单产品串联系统的能力受限的批量问题, 基于凹费用网络分析构造了动态规划最优算法 [12] 年,Steinberg 和 Napier 将一般生产系统的批量问题转化为一个广义约束网络的最小费用问题, 从而可用网络算法求最优解 [29]. 单这两种最优算法的时间效率都很低年, Zahorik 等分析了组装系统批量问题的 MIP 模型的特点, 将只有三个时段的批量问题转化为网络问题, 然后以此为基础对多个时段依次采用只有三个时段的最优算法启发式求解 [30]. 基于 Lagrange 松弛的分枝定界启发式算法 1986 年, Billington 等对组装系统的单瓶颈情形采用 Lagrange 松弛确定下界, 然后采用启发式分枝定界方法求解 [31]. 这与单层能力受限的批量问题的 Lagrange 松弛方法类似, 只是具体过程更复杂些. 基于单层或能力无限批量问题的启发式算法 1984 年, Bahl 和 Ritzman 对产品结构中中间层次上的生产项目, 采用单层能力无限的批量问题批量问题中的直接批量算法, 从而得到了一种简单的启发式算法 [32]. Blackburn 和 Millen 将他们 1982 年用于求解多层能力无限的批量问题的费用修正启发式算法推广到能力受限情形, 提出了与此相关的多种启发式算法 [33] 年, Roll 和 Karni 将他们用于求解单层能力受限的批量问题的移动启发式算法, 推广到求解带一个整体约束的多层批量问题 [34]. 组合优化新算法的应用 1990 年, Kuik 和 Salomon 探讨了模拟褪火 (SA----Simulated Annea-ling) 算法用于求解批量问题的效果 [35]. 这时必须定义一个批量计划的邻域, 通常可以认为 Y it, 决定了批量计划, 即只需定义 Y it, 的邻域即可, 如定义为 ' N T ' ' { Y : Yit, Yit, = 1, Yit, { 0, 1 }}. i= 1 t = 年, 他们又进一步研究了禁忌搜索 (TS----Tabu Search) 算法用于求解批量问题的性能 [36]. 这相当于在邻域中再禁止某些批量计划 ( 禁忌表中的批量计划 ) 成为下一次迭代的候选计划. 基于线性规划松弛的启发式算法 1991 年, Maes 等讨论了多层能力受限的批量问题及其可行性问题的计算复杂性 [8], 并将其 MIP 数学模型形式上等价地变换成广义的设备布置问题的 MIP 数学模型. 求解时分成两步 : (1) 线性规划松弛 ( 即将 Y it, {,} 01 松弛为 Y it, [ 01), ] 求解 ; (2) 若解中有些 Y it, 不为整数, 则将某变量 Y it, 的解进行舍入 (0 或 1), 并将其值固定, 回到 (1). 以此为基础, 还可采用迭代求解过程或分枝定界过程, 以期改进解的性质. 更进一步, 可将此算法与模拟褪火算法或禁忌搜索算法组合求解年, Kuik 等实际计算比较了这三种算法的时间效率和解的优劣 [37]. 多层能力有限的批量问题的研究情况参见表 5 表 5 CLSP-MLCR 批量问题的主要研究文献研究者类型简要评述 [7] Lambrecht 等 (1978) 串联基于凹费用网络分析的动态规划方法 ( 最优解 ) [29] Steinberg 等 (1980) 一般基于广义约束网络分析的网络方法 ( 最优解 ) [7] Williams (1981) 一般比较启发式算法的性能 ( 定常需求 ) [7] Billington 等 (1983) 一般 MIP 模型, 压缩产品结构 [38] Bitran 等 (1983) 组装 MIP 模型, 递阶生产计划 [7] Bahl 等 (1984) 一般中间层采用 LFL 的启发式方法

9 [30] Zahorik 等 (1984) 组装基于网络分析的启发式方法 [31] Billington 等 (1986) 组装单瓶颈问题,Lagrange 松弛, 分枝定界启发式 [7] Blackburn 等 (1984) 组装费用修正的启发式方法 [35] Kuik 等 (1990) 组装模拟退火方法 [36] Kuik 等 (1991) 组装禁忌搜索方法 [34] Roll 等 (1991 组装单瓶颈问题,Shifting 方法 [8] Maes 等 (1991) 组装基于 LP 的启发式方法 6 小结由于 CLSP 的研究和应用方兴未艾, 所以大量研究成果和应用软件如雨后春笋, 不断涌现. 一般来说, 处理 CLSP 的思路大致有两种 : 一是对比较一般的问题进行简化, 利用快速的启发式算法求解 ; 二是对某些特殊的问题采用最优算法或基于最优算法的启发式算法求解, 并希望将其结果应用到一般问题中去. 数学模型和数学规划方法的应用成为了处理批量问题的必不可少的工具. 从研究内容上看, 至少有如下几点值得引起特别的重视 : 应继续深入地进行最优算法和近似算法启发式算法的研究 : 各种批量算法的测试比较, 复杂度分析, 新算法的研究及应用等. 批量问题的研究应集中于讨论有能力限制的情形, 并更多地在模型中考虑实际生产环境中的主要影响因素, 如能力的可替代性等, 因为只有这样的研究才更具实际意义, 而不至于将批量研究变成纯粹的数字游戏. 应重视对动态事件的考虑, 因为实际生产环境总是动态的而不是纯静态的. 如应允许能力的调整, 合同 ( 即需求 ) 的变更, 允许有欠量, 可变的提前期等. 迫切需要建立和研究随机批量模型, 因为实际生产环境总是存在不确定性. 综合应用各种先进技术, 建立统一的生产计划决策模型. 虽然这似乎不太现实, 但却是我们追求的理想目标. 从方法和技术上来看, 我们一方面要追求将最优方法嵌入到生产计划和批量问题的求解过程中, 但这种努力总是有限度的. 因此, 另一方面我们的统一模型应包括从市场预测到产品设计制造和促销等全过程, 综合运用大系统理论的递阶控制和分解协调等技术 ( 如 1983 年, Bitran 等对组装系统提出了递阶生产计划的 MIP 模型 [38]), 致力于开发生产计划的人工智能决策系统和专家系统. 致谢衷心感谢中国科学院韩继业先生对本研究课题的大力支持和编者对本文初稿提出的宝贵意见和建议. 参考文献 [1] Gelders L. F., L. N. Van Wassenhove, Production Planning: A Review, Eur. J. Opnl. Res., 7/2(1981), [2] Harris F. W., How Many Parts to Make at Once, Opns. Res., 38/6(1990), Reprinted from Factory, The Magazine of Management, 10/2(1913), , 152. [3] Wagner H. M., T. M. Whitin, Dynamic Version of the Economic Lot Size Model, Mgmt. Sci., 5/1(1958), [4] Manne A. S., Programming of Lot Sizes, Mgmt. Sci.,4/2(1958),

10 [5] Schussel G., Job-Shop Release Sizes, Mgmt. Sci., 14/8(1968), B449-B472. [6] Salomen M., L. G. Kroon, R. Kuik, L. N. Van Wassenhove, Some Extensions of the Discrete Lotsizing and Scheduling Problem, Mgmt. Sci., 37/7(1991), [7] Bahl H. C., L. P. Ritzman, J. N. D. Gupta, Determining Lot Sizes and Resource Requirements: A Review, Opns. Res., 35/3(1987), [8] Maes J., J. O. McClain, L. N. Van Wassenhove, Multilevel Capacitated Lotsizing Complexity and LP-Based Heuristics, Eur. J. Opnl. Res., 53/2(1991), [9] Aggarwal A., J. K. Park, Improved Algorithms for Economic Lot Size Problems, Opns. Res., 41/3(1993), [10] Coleman B. J., A Further Analysis of Variable Demand Lot-Sizing Techniques, Prod. Invent. Mgmt. J., 33/3(1992), [11] Gupta Y. P., Y. Keung, A Review of Multi-Stage lot-sizing Models, Int. J. Opns. Prod. Mgmt., 10/9(1990), [12] Lambrecht M. R., J. VanderEechen, H. Vanderveken, Review of Optimal and Heuristic Models for a Class of Facilities in Series Dynamic Lot Size Problems, in: L. B. Schwarz(ed.), Multi-level Production/Inventory Control Systems: theory and Practice, TIMS Studies in the Management Sciences 16, Amsterdam, North-Holland, 1981, [13] Afentakis P., B. Gavish, V. Karmarkar, Optimal Solutions to the Lot-Sizing Problem in Multi-Stage Assembly Systems, Mgmt. Sci., 30/3(1984), [14] Afentakis P., B. Gavish, Optimal Lot-Sizing Algorithms for Complex Product Structres, Opns. Res., 34/3(1986), [15] Rosling K., Optimal Lot Sizing for Dynamic Assembly Systems, in: S. Axsater, Ch. Schneeweiss, E. Silver(eds.), Multistage Production Planning and Inventory Control, Lecture Notes in Economics and Mathmetical Systems 266, Springer, Berlin, 1986, [16] Graves, S. C., Multistage Lot-Sizing:An Iterative Procedure, in: L. B. Schwarz(ed.), Multi-Level Production/Inventory Control Systems: Theory and Practice, TIMS Studies in the Management Sciences 16, Amsterdam,North Holland,1981, [17] Blackburn J. D., R. A. Millen, Improved Heuristics for Multistage Requirements Planning Systems, Mgmt. Sci., 28/1(1982), [18] Afentakis P., A Parallel Heuristic Algorithm for Lot Sizing in Multistage Production Systems, IIE Trans., 19/1(1987), [19] Lambrecht M. R., J. VanderEechen, A Capacity Constrained Single-Facility Dynamic Lot-Size Model, Eur. J. Opnl. Res., 2/2(1978), [20] Maes J., L. N. Van Wassenhove, Multi-Item Single-Level Capacitated Dynamic Lot- Sizing Heuristics: A General Review, J. Opnl. Res. Soc., 39/11(1988), [21] Maes J., L. N. Van Wassenhove, A Simple Heuristic for the Multi-Item Single Level Capacitated Lot Sizing Problems, Opns. Res. Lett., 4/6(1986), [22] Gunther H. O.,Planning of Lot Sizes and Capacity Requirements in a Single Stage Production System, Eur. J. Opnl. Res., 31/2(1987), [23] Bahl H. C., Column Generation Based Heuristic for Multi-Item Scheduling, IIE Trans., 15/2(1983),

11 [24] Barang I., T. J. VanRoy, L. A. Wolsey, Strong Formulations for Multi Item Capacitated Lotsizing, Mgmt. Sci., 30/10(1984), [25] Eppen G. D., R. K. Martin, Solving Multi-Item Capacitated Lotsizing Problems Using Variable Redefinition, Opns. Res., 5/6(1987), [26] Thizy J. M., L. N. Van Wassenhove, Lagrangean Relaxation for the Multi-Item Capacitated Lotsizing Problem: A Heuristic Implementation, IIE Tran., 17/4(1985), [27] Gelders L. F., J. Maes, L. N. Van Wassenhove, A Branch and Bound Algorithm for the Multi Item Single Level Capacitated Dynamic Lotsizing Problem, in: S. Axsater, Ch. Schneeweiss, E. Silver(eds.),Multistage Production Planning and Inventory Control, Lecture Notes in Economics and Mathmetical Systems 266, Springer, Berlin, 1986, [28] Trigeiro W. W., L. J. Thomas, J. O. McClain, Capacitated Lot Sizing with Setup Times, Mgmt. Sci., 35/3(1989), [29] Steinberg E., H. A. Napier, Optimal Multilevel Lotsizing for Requirement Planning Systems, Mgmt. Sci., 26/12(1980), [30] Zahorik A., L. J. Thomas, W. W. Trigero, Network Programming Methods for Production Scheduling in Multistage, Multi-Item Capacity System, Mgmt. Sci., 30/3(1984), [31] Billington P. J., J. O. McClain, L. J. Thomas, Heuristic for Multi-Level Lot-Sizing with a Bottleneck, Mgmt. Sci., 32/9(1986), [32] Bahl H. C., L. P. Ritzman, An Intergrated Model for Master Scheduling, lotsizing, and Capacity Requirements Planning, J. Opnl. Res. Soc., 35/5(1984), [33] Blackburn J. D., R. A. Millen, Simultaneous Lotsizing and Capacity Planning in Multistage Assembly Processes, Eur. J. Opnl. Res., 16/1(1984), [34] Roll Y., R. Karni, Multi-Item, Multi-Level Lot Sizing with an Aggragate Capacity Constraints, Eur. J. Opnl. Res., 55/1(1991), [35] Kuik R., M. Salomon, Multi-Level Lot-Sizing Problem: Evaluation of a Simultated- Annealing Heuristic, Eur. J. Opnl. Res., 45/1(1990), [36] Kuik R., M. Salomon, L. N. Van Wassenhove, J. Maes, Linear Programming, Simulated Annealing, and Tabu Search Heuristic for Lot Sizing in Bottleneck Assembly Systems, Technical Report(1991), Economic Institut,Erasmus University Rotteram, The Netherlands. [37] Kuik R., M. Salomon, L. N. Van Wassenhove, J. Maes, Linear Programming, Simulated Annealing, and Tabu Search Heuristics for Lotsizing in Bottleneck Assembly Systems, IIE Trans., 25/1(1993), [38] Bitran G. R., E. A. Haas, A. C. Hax, Hierarchical Production Planning: A Two-Stage System, Opns. Res.,30/2(1983),

12 New Developments of Mathematical Models and Algorithms of CLSP Xie Jinxing, Jiang Qiyuan, Xing Wenxun, Tan Zeguang Dept. of Appl. Mathematics, Tsinghua University Beijing , P. R. China Abstract The capacitated lotsizing ( and scheduling ) problem (CLSP) is becoming more and more interested by researchers in the fields of operations research (OR), management science (MS), and industrial engineering (IE), etc.. This paper surveys the major studies of CLSP by now, especially the recent developments of the mathematical models and solution algorithms of CLSP, and points out some new directions for further researches and applications. Keywords: Production/Inventory, Planning/Scheduling, _ Capacitated Lotsizing Problem, Mathematical Model, Algorithms

892416H009031

892416H009031 The Study of Mass Rapid Transit Drivers Scheduling Problems A Case Study of Taipei MRT Company Abstract This paper proposes an algorithm to improve the efficiency for solving the drivers scheduling problem