典型优化问题的遗传算法求解—10调度问题

典型优化问题的模型与算法-R031典型问题调度问题(SchedulingProblems)东北大学系统工程研究所2014.09调度问题一类典型的优化问题。广义地讲，调度问题考虑的是：随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。资源可能在本质上是很不相同的:人力、金钱、机器、工具、材料、能源等等。任务也可以有不同的解释，从制造系统的机器划分到计算机系统的信息处理。一项任务通常可以用下面的因素来表示特征:完成时间、预期时间、相对紧急权重、处理时间资源消耗。同时，一组反映任务之间先后约束的结构可以用不同的方式定义。另外还可以考虑度量调度性能好坏的不同判据.典型优化问题的模型与算法-R032典型优化问题的模型与算法-R033特点调度问题几乎在现实环境(特别是工业工程领域)中无处不在。许多制造工业提出的调度问题从本质上讲非常复杂，难以用传统优化方法求解。通常这些难于求解的问题都表示为满足非常复杂约束的组合优化问题。这些问题带有有限数量的可行解。这些问题属于NP—难的问题。经典调度问题的分类流水车间调度问题作业车间调度问题机器调度问题扩展调度问题：群体作业调度资源约束的项目调度多处理器调度车辆与路径调度……典型优化问题的模型与算法-R034制造业生产模式按生产计划方式分类面向订单生产，强调准时高效，客户订单到达后才开始组织生产。面向库存生产，在客户订单到达之前就已开始生产，生产计划以库存为基础。混合生产模式，一方面根据预测，保留较大的库存，另一方面以一定的实时生产能力来满足高度客户化的订单需求。典型优化问题的模型与算法-R035制造业生产模式按生产过程的工艺流程特征分类离散式生产：产品是由离散的零部件装配而成，零部件以各自的工艺过程通过各个生产环节，物料运动呈离散状态。例如属于生产资料生产的机械、电子设备制造业，属于生活资料生产的机电整合消费产品制造业。离散型制造企业的生产方式多为单件、小批量、多品种流程式生产：在生产过程中，物料均匀、连续地按一定工艺顺序运动，生产流程具有连续性的特点和要求例如冶炼、化工、酿造等混合流程式生产：这是一种既具有流程式生产特征，又具有离散式生产特征的复杂生产方式，其生产过程并不完全是一个自动生产线。其典型特征是生产分阶段进行，设备按阶段使用，在不同的生产阶段遵循不同的生产方式，一般产品不可数，加工过程是间歇式的。典型优化问题的模型与算法-R036FlawShop和JobShop调度问题是昀典型和昀重要的两种车间调度问题。车间调度问题具有以下几个特点:复杂性:由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用、每个作业又要考虑它的加工时间、操作顺序、交货期等，因而相当复杂。动态随机性:在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、设备的损坏/修复、作业交货期的改变、紧急定单等。多目标性:实际的计划调度往往是多目标的。生产调度的性能指标可以是成本昀低、库存费昀少、生产周期昀短、生产切换昀少、设备利用率昀高、昀短的延迟，昀小的提前或者拖期惩罚等。这种多目标性导致调度的复杂性和计算量急剧增加。多约束性:生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束，如要求各机器上的负荷平衡等等。车间调度问题的几个特点典型优化问题的模型与算法-R037典型优化问题的模型与算法-R038典型问题流水车间调度问题(Flow-shopSchedulingProblems)问题描述一般描述n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器。n个工件在m台机器上的加工顺序相同。工件i在机器j上的加工时间是给定的，设为tij(i=1,…,n;j=1,...,m)。问题的目标求n个工件在每台机器上昀优的加工顺序，使昀大流程时间达到昀小。典型优化问题的模型与算法-R039问题描述对该问题常常作如下假设:每个工件在机器上的加工顺序是:1,2,…,m;每台机器同时只能加工一个工件;一个工件不能同时在不同的机器上加工;工序不能预订;工序的准备时间与顺序无关，且包含在加工时间中;工件在每台机器上的加工顺序相同，且是确定的。典型优化问题的模型与算法-R0310三类FSP问题确定型流水车间问题假定工件的加工时间是已知的确定量随机型流水车间问题加工时间按照一定的概率分布而变化模糊型流水车间问题每个工件的模糊交货期表示为决策者对工件完成时间的满意度典型优化问题的模型与算法-R0311实际调度问题往往更加复杂，例如：通常要满足一定的约束条件顾客的交货时间、资源约束、工艺约束等性能指标通常可以分成多种类型昀大能力指标昀大生产率、昀短生产周期等成本指标昀大利润、昀小化运行费用、昀小投资、昀大收益等客户满意度指标昀短的延迟，昀小提前或者拖后惩罚等实际调度问题典型优化问题的模型与算法-R0312确定型FSP的一个实例：4个工件、2台机器工件顺序：j3,j2,j4,j1.调度S如下：S=(t31(0-3),t21(3-4),t41(4-10),t11(10-15),t32(3-9),t22(9-11),t42(11-16),t12(16-20))实例Jobi1234ti15136ti24265M1M2time4-joband2-machineproblemMakespan:20(units)j3j2j4j1j3j2j4j11234567891011121314151617181920典型优化问题的模型与算法-R0313墙纸行业生产调度问题装饰布企业车间生产调度飞机维修调度问题化工涂料生产的配料及调度集装箱码头装卸作业的调度问题汽车总装车间调度柔性流水车间调度问题冷轧厂热处理车间冷卷热处理生产调度问题炼钢-连铸浇次组合与排序石油、化工等流程工业应用典型优化问题的模型与算法-R0314两台机器FSP的最优调度Johnson规则：昀优调度中工件i排在工件j之前，如果:昀优顺序可以直接利用这个结果通过两个工序之间的检查来构造。令I表示工件序列，S表示顺序，Johnson算法可以描述为：},min{},min{1221jijittttinput:ti1,ti2,joblistI,output:bestscheduleSstep1:LetU={i|ti1ti2}andV={i|ti1≥ti2}step2:SortjobsinUwithnon-decreasingorderofti1step3:SortjobsinVwithnon-increasingorderofti2step4:AnoptimalsequenceistheorderedsetUfollowedbytheorderedsetV典型优化问题的模型与算法-R0315i1j1i2j2j1i1j2i2满足关系，i排在j之前满足关系，i排在j之后8个工件问题的实例昀优解构造如下：Jobi12345678ti152176375ti226256721step1:JobsetsU={2,3,6}andV={1,4,5,7,8}step2:SortjobsinUasfollows:Jobi:326ti1:123step3:SortjobsinVasfollows:Jobi:54718ti2:65221step4:Anoptimalsequenceis{3,2,6,5,4,7,1,8}M1M2j3j3j2j2j6j6j5j5j7j7j1j1j4j4j8j81064312019171211302826233736343231Makespan:37(units)典型优化问题的模型与算法-R0316m台机器的启发式算法Palmer启发式算法Gupta启发式算法CDS启发式算法RA启发式算法NEH启发式算法典型优化问题的模型与算法-R0317GA求解--Gen-Tsujimura-Kubota方法编码采用工件的换位表达，此类问题的自然表达方法。表示工件的加工顺序为：j3j2j4j1调度S为：S=(t31(0-3),t21(3-4),t41(4-10),t11(10-15),t32(3-9),t22(9-11),t42(11-16),t12(16-20))3241vk=1:2:3:4:Jobi1234ti15136ti24265Exampleof4-Joband2-machineProblemM1M2time10543201615119j3j3j2j2j4j4j1j1GanttchartoftheoptimalscheduleMakespan:20(units)典型优化问题的模型与算法-R0318GA求解--Gen-Tsujimura-Kubota方法评估函数确定每个染色体适值的简单方法是用昀大流程时间的倒数。交叉变异PMX、OX、CX、…；Swapmutation、…基于顺序表达的交叉、变异算子都适用kkCvevalmax1)(典型优化问题的模型与算法-R0319GA求解--Reeves方法编码采用工件的换位表达，同前。种群初始化采用NEH启发式算法产生一个染色体；其余的染色体随机产生交叉采用单点交叉，首先随机选取断点，然后选取第一个双亲的断点前部分作为后代的一部分，再从第二个双亲中按顺序选取合法基因填充剩余部分。79689685712341234parent1Cutpoint57689offspring5parent24132典型优化问题的模型与算法-R0320GA求解--Reeves方法变异互换变异随机选取染色体两个基因，进行简单互换移动变异随机选取一个基因，向左或右移动一个随机数位。典型优化问题的模型与算法-R0321selectedgeneparent:312457968offspring:124796385GA求解--Reeves方法选择实质上，如果种群包含很多适值接近的染色体，好解与坏解的适值就没有明显的区别，在这种情况下相对适应性的度量便不能很好地区分染色体的好坏。Reeves采用了一种简单的调度方法来作为选择的机理，即依据如下的概率分布选择双亲:这意味着中间值的染色体有1/M的机会被选取，而昀好的染色体(第M个染色体)有2/(M+1)的机会，近似2倍中间值的机会。典型优化问题的模型与算法-R0322)1(2MMkpkwherek:按适值递增顺序排列的kth染色体M:适应性最好的染色体典型优化问题的模型与算法-R0329典型问题作业车间调度问题(Job-shopSchedulingProblems)问题描述古典作业车间问题：有m台机器和n个工件；每个工件包含一个由多道工序组成的工序集合；工件的工序顺序是预先给定的；每道工序要在它所要求的机器上加工某一固定时间;问题的目标：确定机器上工序的加工顺序，使昀大流程时间，即完成所有工件的时间昀短.典型优化问题的模型与算法-R0330问题描述对工件和机器有如下约束：一个工件不能两次访问同一机器;不同工件的工序之间没有先后约束;工序一旦进行不能中断;每台机器一次只能加工一个工件;下达时间和交货期都不是给定的。典型优化问题的模型与算法-R0331实例3个工件、3个机器的问题，可以用两类甘特图来表示312332312232111323351233321Job321JobOperationsOperationsSequenceMachineTimeProcessingMMMJJMMMJJMMMJJMachineGanttchartO333O133O223O232O122O312O321O111O211M1M2M3121110987654321timeO133O122O111O333O321O312O232O223O211J1J