基于遗传算法的带时间窗并行机调度问题的研究

作     者：陈新娟 

作者单位：华中科技大学 

学位级别：硕士

导师姓名：曹炬

授予年度：2007年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：时间窗 生产调度 遗传算法 

摘      要：车间资源的有限性制约着能否有效利用车间现有资源完成任务,而以最快的速度响应市场需求,促使制造型企业能否赢得市场竞争。调度的任务是根据生产目标和约束,为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。提前/拖期惩罚生产调度问题的典型应用背景是准时制(Just In Time, JIT)生产计划和调度。现实的生产活动中,要注重整体效益。一方面,根据客户要求的提货时间窗口来安排生产满足市场需求,以期吸引更多客户合作;另一方面,也应考虑到自身生产能力并使所安排的生产计划所耗费的生产成本尽可能的低。所以本文讨论的提前/拖期(E/T)问题兼顾到了生产成本,即是不以提高生产成本来降低比之更多的提前/拖期惩罚代价。 本文首先介绍有关窗时排序和车间调度问题的基础知识,阐述遗传算法的基本概念、原理和方法。其次对所研究的带时间窗并行多机调度问题进行了详细的数学分析,并对数学描述进行了简化,为下一步算法设计建立数学模型。 为了克服遗传算法容易出现提早收敛的缺陷,在基本遗传算法基础上对选择和交叉算子进行了改进,并将改进的遗传算法应用于相应的生产调度问题。本文采用Matlab强大的数值计算能力和众多的库函数编写算法;针对生产调度问题给出了算法实例,仿真实例证明,该算法结果较好。