共享制造环境下的同类机排序问题.pdf

资源描述

1、D O I:1 0.3 9 6 9/j.i s s n.1 0 0 1-5 3 3 7.2 0 2 3.4.0 1 5*收稿日期:2 0 2 2-0 7-2 1基金项目:国家自然科学基金(1 2 2 7 1 2 9 5,1 2 0 0 1 3 1 3);山东省自然科学基金(Z R 2 0 2 2 MA 0 1 9);山东省大学生创新创业训练计划项目(S 2 0 2 2 1 0 4 4 6 0 1 8).第一作者:宋嘉欣,女,1 9 9 8-,硕士研究生;研究方向:组合最优化;E-m a i l:1 5 0 0 0 2 5 5 8 9q q.c o m.通信作者:苗翠霞,女,1 9 7 6-,博

2、士,教授,硕士生导师;研究方向:组合最优化、近似算法及次模优化;E-m a i l:m i a o c u i x i a 1 2 6.c o m.共享制造环境下的同类机排序问题*宋嘉欣,孔凡雨,霍雨佳,苗翠霞,赵韵杰(曲阜师范大学数学科学学院,2 7 3 1 6 5,山东省曲阜市)摘要:考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本.对于机器台数是固定常数情况,该文对经典加工模型和简单退化加工模型分别提出了基于

3、程序划分的全多项式时间近似方案.对总服务成本不超过给定上界的限制下最小化最大完工时间问题,给出了其整数规划模型.关键词:排序;共享制造;同类机;全多项式时间近似方案中图分类号:O 2 2 4 文献标识码:A 文章编号:1 0 0 1-5 3 3 7(2 0 2 3)0 4-0 0 1 5-0 90 引言排序论是组合优化的一个重要分支,其中的平行机排序是常见的排序问题之一.一般情况下,每个工件可以被安排在任何一台机器上进行加工,而在食品加工等环境G l a s s和M i l l s1,每个工件可能只允许在某些规定机器上加工,这类平行机排序问题被称之为处理集限制排序问题.处理集限制排序类型可分

4、为嵌套处理集、包含处理集、区间处理集和树状分层处理集以及与之相关的模型有批处理模型、资源约束模型和具有协调机制的模型等.G l a s s和K e l l e r e r2考虑了工件具有分配限制的平行机排序问题.关于处理集为包含处理集的平行机排序问题,O u等3首次给出了该问题的多项式时间近似方案,L i和W a n g4将其拓展到工件具有到达时间的情况,并且给出了相应的多项式时间近似方案.E p s t e i n和L e v i n5考虑了处理集为包含处理集的同类机排序问题,并给出了多项式时间近似方案.L e u n g和N g6考虑了两种处理集下同类机排序问题的快速近似算法.M u r

5、a t o r e等7以及E p s t e i n和L e v i n8给出了处理集为嵌套处理集的平行机排序问题的多项式时间近似方案.L e u n g和L i9,1 0在2 0 0 8年对于不同类型处理集限制的在线和离线排序问题,给出了详细的综述,并在2 0 1 6年对此文献进了更新和补充.在经典排序问题中通常假设工件的加工时间是固定的,但在实际生产生活中,工件可能会因为加工过程的中断和耽搁而导致加工时间发生变化,因而产生了工件具有退化效应的排序问题.G u p t a等1 1首次考虑了工件具有退化效应的排序问题.简单线性退化的排序模型中工件的加工时间为pj=bjt,其中bj和t分别表示工

6、件的退化率和开始加工时间.M o s h e i o v1 2首先研究了简单退化模型.为建立健全资源节约型社会,现代排序又拓展到了共享制造领域.B r a n d t1 3首次提出了共享制造的概念,T a o和Z h a n g等1 4结合新兴的先进技术和制造模式,提出了新的制造模型.J i等1 5首次考虑了共享制造环境下处理集受限制的平行机排序问题,给出了解决该问题的全多项式时间近似方案.本文考虑了共享制造环境下处理集受限制的同类机排序问题,工件加工模型同时考虑了经典加工模型和简单退化加工模型.第4 9卷第4期2 0 2 3年1 0月曲阜师范大学学报J o u r n a l o f Q

