基于邻域渲染的二车间综合调度算法

doi:10.3901/JME.2016.01.149

机械工程学报 ›› 2016, Vol. 52 ›› Issue (1): 149-159.doi: 10.3901/JME.2016.01.149

扫码分享

基于邻域渲染的二车间综合调度算法

谢志强^1,2, 于洁¹, 陈德运¹, 杨静²

1. 哈尔滨理工大学计算机科学与技术学院哈尔滨 150080；
2. 哈尔滨工程大学计算机科学与技术学院哈尔滨 150001

收稿日期:2015-03-13 修回日期:2015-10-25 出版日期:2016-01-05 发布日期:2016-01-05
通讯作者: 谢志强，男，1962年出生，博士，教授，博士研究生导师，CMES和CCF高级会员。主要研究方向为企业智能计算与调度优化。 E-mail：xiezhiqiang@hrbust.edu.cn
基金资助:
国家自然科学基金(60873019，61370086，61370083)、黑龙江省自然科学基金(F201101)、黑龙江省教育厅科技(12531105)、黑龙江省博士后科研启动(LBH-Q13092)、现代制造技术与刀具开发黑龙江省高校重点实验室开放课题(2012DJ-003)和全国高等学校计算机教育研究会(研究生创新)(ER2014018)资助项目

Integrated Scheduling Algorithm of Two Workshops Based on the Principle of the Neighborhood Rendering

XIE Zhiqiang^1,2, YU Jie¹, CHEN Deyun¹, YANG Jing²

1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080;
2. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001

Received:2015-03-13 Revised:2015-10-25 Online:2016-01-05 Published:2016-01-05

摘要/Abstract

摘要： 针对如何将复杂产品工序有效地分配到具有相同设备资源的两车间加工的问题，提出了基于邻域渲染的二车间综合调度算法。该算法为了实现产品加工尽早结束，提出关键设备均衡策略，将关键设备上的所有加工工序预先按并行加工时间最长方案均衡的分配到二车间；为了减少两车间之间的迁移次数，提出邻域渲染策略和同设备工序车间选择策略，通过计算未分配加工车间工序的邻域加工工序的渲染因子和影响因子确定其所在的加工车间；为了提高调度效率，采用动态关键路径策略和短用时策略确定工序调度次序，按序确定工序的加工车间和开始加工时间。分析和实例表明，所提出的算法产品加工时间较短、工序迁移次数较少且不增加算法复杂度。

关键词: 二车间综合调度算法, 关键设备均衡策略, 邻域渲染策略, 同设备工序车间选择策略, 影响因子

Abstract: Aiming at that the problem that how to allocate complex product procedures effectively to two workshops with the same equipment resources, integrated scheduling algorithm of two workshops based on neighborhood rendering is proposed. In order to let two workshops products completed as soon as possible, this algorithm proposes critical-equipment equilibrium strategy, prior allocated procedures of key-equipment balanced to two workshops in accordance with the longest parallel processing scheme. In order to reduce the number of procedures transfer between two workshops, the strategy is put forward based on neighborhood rendering and the strategy to select workshop for the same equipment procedure. By calculating the rendering factor and the influence factor of the neighborhood procedure, other unallocated processing workshops are determined. In order to improve the scheduling efficiency, the strategy of dynamic critical path and short-time strategy to determine the scheduling sequence are adopted, then makes sure the processing workshops and start time. Analysis and instance show that the implementation of algorithm achieve the product in the shorter processing time and the less procedures migration times and not increase the algorithm complexity.

Key words: critical equipment equilibrium strategy, influence factor, integrated scheduling algorithm of two workshops, neighborhood rendering strategy, the same equipment process select workshops strategy

中图分类号:

TP278

谢志强, 于洁, 陈德运, 杨静. 基于邻域渲染的二车间综合调度算法[J]. 机械工程学报, 2016, 52(1): 149-159.

XIE Zhiqiang, YU Jie, CHEN Deyun, YANG Jing. Integrated Scheduling Algorithm of Two Workshops Based on the Principle of the Neighborhood Rendering[J]. Journal of Mechanical Engineering, 2016, 52(1): 149-159.

参考文献

