Ϣ
INFORMATION AND CONTROL
1999 28 6 Vol.28 No.6 1999



³عеԴѡ
 ë  Ǯ
ժҪ챻Ϊ21͵ģʽʵ֯ʽҵAVEݲƷҪ̬ع̬عҵеԴѡǶʵսĸһԴѡ滮ģͣĿʹС֮Ⱥ˳ص㣬ǽ滮ģתΪͼģͣͼģͣǸһŽЧ㷨㸴Ƕʽнģ
ؼʣ죬ҵԴع
ͼţTP14ױʶ룺B
RESOURCE SELECTION FOR SHOP RECONFIGURATION
IN AGILE MANUFACTURING
WU Nai-qi MAO Ning QIAN Yan-ming
(Department of Mechatronics Engineering Guangdong University of Technology, Guangzhou 510090)
AbstractIt is believed that agile manufacturing is the 21st century manufacturing enterprise strategy and it should be realized by agile virtual enterprise (AVE) which is dynamically reconfigured for the manufacturing of one or more products. It creates a significant challenge for the resource selection in reconfiguring an AVE. In this paper, an integer programming (IP) formulation is presented for the resource selection problems to minimize the cost. The IP formulation is then transformed into a graph-theoretical formulation by taking the advantage of the precedence relationship between the tasks. Based on the graph-theoretical formulation, an efficient algorithm is proposed to seed for the optimal solutions of the problems. It is shown that the algorithm is polynomial bounded.
Key wordsagile manufacturing, agile virtual enterprise, resource reconfiguration
1ǰ
Ϊг̱ԽԽ̵ĴӲƷĳ뵽Ͷгʱڿµġ۸͵ġõ²ƷΪӦгµսһµҵģʽ죨Agile ManufacturingAM[12]. һܵ˵ձעΪܳȫԴ[7,8]21ҵķչսԣ
ĹؼԣЩоԱͼͨϵͳʵ[3,4]ϵͳӲеװãֽоȻձΪӦɶ·ﵽ[5,6]ν·ԾһƷơͿֲڵλòͬĵطͬʱУͨ෽ĺͬɣңÿһƺڲͬҵγһҵAgile Virtual EnterpriseAVE[7-10]һҵǸݿĳһ򼸸ƷҪ̬ɵģͨĳҵһ򼸸гг²ƷڱҵڲԴ㣬ҪʱԿɽܵĳɱɿ֯һҵʵֲƷĿǳƸҵĳΪ
ڲƷĿУҵڲĸƺͿصͬʱеؽйҪдϢƷϢƵϢΪʵѸٵϢһҵͨϢʩ磩[11-13]ͬʱҵǿعģǶ̬ģǸ²ƷɵģΪ˱֤ƷĿԣҵҲܿعˣعҪеϢҲͨϢʩʵ֣һҵĳߣҲֻͨѰҺ飮
ˣʵָϾսһоͽҵϢʩһζ̬عҵҵعеĳع⣮عҵعһ֣ԴعҲ˵ڸҵУ̬ѡĳһƷҪԴԿСΪĿ꣬ĸԴѡ滮ģͣòƷȺ˳ϵɽ滮ģתΪͼģͣЧ㷨öʽнĲŽ⣮
2
һҵΪһ򼸸ƷһҵʱҪԴ󼰱ҵеԴԱ豸ȣƷĿֽɸҪָǣͬʿܴͬЩĳƣһЩһƺ죻һ߽һļӹҪṩйصȫϢҲĳƷװ䣬ȵȣ
ΪͨعҵͨҵÿбꡢͶ̣ԻʵعϢ[14]Թ㲥ķʽÿһϷб飬˵ҵͶ꾺еһͼ1ʾбͶҪݣ


ͼ1 бͶĻ
յӹͶҪһγɸѡҪǸͶ˵ǷܴﵽָꡢʱܷܵȣɸѡĺѡŻѡ 
2.1 滮ģ
£ڼӹɣ˳˼ӹ⣬òɺԣģҪõзţ
T={t1, t2, , tn} Ϊе񼯺ϣ
Fi={fi1, fi2, , fim} tiĺѡߵļϣ
cikѡfiktiͶ۸
Wikjhѡfiktiмӹγɵ㲿˵fjhķãȻijҴfikfjhҪ㲿

fik=1 ʾѡfikѡУ
fik=0 ʾѡfikδѡУ
عԴѡǶÿһӹѡһֻѡһѡߣʹüӹúõĺСļӹþǸѡߵͶ۸ˣ滮
(1)
(2)
fik=0,1, i=1,2,,n(3)
2.2 ͼģ
ڼĸԣʵʵԴѡ滮⣬˱Ѱ;֮ĹϵܸΣ֮һȺ˳Լһ״Ĺϵͼ2(a)ʾһֹϵ