7、 u f u N o r m a l U n i v e r s i t y V o l.4 9 N o.4O c t.2 0 2 3 文章的结构安排如下:第1部分对文章所研究的主要问题进行了描述,第2和第3部分主要对经典加工模型提出的模型给出了一个全多项式时间近似方案,同时给出了了总服务成本不超过给定上界的限制下最小化最大完工时间的整数规划模型,第4部分考虑了简单线性退化问题的一个全多项式时间近似方案,第5部分对文章进行了总结并提出有待解决的问题.1 问题描述和预备知识n个工件J=J1,J2,Jn 在m台同类机M=M1,M2,Mm 上加工,机器Mi(i=1,m)一次最多只能加工一个工件且加工

8、速度为si.假设经典加工模型所有工件在0时刻就绪而简单退化模型所有工件在1时刻就绪,且加工过程中工件不允许中断.每个工件Jj都有一个处理机器集MjM,如果它被分配到Mj中的任何一台机器上加工,除时间成本之外不产生任何费用,工件的加工时间为pj(pj=bjt),如果被分配到机器MiM Mj上,则加工时间为pi j(pi j=bi jt),并且产生额外的服务成本wi j,其中pj、pi j、bj、bi j和wi j均为正整数.本文的目标是找到一个最优排序,使得工件的最大完工时间和总服务成本之和最小,或者是在总服务成本不超过给定上界Q的限制下使得最大完工时间达到最小.该问题用G r a h a m等

9、1 6提出的三参数表示法可记为(Q m|Mj,SM|Cm a x+S)、(Q m|Mj,SM,SQ|Cm a x)及(Q m|Mj,SM,pj=bjt|Cm a x+S),其中SM表示共享制造环境,S为总服务成本.令ni为机器Mi上加工工件的个数,Ji,j为机器Mi上第j个位置的工件,显然对于i1,2,m,ni1,2,n,有mi=1ni=n成立.给出m台同类机的一个排序,令Ci,j为工件Ji,j的完工时间,令pi,j为工件Ji,j的加工时间.机器Mi上被安排工件的完工时间如下:Ci,1=pi,1si,Ci,2=pi,1+pi,2si,Ci,j=pi,1si+pi,2si+pi,jsi=ju=1

10、pi,usi.全多项式时间近似方案设最小化问题有一族算法A.若对于任意0,问题的每一个实例I都存在FA(I)F*(I)1+,并且算法A 的运行时间是关于给定实例I的输入大小I和-1的多项式.不失一般性,假设01.文章设计的全多项式时间近似方案是基于K o v a l y o v和K u b i a k1 7,1 8提出的程序划分,其中涉及的函数要求为非负整数函数.对于本文研究的同类机排序问题,在不影响排序的前提下,必须修改原始目标函数来满足这个约束,参考L i u等1 9运用的方法,原始目标函数的修改过程如下:对于i1,2,m,j1,2,n,定义=m i npjsi,pi jsi.假设为有限

11、小数,对于任意正整数k,都有1 0k为正整数.因为Ci,j=ju=1pi,usi,故1 0kCi,j为正整数.在共享制造环境中数据总存在一定的误差,如果误差足够小则越接近于实际值,故可以将目标函数转换为K Cm a x+S,其中K=1 0k.转换后的目标K Cm a x+S为非负整数.2 问题(Qm|Mj,SM|Cm a x+S)的全多项式时间近似方案由J i等1 5讨论的N P-难(P m|Mj,SM|Cm a x+S)可知问题(Q m|Mj,SM|Cm a x+S)也是N P-难的,并且受他们的启发,下面提出对应的同类机问题的全多项式时间近似方案.首先,引入变量xj,j=1,2,n.如果工

12、件Jj被分配到机器Mi(i1,2,m)上加工,则xj=i.令61 曲阜师范大学学报(自然科学版)2 0 2 3年X=x:x=(x1,x2,xn).对J1,J2,Jn 以及xX,假设fij(x)为工件Jj被安排在机器Mi上时机器的最大载重,gj(x)为服务成本函数.边界条件为fi0(x)=0(i=1,2,m)和g0(x)=0.下面不妨假设工件Jj被安排在机器Mi上.若MiMj,则fij(x)=fij-1(x)+Kpjsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x);若MiM Mj,则fij(x)=fij-1(x)+Kpi jsi,i=xj,fij(x)=fij-

