自然科学版 英文版
自然科学版 英文版
自然科学版 英文版

您目前所在的位置:首页 - 期刊简介 - 详细页面

中南大学学报(自然科学版)

Journal of Central South University

第48卷    第8期    总第276期    2017年8月

[PDF全文下载]    [Flash在线阅读]

    

文章编号:1672-7207(2017)08-2063-10
考虑能耗约束的并行机组批调度
李国臣,乔非,王俊凯,马玉敏,卢凯璐

(同济大学 电子与信息工程学院,上海,201804)

摘 要: 研究并行批处理机的组批调度问题,考虑炉容相同、功率不同的非等同并行机的总能耗约束,考虑工件尺寸和到达时间不同,以最小化最大完工时间为目标建立混合整数规划模型。并行机组批调度问题属于NP-hard问题,采用先组批后调度的两阶段方式求解。组批阶段采用基于FFLPT和BFLPT的启发式规则,调度阶段设计带邻域搜索的粒子群-遗传混合算法对模型进行求解。以轧辊生产企业并行热处理设备为研究案例进行模型和算法验证,分析不同能耗约束下最大完工时间优化值,并比较算法的优化性能。实验结果表明:本文算法提高标准遗传算法的收敛速度,且优于2种启发式算法;能耗与最大完工时间之间存在冲突关系,通过本文的模型和算法得到能耗与最大完工时间的近似Pareto前沿面,可为企业的实际生产提供指导。

 

关键字: 并行机;组批调度;能耗约束;最大完工时间;粒子群-遗传算法;邻域搜索

Parallel machine batching scheduling considering energy constraints
LI Guochen, QIAO Fei, WANG Junkai, MA Yumin, LU Kailu

College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China

Abstract:Non-identical parallel machines with same capacity but different power were considered for batching scheduling problems. A mixed integer programming model minimizing makespan was established, with different job sizes and arrival times. As the parallel machine batching scheduling problem was NP-hard, a two-phase method, that was, first batching and then scheduling, was adopted to solve the model. At the phase of batching, two heuristic rules, FFLPT and BFLPT, were employed; and a PSO-GA hybrid algorithm with neighborhood search was designed at the phase of scheduling. The proposed model and algorithm were validated under a case study of parallel heat treatment equipment in roller manufacturing. Optimized makespans under different energy consumption constraints were analyzed, and the performance of different algorithms were compared. The results show that the proposed algorithm improves the convergent speed of standard genetic algorithm, and outperforms the other two heuristic algorithms. Meanwhile, there exists trade-offs between energy consumption and makespan. And the approximate Pareto frontier of these two indicators obtained by the proposed model and algorithm may provide guidance for real production in enterprises.

 

Key words: parallel machines; batch scheduling; energy consumption constraints; makespan; PSO-GA; neighborhood search

中南大学学报(自然科学版)
  ISSN 1672-7207
CN 43-1426/N
ZDXZAC
中南大学学报(英文版)
  ISSN 2095-2899
CN 43-1516/TB
JCSTFT
版权所有:《中南大学学报(自然科学版、英文版)》编辑部
地 址:湖南省长沙市中南大学 邮编: 410083
电 话: 0731-88879765(中) 88836963(英) 传真: 0731-88877727
电子邮箱:zngdxb@csu.edu.cn 湘ICP备09001153号