两阶段flow shop差异工件批调度问题的优化方法研究

《两阶段flow shop差异工件批调度问题的优化方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文两阶段flowshop差异工件批调度问题的优化方法研究作者姓名：学科专业：导师姓名：，—々·--‘÷n—0’’。：171；，巩ptI口j：郝尚刚管理科学与工程陈华平教授二O一二年五月UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeRhon0ptimiati)nResearch0nzat0nMethodsforSchedulingTwoBatchProcessingMachinesinFlowShopAuthor’SName"H

2、aoShanggangspeciality?Manage!nentScienceandEngineeringSupervisor：”’●'’rinishedtime：Prof．ChenHuapingMay,2012Ⅲ3洲mm—●㈣2眦6眦2iiji■■I㈣2咖Y中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。赊已特另tl；Dri以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：拙签字同期：兰!!

3、生兰皇!!{}中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。日公丌口保密(——年)作者签名：盔E＆鱼，签字同期：巫垒垒支盆!幽导师签名：签字同期：＼‘N飞L切澎年ff4ll摘

4、要批调度问题是一类在实际生产环境中广泛存在的现代化调度问题。由于批处理机在平行机环境、车间环境等复杂生产环境中应用广泛，因此包含批处理机的复杂生产环境调度问题成为了当前调度研究的热点之一。本文所研究的问题是由集成电路板生产环境中测试阶段的实际问题发展而来，包含两台差异工件批处理机的flowshop调度环境，优化目标为最小化制造期。该问题兼具差异工件批调度问题和flowshop调度问题的双重特征，相比于传统差异工件单机批调度问题和经典的flowshop调度问题更加复杂。因此该问题的研究不仅具有重要的现实意义，同时还具有理论研究价值。本文对该问题

5、的特点进行了研究，将该问题分为分批和排序两个子问题，并且根据问题的特征，提出了两种算法对该问题进行了求解。主要的工作如下：首先对生产调度问题的概念和描述方法进行了阐述，然后对批调度问题进行了简单的介绍，进一步引出了包含批处理机的两阶段flowshop差异工件批调度问题的概念及其研究价值。回顾和分析了批调度问题的研究现状和方法。其次，本文提出了一种满足机器容量约束的凝聚聚类调度算法(ConstrainedAgglomerateCtustringScheduling，CACS)对该问题进行了求解。阐述了聚类过程与分批过程的异同，并对目标函数进行了

6、分析，给出了一种与原目标函数等价无穷大的近似目标函数。通过分析近似目标函数的结构，问题原目标函数主要决定于两类浪费，进一步提出了内部空间浪费比和外部空间浪费比两类浪费比的概念。采用基于这两类空间浪费比的距离度量函数，提出了一种聚类算法完成了分批过程，随后采用Johnson规则对对批集合进行排序，完成对该问题的求解。仿真实验结果表明，该算法要比SA、ARSA、H．J算法具有更好的性能，尤其是在求解大规模问题是更加有效。由于启发式算法的求解的精度不高，稳定性不够，提出了一种结合模拟退火(SimulatingAnealing，SA)邻域搜索的混合P

7、SO(HybridParticalSwarmOptimization，HPSO)算法对CACS算法的结果进～步优化。根据问题和微粒群算法的特点，采用基于工件序的随机键编码技术和BFF(BatchFirstFit，BFF)规则对编码进行分批和计算适应度值。通过对比实验，该算法比SA、ARSA、CACS等算法具有更好的效果。最后在对本文的主要工作及创新点进行了总结，并且基于本文研究的不足和延伸，进一步阐述了未来的研究方向。关键词：调度流水车间批处理机聚类微粒群优化I原书空白页不缺内容Abs订actABSTRACTBatchingschedulin

8、gproblemisatypicalmodemschedulingproblemwidelyappliedinindustrialproductionenviron