文本描述
声明
本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学
位论文中，除了加以标注和致谢的部分外，不包含其他人己经发表或公布
过的研宄成果，也不包含我为获得任何教育机构的学位或学历而使用过的
材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明
确的说明。
研宂生签名：＞
＞以年＆月d日
学位论文使用授权声明
南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上．？－＇？
网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权
其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，
按保密的有关规定和程序处理。
研究生签名：免基＞6年t月／
？＾
曰
硕士论文HY卷烟厂烟丝生产排程优化研究
摘要
生产车间的作业调度问题一直是生产企业研究的一个热点问题。很多资料己经证明
大部分车间生产作业调度问题是NP完全问题，这类问题求解过程的计算量随问题复杂
程度呈指数增长，求得最优解非常困难。启发式算法不仅具有实现相对容易的优点，而
且在实际生产过程中面对复杂的调度问题可以保持良好的算法性能，因此，在生产调度
算法的设计过程中被广泛采用。
本文研宄的对象是烟草企业烟丝生产环节的生产调度排程优化问题。研宄的具体对
象是两条并行的生产流水线，这两条生产线不完全相同又有公共部分。在工艺路径、设
备性能、产品配方、设备连接关系等多重约束下，生产调度变得异常复杂。通过生产历
史数据描述了生产调度的现状及问题，提出了优化改进需求。
制丝车间两条并行的流水线，经常因为争夺公共部分资源而发生冲突，浪费生产资
源，造成生产实际时间远大于理论生产时间。因此，本文设计了一种基于生产时间的二
重优先分配启发式算法，首先根据优先分配规则排列所有的生产任务，在此基础上对生
产任务进行二次启发式优化，以求得烟丝生产调度排程具有一定的柔性，能够抵御一些
短暂的突发问题。然而在实际生产过程中，不可能完全按照既定计划执行，设备故障、
执行偏差等都会对调度排程产生影响，因此，本文在静态调度的基础上设计了一些异常
情况下的动态调度算法，以保证生产调度排程始终处于较优水平。最后，以HY卷烟厂
生产实际数据举例，通过模拟生产调度排程流程验证了设计算法的有效性。
关键词：启发式算法，烟丝生产排程，静态调度，动态调度
I
Abstract硕士论文
Abstract
Job－shopschedulinghasalwaysbeenahotissueinmanufacturingenterprises．Many
datahaveprovedthatjob－shopschedulingproblemsareNPcompleteproblems．The
computationoftheseproblemsincreasesexponentiallywiththecomplexityoftheproblems，
whichisextremelydifficulttogetanoptimalsolution．Heuristicalgorithmwouldnotonlybe
relativelyeasytoimplement，butalsomaintainagoodalgorithmperformanceincomplex
schedulingproblemsinactualproducingprocess．Accordingly，itiswidelyusedinthedesign
processofproductionscheduling．
Thestudyobjectofthispaperistooptimizetheschedulingoftobaccoproductionin
tobaccoindustry．Thespecificobjectistwoparallelproductionlines，whicharenotexactly
thesamebuthavesharingparts．Underthemultipleconstraintsofprocesspath，equipment
performance，productformula，equipmentconnectionandsoon，productionscheduling
becomesmorecomplicated．Thestatusandproblemsofproductionschedulingaredescribed
throughtheproductionhistorydata，andtheoptimizationandimprovementrequirementsare
putforward．
Thetwoparallelproductionlinesofthesilkmakingworkshopfrequentlyconflictwhen
competingforsomeresources，whichresultsinwastingresources，sotheactualproduction
timeismuchlongerthanthetheoreticaltime．Therefore，adualpriorityallocationHeuristic
algorithmbasedonproductiontimeisdesignedinthispaper．Itrequirestoarrangeall
productiontasksaccordingtothepriorityallocationreles，andthenabtainsaHeuristic
algorithmquadraticopitimization．BythedesignoftheHeuristicalgorithmopitimization，
tobaccoproductionschedulinghasacertainflexibiatyandwillwithstandsomeunexpected
problemsshortly．However，theactualproductionprocesscannotbecompletelyconsistent
withtheestablishedplan，becauseequipmentfailureandexecutivedeviationwillaffectthe
productionscheduling．Therefore，thispaperdesignsadynamicschedulingalgorithmfor
someabnormalconditionsbasedonstaticschedulinginordertoensuretheproduction
schedulingisalwaysinabetterlevel．Finally，withtheactualdataofHYcigarettefactory
productionexample，theeffectivenessofthedesignalgorithmisverifiedbysimulatingthe
schedulingprocessofproductionscheduling．
Keywords：Heuristicalgorithm，Tobaccoproductionscheduling，Staticscheduling，
Dynamicscheduling
II
硕士论文HY卷烟厂烟丝生产排程优化研究
目录
＾要I
AbstractII
1绪论1
1．1研究背景与意义1
1．1．1研究背景1
1．1．2研究意义1
1．2研宄现状2
1．3研究内容和研究方法6
1．4论文结构7
2生产调度理论和启发式算法8
2．1生产调度系统的功能与特点8
2．1．1生产调度系统的功能8、
2．1．2生产调度系统的特点9
2．2常用的生产调度规则和评价指标10
2．2．1常用调度规则10
2．2．2生产调度的评价指标104
2．3启发式算法11
2．3．1启发式算法的基本概念11
2．3．2—般流水作业排列排序问题的启发式算法12
3HY卷烟厂烟丝生产排程现状和优化改进需求14
3．1制丝车间的生产调度14
3．1．1制丝车间的业务描述14
3．1．2制丝生产调度计划分解的业务流程15
3．2HY卷烟厂制丝车间柔性资源及约束分析16
3．2．1工艺路径的柔性及约束16
3．2．2物料输送的柔性及约束17
3．2．3产品的柔性及约束19
3．2．4机器的柔性及约束20
3．3HY卷烟厂烟丝生产排程现状分析21
3．3．1HY卷烟厂烟丝生产排程现状流程分析21
3．3．2HY卷烟厂烟丝生产排程现状历史数据分析22
III。
==>>