文档介绍：中国科学技术大学
硕士学位论文
SAGA算法在差异工件平行机批调度问题中的应用研究
姓名:舒锋
申请学位级别:硕士
专业:管理科学与工程
指导教师:@
2011-04-10
摘要
摘要
调度问题是组合优化领域中一类重要的问题,它广泛地应用在制造业、现代
物流和网络通信等领域,本文主要研究的是生产调度问题,有效的调度能够提高
机器利用率、降低成本、增加利润和提升客户满意度。本文的研究目标是最小化
差异工件平行机批调度问题的制造时间跨度 Cmax,在调度问题的研究中,Cmax
经常被用来衡量调度的性能,与差异工件单机批调度问题相比,差异工件平行机
批调度问题更接近现实生产活动,而且目前关于该问题的研究仍然较少。
本文首先简述了调度问题的概念、研究意义、分类和参数表示、经典调度与
现代调度的区别以及差异工件批调度问题的概念。同时,我们也简单介绍了组合
优化问题的概念与计算复杂性的相关基础知识。
由于差异工件批调度问题是一类典型的 NP-hard 问题,所以解决该类问题的
关键在于寻求有效的优化算法。目前,求解差异工件批调度问题的主要方法有两
种:(1)数学规划方法;(2)启发式方法。前者虽然可以求得问题的最优解,但
是只适用在小规模问题中,后者虽然在大多数情况下不能得到最优解,但是它能
有效地解决大规模问题,在一定时间内给出一个在可以接受范围内的近似最优解,
具有更强的实际可操作性。本文介绍了目前求解差异工件批调度问题的主要的数
学规划方法和启发式方法及其研究情况。
根据问题的特性,本文设计了一种面向差异工件平行机批调度问题的模拟退
火遗传算法(Simulated Annealing ic Algorithm,SAGA)。SAGA 算法集合
了模拟退火算法(Simulated Annealing,SA)和遗传算法(ic Algorithm,
GA)在局部搜索与全局搜索能力方面的优势,并改进了遗传算法的交叉方式和
适应函数的标定方式。仿真实验表明,SAGA 算法的性能优于现有文献中的两个
经典启发式规则 FFLPT 和 BFLPT 以及 GA 算法。
最后,我们总结了本文的主要工作和创新点,并提出了未来可以继续进行研
究的方向。

关键词:调度差异工件批处理机模拟退火遗传算法组合优化
I
Abstract
ABSTRACT
Scheduling is one of the most binatorial optimization problems. It
is widely applied in manufacturing, modern logistics, munication and
other fields, this paper mainly studies production scheduling problem, effective
scheduling operation can improve the utilization of machines, reduce the costs,
increase the profits and improve customers’ satisfaction. Minimizing makespan on
parallel batching machines with non-identical job sizes is the aim of this paper,
makespan is usually used to measure the performance of scheduling operation in the
research of scheduling problem, compared with single batching processing machine
scheduling problems with non-identical job sizes, scheduling on parallel batching
processing machine with non-identical job sizes is more widely used in industrial
production, and so far, there are less researches on this problem.
At first, the concept of scheduling problem, significance of the research,
classificatio