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

第34 卷第

1 期2019 年2月系统工程学报JOURNAL OF SYSTEMS ENGINEERING Vol.

34 No.1 Feb.

2019 可外包条件下最大时间偏离受限的单机重调度 刘乐(济南大学商学院, 山东 济南 250022) 摘要: 在一批新工件突然到达、 单转包商可加工任意工件的条件下, 研究最大时间偏离量与总外包费用不超过给定 上限、 使总完工时间与总外包费用加权和最小化的单机重调度问题. 在构建0-1规划模型、 分析NP困难性、 提出若 干优化性质的基础上, 利用动态规划技术和两种不同的外包工件集决策方式, 分别设计出工件添加型启发式算法和 工件排除型启发式算法. 在仿真实验中, 通过系统生成大量测试算例, 对比分析了两种启发式算法在求解质量、 计 算时间上的表现. 实验结果表明, 工件排除型启发式算法在优化质量与效率上均优于工件添加型启发式算法. 关键词: 重调度;

启发式算法;

外包;

干扰;

单机 中图分类号: F406.2 文献标识码: A 文章编号: 1000?5781(2019)01?0012?17 doi: 10.13383/j.cnki.jse.2019.01.002 Single-machine rescheduling with outsourcing allowed and a limit to maximum time deviation Liu Le (Business School, University of Jinan, Jinan 250022, China) Abstract: This paper considers the single-machine rescheduling addressing an unexpected arrival of new jobs with outsourcing of any jobs to a single subcontractor allowed, where the objective is to minimize the weighted sum of the total outsourcing cost and total completion time, while both the total outsourcing cost and the maxi- mum time deviation are subject to an upper limit. Problem-speci?c 0-1 programming model, nondeterministic polynomial (NP) hardness, and several optimality properties are ?rst established. Subsequently, by using dy- namic programming technique and two different ways of deciding the set of outsourcing jobs, two heuristics are designed to solve this problem, i.e., job addition-related heuristic (JA-H) and job removal related heuristic (JR-H). In the simulation experiments, by systematically generating plenty of test instances, performances of the two heuristics in solution quality and computational times are comparatively analyzed. Experimental results show that JR-H algorithm outperforms JA-H algorithm in terms of both optimization quality and ef?ciency. Key words: rescheduling;

heuristics;

outsourcing;

disruption;

single-machine

1 引引引言言言在经济全球化、 市场竞争日益激烈的大趋势下, 外包(outsourcing)手段在现代企业中得到越来越广泛 的应用, 成为先进制造商响应产品需求波动、 控制库存成本、 缩短生产周期、 规避产能短缺风险的重要途 收稿日期: 2016?05?15;

修订日期: 2016?10?31. 基金项目: 国家自然科学基金资助项目(71501083);

教育部人文社科研究青年基金资助项目(14YJCZH098);

山东省优秀中青 年科学家科研奖励基金资助项目(BS2015ZZ002);

济南大学科研基金资助项目(XKY1322). 第1期刘乐: 可外包条件下最大时间偏离受限的单机重调度

13 径[1] . 借助外包运营方式, 制造型企业不必包揽全部生产环节, 可将非关键的加工任务有偿委托给第三 方的转包商完成, 进而在内部生产成本与外包生产成本的科学权衡过程中追求最大可能收益. 在加工任 务可外包条件下编制车间层调度方案时, 决策者既要确定哪些任务在内部完成加工、 哪些参与外包生产, 又要对参与内部生产的任务进行优化排序, 使得付出的总成本(含生产成本、 库存成本、 外包成本等)最小. 这就是现今生产运作管理中常见的调度与外包联合优化问题(scheduling-outsourcing integrated optimization problems, SOIOP). 近年来, SOIOP在制造型企业运营实践中的应用价值凸显, 逐渐受到生产调度学者的学 术关注. 截至目前, 制造商视角下的SOIOP研究文献已涉及多种运营模式, 如单机单转包商 [2?5] 、 同速机单 转包商 [6?8] 、 同速机多转包商 [9] 、 恒速机多转包商 [10] 、 变速机单转包商 [11] 、 变速机多转包商 [1] 、 两阶段流 水车间单转包商 [12?15] 、 两阶段流水车间双转包商 [12] 、置换流水车间单转包商 [16] 、 置换流水车间多转包 商[17] 、 作业车间单转包商 [18,19] 、 两阶段开放式车间单转包商 [5,20] 、 开放式车间单转包商 [8] 等. 在实际工况中, 事先拟定好的调度方案常会被突发干扰(disruptions)打乱, 甚至变得不可行. 干扰普遍存 在于制造型企业运作过程的各个环节, 表现形式多样、 影响效果各异. 常见的干扰事件有机器突然故障、 新 工件到达、 工件返工、 订单撤销、 加工路线变更等. 为了降低干扰造成的破坏性影响、 保持生产连续性, 受扰 后亟需面向实时工况修复原调度方案或重新编制新调度方案, 这便是响应突发干扰的重调度(rescheduling) 过程. 对于重调度后的效果, 既要尽量少地牺牲在原调度目标函数上的优化水平, 又要确保新调度方案相对 于原方案的稳定性(stability) [21] . 生产重调度问题也是对传统调度问题的拓展与升级;