基于遗传算法的作业车间优化调度方法及其应用.pdf

上海交通大学

硕士学位论文

基于遗传算法的作业车间优化调度方法及其应用

姓名：卞长松

申请学位级别：硕士

专业：工业工程

指导教师：范菲雅;钟宝生

20080401

上海交通大学工程硕士学位论文

基于遗传算法的作业车间优化调度方法及其应用

摘要

随着我国市场化经济的持续发展，在激烈竞争的市场环境中，要想得到更多的
市场份额，就要比竞争对手更有优势竞争力，这就要求企业要拥有快速反应的能力。
这些都对制造企业的生产管理和生产控制提出了更高的要求。在半导体产业的供应
链中，下游环节的零组件生产企业，在必须保证产品质量的前提下，如企业的制造
成本和产能无法满足客户的实际需求和突发变化的调整，就会流失客户的订单，无
法保证制造车间高效且稳定地持续运行。生产计划和调度系统能够帮助制造企业的
竞争力达到这些要求，使得企业的效益最大化。
生产调度是企业管理的核心工作和关键的系统环节，是能在同样的生产条件下
获得最大效益的手段。生产调度问题通常是多约束、多目标和随机不确定的优化问
题，已被证明为属于NP问题。对于生产调度问题的研究已历经几十年，期间已经
提出了多种调度方法，但对于与实际生产接近的大规模优化问题，至今仍未有较为
系统化的理论出现。本文从富士迈半导体工业公司的实际生产状况入手，以系统分
析的角度对现有作业车间的调度问题进行了描述，通过分析和评价启发式的调度优
化方法，引入利用遗传算法解决作业车间调度问题的优化方案。对选定的作业车间
进行建模分析，提出了一个可集成在MES系统环境中的生产调度子系统的总统设计
构想。应用JGAP的遗传算法软件包，完成一个生产调度子系统程序的开发和测试
过程。
关键词作业车间调度，遗传算法

I

上海交通大学工程硕士学位论文

AGENETICALGORITHMAPPLIEDTOJOBSHOP
SCHEDULINGPROBLEM

ABSTRACT

JobShopSchedulingproblemisatypicalNP-HardProblem,anditisaimportant
issuesinCIMSarea.Itisimpossibletofindtheglobaloptimuminpolynomial
complexity.GoodalgorithmsforJSPproblemcanpromoteporductivityofenterprises.
Sothisthesiscanprovidegoodresultsforboththeoryandpractice.Inthisthesis,a
SimpleGeneticAlgorithm(SGA)isproposedforJSP.ByusingtheJGAPjavasoftware
package,theSimpleGeneticAlgorithm(SGA)canbeeasilyusedtoapplyevolution
principlesforJSPproblem.Besides,adecimalencodingmethodforchromosomebased
onprocessingroutesispresentedwhichcanavoiddeadlockandswitchsolutionsto
chromosomesandviceversaeasily.Experimentalresultsofsometestdatashowthat
SGAcanefficientlysolvetheJSPforourcompany.

KEYWORDS:JobShopscheduling,Geneticalgorithm,JGAP

II

上海交通大学工程硕士学位论文

符号说明

DNC(DirectNumericalControl),即计算机直接数
控或分布式数控系统
SEMI国际半导体设备材料产业协会

JGAP基于Java语言的遗传算法软件包

III

上海交通大学

学位论文原创性声明

本人郑重声明：所呈交的学位论文，是本人在导师的指导下，

独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本

论文不包含任何其它个人或集体已经发表或撰写过的作品成果。对本

文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律结果由本人承担。

学位论文作者签名：

日期：年月日

上海交通大学

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，

同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，

允许论文被查阅和借阅。本人授权