生产作业排序管理

zmay10年前 (2015-05-10)生产管理295
生产作业排序管理问题一般可作如下描述:n种零件在m台设备上进行加工,每种零件加工所需要的设备数可以不同,加工的顺序也可以不同,但要求排出生产时间最短的工件加工次序。

解决作业排序问题最原始的方法是Johnson(约翰逊)算法,用Pij表示第j件产品在第i台机器上的加工时间,Johson算法的实施步骤如下:
(1)将工件分为两类,第一类包含满足条件P1j<P2j的工件,第二类包含满足条件P1j>P2j的工件,如果P1j=P2j,就可以分到任何一类中。
(2)先按照P1j的升序加工第一类中的工件,然后按P2j的降序加工第二类中的工件。
(3)将加工顺序组合在一起,这样生成的调度方案便是一个最优方案。
该算法的最大局限性在于只适用于两台机器的作业排序问题。但它的提出为后续复杂排序问题解决办法的提出奠定了基础。

六项任务在两台机器M1、M2上的加工时间如下表所示。
 六项任务在两台机器M1、M2上的加工时间
按照分组规则,将工件分为两类,P组为第一类,A组为第二类。
P组:工件2、4、5、6
Q组:工件1、3
按照P1j的升序加工第一类中的工件,排列的加工顺序为:4→2→5→6
按P2j的降序加工第二类中的工件,排列的加工顺序为:3→1
组合起来的加工顺序为:4→2→5→6→3→1,加工总工时为56。
由此,可以绘制作业排序的甘特图,如图5-6所示。
 作业排序的甘特图
Palmer(帕尔默)在1965年提出了Palmer算法;该算法可以解决多机器多零部件的排序问题。该算法的基本操作步骤如下:
(1)将m台机器分组,产生m-1个两台机器问题的集合。
(2)然后利用Johnson算法获得m-1个加工顺序(每个“两台机器”问题获得一个加工顺序)。
(3)作业i的斜度指标si定义为:
s(i)=Σ[j=1:m](2j-m-1)t(i,j)i=1,2,…,N
其中:m表示机器数目;
t(i,j)为第i个作业在第j台机器上的加工时间。
(4)按s(i)非增的顺序排列作业,可以构造作业的加工序列:
s[i(i)]>=s[i(2)]>=...>=s[i(n)]
如果5项作业在8台机器上进行,那么可得出下列加工时间如下表所示。
5项作业在8台机器上的加工时间
由于该算法过程比较复杂,人们一般直接将算法编写程序,以快速解决排序问题。Palmer求解结果为:
加工顺序为5→2→4→1→3,总工时为148分钟。

如运用APS技术等,也可以对作业过程进行排序。总体而言,作业排序会运用到较多的算法,并需要借助各种语言技术进行解决,如C++,JAVA,MATLAB等。如能熟练操作,可以使排序管理事半功倍。

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。