ͼ2 ״ϵ(a)Ӧͼģ(b) 
ֹ֮ϵǿɽ滮ģתΪͼģͣ·ķʽ⣮ȸҪķţ
I={1, 2, , n}Ϊڵ㼯, iIӦtiͼһԲʾ
Ai={ai1, ai2, , aim}Bi={bi1, bi2, , bim}ΪڵiеĺڵļϣaikbikһӦtiĺѡ֮һfik
N={(aik, bik)},i=1, 2, , n, k=1, 2, , m, Ϊỡļϣ(aik, bik)Ӧtiĺѡfik
CikΪ(aik, bik)ȨӦtiĺѡfikͶļӹã
F={(bik, ajh)}, i, j=1, 2, , n; k, h =1, 2, , m; ij(ti, tj)AAΪͼ2(a)лļϣ, ѡ֮Ļļϣ
WikjhΪ(bik, ajh)ȨӦڴӺѡfikfjhķã
SikSi={(ai1, bi1), (ai2, bi2), , (aim, bim)}Sik=(aik, bik) ǽڵiһڵԣӦtiһѡߣôعԴѡͼѡһS= {S1k, S2k, , Snk}ʹĿ꺯С
(4)
NsNFsFǶӦѡļSĻļϣ ͼ2(b)ǶӦ(a)һͼΪǳSikΪڵiеӽڵ㣮
3㷨
Ϊ˻Ч㷨ȷһڸͼģ͵ص㣮
ͼеһڵûνڵ㣬ǳƸýڵΪʼڵ㣻ͼеһڵûνڵ㣬ǳƸýڵΪսڵ㣮ע⣬ͼпжʼڵ㣬ͼ2(b)еĽڵ123ʼڵ㣬ֻһսڵ㣮ڵjǽڵiֱӺ̣ǳƽڵiǽڵjڵ㣮ͼеһڵжڵ㣬ǳƸýڵΪװڵ㣮ͼ2(b)еĽڵ45װڵ㣮
ͼ2(b)ǿ֪cikΪaikbikľ룬wikjhΪbikajhľ룬ôͼе·⣮
ڵiʼڵ㣬ڵjνڵ㣬ڽڵij֮ûװڵ㣮(Sik, Sjh)ΪӽڵSikSjh֮·(Si, Sjh)ΪڵiӽڵSjh·d((Sik, Sjh))d((Si, Sjh))ֱΪǵľ룮Ȼ
d((Si, Sjh)) =min(d((Si1, Sjh)), d((Si2, Sjh)), , d((Sim, Sjh)))(5)
϶壬Լڷѭͼ·ķص㣺
ص1 ڵiʼڵ㣬ڵjνڵ㣬ڽڵij֮ûװڵ㣬ڵgλڽڵij֮䣬SgeǦ(Sik, Sjh)ϵһӽڵ㣬ô 
d((Sik, Sjh))=min(d((Sik, Sge))+x)(6)
ص2 ڵiʼڵ㣬ڵjνڵ㣬ڽڵij֮ûװڵ㣬ڵgλڽڵij֮䣬SgeǦ(Si, Sjh)ϵһӽڵ㣬ô
d((Si, Sjh))=min(d((Si, Sge))+x)(7)
صζţһæ(Sik, Sge)ͦ(Si, Sge)ǿõĽ(Sik, Sjh)ͦ(Si, Sjh)Ϊʹǵ㷨õ򻯣
1 Ujǽڵjνڵ㼯ϣVjUjеʼڵ㼯ϣÿһvVjһ·ӽڵSjhͬʱκһڵuUjһֻһӽڵЩ·ϣǶЩ·Ϊ·ӽڵSjhɸ·ﵽ
Ϊӣͼ2(b)ڵ123ǽڵ5νڵ㼯еʼڵ㣮ӽڵS51ʼڽڵ123·(a11b11a51), (a22b22a41b41a51)(a31b31a41b41a51)ﵽҪעǣ·23뾭ڵ4ն壬ͨڵ4ʱǾͬһӽڵ㣮ӽڵS41(a41, b41)3·ϣ·(a11b11a51, a22b22a41b41a51, a31b31a41)
2 ·ֵľ֮Ϊ·ľ룮
磬·ӵľΪc11+w1151+c22+w2241+c41+w4151+c31+w3141һӽڵ·̵ľ룬ǳƸ·ΪSjh·æ(Sjh)ʾӦd((Sjh))ʾ룮
װڵĶ壬һװڵɸڵ㡰װ䡱ɣˣն1װڵjڵĸһӽڵSjh·Էֽɲ֣ڵiǽڵjڵ֮һ(Si, Sjh)ʾڵiSjh·ôеص㣺
ص3 ڵjһڵװڵ㣬ڵikڵ㣬ô
d((Sjh)) =d((Si, Sjh))+d((Sk, Sjh))(8)
֤ зֱ𾭹ڵikSjh·(Si, Sjh)ͦ(Sk, Sjh)ʹd((Sjh)) =d((Si, Sjh)) +d((Sk, Sjh))·(Si, Sjh)ͦ(Sk, Sjh)໥ģԦ(Si, Sjh)ĸı䲢Ӱ(Sk, Sjh)֮ȻҪʹd((Si, Sjh))+d((Sk, Sjh))Сd((Si, Sjh))d((Sk, Sjh))ֱСҲ˵(Si, Sjh)=(Si, Sjh)ͦ(Sk, Sjh) =(Sk, Sjh)һ
жڵװڵصȻƵķ֤ص3ص㣮
ص4 ڵjһڵװڵ㣬ڽڵjνڵ㼯ûװڵ㣬ڵikǽڵjνڵеʼڵ㣬ô
d((Sjh))=d((Si, Sjh))+d((Sk, Sjh))(9)
ص4ص3ص3ص4ǿֱͨ󾭹ڵjĸڵĦ(Si, Sjh)(Sjh)Ӷʹ㷨򻯣ص2ص㣮
ص5 ӽڵSge·(Sjh)ϣô
d((Sjh))=min(d((Sge)) +x)(10)
ص5ص2ƹ㣮һڵjͼеսڵ㣬(Sj)=(Sjh)(ajh, bjh)ǵڵjһ·ʹ
d((Sj)) =min(d((Sj1))+cj1, d((Sj2))+cj2, , d((Sjm))+cjm)(11)
(ajh, bjh)ʾĦ(Sj)ԴѡҪ·ڸ·ϵӽڵ㹹ѡĺѡ߼S
ķǿԸ㷨£
1: óʼA0ͼеʼڵɣB0=I-A0, k=1.
2: ӼBkѡһڵSjʹSjڵڼAkУ
3: Ӧ(5)-(10)h = 1, 2, , mֱ(Sjh)
4: Ak+1=Ak+{Sj}Bk+1=Bk-{Sj}
Bk+1=һk = k+12
5: Ӧ(11)(Sj)
6: (Sj)ϵӽڵγɽ⼯S={S1k, S2k, , Snk}ֹͣ
4㸴
ۿ֪عеԴѡʵһŻ⣮һͼģ͵ʣһŽ㷨㸴ԾҪ壮ǽ֤ǵ㷨ļ㸴Ƕʽнģ
|Sj|=miΪڵiеӽڵM=max(m1, m2, , mn)KjΪڵjڵK=max(K1, K2, , Kn)ôм㸴Զ
 һڸ⳵عеԴѡ㷨ļ㸴ΪO(M2n+KMn)