[1] 张长胜，孙吉贵，杨轻云，等．一种求解车间调度的混合算法[J]．自动化学报，2009，35(3)：332-336． ZHANG Changsheng，SUN Jigui，YANG Qingyun，et al. A hybrid algorithm for flowshop scheduling problem[J]. Acta Automatica Sinica，2009，35(3)：332-336．
[2] 胡蓉，钱斌．一种求解随机有限缓冲区流水线调度的混合差分进化算法[J]．自动化学报，2009，35(12)：1580-1586． HU Rong，QIAN Bin．A hybrid differential evolution algorithm for stochastic flow shop scheduling with limited buffers[J]. Acta Automatica Sinica，2009，35(12)：1580-1586．
[3] 赵诗奎，方水良．基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J]．机械工程学报，2013，49(16)：160-169． ZHAO Shikui，FANG Shuiliang. Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J]. Journal of Mechanical Engineering，2013，49(16)：160-169．
[4] 潘全科，王凌，高亮，等．基于差分进化与块结构邻域的作业车间调度优化[J]．机械工程学报，2010，46(22)：182-188．PAN Quanke，WANG Ling，GAO Liang，et al．Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J]．Journal of Mechanical Engineering，2010，46(22)：182-188．
[5] 何彦，刘飞，曹华军，等．面向绿色制造的机械加工系统任务优化调度模型[J]．机械工程学报，2007，43(4)：27-33． HE Yan，LIU Fei，CAO Huajun，et al．Job scheduling model of machining system for green manufacturing [J]．Chinese Journal of Mechanical Engineering，2007，43(4)：27-33．
[6] 曾强，杨育，王小磊，等．基于多规则设备分配及工序排序的FJSP多目标集成优化方法[J]．计算机集成制造系统，2011，17(5)：980-989．ZENG Qiang，YANG Yu，WANG Xiaolei，et al．Integrated multi-objective optimization method for FJSP based on multiple rule machine assignment and job sequencing[J]. Computer Integrated Manufacturing Systems，2011，17(5)：980-989．
[7] 谢志强，邵侠，杨静．存在设备无关延迟约束的综合柔性调度算法[J]．机械工程学报，2011，47(4)：181-189．XIE Zhiqiang，SHAO Xia，YANG Jing．Algorithm for integrated flexible scheduling with device- independence deferred constraint[J]．Journal of Mechanical Engineering，2011，47(4)：181-189．
[8] 谢志强，滕宇峥，杨静．紧密衔接工序组联动的综合调度算法[J]．自动化学报，2011，37(3)：117-125．XIE Zhiqiang，TENG Yuzheng，YANG Jing．Integrated scheduling algorithm with no-wait constraint operation group[J]．Acta Automatica Sinica，2011，37(3)：117-125．
[9] 吉军，蔚承建，陈胜峰，等．分散式多工厂资源调度中的一种理性策略[J]．计算机应用，2010，30(11)：2894-2897．JI Jun，WEI Chengjian，CHEN Shengfeng，et al．Rational strategy in decentralized multi-factory resource scheduling[J]．Journal of Computer Applications，2010，30(11)：2894-2897．
[10] 蒋大奎，李波．基于禁忌搜索的平行机多工厂供应链调度[J]．中国机械工程，2012，23(6)：688-693．JIANG Dakui，LI Bo．Multi-plant supply chain scheduling with parallel machines based on taboo search algorithm[J]．China Mechanical Engineering，2012，23(6)：688-693．
[11] 马士华，黄焜，洪生．基于Supply-Hub的两源供货横向协同策略研[J]．机械工程学报，2011，47(20)：1-9．MA Shihua，HUANG Kun，HONG Sheng． Research on Supply-Hub-based horizontally coordinated dual- sourcing[J]．Journal of Mechanical Engineering，2011，47(20)：1-9．
[12] 李京生，王爱民，唐承统，等．基于动态资源能力服务的分布式协同调度技术[J]．计算机集成制造系统，2012，18(7)：1563-1574．LI Jingsheng，WANG Aimin，TANG Chengtong，et al．Distributed coordination scheduling technology based on dynamic manufacturing ability service[J]．Computer Integrated Manufacturing Systems，2012，18(7)：1563-1574．
[13] 谢志强，郑付萍，朱天浩．两车间可调度工序均衡处理的综合调度算法[J]．计算机工程，2014，40(1)：295-304．XIE Zhiqiang，ZHENG Fuping，ZHU Tianhao．Integrated scheduling algorithm with equalization processing of schedulable processes in two workshops[J]．Computer Engineering，2014，40(1)：295-304．
[14] 谢志强，周含笑，桂忠艳，等．基于拟关键路径的二车间综合调度算法[J]．计算机科学，2013，40(4)：193-198．XIE Zhiqiang，ZHOU Hanxiao，GUI Zhongyan，et al．Integrated scheduling algorithm of two workshops based on ACPM[J]．Computer Science，2013，40(4)：193-198．
[15] XIE Zhiqiang，YU Qinglian，WANG Yue，et al．The algorithm of confirming increasable bottleneck device in dynamic integrated scheduling based on static parallel time[C]//The 2nd International Conference on Computer Engineering and Technology (ICCET 2010)，2010，V4：98 -102.
[16] XIE Zhiqiang，LIU Yong，HAO Shuzhen，et al．Study on confirming increasable bottleneck device in complex product dynamic scheduling[C]// Conference on Computer Modeling and Simulation (ICCMS 2009)，2009：213-217．
[17] 谢志强，杨静，周勇，等．基于工序集的动态关键路径多产品制造调度算法[J]．计算机学报，2011，34(2)：216-222. XIE Zhiqiang，YANG Jing，ZHOU Yong，et al．Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]．Chinese Journal of Computers，2011，34(2)：216-222．

基于邻域渲染的二车间综合调度算法

Integrated Scheduling Algorithm of Two Workshops Based on the Principle of the Neighborhood Rendering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	王小巧, 刘明周, 葛茂根, 马靖, 刘从虎. 基于混合粒子群算法的复杂机械产品装配质量控制阈优化方法[J]. 机械工程学报, 2016, 52(1): 130-138.
[2]	姜潮;李博川;韩旭. 一种考虑路径影响的剪切式多轴疲劳寿命模型[J]. , 2014, 50(16): 21-26.
[3]	姜涛;王安麟;刘广军;张颖;焦继伟. 音叉振动式微机械陀螺输出电容的统计特性分析[J]. , 2007, 43(8): 114-118.