《【国家级精品课程】中南大学数学建模lingomatlab优化建模数模培训全国赛论文企业生产规模和调度的数量分析研究.doc》由会员分享，可在线阅读，更多相关《【国家级精品课程】中南大学数学建模lingomatlab优化建模数模培训全国赛论文企业生产规模和调度的数量分析研究.doc（15页珍藏版）》请在三一办公上搜索。
1、企业生产规模和调度的数量分析研究摘要本文分别在不同条件下讨论了怎样对企业的资源进行合理安排和调度，使该企业的生产过程达到最小规模和合理的周期。在问题一中，要达到无资源浪费、连续均衡生产，由于同类资源在生产中不可以通用，所以整个生产周期中没有闲置的设备和闲散人员，所有产品都在进行生产且在一个周期末时同时结束，且周期中所有设备和人员都一直在工作不停顿。要使所有中间产品和库存与上一周期结束时的库存相同，而单位成品所需各种中间产品的数量有确定的比例关系，则需要合理分配投入到各种产品生产中的人力、物力等多种资源，使中间产品以合适的比例进行生产，生产和消耗达到均衡，避免某种产品库存的空缺或积压。根据均衡生
2、产中的中间产品的消耗等于产出原则，得出生产规模为，周期T30小时，库存。问题二，同类资源在生产中可以通用，即同一资源可以用于多种产品的生产，同一批资源（人力、设备）在单位生产周期不同时间段可以从事不同产品的生产。在保证产品按比例、均衡生产的前提下，对各种资源进行合理搭配，可以大大减小生产规模。由于既不能通过增加工人和设备来缩短时间，也不能通过加长时间而节省工人和设备，故生产1个单位A0所需的各资源总劳动量W保持不变。故周期T越大，生产规模R越小；周期T越小，生产规模R越大，则取W各分量的最大公约数48作为生产周期，即T48小时，此时最小的生产规模为： 然后在一个确定的资源使用量R 下，用搜索的
3、方法求出A*Xt=R的所有解，这些解构成X(t)的状态集合XS。最后由各个状态准备中间产品的持续时间等于各中间产品的总加工工时和线性代数知识得出，若不考虑库存，有120种无差别的生产调度方案，但若要使库存量最小，则生产调度方案为： 问题三，在均衡生产、资源给定的条件下，要使资源浪费越少，则要求各资源的利用程度最高，这可用将生产规模R各分量无量纲化后相加构成的统一资源来衡量，越大，资源利用程度越高。然后根据均衡生产的约束条件用类似问题二的搜索法求出X(t)的状态集合，再根据生产过程X(t)，F(t)，S(t)的控制条件及使目标函数最大编程求出使浪费最小的生产规模和生产调度方案。 关键词：无资源浪
4、费、连续均衡生产、搜索法、状态集合、无量纲化 问题的重述图1是某企业的生产结构示意图，是出厂产品，是中间产品，而表示生产一个单位需要消耗单位。表1给出了生产单位产品所需的资源（工人，设备）和时间，注意表中所给数据是最基本的，即既不能通过增加工人和设备来缩短时间，也不能通过加长时间而节省工人和设备。问题一：无资源浪费、连续均衡生产的最小生产规模是多大？相应的最短周期是多少？其中“无资源浪费”指在整个生产周期中没有闲置的设备和闲散人员。“连续”指整个周期中所有产品生产过程不会停顿。“均衡”指所有中间产品的库存与上一周期结束时的库存相同。“生产规模”是指完成整个生产过程所需各资源的总和。问题二：如果
5、考虑相同的资源可以通用，那么问题一得到的最小生产规模在无资源浪费、均衡生产中能否减少。请写出你得到的生产规模，相应的周期和生产过程调度方案。问题三：如果该企业的资源限制为：类工人120名，类工人80名，技术人员25名，甲种设备8台，乙种设备10台，及周期限制（一星期，共小时），请你做出生产过程的调度方案，使在均衡生产条件下资源的浪费最小。图1 生产结构示意图表1 生产单位产品所需资源和时间产品A0A1A2A3A4A5A6需要的资源类工人71273437183317类工人30181713122823技术人员79076511甲种设备(台)4304202乙种设备(台)1310256加工时间(小时)6
6、365212问题的分析问题的总括：在实际生产中，资源的合理安排和调度将使生产过程达到最优，所以这是一道最优化的问题。问题的目标：1、在资源不能通用的情况下寻找无资源浪费、连续均衡生产的最小规模；2、资源可以通用时的最小规模及调度方案；3、有资源限制时使资源的浪费最小，及利用率最高。问题的关键与难点：在本问题中，“无资源浪费”指在整个生产周期中没有闲置的设备和闲散人员。“连续”指整个周期中所有产品的生产过程不会停顿。“均衡”指所有中间产品的库存与上一周期结束时的库存相同，即在一个周期中，所有中间产品的生产和消耗相等。在问题一中，要达到无资源浪费、连续均衡生产，由于同类资源在生产中不可以通用，所以
7、整个生产周期中没有闲置的设备和闲散人员，所有产品都在进行生产且在一个周期末时同时结束，且周期中所有设备和人员都一直在工作不停顿。要使所有中间产品和库存与上一周期结束时的库存相同，而单位成品所需各种中间产品的数量有确定的比例关系，则需要合理分配投入到各种产品生产中的人力、物力等多种资源，使中间产品以合适的比例进行生产，生产和消耗达到均衡，避免某种产品库存的空缺或积压。对于问题二，同类资源在生产中可以通用，即同一资源可以用于多种产品的生产，同一批资源（人力、设备）在单位生产周期不同时间段可以从事不同产品的生产。在保证产品按比例、均衡生产的前提下，对各种资源进行合理搭配，可以大大减小生产规模。对于问
8、题三，由于存在客观限制，能提供的资源是给定的，周期也一定。这种情况下，在该确定周期下生产的产品越多，将使资源浪费越少。为求解方便，可将各资源规模无量纲化变成统一指标以比较其优劣。基本假设1、所有资源和工序在生产过程中一切正常，不考虑偶然事故的发生。2、所有的中间产品在资源满足的条件下都能转化成下一步生产的产品。3、生产的每种产品都有足够用以保证下一步生产顺利进行的库存量。这样，各种工序可以独立进行，不需要等待前级中间产品的完成。4、设备、人员的调度消耗的时间不记在生产过程中。5、每个工人都可以生产其中的任何产品，但工人之间的调度只能在同类人员中调度，如类工人只能在类工人工人之间进行调度。6、同
9、一种工序可以同时开工，资源消耗等没有差异。7、生产是均衡的，产品的生产按下一步生产的要求成比例进行，一个周期结束时各种产品的库存与上一周期相同。基本符号和术语约定：生产周期；：时间限制。A：，其中表示第j 种工序所需的第i 种资源的数量。 ：，其中 表示生产一个最终产品所需第j 种工序的总加工工时。：一个周期内生产最终产品的数目。：，其中， 表示生产一个成品所需第j 种工序的数量。：，其中 表示生产单位成品（包括最终产品和相应中间产品）所需第i种资源的总工时（台时或人时）。：，其中 表示生产单位成品所需第j 种工序的总加工时间。：资源限制，其中 表示在整个生产过程中第i 种资源的最大允许使用量
10、。：，其中表示进行第j种工序加工的生产线数目。x(t)：,其中表示时刻t 正在进行的第j 种工序的数目。S(t)：，其中表示时刻t 新开工的第j 种工序的数目。F(t)：，其中表示时刻t 结束的第j 种工序。K：，其中表示第i个中间产品的库存数。R：，其中表示第i种资源的规模。模型的建立和求解1 连续均衡无资源浪费的生产由题知，“无资源浪费”意味着每时每刻所有的生产规模都完全投入使用，没有人员和设备的闲置；“连续生产”指在同类资源不能通用时，同一批人员和设备在一个生产周期内始终从事同一产品生产，即周期内的每一时刻,正在进行生产的第种产品的数目不变，也即状态不变；“均衡生产”是使所有中间产品 和
11、库存与上一周期结束时的库存相同，需要合理分配投入到各种产品生产中的人力、物力等多种资源，使中间产品以合适的比例进行生产，从而它们的生产和消耗达到均衡，而不导致产品库存发生变化，而单位成品所需各种中间产品的数量有确定的比例关系，生产规模也须确定并唯一，否则就会有资源浪费，生产不连续或者不能达到均衡。单位周期内生产的各种中间产品数为: (1.1)根据“均衡生产”的中间产品的生产等于其消耗得： (1.2)由公式（1.1）和(1.2)得: (1.3)即 由生产结构示意图：分析出：生产1单位需要各中间产品数为。而6个小时就可生产1单位，各个中间产品的生产能保证生产单位所需中间产品的供应量，且每个单位的生
12、产过程都一样，则由公式（1.3）算出第i个中间产品有个生产线在生产，计算结果如下表：产品1456151212636521261230303012241255524对来说，5条生产线6个小时只能生产5个中间产品，因为每条生产线6个小时只生产1个成品和1个半成品。而在生产周期末，所需中间产品都应被生产完，也被消耗完，只有成品。故生产最短周期为，的最小公倍数，即小时才能使周期末时正好使全为成品，此时可以生产5个单位的，唯一的所求生产规模为：各中间产品的库存数只须在周期开始时保证它们的下一级产品同时开始生产即可，可取为生产单位所需中间产品数，且在周期末时各中间产品仍能保持这样的库存数：2 通用资源的均
13、衡无资源浪费生产2.1最小生产规模的确定在问题2中同类资源在生产中可以通用，即同一资源可以用于多种产品的生产，同一批资源（人力、设备）在单位生产周期不同时间段可以从事不同产品的生产。在保证产品按比例、均衡生产的前提下，对各种资源进行合理搭配，可以大大减小生产规模。由于既不能通过增加工人和设备来缩短时间，也不能通过加长时间而节省工人和设备，故生产1个单位A0所需的各资源总劳动量W保持不变，且由问题1求出为：而由“无资源浪费”得没有人员和设备的闲置，即所有人和设备的生产都贯穿了一个周期，则：故由W不变得知，周期T越大，生产规模R越小；周期T越小，生产规模R越大。而题目要求最小的生产规模，故需最大的
14、生产周期T，而R中各分量都为整数，所以可取W各分量的最大公约数48作为生产周期，即T48小时，此时最小的生产规模为：2.2生产过程的调度1、生产过程的描述：时刻进行的工序为，在时刻时结束的工序为，由工序不可打断，时刻将继续进行时刻未完成的工序为 ，因此下一时刻进行的各种工序的数目将不小于前一时刻未完成的工序数目，即有： （2.1）(其中“”为前者各分量都不小于后者，下同)时刻新开工的工序为： （2.2）时刻t 结束的第j 种工序必在时刻 开始，故有： （2.3）其中，。任何一种可能的生产过程都有唯一对应的X(t)，F(t)，S(t)函数，且X(t)，F(t)和S(t)满足上述三个公式。而满足上
15、述三个基本公式的X(t)，F(t)和S(t)则对应一种可能存在的生产过程。而且，由（公式2.2）、（公式2.3），可根据X(t)确定唯一的S(t)和F(t)。可见，构造出合理的X(t)，t0，T），确定F(t)，S(t)后，则可代表一个生产过程，即为一种合理的调度方案。2、X(t)的确定：在一个确定的资源使用量R 下，由于AX(t)=R，X(t)各分量为非负整数，故可用搜索的方法求出此整数方程的所有解为：，这个整数方程的解集即为状态集，任一时刻的都是状态集XS 中的元素。在周期T中，设各个状态持续的时间为，则由各个状态准备中间产品的持续时间等于各中间产品的总加工工时得：（记，） （2.4）而，
16、是列满秩的，的各列向量线性无关，故这5种状态都为生产调度中的状态，即整个生产周期中都会出现的状态，且t只有一个解。由生产结构图易得：求解线性方程组（2.4）得各个状态持续的时间为：3、生产过程的调度：根据均衡生产中的中间产品的产出等于消耗知，一个周期内生产成品所需的中间产品的消耗量等于这个周期的生产量，所有中间产品的库存与上一周期结束时的库存相同，即使在生产过程中中间产品的库存有消耗，它们也会通过后续生产加以补足以达到均衡。所以，只要有足够的库存量，可不分先后次序，共有种生产次序或者说生产调度，因为它们到周期末时都能生产出成品，且生产出来的中间产品都被生产成品消耗完，即各自库存量不变，只是这些
17、生产次序所需的库存量不同，靠近最终产品的中间产品如越先生产，则需要的中间产品的库存量大，而远离最终产品的中间产品如越先生产，则需要的中间产品的库存量小。一般说来，所需的中间产品的库存量越小的生产调度方案越好，故可根据中间产品的级别以及其所需加工时间易选定：为最优生产调度方案。3 有资源限制的均衡浪费最小生产3.1 约束条件题意要求在给定资源的情况下，在指定的时间内调整生产使得在均衡生产的条件下资源的浪费最小。因为资源给定，一定时间内的全部劳动量也一定：，而生产n个所需的劳动量也是定值：。所以在均衡生产条件下，资源浪费量就是，只与n有关，即生产的 数越多，资源浪费越少，而与生产如何安排等因素无关
18、。因此问题转化为在给定的时间内，在均衡生产、资源给定的条件下，最多可以生产多少个。由此得到此问题对模型的约束如下： （3.1）3.2 状态集合求解在满足第一个约束条件的情况下，通过搜索的方法，求得使各分量为非负的整数，利用问题二的结果可以减少搜索的范围。利用所附的程序，可以迅速求解此不等式（见附程序）。解的结果是此不等式共有80个不同的解（包含一个全零解）。这个不等式的解集即为状态集XS，任一时刻的X(t)都是状态集XS 中的元素。3.3 估计n的上限由于资源浪费量只与n有关，因此有必要估计出n的上限。要用所给的资源能在内生产最多的，资源所提供的劳动量要大于等于产品所需的劳动量。因此，可以简单
19、地用生产一个 所需的各种资源的劳动量去除内相应资源的劳动量，可以得到（用“/”表示两个向量中各分量相比）：于是，只考虑劳动量的情况下，在时间内最多生产的数量为3个单位。3.4 资源利用程度的衡量及统一资源函数由于存在资源的浪费，不同的状态对资源的利用程度是不一样的，而资源是用一个5维的向量来表示，由于向量无法简单地对整体上的“大小”作衡量，因此我们使用的各分量的线性组合来表示，称之为统一资源（Uniform Resource）：其中是第i种资源的限制。引入函数将对求解过程有以下的帮助：1. 可对集中的的优劣进行排序，令，则可以表示对资源的利用程度，其值越大表示对资源利用越充分。利用这一点，可以
20、对求解中的搜索过程进行优化。2. 可以预先去掉一些无效的序列，求出了中的，可求出每个状态每小时至少要浪费的的量。同时，由于时间中的资源总量的值，以及生产n个所需的资源量的值都可求得。因此，可得到整个 中资源的最大浪费量，而如果一个序列在到t 时刻时的资源浪费量已经超过了当前允许的最大浪费量（还要考虑余下的时间中至少需要浪费的资源浪费量），那么就可以确定此序列是无效的。3.5 调度方案的求解一个周期中开工或结束的各种工序的和，在周期结束时都等价得到所生产的各种产品的个数，即有： （3.2）此式保证了均衡生产，且在一个周期里生产出n 个成品。在一个周期内投入各个产品的总生产时间，与最终产品中蕴含的
21、各种工序的时间有如下关系： （3.3）时刻t 生产的产品不得多于还需要生产的产品数。由此，可以推导出： （3.4）根据3.4求得的X序列依据公式（3.2）、（3.3）、（3.4）利用搜索法求出生产调度方案。由于水平有限，还未编出搜索程序求解。模型的评价和推广一、 优点：模型具有良好的通用性，原则上对于所有多资源、多工序，工序间无次序性的生产调度问题都是适用的。通过将生产调度问题抽象为对一个状态序列X(t)的求解，而X(t)则属于一个特定的状态集合XS，可以说对这一类问题给出一个通用的解决方法。对于某个具体的问题，只要求出XS（状态集合）及资源限制，对我们的程序作一定的修改即可求解。本模型将调度
22、方案转化为生产状态序列的求解，通过对相对较小的所有可能状态的集合的求解，使得问题的规模大大缩小。题目定义的最小规模为完成整个生产过程所需各资源的总和，在模型中我们没有使用，而是另外定义了最小规模，是因为考虑到这种资源的总和没有任何意义，与实际情况也不吻合。另外，在问题3 的求解中，我们提出的统一资源函数的概念，用一个可衡量大小的量来反映对多种资源的综合利用、浪费水平，使得对某个状态的优劣判定以及搜索过程中及早去掉无效序列成为可能。这也是有通用意义的。二、缺点：模型的主要缺点是对调度问题没有编出程序来求解其过程，并且对问题解的有无、状态转化等没有作进一步的数学上的讨论，比较依赖于计算机的计算能力
23、。三、改进：进一步的改进可以有如下方面：考虑库存的因素，即如何调度生产，使得可在个中间产品库存最小的情况下完成生产，这也是对生产实际很重要的问题。参考文献1 姜启源等，数学模型,北京，高等教育出版社，2003.82 李丽等，MATLAB工程计算及应用，北京，人民邮电出版社，2001.83 薛定宇等，高等应用数学问题的MATLAB求解，北京，清华大学出版社，20044 吴期明等，均衡生产的调度问题5 王小川等，多资源多工序的生产调度模型附录附录一：问题1：（matlab程序）A =71 27 34 37 18 33 17; 30 18 17 13 12 28 23; 7 9 0 7 6 5 11
24、; 4 3 0 4 2 0 2; 1 3 1 0 2 5 6;n=6 12 30 30 30 12 24;M=1 4 5 6 15 12 12;W=A*n;dmax=0;q=0;0;0;0;0;for d=2:288 Q=0; for i=1:5 q(i)=mod(W(i),d); Q=Q+q(i); end if Q=0 dmax=d; endend %求最大公约数x=0;0;0;0;0;0;0;p=0;0;0;0;0;kmin=0;for k=48:-1:2 P=0; for i=1:5 p(i)=mod(n(i)*k,48); P=P+p(i); end if P=0 kmin=k; e
25、ndend %求满足条件的最小k值for i=1:7 x(i)=n(i)*kmin/48; end %求整个周期内都正常生产的所有工序的数目xR=A*x %求最小规模问题2：（matlab程序）搜索可行解A =71 27 34 37 18 33 17; 30 18 17 13 12 28 23; 7 9 0 7 6 5 11; 4 3 0 4 2 0 2; 1 3 1 0 2 5 6;R=88;53;18;6;7;C=A R;rank(A),rank(C)Z=null(A,r) %求解矩阵A的化零矩阵的规范形式for t1=-10:10 for t2=-10:10 for t3=-10:10
26、for t4=-10:10 X=t1*Z(:,1)+t2*Z(:,2)+t3*Z(:,3)+t4*Z(:,4)+0 0 1 1 0 0 1;%其中0 0 1 1 0 0 1是使用lingo软件得出的一个整数特解 E=(A*X=R); if (E=ones(5,1)&(X(1)=0&X(1)=round(X(1)&(X(2)=0&X(2)=round(X(2)&(X(3)=0&X(3)=round(X(3). &(X(4)=0&X(4)=round(X(4)&(X(5)=0&X(5)=round(X(5)&(X(6)=0&X(6)=round(X(6)&(X(7)=0&X(7)=round(X(
27、7) X end end end endend求解线性方程组的特解（lingo程序）：model:sets:p1/1.7/:a1,a2,a3,a4,a5,x;p2/1.5/:r;endsetsdata:a1=71 27 34 37 18 33 17;a2=30 18 17 13 12 28 23;a3=7 9 0 7 6 5 11;a4=4 3 0 4 2 0 2;a5=1 3 1 0 2 5 6;r=88 53 18 6 7;enddatasum(p1(i):a1(i)*x(i)=r(1);sum(p1(i):a2(i)*x(i)=r(2);sum(p1(i):a3(i)*x(i)=r(3)
28、;sum(p1(i):a4(i)*x(i)=r(4);sum(p1(i):a5(i)*x(i)=r(5);bin(x(1);bin(x(2);bin(x(3);bin(x(4);bin(x(5);bin(x(6);bin(x(7);end问题3：（matlab程序）搜索所有可行方案A =71 27 34 37 18 33 17; 30 18 17 13 12 28 23; 7 9 0 7 6 5 11; 4 3 0 4 2 0 2; 1 3 1 0 2 5 6;R=120 80 25 8 10;C=A R;rank(A),rank(C)for t1=0:1 for t2=0:4 for t3=
29、0:5 for t4=0:5 for t5=0:10 for t6=0:10 for t7=0:10 X=t1 t2 t3 t4 t5 t6 t7; F=R-A*X; E=(F=0); if (E=ones(5,1)&(X(1)=0&X(1)=round(X(1)&(X(2)=0&X(2)=round(X(2)&(X(3)=0&X(3)=round(X(3). &(X(4)=0&X(4)=round(X(4)&(X(5)=0&X(5)=round(X(5)&(X(6)=0&X(6)=round(X(6)&(X(7)=0&X(7)=round(X(7) X end end end end end end endend
