面向两客户的差异工件平行机批调度问题  

Two-customer parallel batch processing machines with non-identical job sizes

作　　者：谭琦[1] 陈华平[2] 张松[2] 李小林[2] 

机构地区：[1]合肥工业大学电气与自动化学院,安徽合肥230009 [2]中国科学技术大学管理学院,安徽合肥230026

出　　处：《系统工程学报》2013年第4期543-553,共11页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70821001;71171184);高等学校博士点专项科研基金资助项目(200803580024)

摘　　要：将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序并安排到平行机,然后设计了一个多目标蚁群优化算法MOACO(multi-objective ant colony optimization)对不同客户中的工件进行分批并结合TSEDD完成对问题Pareto最优解集的求解.实验结果表明,与经典的多目标问题求解算法NSGA-Ⅱ和SPEA2算法相比,MOACO具有较好的求解效果,且随着问题中工件规模的增大,算法的优势更加明显.The problem of scheduling batch processing machines with non-identical job sizes was extended into the two-customer environment,a model that optimized the makespan for the first customer and optimized the maximum lateness for the second one on parallel batch processing machines was proposed.A heuristic algorithm TSEDD（two-set earliest due date） was first proposed to determine the processing sequence of batches on the parallel machines,then a MOACO（multi-objective ant colony optimization） was further presented to arrange the jobs from different customers into batches and combined with TSEDD to search for the Pareto optimal solutions of the problem.The experimental results showed that the MOACO achieved better effectiveness than the classical approaches such as NSGA-Ⅱ and SPEA2 which were widely used in solving the multi-objective optimization problems.The predominance of MOACO was more conspicuous as the scale of problems became larger.

关 键 词：两客户 平行机 批调度 差异工件 多目标蚁群优化算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]