基于遗传算法求解作业车间调度问题

西安交通大学管理学院基于遗传算法求解作业车间调度问题1绪论1.1作业车间调度问题表述作业车间是指利用车间资源完成的某项任务，在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工,一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”,用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程,用“加工顺序”表示各台机器上各个工件加工的先后顺序。在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得总的加工时间最短。1.2作业车间调度问题研究的假设条件及数学模型1.2.1作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2.资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。根据上面以及求解方便，我们做出以下具体假设：1.每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序数不大于设备数；4.每道工序必须在指定的某种设备上加工，所有机器处理的加工类型均不同；5.在作业优化过程中既没有新的工件加入也没有取消的工件；西安交通大学管理学院6.不考虑工件加工的优先权，即工件之间没有优先约束关系限制的；7.工序允许等待，即前一个工序未完成，则后面工序需要等待；8.工件的加工时间事先给定，且在整个加工过程中保持不变。1.2.2车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号［6］：J:所有工件的集合，12{,,}nJJJJ；M:所有机器的集合，12{,,}mMMMM；ijP：工件Ji的工序集合，12{,,}iiiiijjjjpPPPP；P:所有工序的集合，此为12max{,,}nnPPP矩阵。P（i，j）表示i工件的第j道工序。(,)ijPiP•，表示i工件的所有工序按优先顺序的排列。不足12max{,,}nPPP，那么其空余的位置用0填满。111111111212(1)1100000innnniiiPPPjjjPjjjpjPPPPPPPPPPPP（1.1）MJ:机器顺序阵，此为12max{,,}nnPPP矩阵。MJ（i，j）表示i工件的第j道工序的机器号，(,)MJi•表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足12max{,,}nPPP，那么其空余的位置用0填满。11121111121(1)11100000ijPjjjpjjnjPnnniiiPPPPPPMPPPPPPPMMMJMMMM（1.2）T:加工时间阵，此为12max{,,}nnPPP矩阵。T(i,j)表示工件i的第j道工序在MJ（i，j）上的加工时间。同样地，如果某工件的工序数不足12max{,,}nPPP，那么其空西安交通大学管理学院余的位置用0填满。11121111121(1)11100000ijPjjjpjjnjPnnniiiPPPPPPPPPPPPPTTTTTTTT（1.3）jM：工件排列阵，此为12max{,,}nPPPn矩阵。(,)jMij表示在i机器上排在第j位加工的工件号，(,)jMi•表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足12max{,,}nPPP，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的jM，满足*12()min{(),(),()}njjjjfMfMfMfM或*12()max{(),(),()}njjjjfMfMfMfM。即jM使得目标函数()jfM取值最小(或最大)，且与MJ相容，则称jM为车间作业调度问题在此目标函数下的最优解。2基本遗传算法遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者Holland于1975年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1遗传算法的基本思路1.首先确定问题的求解空间；2.将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3.计算当前群体中每个个体的适应度函数值，然后运用选择、交叉、变异算子产生西安交通大学管理学院新一代群体；4.对新一代群体中的每个个体进行评价，若找到满足问题的最优解则结束；否则，转步骤3。2.2基本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等。1.种群数目种群数目N的多少直接影响到遗传算法的优化性能和效率。种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解;种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。2.交换概率交换概率Pc用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象;交换概率太小的时候又容易产生搜索停滞不前的现象。3.变异概率变异概率Pm对于增加种群多样性具有重要意义。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。4.代沟代沟G用于控制每一代群体被替换的比例，每代有N×(1-G)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数，而是评价遗传算法的一个参数。5.尺度窗口该参数用于作出由目标值到适应度函数值的调整。6.选择策略一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接加入下一代种群中，该策略是为了防止最优解的丢失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。西安交通大学管理学院3用遗传算法对具体问题的解决遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。3.1参数编码遗传编码技术是实施遗传算法的核心。遗传算法的工作基础是选择适当的方法表示个体和问题的解，对于同一问题可以有不同的编码表示方法。由于遗传算法不能直接处理空间解的数据，在解决此车间调度问题上把它们转换成遗传空间的基因按一定结构组成的染色体或个体，也就是通过编码将它们表示成遗传空间的基因型串结构数据。我们采用了基于操作的编码来解此车间调度问题，其基本思想是将所有工件的操作进行编码，不同的工件用不同的编码表示，而同一工件的所有操作在染色体中则用相同的编码表示，其解码原则是将染色体上的基因按照从左到右的顺序解释为相应工件的操作顺序，具有相同编码的基因按照其在整个染色体中的位置解释为工件相应顺序的操作。表3.1加工时间和工艺约束项目工件操作序列123操作时间J1J2J3313352233机器J1J2J3M1M1M2M2M3M1M3M2M33.2初始种群的生成在N个工件M台机器的排序问题中，对每个机器的加工存在加工工艺顺约束，这个工艺约束表示为工件的加工顺序矩阵：M11M12…M1MM（J,M）=M21M22…M2M西安交通大学管理学院：：：：(3.2)Mn1Mn2…MnM其中第J行表示第J个工件的机器顺序.机器号为零表示工件加工结束。相应的每个加工操作有时间矩阵：T11T12…T1MT21T22…T2MT(J,M)=：：：：(3.3)TN1TN2…TNM其中第J行表示第J个工件的机器加工时间,时间为零表示工件不在机器上加工。因为群体中的个体都是由工件的符号组成的，而且工件任意排列总能产生可行调度，所以可以采用随机方法产生初始种群。3.3个体的适应度函数在遗传算法中,适应度是描述个体性能的主要指标。根据适应度的大小,对个体进行优胜劣汰。适应度是驱动遗传算法的动力。从生物学角度讲,适应度相当于“生存竞争,适者生存”的生物生存能力,在遗传过程中具有重要意义。适应度函数就是目标函数，在用遗传算法解决车间调度问题里，定义个体的适应度函数为在M台机器上排序加工完N个工件所需的时间，根据染色体编码的思想提出的适应度算法如下：STEP1:定义ti(n)为每个工件的可加工时间，初始化向量为零向量。STEP2:chrom（i）对应相应工序的加工机器为machiner（i）。ti(chrom(1))=ti(chrom(1),machine(1))STEP3:fori=2tonFork=1tonti(chrom(i))=ti(chrom(i-1))+max(ti(chrom(i-k),machine(i-k)+k))其中若当i-k=0,则ti(chrom(i-k),machine(i-k))=0,还有要判断chorm(i)所对应的工件在以前是否加工过，若加工过，则ti(chrom(i))=ti(chorm(i-1))。STEP4:求出适应度函数F=ti(chorm(n))。西安交通大学管理学院3.4遗传算子的设计1.选择算子选择操作是对自然界“适者生存”的模拟。评价值(目标函数)较小的个体有较高的概率生存,即在下一代群体中再次出现。我们采用一种常用的选择方法：按比例选择,即若个体i适应值(目标函数)是fi,则个体在群体中复制(再生)的子代个数在群体中的比例将为:/iiff。其中,∑fi表示指所有个体适应值之和。对群体中各个体的适应值做比较,将适应值小的个体复制,将适应值大的淘汰掉,这是因为在作业调度算法中的适应度函数为在M台机器上加工完N个工件所需的时间,时间越短,更能达到优化的目的。2.交叉算子在用遗传算法解决作业车间调度问题中,在对工序编码的排序问题中,交叉算子不能简单交换两个个体的相应位置的基因段,因为这样得到的后代个体可能不能满足每个工件号重复M次的要求。为了满足我们的工序编码的要求,本文采用下面的交叉算子:随机将工件集合{1,2,…N}分成两个互补子集,相应的将个体的基因分成两个部分，然后把父母个体中的part2部分用h代替形成两个新串，用第二个父母个体的part2部分按照原来的相对顺序逐个替换第一个父母个体的part2产生的新串中的h,同样用第一个父母个体的part2按照原来的相对顺序逐个替换第二个父母个体的prat1产生的新串中的h,得到两个后代个体。例如:对于一个4个工件4个机器问题,假如父母个体为:Parent1:1342423314321421Parent2:3241123442312413假设随机选择工件1，2，则从parent1得到的新串为：New1:1hh2h2hh1hh21h21Part1:12212121Part2:34433434同样从Parent2得到的新串为New2:h2h112hhh2h12h1hPart1:21122121西安交通大学管理学院Part2:34344343然后用Parent2个体的