13、1(x),ixj,gj(x)=gj-1(x)+wi j.令F(x)=m a xi=1,2,mfin(x)+gn(x).求解问题(Q m|Mj,SM|K Cm a x+S)就等价于m i nF(x).为解决上述问题,引入了K o v a l y o v和K u b i a k1 7,1 8提出的程序划分(A,e,),其中AX,e为X上的非负整数函数,并且0(1+)e(x(1).如果i1不存在,那么令Aeke=Ae1=A,并且停止.将向量x(i1+1),x(i1+2),x(i2)分配给集合ae2,其中i2满足e(x(i2)(1+)e(x(i1+1)以及e(x(i2+1)(1+)e(x(i1

15、i,进行如下计算.若MiMj,则fij(x)=fij-1(x)+Kpjsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x);若MiM Mj,则fij(x)=fij-1(x)+Kpi jsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x)+wi j.若j=n,则令yn=Y n,并且执行步骤3.若jn,则令=2(n+1),进行如下计算.调用程序划分(Y j,fij,)(i=1,2,m),将Y j划分为不相交的子集Yfij1,Yfij2,Yfijkfij.71第4期宋嘉欣,等:共享制造环境下的同类机排序问题调用程序划分(Y j,gj,)

16、,将Y j划分为不相交的子集Ygj1,Ygj2,Ygjkgj.将集合Y j分成如下子集Ya1a2amb=Yf1ja1Yfmjamygjb,a1=1,2,kf1j;a2=1,2,kf2j;am=1,2,kfmj;b=1,2,kgj.对每个非空子集ya1a2amb,选择向量x(a1a2amb),使得m i nxYa1a2ambm a xi=1,2,mfij(x)+gj(x).步骤3(生成解)选择向量x0Yn,使得F(x0)=m i nF(x)|xYn.令x*=(x*1,x*2,x*n)为最优解,并且设L=kl o g1 0+l o gn+l o g(pm a x)+l o g(wm a x),其中

18、1个工件,(x*1,x*2,x*j,x*j+1,0,0)和向量x(a1a2amb)=(x(a1a2amb)1,x(a1a2amb)2,x(a1a2amb)j,x*j+1,0,0).令1=,假设xj=i,则MiMj时,有|fij+1(x*)-fij+1(x(a1a2amb)|=fij(x*)+Kpj+1si-fij(x(a1a2amb)+Kpj+1si=|fij(x*)-fij(x(a1a2amb)|1fij(x*)1fij+1(x*).MiM Mj时,有|fij+1(x*)-fij+1(x(a1a2amb)|=fij(x*)+Kpi j+1si-fij(x(a1a2amb)+Kpi j

23、|gn(x*)-gn(x)|n-j+1gn(x*).(5)其中n-j+1由以下递归过程得到n-j+1=+n-j(1+)nj=0(1+)j()=(1+)n+1-1=(1+2(n+1)n+1-11+22-1.则(4)式可写为fin(x)(1+)fin(x*),i=1,2,m.同样的(5)式可写为gn(x)(1+)gn(x*).因而F(x)=m a xi=1,2,mfin(x)+gn(x)m a xi=1,2,m(1+)(fin(x*)+(1+)gn(x*)=(1+)m a xi=1,2,mfin(x*)+gn(x*)=(1+)F(x*).由算法A的步骤3知,对于选择的向量x0,下式成立F(x0)F

24、(x)(1+)F(x*).下面分析算法A的时间复杂性.在原始划分程序(A,e,)的第2步中,在O(|A|l o g|A|)时间内,按照e(x)非递减顺序排列A中的向量,并且在O(|A|)时间内提供一个划分.由此可知,在调用我们的划分程序(Y j,fij,)时,时间复杂性为O(|Y j|l o g|Y j|).由Y j+1的构造知,|Y j+1|m|Yj|mk(f1j)k(fMj)k(gj),且由性质2知k(fij)2(n+1)l o g(Kn(pm a x)+2On L,k(gj)2(n+1)l o g(n(wm a x)+2On L.因此,得到|Y j|=Onm+1Lm+1m+1以及O(|Y

26、 a x1imnj=1xi jpjsi+Yi jpi jsis.t.mi=1(xi j+Yi j)=1,j=1,2,n,mi=1nj=1wi jYi jQ,xi j,Yi j0,1,i=1,2,m,j=1,2,n,其中的等式约束表示每个工件被安排在某一台机器上加工.4 问题(Qm|Mj,SM,pj=bjt|Cm a x+S)的全多项式时间近似方案在这一部分考虑工件具有简单线性退化pj=bjt的情况.机器Mi上第j个位置的工件Jj的完工时间表达式为Ci,j=j=1bsi+1.在共享制造环境中,当MiMj时,工件Jj在机器Mi上的加工时间为bjtsi,否则工件的加工时间为bi jtsi且产生wi

27、j的成本.考虑到程序划分中函数的整数性,参考第2节中引用L i u1 9的方法,令=m i nbjsi+1,bi jsi+1,则1 0k为正整数(k+).修改目标函数为K Cm a x+S,其中K=1 0n k.与第2节中给出的全多项式时间近似方案相似,令X=x:x=(x1,x2,xn).在X上定义递归函数,边界条件为yi0(x)=1,i=1,2,m和l0(x)=0.不妨假设工件Jj被安排在机器Mi上.若MiMj,则yij(x)=yij-1(x)bjsi+11 0k,i=xj,yij(x)=yij-1(x),其它,lj(x)=lj-1(x);若MiM Mj,则yij(x)=yij-1(x)bi

28、 jsi+11 0k,i=xj,yij(x)=yij-1(x),其它,lj(x)=lj-1(x)+wi j.令R(x)=m a xi=1,2,myin(x)+ln(x).在全多项式时间近似方案A的基础上修改其步骤2和步骤3,具体描述如下:02 曲阜师范大学学报(自然科学版)2 0 2 3年算法b步骤1(初始化)令Y0=(0,0,0),并且j=1.步骤2(生成集合Y1,Y2,Yn)对于集合Yj-1,通过向其第j个位置添加i生成集合Y j,i=1,2,m.对任意xY j,假设xj=i,进行如下计算.若MiMj,则yij(x)=yij-1(x)bjsi+11 0ki=xj,yij(x)=yij-1

29、(x),其它,lj(x)=lj-1(x);若MiM Mj,则yij(x)=yij-1(x)bi jsi+11 0ki=xj,yij(x)=yij-1(x),其它,lj(x)=lj-1(x)+wi j.若j=n,则令Yn=Y n,并且执行步骤3.若jn,则令=2(n+1),进行如下计算.调用程序划分(Y j,yij,)(i=1,2,m),将Y j划分为不相交的子集Yyij1,Yyij2,Yyijkyij.调用程序划分(Y j,lj,),将Y j划分为不相交的子集Ylj1,Ylj2,Yljklj.将集合Y j分成如下子集Ya1a2amb=Yy1ja1YymjamYljb,对每个非空

30、子集Ya1a2amb,选择向量x(a1a2amb),使得m i nxYa1a2ambm a xi=1,2,myij(x)+lj(x).步骤3(生成解)选择向量x0Yn,使得R(x0)=m i nR(x)|xYn,其中R(x)=m a xi=1,2,myin(x)+ln(x).对于i=1,2,m和j=1,2,n,定义L=l o g(m a xn,(1/),1+Bm a x,wm a x,1 0k),其中Bm a x=m a xbi jsi,bjsi,wm a x=m a xj=1,2,nwi j|MiM Mj.定理2 对于问题(Q m|Mj,SM,pj=bjt|K Cm a x+S),算

31、法B在O(n2m+2(L)m+2m+1)内找到了一个解x0X满足R(x0)(1+)R(x*).证明与定理1的证明类似.算法B选择了向量x(a1a2amb)=(x(a1a2amb)1,x(a1a2amb)j,0,0).由性质1可得|yij(x*)-yij(x(a1a2amb)|yij(x*),i=1,2,m,|lj(x*)-lj(x(a1a2amb)|lj(x*).考虑第j+1个工件,(x*1,x*2,x*j,x*j+1,0,0)和向量x(a1a2amb)=(x(a1a2amb)1,x(a1a2amb)j,x*j+1,0,0).令1=,假设xj=i,则MiMj时,有|yij+1(x*)-yij

33、*).同样对于ixj时也成立,故有下式成立12第4期宋嘉欣,等:共享制造环境下的同类机排序问题 yij+1(x(a1a2amb)(1+1)yij+1(x*),i=1,2,m.(6)对于成本函数lj(x),与第2节中gj(x)的计算过程相同,因此可得lj+1(x(a1a2amb)(1+1)lj+1(x*).(7)假设x(a1a2amb)Yc1c2cmdY j+1,在第j+1步迭代中,算法B选择了向量x(c1c2cmd)Yc1c2cmd,同第2节的计算过程完全相同,可以证明总是存在x Yn,如下不等式成立.|yin(x*)-yin(x)|n-j+1yin(x*),i=1,2,m,(8)|ln(x

34、*)-ln(x)|n-j+1ln(x*).(9)同样由于n-j+1,(8)式和(9)式可转换为yin(x)(1+)yin(x*),i=1,2,m,ln(x)(1+)ln(x*).因此R(x)=m a xi=1,2,myin(x)+ln(x)m a xi=1,2,m(1+)(yin(x*)+(1+)ln(x*)=(1+)R(x*).由算法B的步骤3知,对于选择的向量x0,下式成立R(x0)R(x)(1+)R(x*).算法B的时间复杂性为O(|Y j|l o g|Y j|).由Y j+1的构造可知,|Y j+1|m|Yj|mk(y1j)k(ymj)k(lj).由性质2知k(yij)2(n+1)l

35、o g(1 0n k(bm a x)n)+2On2L,k(lj)2(n+1)l o g(n wm a x)+2On L.因此算法B的时间复杂性为On2m+2(L)m+2m+1.5 结论本文研究了共享制造环境中的同类机排序问题,其中工件的处理集受限制.考虑了(Q m|Mj,SM|Cm a x+S),(Q m|Mj,SM,pj=bjt|Cm a x+S)和(Q m|Mj,SM,SQ|Cm a x)这3个模型,对这3个模型依次给出了一个全多项式时间近似方案和一个整数规划模型.未来的研究中,可以考虑共享制造环境下其他类型处理集限制的排序问题.参考文献:1G L A S SCA,M I L L SHR

36、.S c h e d u l i n gu n i t l e n g t h j o b sw i t hp a r a l l e l n e s t e dm a c h i n ep r o c e s s i n gs e t r e s t r i c t i o n sJ.C o m p u ta n dO p e rR e s,2 0 0 6,3 3(3):6 2 0-6 3 8.2G L A S SCA,K E L L E R E RH.P a r a l l e lm a c h i n es c h e d u l i n gw i t h j o ba s s i g

37、n m e n t r e s t r i c t i o n sJ.N a vR e sL o g,2 0 0 7,5 4(3):2 5 0-2 5 7.3OUJW,L E UNGJYT,L ICL.S c h e d u l i n gp a r a l l e lm a c h i n ew i t hi n c l u s i v ep r o c e s s i n gs e t r e s t r i c t i o n sJ.N a vR e sL o g,2 0 0 8,5 5(4):3 2 8-3 3 8.4L ICL,WAN GX.S c h e d u l i n gp

38、a r a l l e lm a c h i n e sw i t hi n c l u s i v ep r o c e s s i n gs e t r e s t r i c t i o n sa n dj o br e l e a s et i m e sJ.E u rJO p e rR e s,2 0 1 0,2 0 0(3):7 0 2-7 1 0.5E P S T E I NL,L E V I NA.S c h e d u l i n gw i t hp r o c e s s i n gs e t r e s t r i c t i o n s:P TA Sr e s u l

39、t s f o r s e v e r a l v a r i a n t sJ.I n t JP r o dE c o n,2 0 1 1,1 3 3(2):5 8 6-5 9 5.6L E UN GJYT,N GCT.F a s ta p p r o x i m a t i o na l g o r i t h m sf o ru n i f o r m m a c h i n es c h e d u l i n gw i t hp r o c e s s i n gs e tr e s t r i c t i o n s22 曲阜师范大学学报(自然科学版)2 0 2 3年J.E u r

40、 JO p e rR e s,2 0 1 7,2 6 0(2):5 0 7-5 1 3.7MUR A TO R EG,S CHWA R ZU M,WO E G I N G E RGJ.P a r a l l e lm a c h i n es c h e d u l i n gw i t hn e s t e dj o ba s s i g n m e n tr e s t r i c-t i o n sJ.O p e rR e sL e t t,2 0 1 0,3 8(1):4 7-5 0.8E P S T E I NL,L E V I NA.S c h e d u l i n gw i t

41、 hp r o c e s s i n gs e t r e s t r i c t i o n s:P TA Sr e s u l t s f o r s e v e r a l v a r i a n t sJ.I n t JP r o dE c o n,2 0 1 1,1 3 3(2):5 8 6-5 9 5.9L E UN GJYT,L ICL.S c h e d u l i n gw i t hp r o c e s s i n gs e t r e s t r i c t i o n s:As u r v e yJ.I n t JP r o dE c o n,2 0 0 8,1 1

42、 6:2 5 1-2 6 2.1 0L E UN GJYT,L ICL.S c h e d u l i n gw i t hp r o c e s s i n gs e t r e s t r i c t i o n s:Al i t e r a t u r eu p d a t eJ.I n t JP r o dE c o n,2 0 1 6,1 7 5:1-1 1.1 1GU P T AJND,GU P TASK.S i n g l ef a c i l i t ys c h e d u l i n gw i t hn o n l i n e a rp r o c e s s i n gt

43、 i m e sJ.C o m p u t I n dE n g,1 9 8 8,1 4(4):3 8 7-3 9 3.1 2MO S HE I OVG.S c h e d u l i n g j o b su n d e r s i m p l e l i n e a rd e t e r i o r a t i o nJ.C o m p u tO p e rR e s,1 9 9 4,2 1(6):6 5 3-6 5 9.1 3B R AN D TE.Av i s i o nf o rs h a r e dm a n u f a c t u r i n gJ.M e c hE n g,1

44、9 9 0,1 1 2(1 2):5 2-5 5.1 4T AOF,Z HAN GL,V E NKA T E S H V C,e ta l.C l o u dm a n u f a c t u r i n g:Ac o m p u t i n ga n ds e r v i c e-o r i e n t e dm a n u f a c t u r i n gm o d e lJ.PIM e c hE n gB-JE n g,2 0 1 1,2 2 5(1 0):1 9 6 9-1 9 7 6.1 5J IM,Y EXN,Q I ANFY,e ta l.P a r a l l e l-m a

45、 c h i n es c h e d u l i n gi ns h a r e dm a n u f a c t u r i n gJ.JI n dM a n a gO p t i m,2 0 2 2,1 8(1):6 8 1-6 9 1.1 6G R AHAM RL,L AWL E REL,L E N S T R AJK,e ta l.O p t i m i z a t i o na n da p p r o x i m a t i o ni nd e t e r m i n i s t i cs e q u e n c i n ga n ds c h e d u l i n gJ.A

46、n nD i s c r e t eM a t h,1 9 7 9,5:2 8 7-3 2 6.1 7KOVA L YOV M Y,KU B I AK W.Af u l l yp o l y n o m i a la p p r o x i m a t i o ns c h e m ef o rm i n i m i z i n gm a k e s p a no fd e t e r i o r a t i n gj o b sJ.JH e u r i s t i c s,1 9 9 8,3:2 8 7-2 9 7.1 8KOVA L YOV M Y,KU B I AK W.Af u l l

47、 yp o l y n o m i a l a p p r o x i m a t i o ns c h e m e f o r t h ew e i g h t e de a r l i n e s s-t a r d i n e s sp r o b l e mJ.O p e rR e sL e t t,1 9 9 9,4 7:7 5 7-7 6 1.1 9L I U M,Z HE N GFF,CHUCB,e t a l.A nF P TA S f o r u n i f o r m m a c h i n e s c h e d u l i n g t om i n i m i z em

48、 a k e s p a nw i t h l i n e a r d e t e-r i o r a t i o nJ.JC o m bO p t i m,2 0 1 2,2 3(4):4 8 3-4 9 2.U n i f o r m-m a c h i n e s c h e d u l i n g i ns h a r e dm a n u f a c t u r i n gS ONGJ i a x i n,KONGF a n y u,HU OY u j i a,M I A OC u i x i a,ZHA OY u n j i e(S c h o o l o fM a t h e m

49、 a t i c a lS c i e n c e s,Q u f uN o r m a lU n i v e r s i t y,2 7 3 1 6 5,Q u f u,S h a n d o n g,P R C)A b s t r a c t:I nt h i sp a p e r,t h eu n i f o r m-m a c h i n es c h e d u l i n gw i t hs h a r e dm a n u f a c t u r i n gi sc o n s i d e r e d,i nw h i c he a c hj o bJjh a s a r e s

50、 t r i c t e ds e tMjo fm a c h i n e so nw h i c h i t c a nb ep r o c e s s e d,t h e j o bn o t o n l yc a nb ep r o c e s s e do no n em a c h i n eo fMj,b u t a l s oc a nb ep r o c e s s e do no n eo f t h e r e m a i n i n gm a c h i n e sw i t ha c e r t a i nc o s t.T h eo b j e c t i v e i

展开阅读全文