含不一致任务重量的同型熔炼炉批调度优化

工业工程 ›› 2014, Vol. 17 ›› Issue (3): 73-78.

含不一致任务重量的同型熔炼炉批调度优化

广东工业大学广东省计算机集成制造重点实验室，广东广州 510006

出版日期:2014-06-30 发布日期:2014-07-14
作者简介:胡常伟(1978-)，男，湖北省人，讲师，博士研究生，主要研究方向为计算机集成制造、生产调度.
基金资助:
国家自然科学基金资助项目(51175094,51205068)；国家科技支撑计划项目（2012BAF12B10）；广东省自然科学基金资助项目（S2012040007784）

Optimization for Scheduling Identical Parallel Melting Furnaces withNon-identical Job Weights

Guangdong Provincial Key Laboratory of Computer Integrated Manufacturing System, Guangdong University of Technology, Guangzhou 510006, China

Online:2014-06-30 Published:2014-07-14

摘要/Abstract

摘要： 为求解含不一致任务重量的同型熔炼炉批调度问题，建立了最小化最大任务完工时间优化模型，设计了一种混合粒子群算法（HPSO）。算法使用随机生成的任务序列作为粒子，采用批首次匹配（BFF）规则对任务序列分批，最长加工时间（LPT）规则将批分配到批处理机，并提出了一种最小完工时间差（MCD）规则对LPT调度结果进行优化；为避免早熟，算法引入交叉和变异操作搜索最优解。通过仿真实验与SA、GA算法对比，实验结果表明算法具有良好的性能。

关键词: 批调度, 不一致任务, 熔炼炉, 粒子群算法

Abstract: To solve the batch scheduling problem of identical parallel melting furnaces with nonidentical job weights, an optimization model is established to minimize the makespan on scheduling melting furnaces, and the hybrid particle swarm optimization based jobs sequence (HPSO) designed. In the HPSO, particles are represented by job sequences, the batch first fit (BFF) heuristic used to group jobs to batches, the longest processing time(LPT) heuristic adopted to assign batches to batch processing machines, and the minimum completion time difference(MCD) heuristic proposed to optimize scheduling results by LPT heuristic. In order to avoid the premature convergence problem, the HPSO introduces the crossover and mutation operator to search for the optimal solution. Compared with SA and GA algorithm, simulation experimental results demonstrated that HPSO has a good performance.

Key words: batch scheduling, non-identical jobs, melting furnace, particle swarm optimization

胡常伟，陈新度，陈庆新，毛宁，陈新. 含不一致任务重量的同型熔炼炉批调度优化[J]. 工业工程, 2014, 17(3): 73-78.

Hu Chang-wei，Chen Xin-du，Chen Qing-xin，Mao Ning，Chen Xin. Optimization for Scheduling Identical Parallel Melting Furnaces withNon-identical Job Weights[J]. Industrial Engineering Journal , 2014, 17(3): 73-78.

参考文献

