加工时间存在双重约束的批调度模型及算法  

Model and Algorithm for Batch Scheduling with Double Constrains of Processing Time

作　　者：黄锦钿[1] 黄伟 郑耿灶 HUANG Jindian HUANG Wei ZHENG Gengzao(Department of Mechanical and Electrical Engineering, Jieyang Vocational ＆Technical College, Jieyang 522000, China Jieyang Guangfeng Steel Industry, Jieyang 522000, China Special Equipment Inspection and Research Institute of Guangdong Province, Jiangmen 529000, China)

机构地区：[1]揭阳职业技术学院机电工程系,广东揭阳522000 [2]揭阳市光丰钢业有限公司,广东揭阳522000 [3]广东省特种设备检测研究院江门检测院,广东江门529000

出　　处：《工业工程》2017年第2期78-85,共8页Industrial Engineering Journal

基　　金：揭阳市科技计划资助项目(2015B01026)

摘　　要：为了提高热处理的加工效率并实现准时交货,本文根据热处理各批次加工时间受装炉量和批中最大工件尺寸双重约束的特点,分别以最小化最大完成时间和最小化最大拖期量为调度目标,构建混合整数线性规划模型Model C和Model L。根据分批数量上界设定值与Model C运算结果的关系特性,构建启发式算法HC提高Model C的运算效率。通过反例说明Model C所具有的特性并不适用于求解Model L。提出启发式算法HL求解最小化最大拖期量问题,并证明算法HL的计算复杂度。通过大量实验数据验证,结果显示两个数学模型都分别能够求得最优解,但调度规模不超过18个工件;算法HC能得到调度规模为60个工件的最优解;算法HL与最优解相比平均偏差不超过15%,调度性能明显优于其他2种典型算法。In order to improve the efficiency of heat-treatment and to effect on-time delivery, considering the heat-treatment batch processing time constrained by double factors, the amount of stove and the maximum job size of the batch with two objectives of minimizing makespan and minimizing maximum lateness, two mixed integer linear programming models are developed, respectively called Model C and Model L. According to the relational feature between the calculation result of Model C and the setting value of the batch number upper bound, the heuristic HC is developed to improve the efficiency of Model C. A counter-example shows that the feature of Model C does not apply to solving Model L. The heuristic HL is developed for minimizing maximum lateness. An extensive simulation study is conducted. The results show that the two mathematical models are able to obtain the optimal solution, but not more than 18 jobs. The algorithm HC can get the optimal solution of 60 jobs. Compared with the optimal solution, the average deviation of the algorithm HL is not more than 15%, and the scheduling performance is better than the other two typical algorithms.

关 键 词：批调度 热处理 数学模型 启发式算法 

分 类 号：F406[经济管理—产业经济]