基于两阶段蚁群算法的带非等效并行机的作业车间调度  

Two-stage Ant Colony Algorithm Based Job Shop Scheduling with Unrelated Parallel Machines

作　　者：张洁[1] 张朋[1] 刘国宝[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200240

出　　处：《机械工程学报》2013年第6期136-144,共9页Journal of Mechanical Engineering

基　　金：国家自然科学基金资助项目(60934008)

摘　　要：针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。The job shop scheduling problem with unrelated parallel machines is investigated. Multiple objectives such as production cost and on time delivery rate for manufacturing system are taken into account in the proposed scheduling model. Considering the superiority of ant colony algorithm in solving the complex optimization problem, the mapping relationship between scheduling problem and ant colony parallel search is structured. The schedule process consists of two stages： tasks assignment and task sequencing. For each stage, the ant colony optimization is designed respectively so that a two-stage ant colony system（TSACS） with inheritance relationship is proposed. It can compress the solution space and improve the solving speed. Key parameters of TSACS are identified through the uniform experiment and statistical analysis. Computational experiments of 8 examples with different sizes are conducted. The results indicate that the proposed TSACA significantly outperforms the improved genetic algorithm in both optimization results and computational efficiency. The implementation of TSACS in real-life case also demonstrates that the waiting time between operations can be reduced and the product delivery cycle can be shortened.

关 键 词：作业车间调度问题 非等效并行机 蚁群算法 多目标优化 

分 类 号：TH166[机械工程—机械制造及自动化]