［1］Uzsoy Y R. Scheduling a single batch processing machine with nonidentical job sizes［J］. International Journal of Production Research,1994,32(7):1615-1635. ［2］Damodaran P, Manjeshwar P K, Srihari K. Minimizing makespan on a batchprocessing machine with nonidentical job sizes using genetic algorithms［J］. International Journal of Production Economics, 2006, 103(2): 882-891. ［3］Chou F D, Chang P C, Wang H M. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem［J］. International Journal of Advanced Manufacturing Technology, 2006, 31(3/4):350-359. ［4］程八一,陈华平,王栓狮. 模糊制造系统中的不同尺寸工件单机批调度优化［J］. 计算机集成制造系统, 2008, 14(7):1323-1328. Cheng Ba-yi, Chen Hua-ping, Wang Shuan-shi. Optimization for scheduling a single batchprocessing machine with nonidentical job sizes in fuzzy manufacturing system［J］. Computer Integrated Manufacturing Systems, 2008, 14(7):1323-1328. ［5］Melouk S, Damodaran P, Chang Ping-yu. Minimizing makespan for single machine batch processing with nonidentical job sizes using simulated annealing［J］. International Journal of Production Economics,2004,87(2):141-147. ［6］Damodaran P, Srihari K, Lam S S. Scheduling a capacitated batchprocessing machine to minimize makespan［J］. Robotics and ComputerIntegrated Manufacturing,2007,23(2):208-216. ［7］许瑞,陈华平. 含不同到达时间和尺寸的批调度优化算法［J］. 计算机集成制造系统,2011,17(9):1944-1953. 〖DW〗Xu Rui, Chen Huaping. Optimization algorithm on batch scheduling with different release time and nonidentical job sizes［J］. Computer Integrated Manufacturing Systems, 2011,17(9):1944-1953. ［8］Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines［J］. International Journal of Production Research, 2004,42(19): 4211-4220. ［9］Damodaran P, Chang P Y. Heuristics to minimize makespan of parallel batch processing machines［J］. International Journal of Advanced Manufacturing Technology, 2008,37(9/10):1005-1013. ［10］Ghazvini F J, Dupont L. Minimizing mean flow times criteria on a single batch processing machine with nonidentical job sizes［J］. International Journal of Production Economics,1998, 55(3):273-280 ［11］Kashan A H, Karimi B, Jenabi M. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes［J］. Computers & Operations Research,2008,35(4): 1084-1098. ［12］Cheng Ba-yi, Wang Qi, Yang Shan-lin, et al. An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes［J］. Applied Soft Computing,2013,13(2):765-772. ［13］杜冰,陈华平,杨勃,等.聚类视角下的差异工件平行机批调度问题［J］.管理科学学报,2011,14(12):27-37.

[1]	唐红涛, 杨志鹏, 刘家毅. 考虑工序并行的差异工件批调度研究[J]. 工业工程, 2021, 24(3): 68-76,114.
[2]	王玖河, 刘欢, 高辉. 基于粗糙PSO-BP神经网络的冷链物流服务商选择研究[J]. 工业工程, 2021, 24(2): 10-18.
[3]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[4]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[5]	曾垂飞, 刘建军, 陈庆新, 毛宁. 优化交货可靠性的装配作业车间分批调度[J]. 工业工程, 2019, 22(6): 45-56.
[6]	王玖河, 韩希卓, 时国强. 考虑铁路分割线的物流园区功能区布局规划研究[J]. 工业工程, 2019, 22(5): 102-108.
[7]	蒋革, 冯定忠, 朱伟杭. 基于改进粒子群算法的高效船体分段制造优化[J]. 工业工程, 2018, 21(3): 65-74.
[8]	黄锦钿, 黄伟, 郑耿灶. 加工时间存在双重约束的批调度模型及算法[J]. 工业工程, 2017, 20(2): 78-85.
[9]	何立华，马芳丽. 基于混沌差分进化粒子群算法的模糊资源受限项目调度问题[J]. 工业工程, 2016, 19(5): 39-44.
[10]	李敬峰，叶艳，傅惠. 面向货物装卸需求的越库仓门分配和货车排序[J]. 工业工程, 2016, 19(2): 112-120.
[11]	桂达1, 朱海平1, 廖嘉伟1，杨馥铭1, 余志强2. 基于混合算法的飞机多层次装配计划优化及应用[J]. 工业工程, 2015, 18(6): 8-18.
[12]	钮建伟1，秦洁1，丁文英1，温薇1，于洋1，王道平2. 基于资源限制的多目标网络计划优化模型[J]. 工业工程, 2015, 18(6): 116-124.
[13]	刘炳辉，江小云. 切削参数的两阶段优化系统[J]. 工业工程, 2014, 17(6): 30-35.
[14]	彭建良，李仁健，李修琳. 基于混合粒子群算法的群岛泊位分配问题研究[J]. 工业工程, 2014, 17(5): 17-22.
[15]	于小兵1,2. 基于改进粒子群算法的多目标应急物资调度[J]. 工业工程, 2014, 17(3): 18-21.