֤ ڵiǽڵjһڵ㣬ôڦ(Si1), (Si2), , (Sim)󾭹ڵiĦ(Sjh)ڽڵiеÿһӽڵҪμmi-1αȽ㣬ҪþڵiĦ(Sj1), (Sj2), , (Sjm)ҪΪ
(2 mi+mi-1)mj3mi*mj3M2(12)
װڵĦ(Sjh)ʱڽڵjеÿһӽڵ⻹ҪKjμ㣬Ҫ(Sj1), (Sj2), , (Sjm)ܹҪΪ 
Kj*mjKM(13)
(12)(13)ǵܹnڵ㣬ҪŽ⣬ܵ(3M2+KM)n Σ༴㸴ΪO(M2n+KMn)
ڻǵģ㷨ܹŽͬʱ㸴Ƕʽнģ˿ʵʵĴģ⣮
5
Ϊ˵ķӦãĳҵһʵΪչΪĵӦӣ
ĳģҵһ;עģĶҪ͵ϳĥӹģܼԴģмӹǻоļӹҪ߾ػػӹΣõ𻨼ӹȷΣ𻨼ӹʱҪΪ缫缫ҪػӹȷΣڱҵûҪĴϳĥеػʹʱܳѲҪѰҺ鹲ͬɸģߵ죮ԷֽΪеļӹ
1ģܼԴģеļӹҪϳĥ 
2ǻоĳӹγɴµΣҪػ񻹰NC̣
3缫ļӹҪӹȷΣҪػҲNC̣
4ǻоĵ𻨼ӹ
5ļӹԼģװ䣬Ҫģǯ
6ģдעܻ
7ģģ
ͼ3ʾͼ˸Ⱥ˳ϵЩͨͶ꾺ҵҲͶ꾺Լɵ1346ֱ3ѡߣ257ֱ2ѡߣSikʾiĵkѡߣ1г˸ԪƵͶ۸񣨰Ϸѣ25˸ѡ֮ãԪƣ
1 ѡߵͶ۸

