关于生产调度问题的数学模型

北京航空航天大学大学生数学建模选拔赛2013年6月14日6月16日参赛题目 A B（在所选题目上打勾） 参赛队队长参赛队员1参赛队员2姓名学号学院专业年级电话Email北京航空航天大学教务处数学建模指导组关于生产调度问题的数学模型【摘要】本文从“均衡生产”出发，得到了产品产量之间的固定比例以及各个产品的设备组数的比例，不固定生产规模时，把“无资源浪费”作为约束条件，由是否“连续生产”判定资源的调度问题，将资源按照不同生产过程中各产品的生产比例来调度分配。在“连续”生产的条件下我们把问题转化为了求生产时间最短的线性规划问题，从而解决了不同生产过程的最小生产规模以及最小生产周期问题；在考虑资源通用，失去“连续”条件下，在分析后提出的几种可能的最小生产规模中进行验证，找出满足均衡及无资源浪费的最小生产规模并计算其最小周期。其后，又针对公司给定的生产规模，我们将问题转化为了求使产品产量最高的线性规划问题，做出资源调度的几种不同方案，并计算比较安排了这些方案的最优组合，得出了产品产量高、资源浪费最小、生产周期短的最优方案。在解决问题的过程中，我们通过DEV C+软件编写c语言程序，结合MATLAB软件求解线性方程组，得出最优的生产调度方案。最后，我们针对理想的模型假设提出新的想法。考虑到实际生产中生产调度需要的时间、工人的必要休息所需要的时间，以及设备保养所需要的轮换等问题。这些问题所需要的时间必然会增大生产周期，我们希望能够制定合理的政策规划，保持较高的生产效率。【关键词】线性规划 资源调度 数学模型目录关于生产调度问题的数学模型21.问题描述42.基本假设53.符号定义54.建立模型解决问题54.1无资源浪费、连续均衡生产时的最小生产规模和最小生产周期54.2资源通用情况下的最优调度方案84.3给定生产规模下的最优调度方案95.模型改进116.参考文献111.问题描述图1是某企业的生产结构示意图，是出厂产品，是中间产品，而表示生产一个单位需要消耗单位。表1给出了生产单位产品所需的资源（工人，设备）和时间，注意表中所给数据是最基本的，即既不能通过增加工人和设备来缩短时间，也不能通过加长时间而节省工人和设备。问题一：无资源浪费、连续均衡生产的最小生产规模是多大？相应的最短周期是多少？ “无资源浪费”指在整个生产周期中没有闲置的设备和闲散人员。“连续”指整个周期中所有产品生产过程不会停顿。“均衡”指所有中间产品的库存与上一周期结束时的库存相同。图1 生产结构示意图“生产规模”是指完成整个生产过程所需各资源的总和。问题二：如果考虑相同的资源可以通用，那么问题一得到的最小生产规模在无资源浪费、均衡生产中能否减少。请写出你得到的生产规模，相应的周期和生产过程调度方案。问题三：如果该企业的资源限制为：类工人120名，类工人80名，技术人员25名，甲种设备8台，乙种设备10台，及周期限制（一星期，共小时），请你作出生产过程的调度方案，使在均衡生产条件下资源的浪费最小。表1 生产单位产品所需资源和时间产品A0A1A2A3A4A5A6需要的资源类工人71273437183317类工人30181713122823技术人员79076511甲种设备(台)4304202乙种设备(台)1310256加工时间(小时)63652122.基本假设各类产品有充足的库存，保证生产过程的连续进行，即不会出现因为缺少某一作为原料的产品而导致后续产品无法生产的情况。在各类资源可以通用的情况下，忽略生产调度所需要的时间，同时，理想化的假设各类产品在生产设备之间转移也不浪费时间。整个生产过程不出现意外情况导致生产停滞。3.符号定义M：均衡生产情况下各产品的产量比,记为一个7维行向量N：问题一中各产品生产需要的资源组数比，记为一个7维行向量b : 问题一中最小生产规模，记为一个5维行向量bi : 产品Ai所需的一组生产资源，记为一个5维行向量，i = 0,1,6p : 单位时间单位组生产的产品个数比，记录在一个7维行向量xi : 生产产品Ai所需要的资源组数, i = 0,1,6X : 由xi组成的7维行向量tj：一周期内第j种方案的生产时间Q：问题三中给定的生产规模4.建立模型解决问题4.1无资源浪费、连续均衡生产时的最小生产规模和最小生产周期由图1给出的生产结构示意图，我们可以看出，以A4和A6为原材料，最终生产所需要的A0产品。生产1个A0，需要1个A0，4个A1，5个A2，1个A5，而一个生产一个A1需要3个A5，生产一个A5需要一个A4，所以总共需要个A4，个A5。另外生产一个A2需要一个A3，生产一个A3需要2个A6，所以总共需要个A3，个A6。由此可以得到生产1个A0对应的各产品A0，A6的产量M=(1,4,5,6,15,12,12)。为了达到产品均衡生产，也就是一个周期（设为T，单位：小时）之后，各产品的生产量与消耗量相同，库存量不变，必须做到各产品的产量比和M中的各分量之比相同。由于资源不通用，将生产一个产品所需要的资源记为一组，以A0为例，其一组资源包括71名类工人，30名类工人，7名技术人员，4台甲种设备，1台乙种设备。记b0=71,30,7,4,1b1=(27,18,9,3,3)b2=(34,17,0,0,1)b3=(37,13,7,4,0) b4=(18,12,6,2,2)b5=(33,28,5,0,5) b6=(17,23,11,2,6)用5维行向量bi记录生产Ai所需的5种资源的数量。b表示最小生产规模。下面确定保证各产品产量比达到上面要求时的资源组数比（记录在一个7维行向量中记为N）。我们有下面的等量关系：一个周期内，生产时间全为T小时，由表1可以得到单位时间单位组生产的产品个数比，记录在一个7维行向量中即p=(16,13,16,15,12,1 ,12)。结合M和p及上面的等量关系即可得N=(1,2,5,5,5,2,4)。设xi表示生产Ai需要的资源组数（i=0,1,6），X=(x0,x1,x2,x3,x4,x5,x6),则有条件可以得出以下线性规划模型：s.t.X=cNcZ+xiZ+,i=0,1,6显然当x0=1时，z可能取最小值，此时，X=N，由于生产A0的组数为1，而A0至少要有一条流水线组装，加之题目所给的数据是基本的，不能通过延长时间而减少工人、设备，所以，安排各产品所需资源组数X=1,2,5,5,5,2,4，得到的产量比值为M=1,4,5,6,15,12,12，满足无资源浪费、均衡生产的要求，由此解得最小生产规模b=i=06xibi=704,424,144,48,56，即最小规模包含704名类工人，424名类工人，144名技术人员，48台甲种设备，56台乙种设备。由于生产每个产品需要的时间分别为6小时，3小时，6小时，5小时，2小时，1小时，2小时，最小公倍数是30，故30小时一定是一个周期。最小生产周期一定是30 的约数。1) 生产相同产品的生产线的进度是保持一致的情况下，即所有的设备在一周期初同时启动生产，对于任何T30，都会出现生产的产品不为整数的情况，因此，最小生产周期T=30。2) 30小时内，各产品的产量记录在向量中为5,20,25,30,75,60,60。除去A3，其他产品单位设备组生产单位各产品的最小公倍数为6，同时6也是30的约数，则可以考虑最小生产周期是否为6小时。对A3产品而言，给定5组资源，5个小时能够生产5个产品，需要在剩下一小时内生产1个产品，才能说明T=6是可能的，这在5条生产线同等进度的情况下是不可能做到的。尝试换一种角度，让5条生产线的生产进度不相同。如下图所示，在某一个周期开始时，第一组设备已经工作了1小时，此时这组设备在这个周期内只需再工作4小时便可得到一个A3，第二组设备从周期开始时投入生产，即比第一组设备迟一个小时，工作5小时得到一个A3，第三组设备在本周期中比第二组设备迟开一个小时，但实际已工作了四个小时，恰好再生产一个小时可得到一个A3，在剩余的5个小时内再生产一个A3，第四组设备再生产2小时可得到一个A3，第五组生产线再生产3小时可得到一个A3。这样在6个小时内，共生产出1+1+2+1+1=6个A3。从图中可见生产过程具有连续性。按照这样的生产模式，我们可以将最小周期定为6小时。4.2资源通用情况下的最优调度方案相对于第一个问题而言，没有“连续”生产的限制，即在资源可通用的情况下，相同的资源，比如说甲种设备，既可以用来生产A0产品，也可以用来生产A1等其他产品，某种产品的生产可以停顿。但是仍然要求保持资源不浪费和均衡生产。由于无论是否“连续”生产，要保证“均衡”，实质是指在一个周期结束后，各个产品的产量比值仍为第一个问题已解决的产量比M=1,4,5,6,15,12,12。一个周期中，某产品的产量=单位时间内一组设备生产的此产品的数量X生产此产品的设备组数X一个周期中这一产品的生产时间，同时我们先定义组时数的概念：生产某一产品的设备组数与一个周期中这一产品的生产时间的乘积。“单位时间内一组设备生产的此产品的数量”是表格给出的基本条件，在第一个和第二个问题中都是相同的，所以保证产量比不变，其实可以转化为保持各产品的组时数的比不变，在第一个问题中，由于一个周期中每种产品的生产时间都是T，则组时数比即为已经求出的组数之比N=(1,2,5,5,5,2,4)，又由于是否“连续”生产影响的是产量比的计算式中的“一个周期中这一产品的生产时间”， 从而需要计算出新的“每个产品的设备组数”来确定最优调度方案，通过上述分析，可知，要保证“均衡”条件，也就转化为在第二个问题中求出满足各个产品的组时数之比为第一个问题中的各产品组时数之比N=(1,2,5,5,5,2,4)的调度方案。现在讨论“无资源浪费”条件。考虑相同的资源可以通用后，需要的资源可能减少，第一个问题中求出的最小生产规模为b=704,424,144,48,56，则在此问题中生产规模应该按比例缩小，这是因为若不按比例调度的话，有可能造成资源的浪费和闲置。又b的各分量的公约数有8,4,2,1，则最小生产规模只能为18b、14b、12b、b，我们先检验最小生产规模是否为18b。假设一个周期的生产有多种生产方案，在每个生产方案中，都须考虑“无资源浪费”条件，因为只有这样，这些方案的任意组合使用才能保证一个周期中的“无资源浪费”。记向量bi的各个分量为Ai需要的资源（i=0,1,2,3,4,5,6），如b0=(71,30,7,4,1,6)，记矩阵B=b0T，b1T，b2T，b3T，b4T，b5T，b6T，记向量X的第i分量表示投入生产的Ai的设备组数。用C语言求解方程组BX=b/8，得到五组解（C语言程序见附录一）：x1=(0,0,0,1,1,1,0)x2=(0,0,1,0,3,0,0)x3=(0,0,1,1,0,0,1)x4=(0,2,1,0,0,0,0)x5=(1,0,0,0,0,0,1)五组解代表了五种生产方案，现在要解决的问题是，这五种方案如何组合，在满足“均衡”条件下使得生产周期最小。记tj为第j种方案的生产时间，由本节第一段的分析论证可知此时问题即要求下面的规划（MATLAB程序仍见附录一）：限制条件：j=15tjxjT=kN,kZ+tjR+目标函数：minT=j=15tj由于至少生产一个A0的组时数为6，而N的第一个分量为1，所以k应该为6的倍数，而至少生产一个A3的组时数为5，但N的第四个分量为5，其余产品至少生产一个时组时数均为6的因子，故k取6的倍数即可。解得k=6，t1=12，t2=6，t3=18，t4=6，t5=6时可得minT=48 。按照以上的五个生产方案及其时间安排使用，便实现了无资源浪费、均衡生产。既然最小规模中的4个可能值的最小数b/8，不用再验证其他三种可能。是资源通用情况下的最小生产规模；相应的最小生产周期为48小时，生产过程调度方案如上解决。4.3给定生产规模下的最优调度方案问题3去掉了“连续生产”和“无资源浪费”两个条件，仅保留“均衡生产”一个条件，即一个周期的始末各中间产品库存不变，供需平衡。由给定的条件，该企业的资源限制为：Q=(120,80,25,8,10)，周期限制为一星期（132小时）。由第二题结论，在“无资源浪费”及“均衡生产”且生产规模为 18 b=（88,53,18,6,7） 的情况下，生产周期为48小时，产品A0的产量为1台。由各产品单位周期产量=各产品单位周期资源组数单位周期生产单位该产品所需时间且有各产品单位周期的资源组数=各产品单位周期每一分量生产规模生产单位该产品所需该分量个数而 生产单位该产品所需时间 和 生产单位该产品所需该分量个数 是定量的，故 各产品单位周期的产量 仅与 各产品单位周期每一分量生产规模 和 各产品单位周期产量 有关.下面在第2问的基础上衡量现有限制条件下A0的单位周期产量。取A0资源组的各个分量和周期作为指标：I类工人：12088132483.75 II类工人：8053132484.15技术工人：2518132483.82甲类设备：86132483.67乙类设备：107132483.92以上五个分量的最小值3.67120（Q的第一个分量）故x03，以此类推可得 xi3，i=0，6 ,且xi不全为0.用DEV-C+编程求得 X 的79个解（代码及结果见附录2）：3. 继续转换为7组79维向量（代码及结果见附录3）：4.minj=1mtjs.t.j=1mtjxj=18Nxj=(x0j,x6j)m Ntj0,tj Z , j=1,2,m用Matlab进行线性规划求解得79维向量（代码及结果见附录4），其中将非零项列出：x15=0,0,0,1,0,2,0 t15=7.5 x20=0,0,0,1,2,1,0 t20=2.9711x22=0,0,0,2,0,1,0 t22=16.5 x37=0,0,1,1,1,0,1 t37=46.5289x45=0,0,2,0,1,1,0 t45=1.5289 x49=0,0,3,0,0,0,1 t49=7.4711x70=0,2,1,