物流运筹实务课程设计题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解目录一、 前言……………………………………………………………………… 5二、 问题描述………………………………………………………………… 6三、 算法设计………………………………………………………………… 7四、 实验成果……………………………………………………………… 15摘要自从Johnson 1954年刊登第一篇有关流水车间调度问题的文章以来．流水车间调度问题引起了许多学者的关注安排合理有效的生产调度是生产活动能井然有序开展，生产资源得到最佳配备，运作过程简要流畅的有力保证流水车间调度问题是许多实际流水线生产调度问题的简化模型它无论是在离散制造工业还是在流程工业中都具有广泛的应用因此，对进行研究具有重要的理论意义和工程价值流水线调度问题中一种非常典型的问题，而置换流水线调度问题作为FSP问题的子问题，是一种出名的组合优化问题该问题是一种典型的NP难问题，也是生产管理的核心内容随着生产规模的扩大，流水线调度问题的优化对提高资源运用率的作用越来越大，因此对其研究具有重要的理论和现实意义。
核心字：流水车间，单件小批量生产，jsp模型，Matlab前言公司资源的合理配备和优化运用很大限度上体目前车间一层的生产活动中,因此加强车间层的生产筹划与控制始终在公司生产经营活动中占有十分重要的地位车间 生产筹划与控制的核心理论是调度理论车间调度问题是一类重要的组合优化问题为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率因此,研究成组技术下车间调度问题是很有必要的生产调度，即对生产过程进行作业筹划，是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心置换流水车间调度问题是许多实际生产调度问题的简化模型生产筹划与调度直接关系着公司的产出效率和生产成本，有效的筹划与调度算法能最大限度地提高公司的效益调度问题是组合优化问题，属于NP问题，难以用常规力一法求解随着制造业的迅速发展，大规模定制生产、全球化制造等思想的提出，使车间调度问题呈现出如下的新特点:约束条件多，时间复杂度高，空问复杂度高这将导致在许多状况下，求解所建立的数学模型的迅速性无法满足，如果采用适度线形化解决之后求解，将会因简化太多而使成果严承失真。
因此需选择功能强大的数值计算工具来实现这一问题的求解MATLAB正好提供了这样的平台MATLAB是一种高度集成的系统，集科学计算、图像解决、声音解决于一体，具有极高的编程效率典型JSP模型分析与Matlab的应用结合使流水车间调度问题迎刃而解最大竣工时间是生产调度中最常用的性能度量指标之一，最大竣工时间越短，则阐明产品总的生产周期越短，生产能力越大；此类调度问题的优化研究有助于提高公司的生产效率与资源运用率一、问题描述流水车间调度问题一般可以描述为个工件要在台机器上加工，每个工件有道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序都相似，问题的目的是拟定每台机器上工件的加工顺序及动工时间，使得特定的性能指标最优置换流水车间调度问题PFSP是对流水车间调度问题的进一步约束，即商定每台机器上所有工件的加工顺序相似，其解空间的规模为，远远不不小于流水车间调度问题的规模本次课程实验重要研究PFSP中的最小化最大竣工时间问题，运用三元组表达法（）求解Carlier (1978)提出的8个算例、以及Reeves (1995)提出的21个算由于三台机器以上的调度问题被证明是NP难问题，对于大规模的调度，至今仍未浮现求解最优的措施，常常采用启发式算法来求解近优解。
本案例重要采用instance car2进行求解案例：某产品，需要通过4道工序对13个工件进行加工，这13个工件的生产流程是同样的加工时间表见下：表4-3 某产品加工时间表工件号加工时间12345678910111213tj178963021457321865821420778569653212457tj293021425789653214254786532112412345678tj321475320124752147532145763214257854123tj4320142753214528653514527536214528888999计算环节如下：一方面拟定n/m/F/Cmax的最大竣工时间为： k=2,...,m i=2,...,n 则 Cmax=二、算法设计(一)假设工件在机器上的加工顺序是相似的，同步假定各工件准备就绪，机器一开动就投入生产，动工时间为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 696 0 789 1 930 2 21 3 320 0 630 1 214 2 475 3 142 0 214 1 257 2 320 3 753 0 573 1 896 2 124 3 214 0 218 1 532 2 752 3 528 0 653 1 142 2 147 3 653 0 214 1 547 2 532 3 214 0 204 1 865 2 145 3 527 0 785 1 321 2 763 3 536 0 696 1 124 2 214 3 214 0 532 1 12 2 257 3 528 0 12 1 345 2 854 3 888 0 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-1 for j=1:n tx(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 2515 789 320 1719 341 1740 1271 630 142 844 617 1319 831 214 753 471 1073 791 1330 573 214 1469 338 1593 1234 218 528 750 1280 1502 1812 653 653 795 800 942 942 214 214 761 746 1293 1293 204 527 1069 672 1214 1537 785 536 1106 1299 1869 1620 696 214 820 428 1034 552 532 528 544 785 801 797 12 888 357 。