物流运筹实务课程设计题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解目录一、前言 (5)二、问题描述 (6)三、算法设计 (7)四、实验结果 (15)摘要自从Johnson 1954年发表第一篇关于流水车间调度问题的文章以来．流水车间调度问题引起了许多学者的关注。
安排合理有效的生产调度是生产活动能井然有序开展，生产资源得到最佳配置，运作过程简明流畅的有力保证。
流水车间调度问题是许多实际流水线生产调度问题的简化模型。
它无论是在离散制造工业还是在流程工业中都具有广泛的应用。
因此，对进行研究具有重要的理论意义和工程价值。
流水线调度问题中一个非常典型的问题，而置换流水线调度问题作为FSP问题的子问题，是一个著名的组合优化问题。
该问题是一个典型的NP难问题，也是生产管理的核心内容。
随着生产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此对其研究具有重要的理论和现实意义。
关键字：流水车间，单件小批量生产，jsp模型，Matlab前言企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中,所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。
车间生产计划与控制的核心理论是调度理论。
车间调度问题是一类重要的组合优化问题。
为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念。
在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率。
因此,研究成组技术下车间调度问题是很有必要的。
生产调度，即对生产过程进行作业计划，是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心。
置换流水车间调度问题是许多实际生产调度问题的简化模型。
生产计划与调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。
调度问题是组合优化问题，属于NP问题，难以用常规力一法求解。
随着制造业的快速发展，大规模定制生产、全球化制造等思想的提出，使车间调度问题呈现出以下的新特点:约束条件多，时间复杂度高，空问复杂度高。
这将导致在许多情况下，求解所建立的数学模型的快速性无法满足，如果采用适度线形化处理之后求解，将会因简化太多而使结果严承失真。
所以需选择功能强大的数值计算工具来实现这一问题的求解。
MATLAB恰好提供了这样的平台。
MATLAB是一个高度集成的系统，集科学计算、图像处理、声音处理于一体，具有极高的编程效率。
典型JSP模型分析与Matlab的应用结合使流水车间调度问题迎刃而解。
最大完工时间是生产调度中最常用的性能度量指标之一，最大完工时间越短，则说明产品总的生产周期越短，生产能力越大；此类调度问题的优化研究有助于提高企业的生产效率与资源利用率。
一、问题描述n m流水车间调度问题通常可以描述为个工件要在台机器上加工，m每个工件有道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序都相同，问题的目标是确定每台机器上工件的加工顺序及开工时间，使得特定的性能指标最优。
置换流水车间调度问题PFSP是对流水车间调度问题的进一步约束，即约定每台机器上所有工件的加工顺序相同，其解空间的规模为，远远小于流水车间调度问题的规模!n。
n(!)m本次课程实验主要研究PFSP中的最小化最大完工时间问题，利用F prmu C三元组表示法（）求解Carlier (1978)提出的8个算例、以及maxReeves (1995)提出的21个算。
由于三台机器以上的调度问题被证明是NP 难问题，对于大规模的调度，至今仍未出现求解最优的方法，常常采用启发式算法来求解近优解。
本案例主要采用instance car2进行求解。
案例：某产品，需要经过4道工序对13个工件进行加工，这13个工件的生产流程是一样的。
加工时间表见下：表4-3 某产品加工时间表12345678910111213tj178963021457321865821420778569653212457tj293021425789653214254786532112412345678tj321475320124752147532145763214257854123tj4320142753214528653514527536214528888999计算步骤如下：首先确定n/m/F/C max 的最大完工时间为：1,11)1,(c j t j = k=2,...,m k j t k j c i j c 1)1,(),(11+-=i=2,...,n111)1,(c )1,(c i j i t j j +=- kj i i i i t k j c k j k j +-=-)}1,();,(c max{),(c 1工加则 C max =),(c nm j 二、算法设计(一)假设工件在机器上的加工顺序是相同的，同时假定各工件准备就绪，机器一开动就投入生产，开工时间为0，则最大完工时间等于最大流程时间。
同时3台机器以上的流水车间调度是NP 难问题，所以本文只考虑了2台、3台机器的情况，解决3台机器以上的问题方法也可运用人工智能算法，解的质量更高，但因该类算法需良好的软件编程能力，故本文不加探究。
n 个工件在m 台机器上的加工顺序相同。
工件在机器上的加工时间是给定的。
问题的目标是求n 个工件在每合机器上的最大完工时间等于最大流程时间。
这种流水线调度问题要在满足以下两个约束条件的前提下，使得加工完所有的工件所花的时间尽可能地少：1、工件约束每个工件在每台机器上恰好加工一次，每个工件在各机器上加工顺序相同。
不失一般性，假设各工件按机器1至m 的顺序进行加工。
各工件在各机器上的加工时间已知。
2、机器约束每台机器在任何时刻至多加工一个工件，每台机器加工的各工件的顺序相同。
置换流水线调度问题实质是如何调整加工工件的序列，提高机器的利用率的问题，即在同一时刻正在加工的机攫数越多，机器利用率越大口根据该原则，我们根据下面规则安排工件的加工顺序:(l)在前面机器加工时间较短、后面机器加工时间较长的工件，安排在序列前。
这样可以使得后面的机器尽快参加工作，并且后面的机器不需要作空等待，(2)机器加工时间较为平均且加工时间较长的工件，安排在序列的中部。
这样可以使得各个机器在中期的时候都能得到运作。
(3〕前面加工时间较长，后面加一〔时间较短的上件女排在序列尾部。
这样使得前面的机器能“延迟”完工，后面的机器尽快完工。
（二）利用Matlab软件对上面的案例进行求解，编程如下:软件输出相应的结果，如下：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 532 1 12 2 257 3 5280 12 1 345 2 854 3 8880 457 1 678 2 123 3 999];T=temp(:,2:2:end);[n,m]=size(T); %n为工件数，m为机器数txm=[]; %所有m-1个两台虚拟机器问题的加工时间矩阵Cmax=[]; %所有m-1个两台虚拟机器问题的总完工时间TXY=[]; %存放m-1个加工顺序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)); %第二台虚拟机器上的加工时间end[cmax,xy]=johnson(tx,T,n,m); %调用Johnson 算法函数Cmax =[ Cmax,cmax];txm=[txm,tx];TXY=[TXY,xy];endtxm, Cmax, TXYoptim=min(Cmax) %近似最优总完工时间ind=find(Cmax ==optim);optim_seq=TXY(:,ind)' %近似最优加工顺序rumTime=tocMatlab运行：txm =456 696 1312 1659 2275 2515789 320 1719 341 1740 1271630 142 844 617 1319 831214 753 471 1073 791 1330573 214 1469 338 1593 1234218 528 750 1280 1502 1812653 653 795 800 942 942214 214 761 746 1293 1293204 527 1069 6721214 1537785 536 1106 1299 1869 1620696 214 820 428 1034 552532 528 544 785 801 79712 888 357 1742 1211 2087457 999 1135 1122 1258 1800Cmax =8679 8423 8667TXY =13 13 49 4 74 12 138 6 96 7 141 10 814 1 67 14 110 8 1012 9 22 3 55 11 311 2 123 5 11optim =8423optim_seq =13 4 12 6 7 10 1 14 8 9 3 11 2 5（三）绘制甘特图编程如下：% 已知nbjobs, nbmachines, P% 通过computeCmax计算完工时间矩阵，然后画甘特图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 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:end);nbjobs=14;nbmachines=4;% 给定工件的加工顺序，计算完工时间，进而求makespanjobOrder=[ 13 4 12 6 7 10 1 14 8 9 3 11 2 5];C=zeros(nbjobs,nbmachines); % 完工时间矩阵%% 第一道工序，工件的完工时间C(jobOrder(1),1)=P(jobOrder(1),1); % 第一个工件的完工时间for i=2:nbjobs % 在加工顺序里面的位置% 第一道工序上，上一个工件加工完下一个工件才可以加工C(jobOrder(i),1)=C(jobOrder(i-1),1)+P(jobOrder(i),1);end%% 其余工序，工件的完工时间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(jobOr der(i),j);endendCmax=max(C(:,nbmachines)); % Cmaxfigure_handle=figure;hold on;% Create titletitle(['置换流水车间调度甘特图（Cmax= ',num2str(Cmax),'）'],...'FontWeight','bold','FontSize',12);xlabel('时间');ymax=nbmachines+1;xmax=Cmax;axis([0 xmax 0 ymax]);%--------------------------------------------------------------------------YLabel=cell(ymax,1);y=ymax;for j=1:nbmachinesYLabel{y}=['M' int2str(j)];y=y-1;endset(gca,'Ygrid','on','YTickLabel',YLabel,'YTick',0:ymax);%%hi=0.7;nb=1; % machineyi=ymax-1;for j=1:nbmachinesfor i=1:nbjobsxi=C(jobOrder(i), j)-P(jobOrder(i),j);wi=P(jobOrder(i), j);rectangle('Position',[xi,yi,wi,hi]);text(xi+0.5*wi,yi+0.5*hi,int2str(jobOrder(i)),'HorizontalAlignment',...'center');endyi=yi-1;nb=nb+1;endyi=yi-1;hold off;三、实验结果1、根据上面matlab的求解得到以下实验结果：最优排序为13 4 12 6 7 10 1 14 8 9 3 11 25min(Cmax)= 84232、甘特图如下所示：四、流水线型车间作业调度问题遗传算法MATLAB源码流水线型车间作业调度问题可以描述如下：n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。