资源描述：
《线性规划理论与模型应用05》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、主要内容5.1排队模型5.2选址问题5.3对策论5.4统筹方法5.1排队模型排队问题和线性规划问题同属于运筹模型，排队模型是一个等待服务或等待处理的对象序列，如病人到医院门诊部看病、客户到银行储蓄所办理存取等业务、在一个机床上加工几个不同的部件等均是排队模型。一.在一台机器上加工n种零件在工厂生产中，往往要求零件在各道工序的滞留时间或平均滞留时间达到最小。各零件以不同的次序进行加工，其滞留时间将相差很远，因此在生产之前应考虑加工次序。零件的滞留时间=等待加工时间+加工时间；平均滞留时间(Mt)=各零件的滞留时间的总和/零件个数；排
2、队模型例5.1车间有一台机床，计划加工6个零件，每个零件加工完毕后立刻送到下一道工序加工，但尚未加工的零件必须等待正在加工的零件，待其加工完毕后才可以加工，各零件有关数据如下：解：首先按自然顺序加工滞留时间和加工时间如下表所示排队模型总滞留时间=60+100+120+230+285+315=1110(分)平均滞留时间Mt=1110/6=185(分)对于一般情况，若有n个零件，各个零件加工时间分别为J1,J2,…,Jn，则Mt=[J1+(J1+J2)+…+(J1+J2+…+Jn)]/n=[nJ1+(n-1)J2+…+2Jn-1+Jn
3、]/n显然可以证明，当J1≤J2≤…≤Jn时Mt将达到最小，从而对于此类问题的求解方法是首先对加工时间J1,J2,…,Jn进行排序，使其满足J1≤J2≤…≤Jn，然后进行加工，即依次加工所需时间少的零件。例5.1的正确加工次序为：3、6、2、5、1、4，所需时间Mt=[6*20+5*30+4*40+3*55+2*60+110]/6=825/6=137.5相对于自然次序，平均滞留时间(185)少47.5分。排队模型例5.2设某机床必须完成5种零件的加工，有关数据如下表，问应如何安排加工次序，使平均平均滞留时间最少。解：首先注意到各种
4、零件加工前要有准备时间，因此同一种零件要有准备时间，应放在一起加工，因此某个零件实际的总耗工时为零件i总耗工时=零件i件数*每件加工时间+准备时间各零件总耗时为195，26，132，215，65；工序应为2，5，3，1，4，平均耗时为Mt=[5*26+4*65+3*132+2*195+215]/5=278.2分。排队模型二.在二台机器上加工n种零件有时要求一批零件必须依次在两台机器上加工，而且在两台机器上的加工次序必须相同，即每个零件必须先在第1台机器上加工然后再在第2台机器上加工。例5.3设有5个零件，按工艺要求每个零件必须先在
5、车床上切割然后再在钻床上打孔，其加工耗时如下表，应如何安排工序，效率最高。排队模型先看按A、B、C、D、E顺序加工，用条形图表示如下显然如此顺序加工总耗时9小时。从图中可看出M1的结余时间一定大于E在M2的时间，当然希望在M2上耗时最短的零件放在最后；另一方面要使M2尽快进行工作状态，在M1上耗时最短的零件应尽可能放在前边。排序原则：求M1和M2上耗时最小者：在M1上，尽可能放在前边；在M2上，尽可能放在后边。排队模型解：1)寻找加工顺序首先画如下加工顺序表在加工时间表中找耗时最小者，零件B是0.25，属于M2，因此零件B放在最后
6、加工；在余下的零件中找耗时最小者，零件D是0.5，属于M1，零件D放在前边加工；再找到的是零件A是0.5，属于M2，放在后边加工；再找到的是零件C是1.00，属于M2，零件C放在后边加工；最后加入E，加工顺序表如下：总耗时为7.25+0.25=7.5，显然此值是最小值。排队模型2)加工起讫时间表通常需要建立如下加工起讫时间表全部零件的加工时间是7.5小时M1的等待时间=7.5-7.25=0.25小时M2的等待时间=2.5小时排队模型三.在m台机器上加工n种零件考虑一批零件必须依次在m台机器上加工时的情况，设tij为第i个零件在第j
7、台机器上加工的耗时，再设xij为第i个零件在第j台机器上加工开始时刻，则有(1)第i个零件必须在第j-1台机器上加工结束后才可在第j台机器上加工，即xi,j-1+ti,j-1≤xij(i=1,2,…,n,j=2,3,…,m)(2)任意两个不同的零件I、i在第j台机器上加工必须有一个先后，即xij+tij≤xIj(iI)(3)目标函数各零件必须尽早在所有机器上完成，也就是尽早在第m台机器上完成，即z=max{x1m+t1m，x2m+t2m，…，xnm+tnm}尽可能小，也就是minz。排队模型此时
8、的数学模型为minmax{x1m+t1m，x2m+t2m，…，xnm+tnm}s.t.xi,j-1+ti,j-1≤xij(i=1,2,…,n,j=2,3,…,m)xij+tij≤xIj(iI)(i,I=1,2,…
