置换流水车间调度问题的MATLAB求解（精编版）.docx

物流运筹实务课程设计题目：置换流水车间调度问题的 MATLAB 求解置换流水车间调度问题的 MATLAB求解第 1 页 共 32 页目 录一 、 前言 5二 、 问 题 描述 6三 、 算 法 设计 7四 、 实 验 结果 15第 2 页 共 32 页摘 要自从 Johnson 1954年发表第一篇关于流水 车间调 度问题的文章以来．流水车间调 度问题引起了许多学者的关注安排合理有效的生 产调度是生产活动能井然有序开展，生 产资源得到最佳配置，运作 过程简明流畅的有力保 证流水车间调 度问题是许多实际流水线生产调度问题的简化模型它无论是在离散制造工 业还是在流程工 业中都具有广泛的应用因此，对进 行研究具有重要的理 论意义和工程价 值流水线调度问题中一个非常典型的 问题，而置换流水 线调度问题作为 FSP 问题的子问题，是一个著名的组合优化问题 该问题 是一个典型的 NP 难问题，也是生产管理的核心内容随着生 产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此 对其研究具有重要的第 3 页 共 32 页理论和现实意义关 键 字 ：流水车间 ，单件小批量生 产，jsp 模型，Matlab前言企业资源的合理配置和 优化利用很大程度上体 现在车间一层的生产活动中,所以加强车间层 的生产计划与控制一直在企 业生产经营活动中占有十分重要的地位。

车间 生产计划与控制的核心理 论是调度理论车间调 度问题是一类重要的 组合优化问题为适应订货 式、多品种、小批量生 产的需要,引进了置换流水车间调 度概念在置换流水车间调度优化后,可以避免或大大减少流程工作 时间、提高生产效率因此,研究成组技术下车间调度问题是很有必要的生产调度，即对生产过程进行作业计划，是整个个先进生产制造系 统实现管理技 术、优化技术、白动化与计算机技 术发展的核心置换流水车间调 度问题是许多实际生产调度问题的简化模型生产计划与调度直接关系着企 业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企 业的效益调度问题是组合优化问题，属于 NP 问题 ，难以用常 规力一法求解随着制造业的快速 发展，大规模定制生 产、全球化制造等思想的提出，使 车间调度问题 呈现出以下的新特点 :约束条件多， 时间复杂度高，空问复杂度高这将导致在 许多情况下，求解所建立的数学模型的快速性无法 满第 4 页 共 32 页足，如果采用适度 线形化处理之后求解，将会因 简化太多而使 结果严承失真所以需 选择功能 强大的数 值计算工具来 实现这 一问题的求解MATLAB 恰好提供了 这样的平台。

MATLAB 是一个高度集成的系 统， 集科学 计算、图像处理、声音处理于一体，具有极高的 编程效率典型JSP模型分析与 Matlab 的应用结合使流水 车间调 度问题迎刃而解最大完工 时间是生产调度中最常用的性能度量指 标之一，最大完工 时间越短，则说 明产品总的生产周期越短，生产能力越大；此类调度问题的优化研究有助于提高企 业的生产效率与资源利用率一、问题描述流水车间调 度问题通常可以描述 为n 个工件要在 m 台机器上加工，每个工件有 m 道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序都相同， 问题的目标是确定每台机器上工件的加工 顺序及开工时间，使得特定的性能指 标最优置换流水车间调 度问题 PFSP是对流水车间调 度问题的进一步约束，即约定每台机器上所有工件的加工顺序相同，其解空 间的规模为n! ，远远 小于流水 车间调 度问题的规模(n!) m 本次课程实验主要研究 PFSP中的最小化最大完工 时间问题 ，利用prmu三元组表示法（ FCmax）求解Carlier (1978)提出的 8 个算例、以及Reeves (1995)提出的 21 个算由于三台机器以上的 调度问题被证明是第 5 页 共 32 页NP 难问题 ，对于大 规模的调度，至今仍未出 现求解最 优的方法，常常采用启发式算法来求解近 优解。

本案例主要采用 instance car2进行求解案例：某产品，需要经过 4 道工序对 13 个工件进行加工，这 13 个工件的生产流程是一 样的加工时间表见下：表 4-3 某产品加工时间表工1234567891111加0123t7625262276514j18930147318581407859632257t9228515831136j23014579632424765212424578t2431715172281j31752024524732456314575423t3172565552589j420425314285314273614288899计算步骤如下：首先确定 n/m/F/Cmax 的最大完工 时间为：c( j 1 ,1)t j ,11c ( j1 , i )c( j1 , k 1)1t j kk=2,...,mc ( j 1 ,1)c( j i1 ,1)t j 1i=2,...,nic ( ji , k )max{c ( j i1 , k ); c (j i , k1)}t j i k第 6 页 共 32 页则 Cmax= c(j n , m)二、算法设计(一)假设工件在机器上的加工 顺序是相同的，同 时假定各工件准 备就绪，机器一开动就投入生 产，开工时间为 0，则最大完工 时间等于最大流程时间。

同时 3 台机器以上的流水 车间调 度是 NP 难问题，所以本文只考虑了 2 台、3 台机器的情况，解决 3 台机器以上的 问题方法也可运用人工智能算法，解的 质量更高，但因该类算法需良好的 软件编程能力， 故本文不加探究 n 个工件在 m 台机器上的加工 顺序相同工件在机器上的加工 时间是给定的问题 的目标是求 n 个工件在每合机器上的最大完工 时间等于最大流程 时间 这种流水 线调度问题要在满足以下两个约束条件的前提下，使得加工完所有的工件所花的 时间尽可能地少：1、工件约束每个工件在每台机器上恰好加工一次，每个工件在各机器上加工顺序相同不失一般性，假设各工件按机器 1 至 m 的顺序进行加工各工件在各机器上的加工 时间已知2、机器约束第 7 页 共 32 页每台机器在任何 时刻至多加工一个工件，每台机器加工的各工件的顺序相同置换流水 线调度问题实质 是如何 调整加工工件的序列，提高机器的利用率的 问题，即在同一时刻正在加工的机攫数越多，机器利用率越大口根据 该原则，我们根据下面 规则安排工件的加工 顺序:(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 142第 8 页 共 32 页0 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 个加工顺序第 9 页 共 32 页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];。