Ͷ߼۸
1S1110.2
S128.5
S1312.7
2S219.3
S225.5
3S313.6
S325.3
S334.2
4S412.5
S425.1
S436.4
5S5118.5
S5219.6
6S610.8
S621.0
S630.6
7S713.1
S725.0

2 ɽڵ23ڵ4

S41S42S43
S210.20.40.3
S220.50.20.2
S310.90.50.3
S320.30.20.3
S330.20.50.4

3 ɽڵ14ڵ5

S51S52
S110.90.7
S121.31.0
S130.60.6
S410.20.4
S420.40.6
S430.70.5

4 ɽڵ5ڵ6

S61S62S63
S510.80.70.2
S520.60.60.6

5 ɽڵ6ڵ7

S71S72
S610.50.7
S620.80.6
S630.20.7


ͼ3 ӸȺ˳ϵ
ͼ3ݣǵõͼ4ʾͼģͣӦñĵ㷨еĦ(Sjh)6гǵľd((Sjh))ڱdjhʾd((Sjh))


ͼ4 ӵͼģ
6 d((Sjh))ֵ

d41d42d43d51d52d61d62d63d71d72
10.49.89.622.922.842.242.141.642.242.9

õĸ(Sjh)·(S7)ͼ4ʾ·ɴ˻Ľ⣬ֵΪ45.3Ԫ׿ñĵģͺ㷨׶Ը⣮
6
21͵ҵģʽѳΪҵĹʶҵʵ֯ʽҵǸݲƷҪ̬عģ˽ҵĸĻϢʩͳعʵҪ⣮
˳عԴѡ⣮Ϊ˱֤عԣԴѡϢͨебꡢͶ̻ãǽԴѡ滮ģͣΪ˻Ч㷨֮Ⱥ˳ص㣬ǽ滮ģתΪͼģͣڸͼģͣǸܻŽĶʽн㷨
µƻ͵ȣʵһսΪͬʱУ㲿ڸؼʱ䲻ٿԺԣɲͬʵɣʹƻ͵ȴӻ⽫ǽһоҪ⣮
Ŀ863ƻCIMS
߼
룬УڣʿоΪԪϵͳƻ͵ȣpetriۺӦãɢϵͳ
ëڣ˶ʿоΪCIMSԶϵͳ˶Żݿ⼰Ӧã
ǮʦȤΪݼ͹Ϣϵͳ
ߵλ㶫ҵѧϵ  510090
ο
1, . ݾս˼ϵͳ1996(1)
2 Nagal R, Dove R. 21st Century Manufacturing Enterprise Strategy: An Industry-led View, Iacocca Institute, Lehigh University, 1991
3 Quinn R D et al. Design of an Agile Manufacturing Workcell for Light Mechanical Application, Proceedings of the 1996 IEEE International Conference on Robotics and Automation, 1996: 858863
4 Merat F L, Barendt N A, Quinn R D et al. Advances in Agile ManufacTuring, Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 1997:12161222
5A C Sanderson, R J Graves, D L Millard. Multipath Agility in Electronics Manufacturing. IEEE International Conference on Systems, Man, and Cybernetics, 1994
6 R J Graves, A Agrawal, K Haberle. Estimating Tools to Support Multi-Path Agility in Electronics Manufacturing. IEEE Transactions on Components, Packaging, and Manufacturing Technology, 1996, 19(1):4856
7 R Dove. Agile Denefits: Viability and Leadership. Production, 8, 1995,(8)
8 P M Noaker et al. The Research for Agile Manufacturing, Manufacturing Engineering, 1994,(11)
9 G G Dess, A M A Rasheed, K J McLaughlin, R L Priem. The new Corporate Architecture, IEEE Engineering Management Review, 1996, 24(2):2028
10J Browne, P J Sackett, J C Wortmann. Future Manufacturing Systems-Towards the Extended Enterprise, Computers in Industry, 1995,25(3):235254
11 A Bartmess, K Cerny. Building Competitive Advantage Through a Global Network of Capabilities, IEEE Engineering Management Review, 1996, 24(2):2942
12 P Horstmann et al. Manufacturing Virtual Enterprise Through the use of the National Industrial Infrastructure Protocols (NIIIP), Proceedings of the SPIE-The International Society for Optical Engineering, 1997, 29(13):2047
13 P Herman et al. Creating the Virtual Enterprise with VE Gateway, Proceedings of the SPIE-The International Society for Optical Engineering, 1997, 29(13):174199
14 ë , Ǯ, . Դع⽨ģϵͳ
ո:1998-04-24
