《置换流水车间调度问题的MATLAB求解》由会员分享，可在线阅读，更多相关《置换流水车间调度问题的MATLAB求解（22页珍藏版）》请在金锄头文库上搜索。
1、物流运筹实务课程设计题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解一、前言5二、问题描述6三、算法设计7四、实验结果15摘要自从Johnson 1954年发表第一篇关于流水车间调度问题的文章以来.流水车 间调度问题引起了许多学者的关注。安排合理有效的生产调度是生产活动能井然 有序开展，生产资源得到最佳配置，运作过程简明流畅的有力保证。流水车间调 度问题是许多实际流水线生产调度问题的简化模型。它无论是在离散制造工业还 是在流程工业中都具有广泛的应用。因此，对进行研究具有重要的理论意义和工 程价值。流水线调度问题中一个非常典型的问题，而置换流水线调度问题作为FS
2、P 问题的子问题，是一个着名的组合优化问题。该问题是一个典型的NP难问题，也 是生产管理的核心内容。随着生产规模的扩大，流水线调度问题的优化对提高资 源利用率的作用越来越大，因此对其研究具有重要的理论和现实意义。关键字：流水车间，单件小批量生产，jsp模型，Matlab前言企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中，所 以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地 位。车间生产计划与控制的核心理论是调度理论。车间调度问题是一类重要的组 合优化问题。为适应订货式、多品种、小批量生产的需要，引进了置换流水车间调 度概念。在置换流水车间调度优化后，可以避
3、免或大大减少流程工作时间、提高生 产效率。因此，研究成组技术下车间调度问题是很有必要的。生产调度，即对生产 过程进行作业计划，是整个个先进生产制造系统实现管理技术、优化技术、白动 化与计算机技术发展的核心。置换流水车间调度问题是许多实际生产调度问题的 简化模型。生产计划与调度直接关系着企业的产出效率和生产成本，有效的计划 与调度算法能最大限度地提高企业的效益。调度问题是组合优化问题，属于NP问 题，难以用常规力一法求解。随着制造业的快速发展，大规模定制生产、全球化 制造等思想的提出，使车间调度问题呈现出以下的新特点:约束条件多，时间复杂 度高，空问复杂度高。这将导致在许多情况下，求解所建立的数
4、学模型的快速性 无法满足，如果采用适度线形化处理之后求解，将会因简化太多而使结果严承失 真。所以需选择功能强大的数值计算工具来实现这一问题的求解。MATLAB恰好提 供了这样的平台。MATLAB是一个高度集成的系统，集科学计算、图像处理、声音 处理于一体，具有极高的编程效率。典型JSP模型分析与Matlab的应用结合使流 水车间调度问题迎刃而解。最大完工时间是生产调度中最常用的性能度量指标之 一，最大完工时间越短，则说明产品总的生产周期越短，生产能力越大；此类调 度问题的优化研究有助于提高企业的生产效率与资源利用率。一、问题描述流水车间调度问题通常可以描述为n个工件要在m台机器上加工，每个工件
5、有 m道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序都相同，问 题的目标是确定每台机器上工件的加工顺序及开工时间，使得特定的性能指标最 优。置换流水车间调度问题PFSP是对流水车间调度问题的进一步约束，即约定每 台机器上所有工件的加工顺序相同，其解空间的规模为n!，远远小于流水车间调 度问题的规模(n!) m。本次课程实验主要研究PFSP中的最小化最大完工时间问题，利用三元组表示 法(g|prmu|Cmax)求解Carlier (1978)提出的8个算例、以及Reeves (1995)提出的 21个算。由于三台机器以上的调度问题被证明是NP难问题，对于大规模的调度， 至今仍未出现求
6、解最优的方法，常常采用启发式算法来求解近优解。本案例主要 采用instance car2进行求解。案例：某产品，需要经过4道工序对13个工件进行加工，这13个工件的生产流 程是一样的。加工时间表见下：表4-3某产品加工时间表加工:件02345678910111213时间tj178963021457321865821420778569653212457-93021425789653214254786532112412345678J21475320124752147532145763214257854123tj4320142753214528653514527536214528888999计算步骤
7、如下：首先确定n/m/F/Cmax的最大完工时间为: c( j 1,1)二七k=2,.,mc (j , i) = c (j , k - 1) + t11j1 ki=2,.,nc( j ,1) = c( j ,1) + t1i-1j1c( j , k ) = max c( j , k ); c ( j , k - 1) + tii 一 1ij, k贝。C =、max c( j , m )n二、算法设计(一)假设工件在机器上的加工顺序是相同的，同时假定各工件准备就绪，机器一 开动就投入生产，开工时间为0，则最大完工时间等于最大流程时间。同时3台机 器以上的流水车间调度是NP难问题，所以本文只考虑了
8、 2台、3台机器的情况， 解决3台机器以上的问题方法也可运用人工智能算法，解的质量更高，但因该类 算法需良好的软件编程能力，故本文不加探究。n个工件在m台机器上的加工顺 序相同。工件在机器上的加工时间是给定的。问题的目标是求n个工件在每合机 器上的最大完工时间等于最大流程时间。这种流水线调度问题要在满足以下两个 约束条件的前提下，使得加工完所有的工件所花的时间尽可能地少：1、工件约束每个工件在每台机器上恰好加工一次，每个工件在各机器上加工顺序相同。不失一般性，假设各工件按机器1至m的顺序进行加工。各工件在各机器上的加工时间已知。2、机器约束每台机器在任何时刻至多加工一个工件，每台机器加工的各工
9、件的顺序相同。置换流水线调度问题实质是如何调整加工工件的序列，提高机器的利用率的 问题，即在同一时刻正在加工的机攫数越多，机器利用率越大口根据该原则，我 们根据下面规则安排工件的加工顺序：(1) 在前面机器加工时间较短、后面机器加工时间较长的工件，安排在序列前。 这样可以使得后面的机器尽快参加工作，并且后面的机器不需要作空等待，(2) 机器加工时间较为平均且加工时间较长的工件，安排在序列的中部。这样 可以使得各个机器在中期的时候都能得到运作。(3前面加工时间较长，后面加一时间较短的上件女排在序列尾部。这样 使得前面的机器能“延迟”完工，后面的机器尽快完工。(二)利用Matlab软件对上面的案例
10、进行求解，编程如下：软件输出相应的结果，如下：clc; clear all;temp= 0 456 1 856 2 963 3 6960 789 1 930 2 21 3 3200 630 1 214 2 475 3 1420 214 1 257 2 320 3 7530 573 1 896 2 124 3 2140 218 1 532 2 752 3 5280 653 1 142 2 147 3 6530 214 1 547 2 532 3 2140 204 1 865 2 145 3 5270 785 1 321 2 763 3 5360 696 1 124 2 214 3 2140 53
11、2 1 12 2 257 3 5280 12 1 345 2 854 3 8880 457 1 678 2 123 3 999;%n为工件数，m为机器数%所有m-1个两台虚拟机器问题的加工时间矩阵%所有m-1个两台虚拟机器问题的总完工时间%存放m-1个加工顺序T=temp(:,2:2:end);n,m=size(T);txm=;Cmax=;TXY=;ticfor i=1:m-1for j=1:ntx(j,1)=sum(T(j,1:i);tx(j,2)=sum(T(j,m+1-i:m);endcmax,xy=johnson(tx,T,n,m);Cmax = Cmax,cmax;txm=txm,t
12、x;TXY=TXY,xy;endtxm, Cmax, TXYoptim=min(Cmax)ind=find(Cmax =optim);optim_seq=TXY(:,ind)rumTime=tocMatlab 运行：txm =456696%第一台虚拟机器上的加工时间%第二台虚拟机器上的加工时间%调用Johnson算法函数%近似最优总完工时间%近似最优加工顺序131216592275（三）绘制甘特图编程如下：% 已矢口 nbjobs, nbmachines, P%通过computeCmax计算完工时间矩阵，然后画甘特图temp= 0 456 1 856 2 963 3 6960 789 1 93
13、0 2 21 3 3200 630 1 214 2 475 3 1420 214 1 257 2 320 3 7530 573 1 896 2 124 3 2140 218 1 532 2 752 3 5280 653 1 142 2 147 3 6530 214 1 547 2 532 3 2140 204 1 865 2 145 3 5270 785 1 321 2 763 3 5360 696 1 124 2 214 3 2140 532 1 12 2 257 3 5280 12 1 345 2 854 3 8880 457 1 678 2 123 3 999;P=temp(:,2:2:
14、end);nbjobs=14;nbmachines=4;%给定工件的加工顺序，计算完工时间，进而求makespanjobOrder= 1341267101148931125;C=zeros(nbjobs,nbmachines); %完工时间矩阵%第一道工序，工件的完工时间C(jobOrder(1),1)=P(jobOrder(1),1); % 第一个工件的完工时间for i=2:nbjobs% 在加工顺序里面的位%第一道工序上，上一个工件加工完下一个工件才可以加工end%C(jobOrder(i),1)=C(jobOrder(i-1),1)+P(jobOrder(i),1);其余工序，工件的完工时间for j=2:nbmachinesC(jobOrder(1),j)=C(jobOrder(1),j-1)+P(jobOrder(1),j);for i=2:nbjobs%在上道工序加工完，且前一个工件加工完，才可以加工C(jobOrder(i),j)=max(C(jobOrder(i),j-1),C(jobOrder(i-1),j)+P(jobOrder(i),
