PDF《可外包条件下最大时间偏离受限的单机重调度》

我国 市场的汽车需求量尚未饱和, 汽车制造企业可能突然迎来订购汽车的大订单, 打乱之前针对车身加 工的调度部署. 面对有限的内部冲压资源, 当代的汽车制造企业完全可考虑将适量的车身冲压任务 外包给某个冲压质量较好、 索价公平合理的转包商. 一批新工件突然到达是生产重调度文献中研究 最多的干扰因素之一 [27] . 尽管单机单转包商运营模式相对简单, 但它是多机单转包商、 多机多转包 商模式下相关研究的雏形与基础. 最大时间偏离量是单机重调度建模研究中常用的一种稳定性度 量指标. 它最早由Hall等在文献 [28]中提出, 反映各初始工件在新、 原调度方案中针对完工时间的最大 偏差绝对值. 对于响应新工件突然到达干扰、 考虑最大时间偏离量的单机重调度研究成果, 读者可参 见Hall等[28,29] 、 Mu [30] 、 Zhao等[31] 、 Hoogeveen等[32] 、 Liu等[25] 、 Teghem等[33] 的工作. 假设初始单机调度结束后较多的新工件突然到达, 且唯一的转包商有能力加工任意工件, 文中首先 对最大时间偏离量与总外包费用分别不超过给定上限、 追求总完工时间与总外包成本之间加权和最小化 的ROIOP进行定量描述, 并构建相应的0-1规划模型. 进而, 在阐释所研究的问题是NP-hard的同时, 论证若干 有助于设计启发式算法的优化性质. 随后, 基于动态规划技术、 建立起的优化性质和不同的外包工件集合确 定思路, 设计出两种具备多项式时间复杂度的启发式算法. 最后, 在规模、 特征不同的大量测试算例上, 对设 计出的两种启发式算法开展仿真实验研究, 对比分析它们在优化质量、 效率上的表现情况. 本文设计出的启 发式算法能为后续依赖于问题的高效算法研究奠定技术基础, 并且对 单机单转包商 模式下其他ROIOP的 方法研究具有借鉴意义.

2 问问问题 题 题描 描 描述 述 述与 与 与建 建 建模 模模为方便表述所考虑的单机单转包商重调度与外包联合优化问题, 表1列出若干符号表示及其说明. 表1文中用到的符号表示及其定义 Table

1 Notations used throughout this paper and their de?nitions 符号表示 说明 JO = {J1, J2,JnO } 初始工件集合 JN = {JnO+1, JnO+2,JnO+nN } 新到工件集合 J = JO ∪ JN 由全部工件组成的集合 nO, nN , n 初始工件数、 新到工件数、 ........