考虑学习效应的最小化延误总时间的单机批次排序问题  

Batch scheduling with learning effect on single-machine to minimize the total tardiness

作　　者：胡金昌[1] 吴耀华[1] 吴颖颖[1] 杨栋 HU Jin-chang;WU Yao-hua;WU Ying-ying;YANG Dong(College of Control Science and Engineering,Shandong University,Jinan 250061,China)

机构地区：[1]山东大学控制科学与工程学院

出　　处：《控制与决策》2019年第12期2708-2712,共5页Control and Decision

基　　金：国家自然科学基金项目(61703241)

摘　　要：一些生产场景中,工件以批次作业的形式被安排生产,工件批量大、加工工序基本相同,所以标准工时相同,而且实际加工时间会受到学习效应的影响.为此,讨论学习效应的最小化延误总时间的单机批次排序问题,对该问题建立数学模型.该问题属于NP-hard问题,采用动态规划算法(DP)和模拟退火算法(SA)求解该问题,通过实验分析不同规模时DP的执行时间与SA的执行时间和求解误差的变化趋势,比较SA与其他实践中常用的经典规则的求解效果.最后得出DP适合批次数小于13的小规模问题,可以得到精确解;与经典规则相比,SA至少可以使目标函数降低20%,表明SA算法具有有效性.SA解决大规模问题时效果较优,并得出SA的执行时间和误差随着控制参数改变的变化趋势.In some factory, job has been processed in batches which consist of the processing procedures basical identical jobs, so all jobs have the same normal processing time. The actual processing time is affected by th "learning effect".The batch scheduling problem with learning effect on a single-machine to minimize the total tardiness is discussed, which is a NP-hard problem. For this problem, we model and propose a dynamic programming(DP) algorithm and a simulated annealing(SA) algorithm. The solution time variation trend of the both algorithms and the errors variation trend of SA with different problem sizes are analyzed by experimental tests. We have compared the performance of the SA to other classical rules which are usually applied in real-life. The results show that the DP can get exact solution and more suit the small size problems whose batch number is less than 13. Comparing to other classical rules, the SA is effective because of 20% decline in object value by using the SA. The large size problems can be solved better by using the SA, and the variation trend of the solution time and the errors with controlling parameters changed is analyzed.

关 键 词：批次排序问题 单机 学习效应 动态规划 模拟退火算法 最小化延误总时间 

分 类 号：O223[理学—运筹学与控制论]